Part IA Lent Term

Operating Systems: Examinable Syllabus

What the exam tests

The Part IA Operating Systems paper (Paper 2) is set by Dr Robert Watson (rmm1002). The course covers roughly 16 lectures across Lent term. The exam typically has 2 questions, each worth 20 marks, covering a mixture of bookwork (definitions, descriptions) and application (calculations, scheduling traces, page-replacement traces, access-matrix construction).

Syllabus checklist

1. Introduction and OS concepts

OS as extended machine and resource manager
Kernel mode vs user mode (dual-mode operation)
System calls: mechanism, cost, trap instruction
OS structure: monolithic, microkernel, hybrid

2. Protection and security

Dual-mode operation (mode bit, privileged instructions)
Memory protection: base and limit registers, MMU
Access control matrix: ACLs vs capabilities
UNIX file permissions (9-bit model, SetUID, check-at-open)
Users, groups, UID namespace (root is UID 0, not name “root”)

3. Processes and scheduling

Process vs programme; process states (5-state model)
PCB contents and context-switch steps
fork() and exec(); copy-on-write
Scheduling metrics and preemptive vs non-preemptive
FCFS, SJF, SRTF, RR (properties, Gantt-chart construction)
CFS: vruntime, weight, target latency, minimum granularity, red-black tree

4. Memory management

Address binding: compile-time, load-time, execution-time
Logical vs physical addresses; the MMU
Segmentation: base/limit, external fragmentation
Fragmentation types; compaction

5. Paging and page tables

Paging basics: page number, offset, address translation
PTE structure (present, R/W, U/S, A, D, NX bits)
Multi-level page tables (why, arithmetic, bit-splitting)
TLB: organisation, EAT formula, reach
5-level paging (57-bit addressing, 2025 exam)
Inverted page tables

6. Virtual memory and page replacement

Demand paging (page-fault handling steps, dirty pages)
OPT, LRU, FIFO (tracing on a reference string)
Belady’s anomaly and stack algorithms
Clock and enhanced clock (A and D bit usage)
Emulating A/D bits without hardware support
Thrashing: cause, working-set model, PFF
Allocation policies (fixed vs variable, global vs local)
Page daemon and background reclaim

7. Concurrency and IPC

Why IPC needs OS support (memory protection)
UNIX signals: delivery, unreliability, disposition
Pipes vs named pipes (FIFOs)
Shared memory and synchronisation
File descriptors as capabilities
IPC comparison: signals vs pipes vs named pipes

8. I/O subsystem

I/O methods: PIO, interrupt-driven, DMA
Interrupt handling: top half, bottom half, latency, coalescing
Traps as software interrupts
Buffering: single, double, circular
Device drivers: structure, binding, kernel vs user-space
Spooling

9. File systems

File and directory abstractions; path resolution
UNIX inodes: structure, indirect blocks
Disk-access arithmetic (indirection level for a given byte offset)
Hard links vs symbolic links
File-system layout (superblock, inode table, data blocks)
Free-space management (bitmap vs linked list)
LFS: log structure, cleaner, inode map
Defragmentation and the idle process
Journaling vs fsck

Exam technique

Bookwork answers (4 marks): State the definition, give the two representations, make a reasoned choice. Be concise — 3–4 sentences.
Application answers (7–10 marks): Show all working. For scheduling, draw a Gantt chart or table. For paging, show the address decomposition. For page replacement, trace the frame contents step by step.
Extension answers (6–8 marks): These are open-ended — “discuss trade-offs,” “suggest why X might fail.” Structure your answer: state the concern, explain the mechanism, suggest a mitigation. Two well-developed points are better than four superficial ones.

Key formulae to memorise

Formula	Use
$\text{EAT} = (1-p)T_\text{mem} + p \cdot T_\text{page-fault}$	Demand paging EAT
$\text{EAT} = \alpha(T_\text{tlb} + T_\text{mem}) + (1-\alpha)(T_\text{tlb} + kT_\text{mem} + T_\text{mem})$	TLB + multi-level paging
$\text{Page offset bits} = \log_2(\text{page size})$	Address decomposition
$\text{PTEs per page} = \text{Page size} / \text{PTE size}$	Multi-level table arithmetic
$\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n$	SJF burst prediction
$\Delta\text{vruntime} = t \times w_0 / w_i$	CFS proportional allocation

Back to Operating Systems