25-Comp-A5 Operating Systems · December 2014

Question 1 of 7: CPU Scheduling and Real-Time Priority

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

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, December 2014. 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.

Question 1: CPU Scheduling and Real-Time Priority (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) With lower integer ⇒ higher priority, each policy is reproduced by choosing what quantity becomes the priority number at arrival:

(i) FCFS. Set priority = arrival time (or an ever-increasing arrival-sequence counter). The process that arrived earliest gets the smallest number, i.e. the highest priority, so a strict (non-preemptive, static) priority scheduler that always runs the ready process with the smallest priority value automatically runs processes in arrival order — exactly FCFS.
(ii) Shortest Job First. Set priority = the process's (known or estimated) CPU burst length. The shortest job receives the smallest number and therefore the highest priority, so the priority scheduler always selects the shortest ready job next — exactly SJF. (For the preemptive variant, SRTF, the priority would have to be recomputed continuously as remaining burst time, rather than fixed at arrival.)

Given. Five processes with the arrival and execution (burst) times below; a single CPU; no I/O; each policy is non-preemptive once a process is dispatched.

Given data
Process	Arrival time (s)	Execution time (s)
Proc1	0	21
Proc2	3	8
Proc3	4	14
Proc4	7	2
Proc5	8	2

Find. The mean turnaround time and the fairness index $F=\overline{W}/\overline{E}$ (mean waiting time over mean execution time) under (i) FCFS and (ii) HRRN.

Approach. Build the run order each policy produces (respecting arrival times), read off finish times, then compute turnaround $TT=C-A$ and waiting $W=TT-E$ for each process; mean execution time is policy-independent so it is computed once.

Fig. Q1(b)-i — FCFS Gantt chart. Every process runs strictly in arrival order with no idle gaps since Proc1's 21 s burst outlasts all later arrivals.

(i) FCFS. Proc1 arrives first (t=0) and runs 0–21 uninterrupted. By t=21, Proc2 (arrived 3), Proc3 (arrived 4), Proc4 (arrived 7) and Proc5 (arrived 8) are all waiting; FCFS dispatches them strictly in arrival order: Proc2 runs 21–29, Proc3 runs 29–43, Proc4 runs 43–45, Proc5 runs 45–47. Turnaround $TT=C-A$: $TT_1=21,\ TT_2=26,\ TT_3=39,\ TT_4=38,\ TT_5=39$. $$\boxed{\overline{TT}_{FCFS}=\dfrac{21+26+39+38+39}{5}=\dfrac{163}{5}=32.6\ \text{s}}$$ Waiting time $W=TT-E$: $W_1=0,\ W_2=18,\ W_3=25,\ W_4=36,\ W_5=37$, mean $\overline{W}_{FCFS}=116/5=23.2\ \text{s}$. Mean execution time $\overline{E}=(21+8+14+2+2)/5=9.4\ \text{s}$ (the same under every policy, since it only depends on the fixed burst lengths). $$\boxed{F_{FCFS}=\dfrac{\overline{W}_{FCFS}}{\overline{E}}=\dfrac{23.2}{9.4}\approx 2.468}$$
(ii) HRRN. At each scheduling instant, compute $RR=1+\dfrac{\text{wait}}{\text{burst}}$ for every ready process and dispatch the highest. Proc1 runs 0–21 (only arrival). At t=21 the ready set is Proc2 ($RR=1+\tfrac{18}{8}=3.25$), Proc3 ($1+\tfrac{17}{14}\approx2.214$), Proc4 ($1+\tfrac{14}{2}=8.0$), Proc5 ($1+\tfrac{13}{2}=7.5$) — Proc4 wins, runs 21–23. At t=23: Proc2 ($1+\tfrac{20}{8}=3.5$), Proc3 ($1+\tfrac{19}{14}\approx2.357$), Proc5 ($1+\tfrac{15}{2}=8.5$) — Proc5 wins, runs 23–25. At t=25: Proc2 ($1+\tfrac{22}{8}=3.75$), Proc3 ($1+\tfrac{21}{14}=2.5$) — Proc2 wins, runs 25–33. Only Proc3 remains: runs 33–47. Turnaround: $TT_1=21,\ TT_4=16,\ TT_5=17,\ TT_2=30,\ TT_3=43$. $$\boxed{\overline{TT}_{HRRN}=\dfrac{21+16+17+30+43}{5}=\dfrac{127}{5}=25.4\ \text{s}}$$ Waiting: $W_1=0,\ W_4=14,\ W_5=15,\ W_2=22,\ W_3=29$, mean $\overline{W}_{HRRN}=80/5=16.0\ \text{s}$. $$\boxed{F_{HRRN}=\dfrac{16.0}{9.4}\approx 1.702}$$ HRRN gives both a shorter mean turnaround (25.4 s vs. 32.6 s) and a lower (fairer) fairness index than FCFS — it lets short, long-waiting jobs (Proc4, Proc5) cut ahead of the still-running long job's queue position without starving the longest job (Proc3), which is exactly what the aging term in $RR$ is for.

