Question 5 of 7: File Allocation and the Critical-Section Problem
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
98-COMP A-5 Operating Systems — National Examinations, December 2017. 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.) — CPU scheduling (ch. 5), process synchronization/monitors (ch. 6–7), deadlocks (ch. 8), memory management/paging (ch. 9–10), mass-storage/file-system implementation and disk scheduling (ch. 11–12), real-time systems (ch. 19); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on scheduling, virtual memory and file systems.
Question 5: File Allocation and the Critical-Section Problem (20 marks)
Given. A 120-block file under singly linked allocation (directory holds only a pointer to block 1; each block's "next" pointer is only discoverable by reading that block). Directory operations are free; each read/write of a data block counts as one disk operation; free-space bookkeeping is ignored.
Find. The minimum disk-operation count for cases A–D.
Approach. Because the list is singly linked, reaching block $n$ from the directory's head pointer requires reading every block from 1 through $n$ in order (each block must be read just to learn where the next one is) — there is no way to jump directly to block $n$. The minimum-operations strategy therefore visits all requested block numbers in a single ascending sweep, stopping at the highest block index actually needed.
(A) Read blocks 102, 98, 103. A single ascending sweep from block 1 passes through block 98 (captured), continues to block 102 (captured), and on to block 103 (captured) — reading each block along the way exactly once.
$$\boxed{\text{Ops}_A=\max(102,98,103)=103\ \text{reads}}$$
(B) Exchange contents of blocks 101 and 94. One ascending sweep to block 101 automatically passes through block 94 first, so both contents are captured in $\max(101,94)=101$ reads. The exchange then needs two writes — block 94 is overwritten with the (saved) old content of block 101, and block 101 is overwritten with the (saved) old content of block 94; both physical locations are already known from the sweep, so no extra reads are needed to locate them.
$$\boxed{\text{Ops}_B=101\ \text{reads}+2\ \text{writes}=103}$$
(C) Insert a new block after block 90, copying block 70's content. One ascending sweep to block 90 passes through block 70 (captured as the content to copy) and reaches block 90 (whose "next" pointer — the address of the current block 91 — is captured for reuse), using $\max(90,70)=90$ reads. Two writes finish the job: write the new block (content = old block 70's data, next-pointer = the old block 91 address just captured from block 90) to a free block, and rewrite block 90's next-pointer to point at the new block.
$$\boxed{\text{Ops}_C=90\ \text{reads}+2\ \text{writes}=92}$$
(D) Delete block 65. A sweep to block 65 is required because block 65's own next-pointer (the address of block 66) must be read before block 65 can be unlinked — this costs 65 reads (blocks 1 through 65, the last read yielding block 65's next-pointer). One write updates block 64's next-pointer to skip directly to block 66 (that address having just been read from block 65). Block 65 itself is simply returned to the free list (no data need be overwritten, and free-space bookkeeping is excluded from the count per the question).
$$\boxed{\text{Ops}_D=65\ \text{reads}+1\ \text{write}=66}$$
Final Results – Question 5(a)
Case
Minimum disk operations
(A) Read blocks 102, 98, 103
103
(B) Exchange blocks 101 ↔ 94
103 (101 reads + 2 writes)
(C) Insert after block 90, copy of block 70
92 (90 reads + 2 writes)
(D) Delete block 65
66 (65 reads + 1 write)
(b) The mutual exclusion requirement. Mutual exclusion is the requirement that if one process is currently executing in its critical section, no other process may be executing in its own critical section (for the same shared resource) at the same time. It is the core correctness property any critical-section solution must guarantee: without it, two processes can interleave their reads/writes to shared data and produce a corrupted or inconsistent result (a race condition), regardless of how the other two classical requirements (progress, bounded waiting) are handled. A correct solution enforces this unconditionally — it must hold for every possible interleaving and every relative process speed, not merely "most of the time."
(c) Bounded waiting under semaphore-controlled entry. Whether bounded waiting holds depends entirely on how the semaphore's blocked-process queue is managed, not on the semaphore primitive itself. A semaphore implemented with a strict FIFO waiting queue (as most textbook/OS implementations of wait()/signal() specify) does satisfy bounded waiting: a process that is denied entry joins the back of the queue, and every signal() wakes the process at the front, so no blocked process can be passed over more than $n-1$ times (once by each of the other $n-1$ processes) before it is admitted. However, a semaphore implementation that wakes an arbitrary (e.g. LIFO or unspecified-order) waiting process on `signal()` does not guarantee bounded waiting — a particular blocked process could in principle be starved indefinitely if the scheduler/semaphore repeatedly favours other waiters. So the honest answer is conditional: yes, provided the semaphore's internal queue is FIFO; the semaphore construct by itself, with an unspecified queue discipline, does not automatically guarantee it.
