Skip to content
Jamie Little
Part IA Lent Term

Tripos Worked Solutions: 2019 Paper 2 Question 4

Question: Operating Systems (rmm1002) — 20 marks

(a) OS protection mechanisms [6 marks — BOOKWORK]

Describe the mechanisms by which an OS protects a user process’ use of system resources (CPU, memory, I/O) from interference by other processes. Indicate what special hardware is required.

Answer:

The OS protects resources through three mechanisms, each backed by specific hardware:

CPU protection: The OS uses a hardware timer that generates periodic interrupts. When the timer expires, the CPU vectors to the kernel’s scheduler, which may preempt the running process. Without a timer, a process in an infinite loop would never yield the CPU. The timer is privileged — only the kernel can set it.

Memory protection: The MMU translates every logical address to a physical address. For paging, each PTE contains permission bits (R/W, U/S). If a process attempts an access that violates its permissions, the MMU raises a page fault, and the kernel terminates the process. The hardware required is the MMU itself, plus the page table (or base/limit registers for simpler systems).

I/O protection: I/O instructions are privileged — they can only be executed in kernel mode. A user process that attempts, e.g., IN or OUT on x86 causes a general protection fault. The process must request I/O through a system call, which allows the kernel to validate the request and perform it on the process’s behalf. The hardware required is the dual-mode CPU (mode bit) and the privileged-instruction enforcement mechanism.

(b) IPC comparison [6 marks — APPLICATION]

Why does IPC require special OS support? Compare signals, pipes, and named pipes.

Answer:

IPC requires OS support because memory protection prevents one process from accessing another’s address space. Without kernel mediation, processes have no way to share data.

Signals: Asynchronous notification. A process sends a signal with kill(pid, signum). The signal carries only the signal number — no data payload. Delivery is not guaranteed (signals can be merged if the same signal is pending). Synchronisation is essentially impossible — the sender does not know when or if the signal was delivered. Suitable for simple notification (e.g., “child has terminated”), not for data transfer.

Pipes: Byte-stream IPC between related processes. Created by pipe() and inherited across fork(). Data written to the write end is buffered by the kernel (64 KB default) and read from the read end. read() blocks until data is available; write() blocks when the buffer is full — this provides natural flow control. All data is transferred reliably and in order. The main limitation is that pipes only work between related processes (parent-child, siblings).

Named pipes (FIFOs): Extend pipes to unrelated processes. Created with mkfifo() in the file system — any process can open the FIFO by name. Once opened, a named pipe behaves like an anonymous pipe: byte-stream, reliable, flow-controlled. The file-system name provides a rendezvous point for unrelated processes. Used for simple client-server communication on the same machine.

Comparison: Signals are the weakest — no data, no synchronisation. Pipes and named pipes are roughly equivalent in capability, but pipes require a common ancestor whereas named pipes allow arbitrary processes to communicate by name.

(c) Capability-based file protection [8 marks — EXTENSION]

Discuss trade-offs of checking permissions on every read/write vs at open time. Design a capability system for file protection. Compare with UNIX.

Answer:

Check-on-open vs check-on-every-access:

Checking at open() (UNIX’s choice) is efficient — one permission check establishes access, and the returned file descriptor acts as a capability for subsequent operations. The trade-off is staleness: if the file’s permissions are changed after open(), the process retains access. Checking on every read()/write() would detect permission changes immediately, but (a) it is more expensive (permission check on every operation, not just once), and (b) it introduces a new failure mode — a descriptor that was valid for read() may suddenly become invalid, complicating error handling in every program.

Capability system design:

A capability could be implemented as a cryptographic hash of the file content (or a server-generated token) combined with the permitted operation:

  • capability = H(file_content, operation, random_nonce) for a read capability.
  • capability = H(new_file_content, WRITE, random_nonce) for a write capability. The server returns a new capability for the new content, enabling subsequent reads of the written data.

API:

cap_t cap = open_by_capability(user_read_cap);
// cap validates against the file's current content
write_cap = write(cap, data, len);
// write returns a new capability reflecting the new file state

Comparison with UNIX:

  • Advantage: Capabilities can be passed freely between processes (delegation is natural — Alice gives Bob her read capability). No need for group membership or ACL manipulation. Cross-machine capability passing is possible (if the capability is a token that a remote server can validate).
  • Disadvantage: Revocation is hard. Once Alice gives Bob a capability, taking it back requires either expiring all capabilities for that file (affecting all holders) or maintaining a revocation list. UNIX ACLs support revocation trivially — just chmod the file.
  • Cost: UNIX’s open()-time ACL check plus descriptor-based operations is simpler and typically faster (no cryptographic operations on each read/write). Capabilities require hash computation or token verification.

UNIX’s hybrid — ACLs for access control, descriptors as short-lived capabilities — strikes a pragmatic balance that most capability proposals fail to improve upon for local file-system use.

Back to Operating Systems