System Software & Operating Systems

Overview: what this unit covers

Think of this unit as three linked questions. First, who runs, and in what order: processes, threads, and CPU scheduling, plus the synchronisation rules that stop concurrent processes from corrupting shared data. Second, where does data live while a program runs: memory management and virtual memory, including paging, replacement, and thrashing. Third, what happens when sharing goes wrong or reaches slow hardware: deadlock, file systems, disk scheduling, and input-output. Learn the terms as one connected system.

Processes, threads & scheduling

A program is passive code stored on disk; a process is that program in execution, together with its program counter, registers, stack, data, and open files. A process moves through states: new, ready, running, waiting, and terminated. Ready waits only for the CPU; running holds it; waiting waits for an event; terminated has finished. The operating system records all of this in the process control block, or PCB, which holds the process identifier, state, program counter, CPU registers, scheduling information, memory information, accounting data, and input-output status. When the CPU switches from one process to another, it saves the old process state into its PCB and loads the new one, an operation called a context switch. Context switching is pure overhead.

A thread is a lighter unit of execution inside a process. Threads of one process share the code, data, and open files, but each has its own program counter, registers, and stack. Because threads share so much, creating a thread and switching between threads of the same process is cheaper than creating a process and switching between processes. Multithreading models describe how user threads map to kernel threads: many-to-one maps many user threads to one kernel thread, so one blocking system call blocks them all; one-to-one maps each user thread to a kernel thread, giving true parallelism at higher cost; and many-to-many multiplexes many user threads over a smaller or equal number of kernel threads.

CPU scheduling decides which ready process runs next. The criteria are CPU utilisation, throughput, turnaround time, waiting time, and response time. Turnaround time is completion time minus arrival time; waiting time is turnaround time minus burst time; response time is the time from arrival to first CPU use. Schedulers may be non-preemptive or preemptive. First-come first-served is simple and non-preemptive but suffers the convoy effect, where one long process delays many short ones behind it. Shortest-job-first chooses the smallest next burst and gives the minimum average waiting time among non-preemptive algorithms, but it can starve long processes and needs burst estimates. Shortest-remaining-time-first is its preemptive version. Round robin cycles processes through a fixed time quantum. Priority scheduling attaches a priority to each process and can starve low-priority processes unless aging gradually raises the priority of a process that has waited long. Multilevel feedback queues let a process move between queues based on its behaviour.

When processes share data, a race condition occurs if the final result depends on the order in which processes access shared data. The part of code that accesses shared data is the critical section. A correct solution must give mutual exclusion, so only one process is in its critical section at a time, progress, so no process outside the critical section blocks others, and bounded waiting, so no process waits forever to enter. A semaphore is an integer variable accessed only through two atomic operations: wait, which decrements the value and blocks the caller if it becomes negative, and signal, which increments the value and wakes a waiting process. A binary semaphore takes only values zero and one and works like a lock; a counting semaphore can take any non-negative value and tracks a pool of identical resources. A monitor is a higher-level construct: an abstract data type whose procedures are mutually exclusive by construction, with condition variables for waiting and signalling inside it. Classic problems include producer-consumer, readers-writers, and dining philosophers. Expect Gantt-chart arithmetic and questions on starvation and preemption.

Memory management & virtual memory

Every process sees logical addresses generated by the CPU, while the hardware works with physical addresses in real memory. The memory management unit translates logical addresses to physical ones, usually at run time, so a program can be loaded at different physical locations without being rewritten. In contiguous allocation, each process occupies one continuous block of memory. Fixed partitioning divides memory into fixed blocks, wasting space inside a block when a process is smaller, which is internal fragmentation. Variable partitioning gives each process exactly the block it requests, but leaves scattered holes that are individually too small, which is external fragmentation. Allocation strategies choose among holes: first-fit takes the first hole large enough, best-fit takes the smallest adequate hole, and worst-fit takes the largest hole. First-fit is usually fastest; best-fit can leave many tiny unusable fragments.

Paging removes external fragmentation by dividing logical memory into fixed-size pages and physical memory into frames of the same size. A page table maps each page number to a frame number, and a logical address splits into a page number and an offset within the page. A page table kept in memory would double memory accesses, so the translation lookaside buffer, or TLB, caches recent page-to-frame translations in fast associative memory. The effective access time combines these cases: if the hit ratio is h, memory access time is m, and the extra cost of a page-table lookup is folded in, the usual textbook form is effective access time equals h times the fast path plus (1 minus h) times the slow path. Multilevel page tables page the page table itself; an inverted page table keeps one entry per frame. Segmentation divides a program by logical meaning, such as code, data, stack, and heap, so each segment has a name, a base, and a limit, and addresses are checked against the segment limit. Many systems combine paging and segmentation.

