25-Comp-A5 Operating Systems · December 2015

Question 4 of 7: Linked Allocation and Scheduler Design

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Question 4: Linked Allocation and Scheduler Design (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

(a) Given. A 150-block file (blocks numbered 1–150), linked allocation (each block holds its data plus a pointer to the next block in the chain) with only the head pointer kept in the (in-memory) directory — so reaching logical block $k$ requires sequentially reading blocks $1,2,\dots,k$ (k reads), since a singly-linked chain offers no random access. The file's length (150) is known to the system, so the end of the chain never needs to be read just to confirm it has no successor. Find. The minimum disk operations for cases (A)–(D). Approach. For each case, traverse only as far as the farthest block actually needed (which subsumes reading every closer block "for free" along the way), then add the writes each operation actually requires.

1. (A) Read blocks 100, 98, 102. A single sequential traversal from block 1 to block 102 passes through block 98 (position 98) and block 100 (position 100) on the way, so all three requested contents are captured in one pass. No writes. $$\boxed{\text{Ops}_A = \max(100,98,102) = 102\ \text{reads}}$$
2. (B) Exchange contents of block 110 and block 95. "Exchange contents" swaps only the data payload of the two blocks — the chain's next-pointers, and hence every block's logical position, are untouched. Traversing from block 1 to block 110 passes block 95 en route, giving both blocks' current data and disk locations in one pass (110 reads); then 2 writes place each block's new (swapped) content back at its own already-known location. $$\boxed{\text{Ops}_B = \max(110,95) + 2\ \text{writes} = 112}$$
3. (C) Insert 2 new blocks after block 80, contents copied from block 100. Traversing from block 1 to block 100 passes block 80 en route, so the same 100-read pass both reads block 100's content (to copy) AND locates block 80 (whose next-pointer must change). Three writes follow: the two new blocks (each write stores both a copy of block 100's data and a next-pointer — the first new block points to the second, the second points to block 80's OLD next block) and one write to block 80 itself (next-pointer updated to point to the first new block). Allocating the two new physical blocks is free per the "ignore free-space operations" assumption. $$\boxed{\text{Ops}_C = 100\ \text{reads} + 3\ \text{writes} = 103}$$
4. (D) Delete blocks 75 and 150. Deleting block 75 (mid-chain) needs its predecessor, block 74, to have its next-pointer rewritten to skip straight to block 76 — both block 74's location and block 75's own next-pointer (=block 76's address) are obtained while traversing past them. Deleting block 150, the LAST block, needs only its predecessor block 149's next-pointer set to NULL; because the file length (150) is already known, block 150 itself never needs to be read to discover it has no successor. Since $74 < 75 < 149$, a single traversal from block 1 to block 149 (the farthest point needed) sweeps up everything: 149 reads. Two writes follow: block 74's next → block 76's address, and block 149's next → NULL. $$\boxed{\text{Ops}_D = 149\ \text{reads} + 2\ \text{writes} = 151}$$

(b) This scheduler has several compounding design defects:

1. Positional (top-of-table) bias on ties. Scanning strictly from the top and taking the FIRST minimum-Itime match means that whenever two READY processes tie on Itime, the one occupying an earlier table slot always wins — an arbitrary advantage tied to table position (roughly, which PID/slot a process happened to be assigned), not to any real scheduling merit.
2. New arrivals always start at the global minimum (Itime = 0), backwards from proper aging. Since the scheduler always dispatches the smallest Itime, and every newly-created process starts at exactly 0, a brand-new process immediately outranks every process that has been in the system for any positive amount of time (their Itime has already been incremented at least once). This is the OPPOSITE of what an aging mechanism should do — aging is meant to raise the priority of processes that have waited the longest, not reset every newcomer to a position of maximum priority. The result is indefinite postponement (starvation) of established processes under a steady stream of new arrivals.
3. The periodic ×M (M>1) scaling entrenches the bug instead of fixing it. Multiplying every existing process's Itime by a factor greater than 1 every 100T units makes ALREADY-large Itime values grow even larger (compounding upward), which further worsens old processes' standing rather than boosting them — a genuine anti-starvation aging scheme should instead DECREASE a waiting process's priority number over time so it eventually wins the comparison.

Would M<1 help? Modeling Itime's evolution as the recurrence $I_{n}=M\,(I_{n-1}+100)$ (100 unit increments of +1 per 100T-period, then the multiply), a value $0<M<1$ converges to a finite steady state rather than diverging:

$M<1$ does bound Itime (prevents unbounded growth/overflow) and does slow the entrenchment described in defect 3. But it does NOT fix the fundamental flaw: $I^{*}=100M/(1-M)$ is strictly positive for every $M$ in $(0,1)$, and a brand-new process still starts at exactly Itime$=0$ — strictly below any established process's steady-state value. New arrivals therefore still cut in front of every already-running process, no matter how small $M$ is made. $M<1$ is a partial mitigation (numerical stability, slower divergence) but not a correct fix; a genuine fix requires Itime to actually DECREASE the longer a process has waited (e.g. a true aging decrement per unit time waited), not merely be periodically rescaled.