Operating Systems

System calls and kernel mode

How a user program asks the operating system for a service: user and kernel mode, the mode bit and privileged instructions, the trap that switches modes, the system call table and parameter passing, library wrappers, and the difference between a mode switch and a context switch.

Process model and PCB

What a process is and how the OS represents it: program versus process, the process image, the process control block and the process table, process identifiers and hierarchy, CPU-bound and I/O-bound processes, and CPU utilization as a function of the degree of multiprogramming.

Process states, fork and exec

The life cycle of a process: the five-state model and its legal transitions, suspended states, the queues and the three schedulers, and how processes are created and ended with fork, exec, wait and exit, including zombies, orphans and counting the processes a fork program creates.

Context switching

Moving the CPU from one process to another: what the context is, the steps of a context switch (save, choose, restore), what triggers one, the dispatcher and its latency, why it is pure overhead and what makes it expensive, and the efficiency of round robin with a switch cost.

Threads and multithreading models

Threads as units of execution inside a process: what threads share and what is private, why they are cheaper than processes, user-level and kernel-level threads, the many-to-one, one-to-one and many-to-many models, blocking behaviour and multicore speedup.

CPU scheduling: criteria, FCFS, SJF and SRTF

How the OS chooses which ready process runs: the scheduling criteria and their formulas, preemptive and non-preemptive scheduling, the dispatcher, and first come first served, shortest job first, shortest remaining time first and highest response ratio next, with Gantt charts and the average waiting time.

Priority and round robin scheduling

Priority scheduling (preemptive and non-preemptive, starvation and aging) and round robin (the time quantum, the circular ready queue, bounds on waiting and response time, the effect of the quantum and of the context-switch cost), with Gantt charts and the conventions that change the answer.

Disk scheduling

Ordering the requests to a hard disk to cut head movement: the access time of a disk (seek, rotational latency, transfer), and the FCFS, SSTF, SCAN, C-SCAN, LOOK and C-LOOK algorithms with their total head movement, their fairness and starvation behaviour, and the conventions that change the numbers.

Critical section and race conditions

Why concurrent access to shared data goes wrong: race conditions and lost updates, the structure of a critical section (entry, exit, remainder), the three requirements of a solution (mutual exclusion, progress, bounded waiting), and counting the possible results of racing updates.

Peterson, Dekker and software solutions

Mutual exclusion for two processes with nothing but ordinary reads and writes: strict alternation, the flag attempts and why each fails, Peterson's algorithm and why it works, Dekker's and the bakery algorithm, the checks of mutual exclusion, progress and bounded waiting, and the memory-ordering caveat.

Semaphores

The semaphore: an integer with atomic wait and signal operations; busy-waiting and blocking implementations, the value arithmetic, binary and counting semaphores, the three uses (mutual exclusion, ordering, resource counting), the rendezvous, deadlock from the wrong order, and finding the possible outputs of programs with semaphores.

Producer-consumer, readers-writers, dining philosophers

The standard synchronization problems and their semaphore solutions: the bounded buffer (producer-consumer), the readers-writers problem and its starvation, and the dining philosophers with the ways to avoid deadlock, each checked by exploring every interleaving.

Deadlock: conditions and resource allocation graphs

What a deadlock is, the four necessary conditions (mutual exclusion, hold and wait, no preemption, circular wait), resource allocation graphs and when a cycle means deadlock, the four ways of handling deadlock, prevention by breaking each condition, and the minimum number of resources that makes deadlock impossible.

Deadlock avoidance and the Banker's algorithm

Granting requests only when the system stays safe: safe and unsafe states, the Allocation, Max, Need and Available matrices, the safety algorithm, the resource-request algorithm, the relation between unsafe states and deadlock, and the claim-edge version for single-instance resources.

Memory management: partitioning and fragmentation

Sharing main memory among processes by contiguous allocation: fixed and variable partitions, the first, best, worst and next fit placement rules, internal and external fragmentation, compaction, swapping, and the buddy system.

Process address space

The addresses a process uses and the addresses the memory sees: logical and physical address spaces, address binding at compile, load and execution time, the memory-management unit with base and limit registers, dynamic loading and linking, shared libraries, and how each process gets its own layout of code, data, heap and stack.

