Operating System
The Operating System section covers process management, synchronisation, deadlock, memory management and file/disk subsystems. Questions are numerical (scheduling averages, page faults, effective access time) or conceptual (which condition is violated, which algorithm guarantees what).
Scheduling
- FCFS suffers the convoy effect; SJF minimises average waiting time but needs burst prediction; round robin trades turnaround for responsiveness.
- Waiting time = turnaround time − burst time. Compute per process, then average.
Synchronisation and deadlock
- P (wait) decrements a semaphore and blocks at zero; V (signal) increments and wakes a waiter. A mutex is a binary semaphore with ownership.
- Deadlock needs all four: mutual exclusion, hold-and-wait, no preemption, circular wait.
- Banker's algorithm grants a request only if the resulting state is safe (a safe sequence exists).
Memory
- Page size is a power of two; the offset is log₂(page size) bits, the rest is the page number.
- EMAT with a TLB: h(t_TLB + t_mem) + (1−h)(t_TLB + 2·t_mem).
- FIFO suffers Belady's anomaly; LRU and Optimal do not.
Worked example
Reference string 1,2,3,4,1,2,5,1,2,3,4,5 with three frames. FIFO faults on 1,2,3,4,1,2,5,3,4 = 9 faults. LRU faults on 1,2,3,4,1,2,5,3,4,5 = 10 faults. FIFO performs better here - the reverse of intuition, and exactly the point of Belady's anomaly.
Traps that cost marks
- Reporting waiting time when turnaround time is asked.
- Missing that acquiring two semaphores in inconsistent order creates a circular wait.
- Assuming LRU can be implemented cheaply in hardware; it needs a stack or reference bits.