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

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

Question 3: Access matrix and UNIX permissions

(a) Access matrix representations [4 marks — BOOKWORK]

State the two common representations of the access matrix, and explain which you would use for a modern personal laptop.

Answer: The two representations are:

Access Control Lists (ACLs): store the matrix by column — each object carries a list of (subject, rights) pairs. Checking access involves scanning the object’s ACL. Revocation is easy (modify the ACL); delegation is harder (the object owner must update the ACL).
Capabilities: store the matrix by row — each subject holds a set of unforgeable tokens (capabilities) granting specific rights to specific objects. Access is proven by presenting the capability. Delegation is easy (pass the capability); revocation is hard (all copies must be tracked and invalidated).

Choice for a personal laptop: ACLs are more appropriate. A personal laptop has a small number of users (often just one or a handful) but a very large number of files (millions). With ACLs, each file has an attached list of which users/groups can access it. With capabilities, each user would need to carry a capability for every file they can access — millions of capabilities per user — which is impractical. On a laptop, the user simply belongs to a small number of groups, and files grant access to those groups. This is exactly what UNIX file permissions provide (a simplified ACL with owner/group/other).

(b) Access matrix construction [5 marks — APPLICATION]

Construct the access matrix for four peripherals (printer, hard disk, web camera, speaker) and four domains (root, alice, bob, chris) given the policy statements.

Answer:

Domain	Printer	Hard disk	Web camera	Speaker
root	read/write	read/write	read/write	read/write
alice	read/write	—	read	write
bob	read	read	read	write
chris	—	—	—	write

Reasoning:

Root: in any UNIX-derived system, root has all permissions automatically (UID 0 bypasses permission checks). Losing a mark for not granting root full access to all objects.
Printer: alice → full use = read/write. bob → check status only = read (can read status, not submit jobs). chris → no access.
Hard disk (backups): root → create backups = read/write. bob → recover files = read (can restore but not create backups). alice and chris → no policy statement = no access.
Web camera: alice and bob → full video-conferencing = read (receive video from camera). chris → music only, no video = no access. Note: “write” on a camera makes no physical sense — the camera provides video; the system reads from it. Marks lost for inventing non-standard operations.
Speaker: alice, bob, chris → audio output = write (send sound to speaker). “Read” on a speaker makes no physical sense — marks lost for assigning it.

(c) UNIX permission patterns [7 marks — APPLICATION]

Configure users, groups, and file permissions:

(i) File readable and writable by root and alice, readable by bob:

Create group gbob = {bob}.
File ArwBr owned by alice, group gbob, permissions u=rw, g=r, o= → 640.
Or owned by bob, group galice = {alice}, u=r, g=rw, o= → 460.
Root bypasses permissions (UID 0). Alice gets rw via ownership (or group in the alternative). Bob gets r via group.

(ii) File readable and writable by root and bob, readable by any user:

File owned by bob, any group, permissions u=rw, g=r, o=r → 644.
Or owned by anyone, group gbob, permissions g=rw, o=r → 064.
Root bypasses. Bob gets rw via ownership (or group). Any user gets r via the other bits.

(iii) File owned by alice but readable and writable only by root:

File owned by alice, any group, permissions 000.
Root bypasses and can read/write. Alice owns it but permissions deny her — she cannot read or write. However, since alice is the owner, she can use chmod to change the permissions back (ownership grants the power to change permissions).

(d) Changing root’s UID [4 marks — EXTENSION]

Effect of changing root’s UID from 0 to 1000:

The kernel identifies users by numeric UID, not by name. The name “root” is just an entry in /etc/passwd; what matters for privilege is UID 0. If /etc/passwd is changed so that “root” maps to UID 1000, then:

