Question 6 of 7: File Systems — Access Control and Allocation Performance
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
17-COMP A-5 Operating Systems — National Examinations, May 2018. 3 hours, closed book (one approved pocket calculator only). Candidates were instructed to answer any five of the seven questions; all seven are answered below as a complete study resource.
Reference texts: Silberschatz, Galvin & Gagne, Operating System Concepts (10th ed.) — process synchronization/monitors (ch. 6–7), CPU scheduling (ch. 5), deadlocks (ch. 8), memory management/paging (ch. 9–10), mass-storage/file-system implementation and disk scheduling (ch. 11–12), protection (ch. 14); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on synchronization, scheduling, memory and file systems.
Question 6: File Systems — Access Control and Allocation Performance (20 marks)
(a) Role of access control in multi-user file systems. When a file system is shared by many users, the operating system must decide, for every open/read/write/execute/delete request, whether the requesting identity is permitted — without this, any user could read another's private files or corrupt shared/system files. Access control provides confidentiality (only authorized users can read sensitive data), integrity (only authorized users/processes can modify a file, preventing accidental or malicious corruption), and controlled sharing (a project team can share a common file while excluding everyone else) all through the same underlying mechanism: an authorization check performed by the OS at every access, using an identity (user/group) associated with the requester and a policy (permissions/ACL) associated with the file.
(b) A concrete access-control technique: POSIX owner/group/other permission bits. Each file/directory carries an owner, a group, and three permission triples (read/write/execute) — one for the owner, one for the owning group, one for everyone else. On every access the OS compares the requester's user ID against the file's owner ID and group membership and applies the first matching triple: owner permissions if the requester is the owner, group permissions if the requester is in the owning group (but not the owner), otherwise the "other" permissions. Example: a shared project source file owned by a lead developer, group-owned by the project team, might be set rw-r--r-- — the lead can read/write it, any teammate can read but not modify it, and non-team users cannot access it at all. This is compact (3 bits × 3 categories stored directly in the inode) but coarse — it cannot express "grant write access to exactly these two additional users" without adding them to a group, which is precisely the gap that finer-grained access control lists (ACLs) are designed to close.
Given (c). A 150-block file (blocks numbered 1–150); directory held in main memory (directory lookups are free). Compare contiguous vs. singly-linked allocation for cases (A) read blocks 131 and 95, (B) exchange blocks 149 and 90, (C) delete block 95. Directory/free-space bookkeeping is excluded from the count; no room to grow at the start, room at the end.
Find. Minimum disk operations $M$ for each case under each technique, and which technique has the lower average $M$ over A–C.
Approach. Contiguous allocation lets the system compute any block's physical address directly from the in-memory directory (start $+$ offset), so any single block access costs exactly 1 operation — except deleting a block from the middle, which forces every following block to shift one position to keep the file a single contiguous extent (1 read $+$ 1 write per shifted block). Linked allocation (singly linked list, head pointer only) can only reach the $k$-th block of the file by reading blocks $1,\dots,k$ in sequence, since each block's link is only discoverable by reading that block.
(A) Read blocks 131 and 95. Contiguous: both addresses are computed directly, 1 read each. Linked: a single ascending sweep to $\max(131,95)=131$ captures both.
$$\boxed{M_{\text{contig}}(A)=2\ \text{reads}\qquad M_{\text{linked}}(A)=131\ \text{reads}}$$
(B) Exchange blocks 149 and 90. Contiguous: 2 direct reads (fetch old contents) $+$ 2 direct writes (swap) $=4$. Linked: one sweep to $\max(149,90)=149$ reads (both contents captured en route) $+$ 2 writes (both physical locations already known from the sweep).
$$\boxed{M_{\text{contig}}(B)=4\qquad M_{\text{linked}}(B)=149+2=151}$$
(C) Delete block 95. Contiguous: blocks 96–150 (150$-$95$=$55 blocks) must each shift one position left to close the gap and stay contiguous, at 1 read $+$ 1 write per block. Linked: a sweep to block 95 (95 reads, the last giving block 95's own next-pointer $=$ address of block 96) $+$ 1 write updating block 94's next-pointer straight to block 96 — nothing after block 95 needs to move.
$$\boxed{M_{\text{contig}}(C)=55\times2=110\qquad M_{\text{linked}}(C)=95+1=96}$$
(i) M for each case, both techniques — summary. Contiguous: $M(A)=2$, $M(B)=4$, $M(C)=110$. Linked: $M(A)=131$, $M(B)=151$, $M(C)=96$ (each derived in the steps above).
(ii) Average $M$ over A–C, and which technique wins.
$$\overline{M}_{\text{contig}}=\dfrac{2+4+110}{3}=\dfrac{116}{3}\approx38.7\qquad \overline{M}_{\text{linked}}=\dfrac{131+151+96}{3}=\dfrac{378}{3}=126$$
$$\boxed{\text{Contiguous has the lower average }M\ (\approx38.7\text{ vs. }126)}$$
Contiguous wins on average despite losing badly on the single expensive case (C, the shift-heavy deletion), because its cheap $O(1)$ direct access dominates the other two cases, whereas linked allocation pays an $O(k)$ sequential-scan cost on every case, including the two that don't need any element shifting at all.
