Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
98-COMP A-5 Operating Systems — National Examinations, May 2013. 3 hours, closed book, 100 marks. 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.) — scheduling (ch. 5), process synchronization/monitors (ch. 6–7), deadlocks (ch. 8), memory management/paging (ch. 9–10), file systems and disk scheduling (ch. 11–12); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on scheduling and file systems.
Given. Five processes with the arrival and execution (burst) times below; a single CPU; no I/O; each process runs to completion once given the CPU (except where explicitly noted for HRRN's preemption status, which is non-preemptive).
Given data
Process
Arrival time (s)
Execution (burst) time (s)
P1
0
3
P2
12
6
P3
14
4
P4
16
5
P5
18
2
Find. The mean turnaround time (completion time − arrival time, averaged over the five processes) under FCFS, under the mean-turnaround-optimal non-preemptive policy, and under HRRN.
Approach. Build the run order each policy produces (respecting arrival times — the CPU idles if no process has yet arrived), read off each process's finish time, then average the five turnaround times.
Fig. Q1(a)-i — FCFS Gantt chart. The CPU is idle from t=3 to t=12 because P1 finishes long before P2 arrives.
(i) FCFS. Processes run strictly in arrival order. P1 runs 0–3 (arrives with an empty system, no wait). The CPU then sits idle from t=3 until P2 arrives at t=12 — FCFS cannot start a not-yet-arrived process early. P2 runs 12–18. By t=18, P3 (arrived 14) and P4 (arrived 16) are both waiting; FCFS runs P3 next: 18–22, then P4: 22–27, then P5 (arrived 18, waited the whole time): 27–29.
Turnaround = finish − arrival for each process:
$$TT_{P1}=3-0=3,\quad TT_{P2}=18-12=6,\quad TT_{P3}=22-14=8,\quad TT_{P4}=27-16=11,\quad TT_{P5}=29-18=11$$
$$\boxed{\overline{TT}_{FCFS} = \dfrac{3+6+8+11+11}{5} = \dfrac{39}{5} = 7.8\ \text{s}}$$
(ii) Optimal non-preemptive policy. With no preemption, the schedule that minimizes mean turnaround runs, at every point the CPU becomes free, the shortest-burst job among those that have already arrived (a greedy exchange argument shows swapping a longer job ahead of a shorter one that is also ready can only increase or hold constant the sum of completion times, so always picking the shortest ready job is optimal here). P1 runs 0–3 (only arrival). CPU idles to t=12 (still only P2 has arrived). P2 runs 12–18 (only job ready). By t=18, P3 (burst 4, arrived 14), P4 (burst 5, arrived 16) and P5 (burst 2, arrived 18) are all ready — the shortest is P5, so P5 runs 18–20, then the next-shortest ready job P3 runs 20–24, then P4 runs 24–29.
$$TT_{P1}=3,\ TT_{P2}=6,\ TT_{P5}=20-18=2,\ TT_{P3}=24-14=10,\ TT_{P4}=29-16=13$$
$$\boxed{\overline{TT}_{opt} = \dfrac{3+6+2+10+13}{5} = \dfrac{34}{5} = 6.8\ \text{s}}$$
This is confirmed by an exhaustive search over all 120 possible run orders of the five processes — no non-preemptive order does better than 6.8 s.
(iii) HRRN. At each scheduling instant, compute response ratio $RR = 1 + \dfrac{\text{wait}}{\text{burst}}$ for every ready process and run the one with the highest ratio (a longer-waiting or shorter job is favoured, but the two effects trade off — this is what distinguishes HRRN from plain SJF). P1 runs 0–3 (only arrival); CPU idles to t=12; P2 runs 12–18 (only job ready). At t=18 the ready set is P3 (wait $18-14=4$, burst 4, $RR=\tfrac{4+4}{4}=2.0$), P4 (wait $18-16=2$, burst 5, $RR=\tfrac{2+5}{5}=1.4$), P5 (wait $0$, burst 2, $RR=\tfrac{0+2}{2}=1.0$). P3 has the highest ratio (2.0) despite P5 being shorter, so P3 runs 18–22. At t=22 the ready set is P4 (wait $22-16=6$, burst 5, $RR=\tfrac{6+5}{5}=2.2$) and P5 (wait $22-18=4$, burst 2, $RR=\tfrac{4+2}{2}=3.0$); P5's long relative wait now dominates, so P5 runs 22–24, and finally P4 runs 24–29.
$$TT_{P1}=3,\ TT_{P2}=6,\ TT_{P3}=8,\ TT_{P5}=24-18=6,\ TT_{P4}=29-16=13$$
$$\boxed{\overline{TT}_{HRRN} = \dfrac{3+6+8+6+13}{5} = \dfrac{36}{5} = 7.2\ \text{s}}$$
Fig. Q1(a)-iii — HRRN Gantt chart. Note P3 is chosen ahead of the shorter P5 at t=18 because its response ratio is higher.
Final Results — Q1(a)
Policy
Run order (after P1, idle, P2)
Mean turnaround
FCFS
P1, P2, P3, P4, P5
7.8 s
Optimal (shortest ready job first)
P1, P2, P5, P3, P4
6.8 s
HRRN
P1, P2, P3, P5, P4
7.2 s
(b) A hard real-time system is one in which a task that misses its deadline is considered a total failure of the system, because a late result is as useless (or dangerous) as a wrong one — there is no partial credit for tardiness. Example: the engine-control unit firing a spark plug or the flight-control computer on a fly-by-wire aircraft adjusting a control surface; missing the deadline by even a few milliseconds can crash the vehicle. A soft real-time system tolerates occasional missed deadlines with a graceful, bounded degradation in quality rather than catastrophic failure — the requirement is statistical (most deadlines met, on average) rather than absolute. Example: a video-streaming player or a VoIP call — a late audio/video frame causes a momentary glitch or a dropped frame, not a system failure, and the stream simply continues.
