Wikinotes

Maintainer: admin

The midterm will take place on Tuesday, October 23, during class (in the regular room). Chapters covered: 1-4, 10, 11 (notably not chapter 5).

1 Chapter 1: Introduction
- 1.1 Sample questions
2 Chapter 2: Operating system structures
- 2.1 Sample questions
3 Chapter 3: Processes
- 3.1 Sample questions
4 Chapter 4: Threads
- 4.1 Sample questions
5 Chapter 10: Filesystem interface
- 5.1 Sample questions
6 Chapter 11: Filesystem implementation
- 6.1 Sample questions

OS: program, between user and hardware
- goals:
  - execute user programs, solve user problems
  - make computer convenient to use
  - use hardware efficiently
- allocates resources fairly and efficiently
- controls execution of programs to prevent errors, etc
4 components of a computer system
- hardware: computing resources
- OS: controls, coordinate hardware use
- application programs
- users
kernel: one program always running; everything else = system/application program
- monolithic: put as much as possible in the kernel; used by windows and GNU/linux
- microkernel: put as little as possible in the kernel, have everything else run in user space; used by Mac OS (Linus Torvalds thinks this is dumb)
bootstrap program: stored in ROM/EPROM, aka firmware (and not RAM, because RAM is volatile, lol)
- loads kernel, begins its execution; bootstraps everything else
computer system organisation
- CPUs and device controllers compete for access to shared memory, using a common bus
- I/O devices and CPUs can execute concurrently
- each device controller is responsible for a particular device (or multiple devices, e.g., disks), has a local buffer
- data is first stored in controller's local buffer
- CPU moves data between local buffers and main memory
- when device controller is done, it causes an interrupt to let the CPU know
  - CPU looks up memory address of the relevant interrupt handler (aka interrupt service routine) based on the type of interrupt, using the interrupt vector table
  - the address and PC of instruction that is currently being interrupted is saved (along with registers)
  - control is transferred to interrupt handler
  - incoming interrupts are ignored to prevent a lost interrupt
  - once the interrupt handler has completed, returns to previous instructions (return address, flags popped from stack - what flags?)
- trap: software-generated interrupt (caused by error or user request)
- interrupts form the basis of modern operating systems
- interrupt timeline diagram, explained in words:
  - at first, CPU is executing user process
  - then, I/O device receives data, takes some time to complete the transfer
  - once the transfer is complete, CPU processes the interrupt; I/O device is idle again
  - CPU returns to executing user process
  - I/O device remains idle until another I/O request occurs - repeat the process
- System call: request to OS, user waits for I/O completion
- Device status table: comtains type, address and state for each I/O device
  - When an interrupt occurs, OS updates the DST entry for the device to indicate interrupt
- direct memory access:
  - special controller (DMA controller) takes care of transmitting data to/from main memory, without involving the CPU
  - increased data throughput
  - CPU can do other work while data is being transferred
  - data can be transferred faster (useful for sound, network, graphics cards)
storage structures
- main memory: only large storage media that CPU can access directly; volatile, quick to access, limited in size
- secondary: disk storage i think? not sure, access managed via disk controller
- hierarchy:
  - registers
  - CPU cache
  - main memory
  - electronic disk
  - magnetic disk
  - optical disk
  - magnetic tapes lol
- caching
  - performed at many levels (hardware, OS, software)
  - copied from larger but slower storage to a smaller, faster one
  - I'm sure everyone knows how caching works by now
computer system architecture
- usually one general-purpose processor, and possibly special-purpose ones too (e.g., GPU)
- multiple cores = still one processor, just more than one core on a single chip (efficient for communication and power usage)
- multiprocessor systems:
  - asymmetric (master-slave) or symmetric (peers)
  - increased throughput, shared peripherals, graceful degradation
  - each CPU still has its own registers and cache
- clustered systems
  - multiple computers working in tandem
  - asymmetric or symmetric clustering
  - usually shared storage via a storage area network (SAN)
operating system structure
- multiprogramming: organises jobs so that CPU always has one to execute (fair scheduling)
- timesharing: always 1 process running in memory
  - other jobs kept in memory, OS switches between processes very quickly
  - if all the processes don't fit in memory, they're swapped to disk (virtual memory)
- dual-mode: user mode, kernel mode
  - some instructions are "privileged" - can only be executed in kernel mode
  - system calls are executed in kernel mode, returns to user mode after (if relevant)
  - mode bit: 1 for user mode, 0 for kernel mode
  - programs can leave user mode by triggering interrupt
  - there is a timer to prevent user programs from causing infinite loops and whatnot; when a counter reaches 0, OS generates interrupt
