Loading…
The most-examined subject on any CS syllabus. Processes and threads, scheduling, synchronisation, deadlock, virtual memory, page replacement, file systems and disk scheduling.
| Function | What it provides |
|---|---|
| Process management | Creation, scheduling, termination, synchronisation, IPC |
| Memory management | Allocation, address translation, protection, virtual memory |
| File management | Directory structure, access control, allocation of blocks |
| Device management | Drivers, buffering, spooling, interrupt handling |
| Protection & security | Isolation between processes, authentication, access control |
The CPU carries a mode bit. In kernel (supervisor) mode every instruction is permitted, including I/O and memory-mapping instructions. In user mode privileged instructions trap. This is the hardware support that makes protection possible - without it, any program could rewrite the page tables and the OS would be merely advisory.
| Kernel design | Runs in kernel space | Trade-off | Examples |
|---|---|---|---|
| Monolithic | Everything: scheduler, memory, file systems, drivers | Fast - no message passing - but a driver bug can crash the system | Linux, traditional Unix |
| Microkernel | Only IPC, scheduling and basic memory management | Robust and modular, but IPC between servers costs performance | QNX, MINIX, seL4 |
| Hybrid | A microkernel design with performance-critical parts pulled back in | A pragmatic middle ground | Windows NT, macOS (XNU) |
| Process state | Meaning | Leaves when |
|---|---|---|
| New | Being created | Admitted to the ready queue |
| Ready | Waiting for a CPU | The scheduler dispatches it |
| Running | Executing on a CPU | It is preempted, blocks, or exits |
| Waiting / Blocked | Waiting for I/O or an event | The event completes → back to Ready |
| Terminated | Finished; awaiting cleanup | The parent reaps its exit status |
The PCB is the kernel's record of a process - everything that must be saved to suspend it and restored to resume it: process ID and parent ID, current state, program counter, CPU registers, scheduling information (priority, queue pointers), memory-management information (page-table or segment-table base), accounting data, and the list of open files and I/O devices.
pid_t pid = fork();
// Returns TWICE: 0 in the child, the child's PID in the parent, -1 on failure.
// The child gets a copy of the parent's address space (copy-on-write in practice).
if (pid == 0) printf("child\n");
else if (pid > 0) printf("parent\n");
// How many processes does this create?
fork(); fork(); fork();
// 2^3 = 8 processes total (7 new children). Each fork doubles the count.
// exec() REPLACES the current image - it does not return on success.
// The fork-then-exec pair is how Unix starts a new program.| Process | Thread | |
|---|---|---|
| Address space | Private | Shared with sibling threads |
| Owns privately | Everything | Stack, registers, program counter, thread-local storage |
| Shares | Nothing without explicit IPC | Code, data, heap, open files, signals |
| Creation cost | High - new page tables, new PCB | Low |
| Context switch cost | High - TLB flush, cache pollution | Low - same address space, no TLB flush |
| Communication | IPC: pipes, shared memory, message queues | Direct - just read shared variables |
| Fault isolation | A crash kills only that process | A crash kills the whole process |
| Model | Mapping | Consequence |
|---|---|---|
| Many-to-one | Many user threads → one kernel thread | Fast switching in user space, but one blocking call blocks all threads, and no real parallelism |
| One-to-one | Each user thread → one kernel thread | True parallelism and independent blocking; kernel thread count must be bounded. Used by Linux and Windows |
| Many-to-many | m user threads → n kernel threads | Flexible and scalable, but complex to implement |
| Criterion | Definition | Goal |
|---|---|---|
| CPU utilisation | Fraction of time the CPU is busy | Maximise |
| Throughput | Processes completed per unit time | Maximise |
| Turnaround time | Completion − arrival | Minimise |
| Waiting time | Turnaround − burst; time spent in the ready queue | Minimise |
| Response time | First scheduled − arrival | Minimise - matters most for interactive work |
| Algorithm | Preemptive? | Selects | Strength | Weakness |
|---|---|---|---|---|
| FCFS | No | Earliest arrival | Trivially simple and fair | Convoy effect - one long job delays everyone |
| SJF | No | Shortest next burst | Provably minimal average waiting time | Burst length is not known in advance; starves long jobs |
| SRTF | Yes | Shortest remaining time | Better average than SJF | Same problems, plus more context switches |
| Priority | Either | Highest priority | Supports importance levels | Starvation - cured with ageing |
| Round Robin | Yes | Next in queue, one quantum each | Excellent response time; no starvation | Higher average turnaround; sensitive to quantum size |
| Multilevel queue | Yes | By queue class | Separates interactive from batch | Rigid - a process never changes queue |
| Multilevel feedback | Yes | By queue, with movement between them | Adapts to observed behaviour; the general-purpose answer | Many parameters to tune |
Process Arrival Burst
P1 0 7
P2 2 4
P3 4 1
P4 5 4
FCFS order: P1(0-7) P2(7-11) P3(11-12) P4(12-16)
Waiting = start - arrival: P1=0, P2=5, P3=7, P4=7 -> avg 4.75
SJF (non-preemptive): P1(0-7) P3(7-8) P2(8-12) P4(12-16)
Waiting: P1=0, P3=3, P2=6, P4=7 -> avg 4.00
SRTF (preemptive): P1(0-2) P2(2-4) P3(4-5) P2(5-7) P4(7-11) P1(11-16)
Waiting: P1=9, P2=1, P3=0, P4=2 -> avg 3.00
Note SRTF <= SJF <= FCFS on average waiting time. That ordering is the
point of the exercise.| Mechanism | How | Notes |
|---|---|---|
| Shared memory | Two processes map the same physical frames | Fastest - no kernel copy after setup - but you must synchronise |
| Pipes | A unidirectional byte stream | Anonymous pipes need a common ancestor; named pipes (FIFOs) do not |
| Message queues | The kernel holds discrete messages | Preserves message boundaries; kernel-mediated, so slower |
| Sockets | Endpoints, local or across a network | The only option that spans machines |
| Signals | Asynchronous notification of an event | Carries almost no data; handlers must be async-signal-safe |
// counter++ compiles to roughly:
// LOAD R1, counter
// ADD R1, 1
// STORE counter, R1
// With counter = 5 and two threads incrementing:
// T1: LOAD R1 = 5
// T2: LOAD R1 = 5 <- context switch before T1 stored
// T1: ADD -> 6, STORE 6
// T2: ADD -> 6, STORE 6 <- overwrites; counter is 6, should be 7Any correct solution to the critical section problem must satisfy three requirements:
Mutual exclusion
Progress
Bounded waiting
| Primitive | What it is | Key property |
|---|---|---|
| Mutex lock | Binary lock with ownership | Only the thread that locked it may unlock it. Use for mutual exclusion |
| Binary semaphore | Counter capped at 1, no ownership | Any thread may signal it - usable for signalling between threads |
| Counting semaphore | Counter over a resource pool | wait() decrements and blocks at 0; signal() increments. Use for N identical resources |
| Monitor | A language construct: data plus procedures with automatic mutual exclusion | Only one thread active inside at a time; condition variables provide wait/signal |
| Spinlock | A lock that busy-waits rather than blocking | Correct only when the wait is shorter than a context switch - i.e. inside multiprocessor kernels |
| Problem | The difficulty | Standard solution |
|---|---|---|
| Producer-Consumer (bounded buffer) | Producers must block when full, consumers when empty | Two counting semaphores (empty, full) plus a mutex for the buffer |
| Readers-Writers | Any number of readers may share; a writer needs exclusive access | A reader count guarded by a mutex, plus a write lock. Prone to starving one side - hence reader-priority and writer-priority variants |
| Dining Philosophers | Five philosophers, five forks, each needs two - naive code deadlocks | Break circular wait: have one philosopher pick up forks in the opposite order, or allow at most four at the table |
| Condition | Meaning | How to break it |
|---|---|---|
| Mutual exclusion | At least one resource is non-shareable | Make resources shareable - often impossible; a printer cannot be shared |
| Hold and wait | A process holding resources requests more | Require all resources be requested at once; hurts utilisation and can starve |
| No preemption | Resources cannot be forcibly taken | Allow preemption - practical for CPU and memory, not for a half-written file |
| Circular wait | A cycle exists in the wait-for graph | Impose a global ordering on resources and require requests in increasing order - the most practical of the four |
| Strategy | Approach | Cost |
|---|---|---|
| Prevention | Structurally negate one of the four conditions | Low resource utilisation; restrictive |
| Avoidance | Grant a request only if the system stays in a safe state (banker's algorithm) | Requires knowing maximum needs up front; expensive to run |
| Detection & recovery | Let it happen, run cycle detection, then kill or roll back a victim | Detection cost plus lost work |
| Ostrich algorithm | Ignore it; reboot if necessary | What Windows, Linux and Unix actually do |
Total resources: A=10 B=5 C=7
Allocation Max Need (Max - Allocation)
A B C A B C A B C
P0 0 1 0 7 5 3 7 4 3
P1 2 0 0 3 2 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
Allocated = 7 2 5, so Available = 10-7, 5-2, 7-5 = 3 3 2
Walk it: Need(P1)=1 2 2 <= 3 3 2 -> run P1, release 2 0 0 -> Avail 5 3 2
Need(P3)=0 1 1 <= 5 3 2 -> run P3, release 2 1 1 -> Avail 7 4 3
Need(P4)=4 3 1 <= 7 4 3 -> run P4, release 0 0 2 -> Avail 7 4 5
Need(P0)=7 4 3 <= 7 4 5 -> run P0, release 0 1 0 -> Avail 7 5 5
Need(P2)=6 0 0 <= 7 5 5 -> run P2
Safe sequence: P1, P3, P4, P0, P2 -> the state is SAFE.The problem: give every process the illusion of a private, contiguous address space, while physical memory is shared, fragmented, and smaller than the sum of demands.
| Scheme | Division | Fragmentation | Note |
|---|---|---|---|
| Contiguous, fixed partitions | Memory split into fixed blocks | Internal - a process rarely fills its partition exactly | Simple; wasteful |
| Contiguous, variable partitions | Blocks allocated to fit | External - free space exists but is scattered | Needs compaction |
| Paging | Fixed-size pages mapped to frames | Internal only, at most one page per process | No external fragmentation at all - the key advantage |
| Segmentation | Variable-size logical units: code, stack, heap | External | Matches the programmer's view; supports per-segment protection |
| Allocation strategy | Picks | Behaviour |
|---|---|---|
| First fit | The first hole large enough | Fastest; good enough in practice |
| Best fit | The smallest hole large enough | Wastes least per allocation but leaves many unusable slivers |
| Worst fit | The largest hole | Leaves large usable remainders; performs poorly in practice |
A logical address is split into a page number and an offset. The page number indexes the process's page table to find a frame number; the frame number and offset concatenate into the physical address. Because pages and frames are the same fixed size, any page fits any frame - which is exactly why external fragmentation disappears.
Reference
Trap
Locate
Load
Update and restart
| Replacement algorithm | Evicts | Belady's anomaly? | Note |
|---|---|---|---|
| FIFO | The oldest-loaded page | Yes | Simple; may evict a heavily used page |
| Optimal (OPT/MIN) | The page used farthest in the future | No | Unimplementable - requires the future. Used as a benchmark |
| LRU | The least recently used page | No | Good approximation of OPT; costly to implement exactly |
| LFU | The least frequently used page | Yes | A page popular once then unused lingers forever |
| Clock (second chance) | FIFO, but skip pages whose reference bit is set | Yes | The practical LRU approximation real kernels use |
FIFO LRU
7 -> [7] fault 7 -> [7] fault
0 -> [7,0] fault 0 -> [7,0] fault
1 -> [7,0,1] fault 1 -> [7,0,1] fault
2 -> [2,0,1] fault (7 out) 2 -> [2,0,1] fault (7 least recent)
0 -> [2,0,1] HIT 0 -> [2,0,1] HIT
3 -> [2,3,1] fault (0 out) 3 -> [2,0,3] fault (1 least recent)
0 -> [2,3,0] fault (1 out) 0 -> [2,0,3] HIT
4 -> [4,3,0] fault (2 out) 4 -> [4,0,3] fault (2 least recent)
FIFO: 7 faults LRU: 6 faults
LRU wins here because it keeps 0, which keeps being referenced.Thrashing is the state where a process spends more time paging than executing. The mechanism is a feedback loop: high paging lowers CPU utilisation, so the scheduler admits more processes to raise utilisation, which reduces frames per process further, which increases paging. Utilisation collapses.
| Cure | How it works |
|---|---|
| Working set model | Track the pages referenced in the last references. Give each process enough frames for its working set; suspend a process if the sum exceeds available frames |
| Page fault frequency | Measure each process's fault rate directly. Above an upper bound, grant more frames; below a lower bound, take some away |
| Reduce multiprogramming | Swap whole processes out - counterintuitive, but the only way to break the loop |
| Allocation method | How | Sequential access | Direct access | Weakness |
|---|---|---|---|---|
| Contiguous | Consecutive blocks | Excellent | Excellent | External fragmentation; the file cannot grow |
| Linked | Each block points to the next | Good | Poor - O(n) to reach block n | One bad pointer loses the tail; per-block overhead |
| Indexed | An index block lists every data block | Good | Excellent | Index-block overhead; large files need multi-level indexes |
The classic inode layout has twelve direct pointers, one single-indirect, one double-indirect and one triple-indirect. Small files are reached in a single lookup; large files remain addressable through the indirect levels.
| Hard link | Symbolic (soft) link | |
|---|---|---|
| Points to | The same inode | A path string |
| Survives deleting the original | Yes - data lives until link count hits 0 | No - becomes a dangling link |
| Can cross filesystems | No | Yes |
| Can link a directory | No - it would allow cycles | Yes |
| Consumes an extra inode | No | Yes |
| Algorithm | Behaviour | Trade-off |
|---|---|---|
| FCFS | Serve in arrival order | Fair; a great deal of head movement |
| SSTF | Nearest request first | Good throughput; starves distant requests |
| SCAN (elevator) | Sweep to one end, then reverse | No starvation; the edges wait longest |
| C-SCAN | Sweep one way, jump back to the start | More uniform waiting time than SCAN |
| LOOK / C-LOOK | As SCAN/C-SCAN, but reverse at the last request rather than the disk edge | Avoids pointless travel to the platter edge |
12 questions on Operating Systems · misses join your review queue, on this device only