Virtual memory goes further: it lets a program run even when only part of it is in physical memory. With demand paging, a page is loaded only when it is referenced. A reference to a page not in memory causes a page fault, and the system loads the page and restarts the instruction. If no frame is free, a victim page must be chosen for replacement. Page-replacement algorithms are judged by the number of page faults on a reference string. First-in first-out evicts the oldest loaded page and is simple but can evict a heavily used page, and it can show Belady's anomaly, where giving the process more frames increases the number of faults. Least recently used evicts the page unused for the longest time, on the principle that the recent past predicts the near future; it performs well but needs hardware support to track usage order. Optimal replacement evicts the page whose next use is farthest in the future, or never, and gives the fewest faults, but it requires knowledge of the future and so serves as a benchmark, not a practical algorithm. Thrashing is the collapse that follows when a process spends more time paging than executing: the degree of multiprogramming is too high, frames are too few, and the system services page faults instead of doing useful work. The working-set model keeps each process's recently referenced pages in memory. Expect fault counts, effective-access-time calculations, and fragmentation distinctions.

Deadlock, file systems & I/O

Deadlock is a state in which each process in a set waits for a resource held by another process in the set, so none can proceed. Four conditions must all hold simultaneously: mutual exclusion, meaning a resource is held by one process at a time; hold and wait, meaning a process holds resources while waiting for more; no preemption, meaning a resource can be released only voluntarily by its holder; and circular wait, meaning a cycle of processes each waiting for a resource held by the next. A resource-allocation graph makes this visible: processes are circles, resource types are squares with one dot per instance, an edge from a process to a resource is a request, and an edge from a resource to a process is an assignment. A cycle is necessary for deadlock; with one instance per resource type it is also sufficient.

Deadlock can be handled four ways. Prevention breaks at least one of the four conditions. Avoidance allows requests only when the resulting state is safe. The Banker's algorithm is the standard avoidance method: a state is safe if there is an order in which every process can finish using currently available resources plus the resources released by processes that finish earlier. A request is granted only if it leaves the state safe; otherwise the process waits. Detection and recovery lets deadlock occur, periodically checks for it, and then recovers by aborting a process or preempting a resource, accepting the cost of lost work. Ignoring deadlock, sometimes called the ostrich approach, is what many real systems do when deadlock is rare and prevention is expensive.

A file system must decide how a file's blocks are placed on disk. Contiguous allocation stores each file in consecutive blocks, giving fast sequential and direct access, but it suffers external fragmentation and makes growing a file hard. Linked allocation stores each block with a pointer to the next, so files can grow easily and no external fragmentation occurs, but direct access requires following pointers and a lost pointer loses the rest of the file. Indexed allocation keeps an index block holding pointers to all data blocks, giving direct access without external fragmentation, at the cost of the index block itself and a limit on file size unless multilevel indexing is used. Directories map names to file metadata and locations.

Disk scheduling orders requests to a moving head. FCFS serves in arrival order but can move the head far. Shortest-seek-time-first serves the nearest pending request and reduces total movement, but can starve distant requests. SCAN, the elevator algorithm, moves in one direction serving requests until the end of the disk, then reverses; C-SCAN moves in one direction only and jumps back to the start without serving on the return, giving more uniform waiting times. LOOK variants stop at the last request instead of the disk end.

Input-output completes the picture. Polling makes the CPU repeatedly check a device, wasting cycles. Interrupts let a device signal the CPU when it needs attention, so the CPU works on other tasks in between and handles the device only on the signal. Direct memory access goes further: a DMA controller transfers a whole block between device and memory without the CPU moving each byte, interrupting the CPU only when the block transfer finishes. Buffering holds data temporarily to smooth speed differences between producer and consumer, while spooling queues jobs for a slow device, classically a printer, so that several processes can write to a spool area on disk while only one job at a time actually reaches the device. Expect Banker sequences and disk-scheduling totals.

CPU scheduling algorithms compared

Page-replacement algorithms compared

File-allocation methods compared