Tripos Worked Solutions: 2024 Paper 2 Questions 3 & 4 | Operating Systems

Question: Operating Systems (rmm1002) — 40 marks (Q3: 20, Q4: 20)

Question 3: Context switches and scheduling

(a) Context-switch state [4 marks — BOOKWORK]

What state must be included in a context switch?

Answer: The state that must be saved and restored includes:

General-purpose registers (all user-visible registers — rax, rbx, etc. — and the program counter, stack pointer, and frame pointer).
Memory-management state (CR3 / page-table pointer — unless PCIDs allow retaining some TLB entries, the TLB must be flushed or selectively invalidated).
The kernel stack pointer (each process has its own kernel stack; switching processes means switching the kernel stack the CPU uses while in kernel mode).

State that must be flushed from hardware before the new process runs: the TLB entries for the old process’s address space must be invalidated so the new process cannot read the old process’s memory. On hardware without PCIDs (process-context identifiers), this is done by reloading CR3, which flushes all TLB entries except those marked global. With PCIDs, the flush is selective.

(b) Scheduling under RR and CFS [10 marks — APPLICATION]

Five CPU-bound processes arrive simultaneously with CPU demands: 10, 20, 30, 40, 50 ms.

(i) RR with q = 5 ms:

At q = 5 ms, each process gets 5 ms before being preempted. Trace:

Time 0–5: P1 (5/10), queue: P2,P3,P4,P5,P1(5)
Time 5–10: P2 (5/20), queue: P3,P4,P5,P1(5),P2(15)
…continuing this pattern until all finish.

Processes complete their demands after exhausting their quantum count:

P1 needs 2 quanta (completes at t = (order…) 5×5 = 25? Actually, needs careful trace).

The trace produces 5 (initial) + 1 (P1 finishes) + 1 (P2 finishes) … = approximately 14 context switches. For batch workloads, a larger quantum would be preferable (fewer switches = more throughput). For interactive workloads, 5 ms provides good response time (max wait ~20 ms before a process gets CPU).

The detailed Gantt chart is left as an exercise — the key is understanding that RR with small quantum gives good response but many switches, and CFS gives proportional-share fairness.

(ii) RR with q = 20 ms:

Larger quantum = fewer switches. P1 gets 10 ms of its 20 ms quantum (finishes early). P2 gets 20 ms, etc. Good for batch; poor response time for interactive (a process may wait up to 80 ms before its first 20 ms slice).

(iii) CFS with target latency 60 ms, min granularity 2 ms:

All processes have equal weight (nice 0, weight 1024). Target latency 60 ms / 5 processes = 12 ms per process in the first round. Since min granularity is 2 ms and 12 ms > 2 ms, each gets 12 ms.

Round 1: P1 10/10 → finishes (2 ms unused redistributed). P2 12/20. P3 12/30. P4 12/40. P5 12/50.
Round 2: P2 8/20 → finishes. P3 15/30. P4 15/40. P5 15/50.
Round 3: P3 3/30 → finishes. P4 13/40 → finishes. P5 20/50 → 30/50.
Round 4: P5 20/50 → finishes.

Context switches: ~9. This is balanced between batch and interactive.

(iv) CFS with target latency 20 ms, min granularity 5 ms:

Target latency 20 ms / 5 processes = 4 ms per process. But min granularity is 5 ms, which is larger than 4 ms. So each process gets the minimum granularity: 5 ms. The effective latency becomes 5 ms × number of processes, roughly. More switches, better interactive response, worse batch throughput.

Preference: For batch workloads, larger quantum/CFS with large target latency (fewer switches) is better. For interactive workloads, smaller quantum/CFS with small target latency (more switches, better response) is better.

(c) Cloud-provider assumptions [6 marks — EXTENSION]

Discuss why the cloud provider’s assumptions may fail:

Predictable behaviour: Small functions may have unpredictable tail latencies due to cold starts (first invocation pays the cost of loading the runtime, establishing connections). Dense packing increases resource contention (CPU cache, memory bandwidth, last-level cache), making individual function latencies noisy rather than predictable.
Dense packing: Small functions increase context-switch frequency (more processes per core, each making brief runs), increasing scheduler overhead. Memory pressure from many small processes may trigger the OOM killer or excessive paging, defeating the denser packing. The provider could use cgroups to enforce per-function memory limits and isolate resources, and use idle-process or background threads for proactive reclaim.

Question 4: Memory management

(a) Address binding [3 marks]

At compile time: the compiler emits absolute physical addresses. The programmer or compiler must know the load address. The programme can only run at that address. No hardware or software relocation is needed, but flexibility is zero.

At load time: the compiler emits relocatable code. The loader adds the base load address to all addresses. No special hardware needed — the loader (software) patches the binary. Once bound, the programme cannot move.

During execution: the MMU translates logical to physical addresses on every access (using a page table or base/limit registers). Hardware MMU required. The programme can be moved transparently by changing the page table, and the same logical address can map to different physical frames over time (swapping, shared libraries).

(b) Page replacement on 1 2 3 2 4 3 5 1 3 2 3 4 [9 marks]

Worked through in detail in the page-replacement worked examples note. Summary:

OPT: 8 faults
LRU: 8 faults
FIFO: 9 faults

(c) Belady’s anomaly [4 marks]

Definition: Belady’s anomaly is the phenomenon where increasing the number of available frames increases the number of page faults for a given reference string. It is counter-intuitive — more memory should not worsen performance.

Why OPT and LRU cannot exhibit it: Both are stack algorithms — the set of pages in memory with $n$ frames is always a subset of the set with $n+1$ frames. For LRU: the $n$ -frame set is the $n$ most-recently-used pages; the $n+1$ -frame set is the $n+1$ most-recently-used, which strictly contains the $n$ set. The subset property implies that a page fault with $n+1$ frames implies one with $n$ frames, so faults are monotonic (non-increasing) with frame count.

Why FIFO can: FIFO’s eviction depends on load order, not recency. Changing the frame count changes which pages are evicted earlier or later, which can cause pages that would have been resident under $n$ frames to be prematurely evicted under $n+1$ frames, causing additional faults. The resident set under $n$ frames is not necessarily a subset of the set under $n+1$ frames.

(d) Emulating reference and dirty bits [4 marks]

Without hardware A (Accessed) and D (Dirty) bits, the OS can emulate them:

Reference bit (A): Initially mark all pages as not-present (P=0) in the page table, even though they are in memory. On the first access, the MMU raises a page fault. The kernel’s page-fault handler recognises this as an “artificial” fault (the page is in memory, just marked not-present), records “this page was referenced” (setting a software A bit), sets P=1, and resumes. Periodically, the kernel resets all pages to not-present. Between sweeps, each accessed page pays exactly one extra page fault.

Dirty bit (D): Initially mark all pages as read-only (R/W=0), even though writes should be permitted. On the first write, the MMU raises a protection fault. The kernel records “this page is dirty” (software D bit), sets R/W=1, and resumes. The overhead is one extra fault per written page between sweeps.

This technique works but adds page-fault latency to the first access and first write after each sweep, turning a lightweight hardware operation (bit test/set) into a heavyweight software operation (trap, handler execution, return).