Tripos Worked Solutions: 2023 Paper 2 Question 3 | Operating Systems

Question: Operating Systems (rmm1002) — 20 marks

(a) Interrupts and traps [4 marks — BOOKWORK]

(i) How are interrupts handled in a modern UNIX-like OS?

Answer: Interrupts are handled by vectoring into a table of pointers (the IDT — Interrupt Descriptor Table) to Interrupt Service Routines. The CPU saves the address of the interrupted instruction and disables interrupts. The ISR does minimal work — acknowledges the interrupt, copies urgent data from device registers — and then schedules deferred work (the bottom half) to complete processing later in a safer context. Interrupts remain disabled for the duration of the ISR unless the ISR explicitly re-enables them. Keeping the ISR short is critical; long ISRs cause lost interrupts and increase interrupt latency for other devices.

(ii) Why are traps sometimes referred to as software interrupts?

Answer: Traps are handled in essentially the same way as interrupts: the caller puts values in registers (system-call number, arguments), the CPU vectors to the relevant kernel entry point through the IDT or a model-specific register (syscall/sysenter), and the kernel dispatches to the appropriate handler. Both are mechanisms to invoke kernel code in response to an event; the distinction is the source — hardware (interrupt) vs software instruction (trap). The terminology “software interrupt” reflects this shared mechanism.

(b) Effective Access Time with paging [12 marks — APPLICATION]

System: memory access time = 80 ns, page-fault service time = 8 ms (assuming free frame available).

(i) Maximum permitted page-fault rate for EAT ≤ 100 ns.

$\text{EAT} = (1 - p) \times 80 + p \times 8{,}000{,}000 \le 100$

$80 + 7{,}999{,}920 \cdot p \le 100$

$p \le \frac{20}{7{,}999{,}920} = \frac{1}{399{,}996}$

The maximum page-fault rate is approximately $2.5 \times 10^{-6}$ — one page fault per ~400,000 memory accesses.

(ii) EAT when the fault rate is double the maximum:

$p = \frac{1}{199{,}998}$

$\text{EAT} = \left(1 - \frac{1}{199{,}998}\right) \times 80 + \frac{1}{199{,}998} \times 8{,}000{,}000$

$= \frac{199{,}997 \times 80 + 8{,}000{,}000}{199{,}998} = \frac{15{,}999{,}760 + 8{,}000{,}000}{199{,}998}$

$= \frac{23{,}999{,}760}{199{,}998} \approx 120 \text{ ns}$

The effective access time rises to approximately 120 ns.

(iii) EAT when half of page faults occur with no free frames available:

When no free frame is available, the OS must first write a dirty page to disk before reading the faulting page, approximately doubling the service time for those faults. The average service time becomes:

$T_{\text{avg}} = 0.5 \times 8{,}000 + 0.5 \times 16{,}000 = 12{,}000 \text{ ns}$

Wait — careful with units. 8 ms = 8,000,000 ns. Double is 16,000,000. Average: $0.5 \times 8{,}000{,}000 + 0.5 \times 16{,}000{,}000 = 12{,}000{,}000 \text{ ns}$ .

$\text{EAT} = \left(1 - \frac{1}{199{,}998}\right) \times 80 + \frac{1}{199{,}998} \times 12{,}000{,}000$

$= \frac{199{,}997 \times 80 + 12{,}000{,}000}{199{,}998} = \frac{15{,}999{,}760 + 12{,}000{,}000}{199{,}998}$

$= \frac{27{,}999{,}760}{199{,}998} \approx 140 \text{ ns}$

The EAT rises further to approximately 140 ns.

(c) Swap-two-frames proposal [4 marks — EXTENSION]

An engineer proposes swapping out two frames instead of one whenever eviction is needed, to ensure a free frame is always available. State and discuss two system-wide performance implications.

Answer:

Increased disk activity: Swapping out two frames requires writing two pages to disk instead of one, doubling the write I/O per eviction event. However, if one of those two pages would have been evicted soon anyway, the extra write may be productive (pre-emptive eviction reducing future synchronous I/O). The net effect on total I/O depends on how well the algorithm predicts future eviction candidates.
Improved page-fault handling latency (for some faults): Since at least one free frame is always available, page faults that occur soon after the double-eviction never need to wait for a synchronous disk write — the free frame is already available, and only the read is needed. This makes those page-faults faster (read-only instead of write+read). However, against this must be weighed the increased total I/O from more aggressive eviction.

Other valid points: better locality (two adjacent pages swapped together may have correlated access patterns); greater memory pressure (the process loses an extra frame that it might have needed soon, causing an additional page fault later); potential for positive feedback (if the extra eviction causes extra faults, more frames are evicted, worsening the problem).