25-Comp-A5 Operating Systems · May 2015

Question 5 of 7: Real-Time Systems; Disk-Head Scheduling; Address Binding

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

Question 5: Real-Time Systems; Disk-Head Scheduling; Address Binding (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) Real-time systems and preemptive scheduling

A real-time system is one whose correctness depends not only on producing the logically correct result but also on producing it by a specific deadline — a late result is treated as a failure (in a hard real-time system, a catastrophic one; in a soft real-time system, a degradation), not merely an inconvenience. Preemptive scheduling is important because a real-time workload typically mixes tasks of different urgency, and a newly arrived (or newly runnable) high-urgency task may need to seize the CPU immediately to have any chance of meeting its own deadline. Without preemption, a long-running lower-priority task already on the CPU could hold it past the point where the urgent task's deadline has already passed — an unbounded, unpredictable delay that a real-time system cannot tolerate. Preemptive scheduling bounds this delay to (at most) some small, analyzable amount, which is what makes deadline guarantees possible to reason about and verify in advance, rather than merely hoped for.

Given (b). 120 tracks, numbered 0–119. The head has just finished a request at track 50 and is now at track 54 — i.e., travelling in the direction of increasing track number. Pending FIFO queue: 39, 68, 95. No further arrivals during service.

Find. Total head movement under (i) SSTF and (ii) LOOK, and (iii) the service order that minimizes total head movement.

Approach. SSTF always jumps to whichever pending request is currently nearest the head; LOOK continues in the head's current direction, servicing every request it passes, then reverses at the last request in that direction (never travelling all the way to the physical disk boundary, unlike SCAN); the true minimum-movement order is found by checking every possible visiting order of the three requests (a small enough set to enumerate exhaustively) and is not guaranteed to match either heuristic.

1. (i) SSTF. From 54, distances to {39,68,95} are 15, 14, 41 — nearest is 68, move there (14). From 68, distances to {39,95} are 29, 27 — nearest is 95, move there (27). From 95, only 39 remains (56). $$\boxed{\text{Total SSTF movement} = 14+27+56 = 97\ \text{tracks}}$$
2. (ii) LOOK. The head is moving upward (50→54), so LOOK continues upward, servicing 68 then 95 (both $\ge54$, in increasing order) — net upward travel is simply $95-54=41$ tracks, since the head passes through 68 on the way. LOOK then reverses (no request remains above 95, so — unlike SCAN — it does not continue on to track 119) and travels down to the one remaining request, 39: a further $95-39=56$ tracks. $$\boxed{\text{Total LOOK movement} = 41+56 = 97\ \text{tracks}}$$ (This particular request pattern happens to make SSTF and LOOK produce the identical service order, 68, 95, 39, and hence the identical total — that is a coincidence of this data set, not a general property of the two algorithms.)
3. (iii) Minimum-movement order. With only three pending requests it is cheapest to check every ordering directly (a 1-D "visit all points, minimize total travel, no return to start" problem) rather than trust either heuristic. The general rule for such a problem is: go first to the farthest request in whichever direction gives the smaller total, sweeping up every request passed along the way, then reverse for the remaining side. Here the head at 54 has one request below (39) and two above (68, 95); comparing the two possible sweep directions: $$\text{Up-first (as SSTF/LOOK did): } (95-54)+(95-39) = 41+56 = 97$$ $$\text{Down-first: } (54-39)+(95-39) = 15+56 = 71$$ Going down to the single nearby request 39 first, then reversing and sweeping all the way up through 68 to 95, costs only 71 tracks — substantially less than either heuristic's 97, because both SSTF and LOOK are locally greedy (they take the closest gain right now) and neither looks ahead to see that briefly moving toward the lone isolated request pays for itself. $$\boxed{\text{Optimal order: } 39,\ 68,\ 95 \quad(\text{total } = 71\ \text{tracks})}$$

(c) Load-time binding translates every logical (relative) address in a program to an absolute physical address once, at the moment the program is loaded into memory, and bakes those physical addresses directly into the running code/data references; the program must then remain at exactly that memory location for its entire execution, because nothing recomputes the mapping afterward — if it needs to be relocated, the whole program must be reloaded and re-bound. Execution-time (run-time) binding defers the logical-to-physical translation until each individual memory reference actually occurs during execution, using hardware support (typically a base/relocation register or a full MMU) that adds a base offset to every logical address on the fly. This makes the process freely relocatable during its lifetime — it can be swapped out and reloaded at a different physical location, or moved by a compacting memory manager — because only the one hardware register needs to change, not every address reference inside the program.