Processes
- process: program in execution
- needs resources: CPU, memory, I/O, files, initial data
- single-threaded process: has one PC, instructions executed sequentially
- multi-threaded: one PC per thread (more detail later)
- the OS must take care of:
  - creating, deleting user/system processes
  - suspending and resuming processes as necessary
  - providing mechanisms for process synchronisation
  - providing mechanisms for process communication
  - handling deadlock
memory management: keeps track of what is being used, deciding which to swap, allocating and deallocating shit etc
storage management
- OS provides an abstraction for physical storage devices; logical storage unit = file
- file system management: access control, creating/deleting, mapping files onto physical location, etc
I/O subsystems
- hide details of I/O devices
- take care of memory management, including buffering, caching, spooling (simultaneous peripheral operations on line), drivers, etc
computing environments
- client-server (fileserver, webserver, etc)
- peer-to-peer (distributed)

Name the four components of a computer system.

Hardware, operating system, application programs, users

What is a bootstrap program?

Program that loads the kernel and begins its execution, bootstrapping everything else

Difference between the two, name one OS that uses each method.

Monolithic: put as much as you can inside the kernel itself; used by GNU/Linux, Windows
Microkernel: put very little inside the kernel, and let most things be user programs; used by Mac OS

Draw a diagram showing how CPUs, devices, device controllers and main memory are connected in a standard computer system.

CPUs on same level as device controllers, devices connected to controllers, CPUs and controllers connected to main memory via a shared bus

Draw a diagram illustrating the interrupt model, and explain what happens.

i hope this isn't on the midterm

Draw the interrupt timeline.

lol

What is a trap, and how are they caused?

Software-generated interrupt, caused by errors or user requets

What information does a device status table contain?

Type, address, and state for each I/O device

How does direct memory access work, and what are its benefits?

A special controller, called a DMA controller, takes care of transmitting data to and from main memory so that the CPU doesn't have to. Benefits: increased data throughput, CPU can do other work when the data is being transferred, data can be transferred faster (useful for sound, network, graphics cards, etc).

What factors determine the storage structure hierarchy and what are its components?

Closer to CPU: faster, more volatile, more expensive, smaller. Hierarchy: registers, CPU cache, main memory, electronic disk, etc.

Types of multiprocessor systems, and benefits of multiprocessing in general

Asymmetric (master-slave), symmetric (peers). Benefits: increased throughput, shared peripherals, graceful degradation.

Benefits of placing multiple cores on a single chip?

More efficient for communication and power consumption

How does timesharing work? What happens if there are too many processes to fit in main memory?

one process running in memory, other jobs waiting to run, OS switches between jobs quickly (creating the illusion of interactive computing)

Swapped to disk

Difference between user and kernel mode, mode bits for each

Kernel: for privileged system programs, mode bit 0; user: for application programs, mode bit 1

Difference between a program and process

Process: program in execution

Operating system services, provided for users:
- user interface (GUI or CLI)
- program execution
- I/O operations
- file system manipulation
- inter-process communication
- error detection (could occur in hardware, I/O, or user programs)
services needed for efficient operation of system
- resource allocation
- accounting (keep track of resource usage)
- protection (resource usage is controlled properly)
- security (from outsiders)
system calls: programming interface to OS-provided services
- usually accessed via APIs (different one for each type of OS) - more portable, etc
- three methods for passing parameters to OS:
  - registers (limiting)
  - block, or table, in memory; address of block passed as parameter in a register
  - pushed onto stack by program, popped off by OS
system programs
- can be simply interfaces to system calls, or more complex
- file management: create, delete, copy, rename, etc
- status info: date, du, top, etc
- file modification: sed, vim, etc
- programming support: compilers, assemblers, interpreters
- program loading and execution: gdb, loaders
- communication: email, scp, ssh, IPC, etc
OS design
- user goals: convenient to use, easy to learn, reliable, safe, fast
- system goals: easy to design and implement, reliable, flexible, error-free, efficient
- policy: what will be done
- mechanism: how to do it
- the two should be separate. e.g., scheduling is controlled by loadable tables in solaris - can be time-shared, real-time, etc
- MS-DOS:
  - not modular, interfaces and levels of functionality not well separated
  - applications can access basic I/O routines, write directly to disk/display
- UNIX
  - system programs, then the kernel (everything below syscall interface)
  - kernel provides file system, CPU scheduling, memory management, etc
  - traditional structure: some layers, but a lot of functionality per level
- layered approach: N + 1 layers; 0 is hardware, N is user interface
  - each layer only uses functions defined in lower layers
- microkernel
  - easier to extend
  - easier to port to new architectures
  - more reliable (less code running in kernel mode)
  - more secure
  - performance overhead of user space to kernel space communication
- modular kernels (like with solaris)
  - each module talks to others over defined interfaces
  - similar to layers but more flexible, as any module can call any other module