The access matrix does not change — UID 0 still has all permissions. But UID 0 is now unnamed in /etc/passwd.
When someone logs in as “root”, they get UID 1000, which has no special privileges. They become a normal user.
Administration becomes extremely difficult: no one can log in as UID 0 (the privilege-granting identity) through normal means. Commands like su (which look up UID by name) would give UID 1000, not UID 0.
Recovery requires booting into single-user mode (where the kernel starts a root shell with UID 0 regardless of /etc/passwd contents) or using sudo (which checks /etc/sudoers, not the passwd mapping).

The key insight: username ≠ UID. The privilege is tied to the number, not the string.

Question 4: 5-Level paging and TLB

(a) Addressable memory [2 marks]

57-bit virtual addressing: $2^{57}$ bytes = $2^{7} \times 2^{50} = 128 \times 2^{50}$ = 128 PB (petabytes, or pebibytes — both accepted).

(b) Address translation walk [9 marks]

Virtual address 0x00c0_ffee_ba5e_f00d, 5-level page table, 4 KB pages (12-bit offset), 64-bit PTEs, 512 PTEs per page (9 bits per level).

Decomposition:

The 57-bit address splits into five 9-bit fields and a 12-bit offset:

$\text{Level 5: bits 56–48} \mid \text{L4: 47–39} \mid \text{L3: 38–30} \mid \text{L2: 29–21} \mid \text{L1: 20–12} \mid \text{Offset: 11–0}$

Walk:

PTBR (CR3) points to the Level-5 page table (one page, 4 KB, 512 entries of 8 bytes).
Level-5 index selects the PTE containing the base of the Level-4 page table.
Level-4 index selects the PTE containing the base of the Level-3 page table.
Level-3 index selects the PTE containing the base of the Level-2 page table.
Level-2 index selects the PTE containing the base of the Level-1 page table.
Level-1 index selects the PTE containing the physical frame number.
Offset (12 bits) is added to the frame base to produce the physical address.

Table sizes:

Level	Entries	Size	Cumulative
L5	$512^1 = 512$	4 KB	4 KB
L4	$512^2$	2 MB	~2 MB
L3	$512^3$	1 GB	~1 GB
L2	$512^4$	512 GB	~512 GB
L1	$512^5$	256 TB	~256 TB

The total page-table size, if fully populated, is approximately 256 TB. In practice it is sparsely populated; only the portions of the address space actually used have backing physical pages for their page-table levels.

(c) TLB and EAT [4 marks]

$T_\text{mem} = 40 \text{ ns}$ , $T_\text{tlb} = 5 \text{ ns}$ , $\alpha = 0.99$ , 5-level PT ( $k = 5$ ).

$\text{EAT} = \alpha(T_\text{tlb} + T_\text{mem}) + (1 - \alpha)(T_\text{tlb} + k \cdot T_\text{mem} + T_\text{mem})$ $= 0.99 \times (5 + 40) + 0.01 \times (5 + 5 \times 40 + 40)$ $= 0.99 \times 45 + 0.01 \times 245$ $= 44.55 + 2.45 = 47.0 \text{ ns}$

Mark scheme: 1 mark for correct split (hit/miss), 1 mark for TLB lookup in both cases, 1 mark for $5 \times 40$ walk latency, 1 mark for final read.

(d) Binary trie vs page table [5 marks]

Would a binary trie perform better?

No, it would not perform better. Reasons (2 marks each, up to 5):

The page table is already a trie: the 5-level page table is an N-ary trie with $N = 512$ (the fanout at each level) and depth limited to 5. A binary trie would have $N = 2$ and depth up to 57, requiring many more pointer dereferences to navigate (bitwise operations, poor cache efficiency).
Hardware alignment: the page-table structure is designed to fit exactly into page-sized chunks (4 KB), creating locality for CPU caches. A binary-trie node is not naturally page-aligned and would cause more cache misses.
Hardware support: the 5-level page table is supported directly by the MMU and the TLB. A binary trie would need to be walked in software on every TLB miss, which is far slower than the hardware page-table walker.
TLB compatibility: the TLB caches the final translation; the structure of the walk is immaterial once cached. The page-table structure is optimised for the hardware walker; a binary trie would give no benefit for cached translations.