Fig. Q1(b)-ii — HRRN Gantt chart. Proc4 and Proc5 cut ahead of Proc2/Proc3 once their response ratios climb past them.

Final Results — Q1(b)
Policy	Run order	Mean turnaround	Mean wait	Fairness index F
FCFS	Proc1, Proc2, Proc3, Proc4, Proc5	32.6 s	23.2 s	2.468
HRRN	Proc1, Proc4, Proc5, Proc2, Proc3	25.4 s	16.0 s	1.702

(c) On a real-time system, priority alone does not guarantee that the highest-priority ready process always runs immediately — a lower-priority process can legitimately keep the CPU (or even keep a resource that blocks a higher-priority process) in two important situations:

Non-preemptible critical sections. If the lower-priority process is executing inside a critical section that must run to completion for correctness (e.g. it is holding a spinlock while updating a shared kernel data structure, or its architecture disables interrupts during the section), the scheduler must let it finish rather than preempting it mid-update, even though a higher-priority process has just become ready. Example: a low-priority logging task is midway through appending a record to a shared ring buffer (interrupts briefly masked to keep the append atomic) when a high-priority sensor-interrupt task becomes ready; the logging task is allowed to finish its short critical section before the sensor task is dispatched, because interrupting it partway would corrupt the ring buffer for every task that reads it, including the sensor task.
Priority inversion via a shared resource (mutex/semaphore). If a low-priority process holds a lock that a high-priority process needs, the high-priority process must block until the low-priority process releases it, so the low-priority process necessarily continues to run (and finish using the resource) while the high-priority process waits — this is priority inversion. Example (the classic Mars Pathfinder incident): a low-priority meteorological data-collection task holds a mutex protecting a shared information bus; a high-priority bus-management task needs the same mutex and blocks; without priority inheritance, a medium-priority task with no interest in the mutex can preempt the low-priority task and run indefinitely, extending the high-priority task's wait far beyond the time the low-priority task alone would have held the lock. The standard fix is a priority-inheritance protocol: while the high-priority task is blocked on the mutex, the low-priority holder temporarily inherits the high priority, which lets it finish and release the lock quickly and prevents medium-priority tasks from cutting in.

Topic: Priority-based scheduling, response-ratio aging, and priority inversion on real-time systems.

Key relations: Turnaround $TT=C-A$; mean turnaround = mean wait + mean execution (execution mean is policy-independent, so minimizing mean turnaround $\equiv$ minimizing mean wait); HRRN response ratio $RR=1+w/s$; fairness index $F=\overline{W}/\overline{E}$ (lower is fairer — a process waits proportionally less relative to how much CPU time it actually needs).

Why this works: Mapping a policy's ranking rule directly onto the numeric priority field is possible whenever the policy is expressible as "always run the ready process that minimizes/maximizes some computable quantity" — FCFS ranks by arrival order, SJF by burst length, and (though not asked here) HRRN itself could be implemented as a dynamically recomputed priority equal to $-RR$. Priority inheritance works because it removes the incentive for unrelated medium-priority work to preempt the lock holder, bounding the inversion to, at worst, the time the low-priority task needs to finish its critical section.

Common pitfall: Assuming "highest priority always runs next" is an absolute guarantee ignores mutual exclusion — a strict priority scheduler with no inheritance mechanism can suffer unbounded priority inversion. In the fairness-index calculation, students often forget that mean execution time is fixed regardless of the scheduling policy and re-derive it per policy, or divide waiting time by turnaround time instead of by execution time.

Source: Silberschatz, Galvin & Gagne, Operating System Concepts, ch. 5 (CPU Scheduling) §5.3 (algorithms, incl. HRRN-style aging) and §5.8 (real-time scheduling, priority inversion, priority inheritance protocol).

← Paper overview Next: Question 2 →