Paging and address translation

Non-contiguous allocation by fixed-size pages and frames: splitting a logical address into page number and offset, the page table, the translation to a physical address, the sizes of address spaces and page tables, internal fragmentation, the choice of page size, protection bits and sharing.

Segmentation and segmented paging

Memory as a set of variable-size segments that follow the program's structure: logical addresses as (segment, offset), the segment table with base and limit, translation and its traps, protection and sharing, external fragmentation, the comparison with paging, and segmentation combined with paging.

Multilevel, inverted and hashed page tables

Why a flat page table is too big and how to shrink it: hierarchical (multilevel) tables with the address bits split by level, how many levels are needed, the memory they save, hashed page tables for sparse large address spaces, and the inverted page table that has one entry per frame.

Virtual memory and demand paging

Running programs that are not fully in memory: the idea of virtual memory, demand paging and the valid bit, what happens on a page fault step by step, the effective access time with page faults and the fault rate it allows, the modified bit, copy-on-write, and locality of reference.

TLB and effective access time

The translation lookaside buffer: why paging doubles memory accesses, how a small associative cache of recent translations fixes it, hits and misses, the effective access time with one or several page-table levels, the TLB reach, address-space identifiers and flushing, and the combination with page faults.

Page replacement algorithms

Choosing the victim when memory is full: FIFO, optimal, LRU and the approximations of LRU (reference bits, second chance and the clock, the enhanced version with the modify bit), counting algorithms, Belady's anomaly, stack algorithms, and counting page faults for a reference string.

Thrashing and the working set

What happens when a process does not have enough frames: thrashing and the collapse of CPU utilization, locality, the working-set model and its use to control the degree of multiprogramming, the page-fault-frequency scheme, and the allocation of frames among processes.

File systems: concepts and directories

What a file is and what the system keeps about it: attributes, operations, the open-file tables, access methods, directory structures from single-level to graphs, path names and their cost, hard and symbolic links and link counts, protection bits, and the layers and on-disk layout of a file system.

File allocation methods and inodes

How the blocks of a file are placed on the disk and found again: contiguous, linked, FAT and indexed allocation with their access costs, the Unix inode with direct and indirect pointers, the maximum file size, the number of disk accesses to read a given block, and the size of a FAT.

Inter-process communication

How processes with separate address spaces exchange data: the two models (shared memory and message passing), direct and indirect naming, blocking and non-blocking send and receive, mailbox capacity (rendezvous, bounded, unbounded), pipes and their end-of-file and broken-pipe behaviour, a shared-memory ring buffer that holds N-1 items, the lost update when a shared counter replaces it, signals and sockets, and a comparison of the mechanisms.

Test-and-set, swap and atomic instructions

Mutual exclusion with hardware help: disabling interrupts, the atomic instructions test-and-set, swap, compare-and-swap and fetch-and-add, the spinlocks built on them, why a plain test-and-set lock allows starvation, the bounded-waiting algorithm, the ticket lock, and how a lock that looks right can still fail.

Deadlock detection and recovery

Letting deadlocks happen and then dealing with them: the wait-for graph for single-instance resources, the detection algorithm for several instances (Allocation, Request, Work), how it differs from the Banker's safety test, how often to run it, and recovery by terminating processes or preempting resources, including how to choose the cheapest victims.

Multilevel queues and real-time scheduling

Scheduling beyond FCFS, SJF and round robin: multilevel queues and the multilevel feedback queue (how a scheduler approximates shortest-job-first without knowing the bursts), periodic real-time tasks with rate-monotonic and earliest-deadline-first scheduling, the utilisation tests (U at most n(2^(1/n) - 1) for rate monotonic, U at most 1 for EDF) and the exact response-time analysis, priority inversion and priority inheritance, and short definitions of gang, fair-share, guaranteed and lottery scheduling.

I/O subsystem, buffering and spooling

How the operating system handles input and output: controllers, drivers and interrupt handlers, memory-mapped and isolated I/O and how it is protected, polling against interrupts against DMA, the services of the kernel I/O subsystem (scheduling, buffering, caching, spooling), blocking, non-blocking and asynchronous I/O, the time saved by single and double buffering, and CPU utilisation when processes wait for I/O.