virtual machine: provides interface identical to underlying hardware
- separate execution environment
- protected
- can communicate with each other
- can share some files, etc
- paravirtualisation: guest OS is provided with system similar to (but not identical to) hardware
  - guest OS must be modified to run on paravirtualised hardware
  - smaller virtualisation layer, more efficient use of resources
system boot
- bootstrap loader locates the kernel, loads it into memory, starst it
- can be a 2-step process: boot block loads bootstrap loader, etc
- execution then starts at a fixed memory location
- stored in firmware (ROM) not RAM because RAM is volatile and at an unknown state when the system starts up, and because ROM needs no initialisation and cannot be easily infected by a virus

What are the three methods for passing parameters in a system call?

Registers, memory block (or table) - address passed as parameter in register, stack

Benefits of microkernels? Disadvantages?

Benefits: easier to extend, more portable, more reliable, more secure

Disadvantage: performance overheard of user space to kernel space communication

What is a virtual machine etc

Application program that provides interface identical to underlying hardware so that it can run other operating systems, unmodified

What is paravirtualisation

When the interface is similar but not identical to the underlying hardware. Smaller virtualisation layer, more efficient use of resources. The guest OS must be modified, though.

Why in ROM and not RAM

Well, RAM is volatile, don't know what state it could be in when you start up a system. Also, ROM needs no initialisation and cannot easily be infected with a virus.

Process includes:
- program counter
- stack (for temporary data - function params, return addresses)
- data section (global variables)
in memory, we have:
- stack
- heap, which grows upwards as the stack grows downwards (towards each other), it doesn't seem to count though
- data section
- text (program code)
process states:
- new: being created
- ready: waiting to be assigned to a processor
- running: being executed
- waiting: waiting for something to occur (e.g., I/O completion, signal reception)
- terminated: done
only one process can be running on one processor at a time
process control block, data structure in OS kernel, for storing process info; includes:
- process state
- program counter (address of next instruction)
- CPU registers
- CPU scheduling info
- memory management info
- accounting info (CPU used, time used, process number, etc - stuff you see using top)
- I/O status info (list of devices allocated and open files)
- (the first three are saved when interrupt occurs)
switching between processes
- CPU executes process, then along comes an interrupt of some sort
- the process state is saved into PCB₀
- OS handles interrupt
- now it's time for another process, which uses PCB₁ to execute
- OS loads state from PCB₁, then the other process executes
- etc
process scheduling queues (implemented via linked lists)
- job queue: set of all processes in system
- ready queue: set of all processes residing in main memory that are ready to execute
- device queues: set of processes waiting for each I/O device
- processes migrate between queues (or rather, the PCBs do)
schedulers
- long-term scheduler: decides which processes should be loaded from disk and brought into the ready queue (in memory)
  - invoked very infrequently, can be slow
  - controls degree of multiprogramming
- short-term scheduler: decides which process should be executed next and allocates CPU for it
  - invoked frequently, must be fast
- medium-term scheduling: removes processes from memory to reduce degree of multiprogramming
I/O-bound: more time spent doing I/O (so many short CPU bursts); CPU-bound: more time doing computations (so long CPU bursts)
context switching
- info saved in PCB
- overhead, no useful wrk done
creating process babies
- parent processes create child processes, and so on (--> tree)
- processes identified by pid, integer
- different resource sharing schemes:
  - parent, child share all
  - child has access to some of parent's
  - parent, child share nothing
- different execution schemes:
  - concurrent execution
  - parent waits until children die
- child is first a duplicate of parent, with the same program and data, then has a new program loaded into it
- UNIX examples
  - fork: new process, identical to parent
  - exec: after fork, process' memory space replaced by new program
- solaris example
  - root of tree: scheduler, pid = 0; creates other processes, etc
termination
- after a process executes its last statement, it asks the OS to delete it (exit)
- return status is passed to the parent, if the parent used wait
- OS deallocates the process' resources
- parents can abort their children - reasons include
  - child is using too many resources
  - whatever the child is doing is no longer useful
- if parent exists, the children may all be terminated (depends on OS)
inter-process communication
- processes can be independent or cooperating
- cooperating processes can share data, etc - need communication
- shared memory, via some location in memory accessible by both processes
- message passing, via kernel
- producer-consumer problem: which paradigm to use?
  - unbounded buffer vs bounded buffer
  - if bounded (which is the only feasible one really), producer needs to wait if full; consumer, if empty (in all cases)
  - shared memory solution for a bounded (circular) buffer:
    - save a pointer to the first free position (in), and a pointer to the first full position (out)
    - producer: while there are no free buffers, wait; when there are, add an item, increase the pointer to the first free position
    - consumer: while there are no items, wait; when there are, remove an item, increase the pointer to the first full position
  - can only use BUFFER_SIZE - 1 elements
  - empty when in == out
  - full when (int + 1) % BUFFER_SIZE == out
