Operating Systems
The most-examined subject on any CS syllabus. Processes and threads, scheduling, synchronisation, deadlock, virtual memory, page replacement, file systems and disk scheduling.
If you remember nothing else
- A process has its own address space; threads of one process share it — that single fact explains every difference between them.
- Deadlock needs all four of mutual exclusion, hold-and-wait, no preemption and circular wait; breaking any one prevents it.
- A context switch is pure overhead — the CPU does no useful work while saving one PCB and loading another.
- Virtual memory gives each process a private address space larger than RAM; the MMU translates and the TLB caches those translations.
- Belady's anomaly — more frames causing more page faults — affects FIFO but never LRU or Optimal, because those are stack algorithms.
- Thrashing is when a process spends more time paging than executing; the cure is to reduce the degree of multiprogramming, not to add more swap.
What an operating system is
| 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 |
Kernel mode and user mode
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) |
Processes and the PCB
| 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 Process Control Block
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.
Cfork() and the classic counting question
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.Threads
| 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 |
CPU scheduling
| 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 |
Plain textWorked example — compute the averages
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.Inter-process communication
| 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 |
Synchronisation
CWhy counter++ loses updates
// 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
At most one process is inside its critical section at any time.Progress
If no process is in its critical section and some wish to enter, only those wishing to enter participate in the decision, and it cannot be postponed indefinitely.Bounded waiting
There is a limit on how many times other processes may enter after a process has requested entry — this is what rules out starvation.
| 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 |
The three classic problems
| 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 |
Deadlock
| 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 |
Plain textBanker's algorithm — finding the safe sequence
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.Memory management
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 |
Paging mechanics
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.
Virtual memory and page replacement
Reference
The CPU issues an address whose page-table entry has the valid bit clear.Trap
The MMU raises a page fault, trapping to the OS. The faulting instruction is suspended.Locate
The OS finds the page on the backing store and finds a free frame — running page replacement if none is free.Load
The page is read into the frame. This is a disk I/O, so the process blocks and another is scheduled.Update and restart
The page table is updated, the valid bit set, and the faulting instruction is restarted — not resumed midway.
| 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 |
Plain textReference string 7,0,1,2,0,3,0,4 with 3 frames
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
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 |
File systems and disk scheduling
| 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 |
Disk scheduling
| 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 |
Self-check
12 questions on Operating Systems · nothing is stored