- message passing:
  - IPC facility provides send, receive functions
  - if processes P and Q want to communicate, they first establish a link, then exchange messages
  - can be direct (must explicitly name the other process) or indirect (using mailboxes)
  - direct communication links:
    - send(P, message) and receive(Q, message)
    - each link associated with exactly 2 processes
    - between two processes there can be at most one link
    - can be unidirectional or bidirectional (more common)
    - disadvantages: hard-coded identity, hard to make changes later
  - indirect:
    - "mailboxes"; but really, just ports lol
    - each port has unique ID
    - processes can only communicate if they share a common port
    - link can be associated with many processes
    - each pair of processes can share several links
    - can be uni or bidirectional
    - operations: create mailbox, send/receive, destory
    - send(A, message) where A is the mailbox, etc
  - link: only two processes?
  - only one process can execute receive operation at a time?
  - round-robin scheme - sender throws it out randomly, some receiver gets it, sender gets notified as to who
- message passing: blocking or not, on part of sender or receiver
- queue of messages attached to link
  - zero capacity: sender waits for receiver (rendez-vous)
  - bounded (finite) capacity: sender waits if queue full
  - unbounded (infinite) capacity: sender never waits, is this even possible?
- Examples
  - POSIX shared memory
    - process creates shared memory segment, returns an ID
    - processes wanting access to that segment must attach to it by ID (call returns pointer)
    - can write to that memory segment (using the pointer)
    - can detach it from its address space when done
  - Mach:
    - message-based (everything! even system calls)
    - all tasks are created with 2 mailboxes (which are created with port_allocate(): kernel, and notify
    - three system calls: msg_send, msg_receive, msg_rpc (remote procedure call, to execute something elsewhere)
  - Windows XP:
    - message-based using "local procedure call" (can only be used by local processes)
    - communication channels established using ports (sort of like mailboxes)
    - client opens handle to subsystem's connection port, sends a connect request
    - server creates two private communication ports, sends one to client, keeps the other one
    - corresponding ports are used by server and client to send/receive messages
    - INSERT DIAGRAM LATER
client-server communication
- sockets (endpoints for communication)
  - IP address + port
  - different services listen on different ports, e.g. ssh on 22, typical web servers on 80, etc
- remote-procedure calls
  - allows clients to invoke a procedure on a remote host as if it were local
  - client-side stub locates server, marshalls parameters, sends them over (underlying details abstracted)
  - server-side stub receives messages, unmarshalls parameters, performs procedure
  - INSERT DIAGRAM LATER (or describe it at least)
- remote method invocation (java only)
  - java program on one machine can call a method on a remote java object
  - basically the same as RMI except there are objects involved
  - THERE IS A DIAGRAM HERE. it doesn't really say much though. look it over anyway

What is associated with process in memory etc

Stack (which grows downward), heap (which grows upward), data section (for global variables), text (program code)

Five process states?

New, ready, running, waiting, terminated

What's contained in a PCB, and which of these things are saved (updated) when an interrupt occurs?

Process state
Program counter
CPU registers
CPU scheduling info
Memory management info
Accounting info
I/O status info

First three are saved when an interrupt occurs

Types of queues? What are the elements of these queues?

Job queue (all processes), ready queue (those residing in main memory that are ready to execute), device queues (those waiting for each I/O device, so a different one for each device). Elements: PCBs

Describe the types of schedulers and how often they're invoked, etc.

Long-term scheduler: decides which processes to bring into main memory (ready queue), invoked infrequently

Short-term scheduler: which process should be executed next (from ready queue to CPU), invoked frequently

There is also a medium-term scheduler which is probably less important but apparently it removes processes from memory once in a while.

What is an I/O-bound process? What is a CPU bound process?

I/O-bound: spends a lot of time doing I/O (and thus waiting for that). Characterised by many short CPU bursts.

CPU-bound: guess

What happens during context switching

Registers, PC, process state saved in PCB (no useful work done)

What does fork do, and how does it differ from exec

Fork creates a new process identical to the parent. Exec uses fork, then replaces the child process' memory space with that of a new program.

Why would a parent abort a child?

If the child is consuming too many resources (e.g., milk) or the child is not doing anything useful (a very common occurrence).

How can two processes communicate and shit (the two main methods)

Message-passing and shared mailboxes

Describe the bounded buffer thing.

in: pointer to first free position; out: pointer to first full position

Producer needs to wait when full (when (int + 1) % BUFFER_SIZE == out). Otherwise, add an item, increase in.

Consumer needs to wait when empty (when in == out). Othewise, remove an item, increase out.

Describe direct communication. Advantages? Disadvantages?

A process specifies another process by name, establishes a link between the two. Advantages: simple; disadvantages: hard-coded identity, hard to make changes later

what is it

Ports ("mailboxes"), each has unique ID, processes put shit in ports

what is it

Sender randomly throws a message into the air, some receiver gets it and consequently will be the next to get married. Sender gets notified as to who.

Types of queues (for messages, attached to link)?

Zero capacity (sender must wait for receiver - they must meet)
Bounded (sender waits if queue is full)
Unbounded (sender never waits, but this isn't really feasible lol)

Describe IPC implementations for POSIX, Mach, Windows XP.

POSIX: shared memory. Process creates shared memory segment, which returns an ID. Processes wanting access to that segment attach to it by ID (this function returns a pointer to that memory segment), and can then write to it using the pointer. Can detach from segment when done.

Mach: message-based (everything is, even system calls). All tasks are created with 2 mailboxes.

Windows XP: message-based using local procedure call. Communication channels established using ports. Whatever

What does a socket consist of

IP address and port

What is this, how does it differ from remote method invocation

Allows clients to invoke procedures on remote hosts as if they were local. Client-side "stub" locates server, marshalls parameters, sends them over; server-side stub unmarshalls, executes procedure.

Remote method invocation is a Java-only thing that allows programs on one machine to call methods on remote objects. Same as above except, objects.

Thread: unit of CPU utilisation, forms basis of multithreaded computers
- things unique to each thread: thread ID, program counter, register set, stack
- things threads from the same process share: code, data (statically-created variables), OS resources (open files, signals)
- single-threaded process: code + data + files, then registers + stack
- multi-threaded: code + data + files, then each thread gets its own registers and stack
- Benefits of threading
  - Greater responsiveness (if one thread is blocked or busy, can keep going - e.g., webservers)
  - Resource sharing (memory, other resources)
  - Cheapter than creating new processes in terms of allocating memory and resources (context-switching is easier)
  - Scalability: threads can run in parallel on multiple processors (I don't really see how this is best characterised as "scalability"; perhaps making full use of resources?)
- In the client-server model: client sends request, server spawns new thread to handle request, server resumes listening for requests
Single vs. multicore
- on a single-core system, threads are allocated in a cycle: t1, t2, t3, t4, t1, t2, t3, t4 etc (this is what is meant by concurrency apparently?)
- on a multicore system, concurrency means that threads are actually executed at the same time. could be t1 t3 t1 t3 on one core, t2 t4 t2 t4 on the other, etc
- challenges of multicore systems:
  - how to divide up activities? need to find parts of application that can be divided into smaller tasks that can run in parallel
  - how to split data? must be divided to run on separate cores (? how does this make sense)
  - data dependency: what if one task depends on the results of another?
  - testing/debugging: many different execution paths
user-level thread libraries:
- POSIX threads
- win32 threads
- Java threads
Kernel threads: handled by the kernel
Multithreading models, per process (user-to-kernel):
- many-to-one (many user-level, single kernel)
  - examples: solaris green threads library, gnu portable threads
  - thread management done by user space thread library (efficient)
  - but only thread can access the kernel at a time, so if any user thread makes a blocking syscall entire process will block
- one-to-one (one kernel thread per user thread)
  - examples: windows nt/xp/2000, linux, solaris 9+
  - benefits: more concurrency (syscalls are not blocking for other threads)
  - downsides: can result in decreased performance as you have to create many kernel threads, etc
  - also, some OSes limit the number of kernel threads possible at any given time
- many-to-many
  - examples: solaris before 9, windows nt/2000 with threadfiber package (how cute)
  - many user threads mapped to the same number of or fewer kernel threads
  - OS can create as many user threads as it needs to, since it doesn't have to create a kernel thread for each one
  - true concurrency: corresponding kernel threads can run in parallel on a multiprocessor (what does this have to do with anything)
- two-level model
  - examples: IRIX, HP-UX, Tru64 unix, solaris before 9
  - like the many-to-many model, except user threads can be bound to kernel threads as well (so a superset of many-to-many)
thread libraries
- APIs for creating, managing threads
- can be implemented in user space
  - calling a function in library results in a local call (not sys call) in user space
- or, using the kernel-level library provided by OS
  - code, data structures of library exist in kernel space
  - invoking APi function usually results in sys call
- pthreads: a POSIX standard for APIs for thread creation and sync
  - provided as user-level or kernel-level
  - the behaviour is specified by this standard, but it can be implemented differently by different OSes
  - examples: Solaris, Mac OS X, FreeBSD, Linux (there is even a windows implementation)
- Java threads
  - managed by the JVM, implemented using underlying thread library provided by OS
  - these threads can be created by extending the Thread class or implementing the Runnable interface
various issues (and non-issues) relating to threads
- behaviour of fork()
  - should it duplicate only the calling thread or all threads of that process?
  - some unix systems thus have two versions of fork()
  - exec, when invoked by a thread, will replace all the threads in that process. wait wtf? how? and why is this relevant to fork?
- thread cancellation (premature termination)
  - how to deal with resource allocation, or if it's updating a data segment shared by other threads?
  - asynchronous cancellation: terminates the thread immediately (bit of a misleading name)
  - deferred cancellation: thread periodically checks if it should be cancelled, giving it the chance to die nobly
    - aside: signal handling (i think this section should count as an aside, even though it has its own slide)
    - signal handlers used to notify processes that specific events (e.g., kill events) have occurred
    - event generates signal, signal gets delivered to process, signal is handled
    - many options as to whom the signal is delivered to:
      - only the relevant thread
      - every thread in the process to which the relevant thread belongs
      - certain threads in the relevant process
      - a specific thread that receives all signals for the process
- thread pools
  - create some threads, throw them into a pool in which they wait around for work to be doled out, the poor creatures
  - faster to make an existing thread service a request than to create a new thread
  - number of threads in application bounded by the size of the pool
  - of course, this has the slight disadvantage of having to create all the threads at the very beginning (slower startup maybe)
- thread-specific data
  - so that each thread can have its own copy of data
  - supported by most threading libraries
  - e.g., transaction system (?)
- scheduler activations
  - what does this even meeeeeean
  - both the many-to-many and the two-level models require communication to ensure correct number of kernel threads
  - the mechanism for this communication is via upcalls (like the opposite of a system call?), from the kernel to the thread library, provided by "scheduler activations" whatever those are
threads in different OSes
- windows XP
  - each app runs as a separate process
  - each can have one or more threads
  - thread library included in win32 api, one-to-one
  - fiber library (many-to-many) available too
  - each thread contains thread ID, register set, separate user/kernel stacks, private data storage area (last three collectively known as context)
  - primary data structures of a thread:
    - ethread: executive thread block (thread start address, pointer to parent block, pointer to kthread) - kernel space
    - kthread: kernel thread block (scheduling and sync info, kernel stack, pointer to teb) - kernel space
    - teb: thread environment block (thread identifier, user stack, thread-local storage) - user space
- linux
  - called tasks not threads
  - one-to-one
  - threads created by calling clone() (allows child task to share address space of parent task, or process)
  - amount of sharing that takes place is controlled by flags
    - CLONE_FS: file-system info shared
    - CLONE_VM: same memory space
    - CLONE_SIGHAND: share signal handlers
    - CLONE_FILES: share open files (how does this differ from CLONE_FS?)
  - NPTL (Native POSIX Thread Library) supported by most modern distros, POSIX-compliant

What is unique to each thread? What do threads from the same process share?

Unique: Thread ID, program counter, register set, stack

Shared: code, data (statically-created variables), OS resources (open files, signals)

^

More responsive
Can share memory, other resources
Cheaper than creating processes, context-switching is easier
More scalable? for multiple processors

What are the multithreading models, describe them, pros, cons, etc

Many-to-one (many user-level threads per kernel thread). Only one thread can access kernel at each time, so if one thread makes a blocking call, entire process blocks
One-to-one (one kernel per user): not blocking so more concurrency, but decreased performance as you have to create many kernel threads; also, some OSes limit number of kernel threads that can be created, so the number of user threads is limited too
Many-to-many (many user to some kernel): true concurrency, OS can create as many user threads as it wants, etc. Variant: two-level model, where you can have one user thread per kernel thread maybe

Different methods for dealing with thread cancellation

Asynchronous: terminates it immediately

Deferred: thread periodically checks to see if it should be cancelled

What are thread pools, pros and cons

Create a bunch of threads, throw them into a pool. There they wait to be given stuff to do. Pros: faster for existing thread to service request than to make a new thread. Cons: increased startup time to create all the threads, etc

attributes (kept in dir structure, which is on disk)
- name
- system identifier
- type
- location
- size
- protection (permissions)
- time, date, user identification
operations
- create: allocate space in system, make new entry in directory
- write: given file name and info to be written, system searches for it, keeps a write pointer
- read: ^ but read pointer
- reposition in file: seek, pointer value changes
- delete: find file, release space, delete dir entry
- truncate: delete contents, keep attributes
open() system call avoids constant searching for dir entry (saves it in memory; close() frees)
- takes file name, copies dir entry into open file table, returns pointer
- per-process table (pointer, rights), system-wide (location, access dates, file size)
- to manage open files, need pointer, open count, location, access rights
access methods
- sequential
- direct
- index
- can simulate sequential on direct
- direct on sequential is inefficient
storing files on disks
- partitions
- raw or formatted
- RAID protection
- volume = entity with filesystem
directory structure
- collection of nodes pointing to files
- operations
  - search for file
  - create
  - delete
  - list
  - rename
  - traverse
- single-level directory for all users: dumb
- two-level, one for each user: bad for cooperation
- tree-structured: each file has unique path name
  - acyclic graph
  - hard links?
  - multiple abs path names
  - reference list: delete files when no references to it exist
  - self-reference?
  - check that there are no cycles
mounting
sharing, etc, nothing special
failure
- directory corruption, disk-controller failure, etc
types of access (for right management):
- read
- write
- execute
- append
- delete
- list

What are they?

Name
System identifier
Type
Location on disk
Size
Permissions
Time, date, user identification

Purpose? What does close do?

To cache file info in memory, to avoid constantly searching for the dir entry. Close frees that memory. It takes the file name, copies the the dir entry into the open file table, and returns the pointer.

What's stored in the per-process table? System-wide table?

Per-process: pointer (to file contents, in memory), access rights

System-wide: location on disk (?), access dates, file size

Structure
- Organised into layers somehow
- File system resides on disk, provides efficient and convenient access to disk
- File control block: storage structure, contains info about file (owner, permissions, location on disk)
- Device driver controls physical device
Implementation
- Boot control block: contains info needed by system to boot OS from volume
- Volume control block (per volume): contains details for that partition (number of blocks, block size, etc)
- File control block:
  - permissions
  - file create, access, write dates
  - file owner, group
  - file size
  - pointers to data blocks
Directories
- linear list of file names is very inefficient
- instead, we use a hash table
- linear list to store the directory entries, hash data structure for accessing pointers
- pros: directory search time decreases
- cons: collisions, etc
Allocation methods
- contiguous: each file occupies a set of consecutive blocks on disk
  - dir entry indicates address of starting block, number of blocks
  - pros: simple, sequential access is easy, direct access isn't too hard
  - cons:
    - wasteful of space (can result in external fragmentation)
    - files cannot grow in size after they are first created (like arrays in C)
- linked allocation: file is linked list of disk blocks
  - blocks can be stored anywhere
  - directory contains pointer to first, last blocks of file
  - each block contains pointer to next block
  - pros: no external fragmentation, because any free block can be used; files can grow; simple
  - cons: random access is inefficient, lots of space overhead for pointers
  - FAT (file allocation table): used by MS-DOS
    - variation on linked allocation
    - dir entry contains block number of first block in file
    - a section of disk at the beginning of each volume is reserved for a table
    - that table contains the next block number for each block in the file
    - unused blocks indicated by value of 0
    - last block contains EOF value
    - pros: random access is fast
- indexed allocation
  - all pointers stored in index block (one for each file)
  - ith entry in the index block points to ith block of file
  - directory contains address of index block
  - pros:
    - direct access
  - cons:
    - pointer overhead of index block (usually greater than the pointer overhead for linked allocation)
    - if most files are small, then linked allocation wins - only one pointer per block for linked, but an entire index block for indexed
  - optimal size for index blocks? if small, less overhead, but may not be able to hold enough pointers
  - linked scheme: link together several index blocks
    - one block contains n file block addresses
    - large files may need several index blocks
    - multi-level index: one index block points to other blocks, etc
    - example: 4096-byte blocks, each pointer 4 bytes, 2-level index
    - store 1024 = 2¹⁰ pointers per index block
    - 2 levels of indexes, so 1024² = 10²⁰ data blocks
    - so 10²⁰ * 4096 = 10²⁰ * 10¹² = 10³² = 4 * 10³⁰ = 4 GB
  - combined scheme: used in UFS
    - keep first 15 pointers of index block in file's inode (FCB for UNIX)
    - first 12 pointers: directly to blocks (so small files don't need separate index blocks)
    - the 13th: points to index block containing addresses of file blocks
    - 14th points to double indirect block (pointer to index block containing pointers to file block, what is this i don't even)
    - 15th: triple indirect block
Free space management
- disk space is limited, need to reuse space from deleted files
- to keep track of free disk space, system maintains free space list for free blocks
- usually implemented as a list (bit vector, length n where n is the number of blocks)
  - if 1, free; if 0, occupied
  - block number calculations are supported by the hardware somehow
    - to find the first free block number: number of bits per word * number of 0-value words + offset of first 1 bit, what
  - this bit map requires extra space
  - if block size = 2¹² bytes, and disk size = 2³⁰ bytes (1 GB), then you need 2¹⁸ bytes for the bit map (so 32 KB)
  - but, it's easy to get contiguous blocks
- another solution: linked list (free list)
  - link together all the free disk blocks
  - pointer to the first free block in a special location on disk (also cached in memory)
  - harder to get contiguous space
  - but, less space is wasted
- grouping: modification of the linked list approach
  - first free block stores the addresses of n free blocks, and then one other block which is not actually a free block but instead contains address of another n free blocks
  - faster to find a large number of free blocks using this method
Recovery
- files, directories kept in main memory (for speed) but also disk (for consistency)
- system failure/crash can result in data loss or inconsistency
- consistency checking: compares data in dir structure with data blocks on disk, etc
- fsck for Unix, chkdsk for windows
- journaling (like ext3/4 for linux)
  - each update to file system recorded as transaction
  - same techniques used by databases to guarantee FS consistency
NFS
- Sun Network File System
- implementation/specification of software system for accessing remote files across LANs/WANs
- part of Solaris, SunOS operating systems
- Ethernet: family of computer networking technologies for LAN, part of IEEE standard
- independent machines can access shared file systems transparently (i.e. user doesn't need to see the details)
- remote directory mounted over a local file system directory
- the mounting operation isn't "transparent", though
- cascading mount: allowed in some NFS implementations (remote file systems mounted on a remote file system can be accessed, etc)

What's in a file control block

Permissions
Create, last accessed, last modified dates
File owner, group
File size
Pointers to data blocks

How

Linear list (like an array? linked list?) to store the dir entries, hash data for accessing pointers to files

What are they, pros and cons of each

Contiguous, linked allocation, indexed allocation.

Contiguous: consecutive blocks. wasteful of space (results in external fragmentation), files cannot grow in size.

Linked: Linked list, each thing has some content and pointer to next thing. No external fragmentation, and files can grow, but random access is inefficient and there's lots of space overhead for the pointers.

Indexed: pointers stored in index block (one for each file), basically an array. Dir entry contains address of index block. Direct access is fast, pointer overhead is greater than for linked if files are small

Given x-byte blocks, each pointer = y bytes, 2-level index. Can store x / y pointers per index block. 2 levels of indexes, so (x/y)² data blocks. So x²/y² * x = x³/y³ bytes that can be stored total

Describe the different solutions

Bit vector: length n, where n is the number of blocks. 1 if free, 0 if occupied. To find the first free block number: number of bits per word * number of 0-value words + offset of first 1-bit block. If block size is x, and disk size is y, you need y/x bytes for the bit map. Easy to get contiguous space.

Linked list: each element is a free disk block, pointer to first block from special location in disk and memory. Harder to get contiguous space but less is wasted.

Grouping: like linked list. First free block stores addresses of n free blocks, and then a pointer to the next thing like this. Faster to find a large number of free blocks.

What is it

Like transactions with databases. For guaranteeing consistency.

What is it

NFS, when you mount a remote file system somewhere on a machine, then that is mounted by another machine

Can blocks be partially written to? That is, can part of one block be used for something, with the other part being used for something else?

No. Even if only one bit in the block is actually written to, the entire block is considered used. (I couldn't find the right place for this in the notes above.)

Midterm review

1Chapter 1: Introduction¶

1.1Sample questions¶

1.1.1Components of a computer system¶

1.1.2Bootstrap programs¶

1.1.3Monolithic kernels and microkernels¶

1.1.4Computer system organisation¶

1.1.5The interrupt model¶

1.1.6Interrupt timelines¶

1.1.7Traps¶

1.1.8Device status tables¶

1.1.9Direct memory access¶

1.1.10Storage structure hierarchy¶

1.1.11Multiprocessor systems¶

1.1.12Multicore systems¶

1.1.13Timesharing¶

1.1.14Modes¶

1.1.15Processes¶

2Chapter 2: Operating system structures¶

2.1Sample questions¶

2.1.1Parameter-passing¶

2.1.2Microkernels¶

2.1.3Virtual machines¶

2.1.4Paravirtualisation¶

2.1.5Bootloaders¶

3Chapter 3: Processes¶

3.1Sample questions¶

3.1.1Processes in memory¶

3.1.2Process states¶

3.1.3Process control blocks¶

3.1.4Process scheduling queues¶

3.1.5Schedulers¶

3.1.6I/O and CPU bound processes¶

3.1.7Context switching¶

3.1.8Forking and execing¶

3.1.9Abortion¶

3.1.10Inter-process communication¶

3.1.11Producer-consumer problem¶

3.1.12Direct communication¶

3.1.13Indirect communication¶

3.1.14Round-robin communication¶

3.1.15Message queues¶

3.1.16IPC in various operating systems¶

3.1.17Client-server communication¶

3.1.18Remote procedure calls¶

4Chapter 4: Threads¶

4.1Sample questions¶

4.1.1Things associated with threads¶

4.1.2Benefits of threading¶

4.1.3Multithreading models¶

4.1.4Thread cancellation¶

4.1.5Thread pools¶

5Chapter 10: Filesystem interface¶

5.1Sample questions¶

5.1.1File attributes?¶

5.1.2The open system call¶

5.1.3Open file tables¶

6Chapter 11: Filesystem implementation¶

6.1Sample questions¶

6.1.1File control blocks¶

6.1.2Directory implementation¶

6.1.3Allocation methods¶

6.1.4Linked index allocation calculations¶

6.1.5Free space management¶

6.1.6Journaling¶

6.1.7Cascading mount¶

6.1.8Blocks and partial storage¶