Tutorial 5 – CPU Scheduling Study Notes

Preemptive vs Non-Preemptive Scheduling

• CPU scheduling decides which ready process gets the CPU next.
• Non-preemptive (co-operative)
– Once a process is dispatched, it runs until it voluntarily yields (terminates or blocks for I/O).
– No external interruption → simpler implementation, lower context-switch overhead.
– Risk: one long CPU-bound job can create the Convoy Effect (many short jobs queue behind it, inflating average wait times).
• Preemptive (time-sharing)
– The OS may forcibly remove a process from the CPU on a scheduling event (timer interrupt, higher-priority arrival, etc.).
– Improves response time for interactive workloads; enables finer-grained fairness.
– Adds context-switch cost, needs hardware support (timer, mode bit) & data-consistency measures (kernel/user boundary, critical-section protection).

First-Come, First-Served (FCFS)

• Rule: schedule in strict order of arrival time (AT).
• Implementation: simple FIFO queue.
• Characteristics
– Non-preemptive, O(1) dispatch.
– Possible large average waiting/turnaround due to Convoy Effect.
– No starvation, but poor response-time for short jobs.
• When all jobs are the same length it is optimal; otherwise sub-optimal compared with SJF.

Shortest-Job-First (SJF)

• Non-preemptive version chooses the ready process with minimum CPU burst time (BT).
• Why optimal? By the Shortest-Process-Next theorem, scheduling jobs in ascending length order minimises the average waiting time $\bar{W}$ for a fixed set of non-arriving jobs.
• Requirements & caveats
– Needs exact or predicted BT (difficult in practice → use exponential averaging, compiler hints, etc.).
– Can cause starvation for long jobs if a steady stream of short jobs arrives.

Shortest Remaining Time First (SRTF)

• Preemptive counterpart to SJF.
• Rule: whenever an event occurs (arrival/completion), pick process with smallest remaining burst.
• Yields the same optimality (minimises average turnaround time $\bar{T}$) in the preemptive universe.

Multilevel Feedback Queue (MLFQ)

• General-purpose, adaptive, preemptive scheduler.
• Architecture
– Several priority levels, each with its own ready queue.
– Time quantum grows at lower levels (e.g., 8 ms, 16 ms, 32 ms …).
• Rules (example variant)

1. New processes enter the highest priority queue.

2. If a process uses an entire quantum, it is demoted to the next lower queue (assumed CPU-bound).

3. If it blocks or yields early, it remains or is promoted (assumed I/O-bound or interactive).

4. Scheduler always chooses the highest non-empty queue (preemptive between levels, usually round-robin within a level).
   • Outcome: approximates SJF without needing exact BT; balances responsiveness for short/interactive jobs with fairness for long/CPU-bound jobs.

Key Formulae

• Completion Time: $CT<em>i$ (time a process $i$ terminates) • Turnaround Time: $TAT</em>i = CT<em>i - AT</em>i$
• Waiting Time: $WT<em>i = TAT</em>i - BT<em>i$ • Averages: $\text{Average }TAT = \frac{\sum</em>{i=1}^{n} TAT<em>i}{n}\quad \text{and}\quad \text{Average }WT = \frac{\sum</em>{i=1}^{n} WT_i}{n}$

Numerical Example – Given Data

• Processes
– P1 (AT 0 ms, BT 8 ms)
– P2 (AT 1 ms, BT 4 ms)
– P3 (AT 2 ms, BT 9 ms)
– P4 (AT 3 ms, BT 5 ms)

(a) Non-Preemptive SJF Results

• Gantt chart: P1 |0-8| → P2 |8-12| → P4 |12-17| → P3 |17-26|
• Metrics
– P1: $CT=8,\;TAT=8,\;WT=0$
– P2: $CT=12,\;TAT=11,\;WT=7$
– P3: $CT=26,\;TAT=24,\;WT=15$
– P4: $CT=17,\;TAT=14,\;WT=9$
• Averages
– $\bar{TAT}=\frac{8+11+24+14}{4}=14.25\,\text{ms}$
– $\bar{WT}=\frac{0+7+15+9}{4}=7.75\,\text{ms}$

(b) Preemptive SRTF Results

• Timeline

1. 0-1 ms → P1

2. 1-5 ms → P2 (preempts P1 at 1 ms; finishes at 5 ms)

3. 5-10 ms → P4 (shortest remaining 5 ms)

4. 10-17 ms → P1 (remaining 7 ms)

5. 17-26 ms → P3 (remaining 9 ms)
   • Metrics
   – P1: $CT=17,\;TAT=17,\;WT=9$
   – P2: $CT=5,\;TAT=4,\;WT=0$
   – P3: $CT=26,\;TAT=24,\;WT=15$
   – P4: $CT=10,\;TAT=7,\;WT=2$
   • Averages
   – $\bar{TAT}=\frac{17+4+24+7}{4}=13\,\text{ms}$
   – $\bar{WT}=\frac{9+0+15+2}{4}=6.5\,\text{ms}$

Insights & Takeaways

• SRTF improved both average TAT and WT compared with non-preemptive SJF for this workload, thanks to earlier completion of P2 & P4.
• However, P3 still suffers long wait → highlights potential starvation/fairness issues when job lengths vary greatly.
• MLFQ attempts to mitigate such starvation without needing exact burst predictions.
• Choosing a scheduling algorithm is a policy decision balancing:
– Throughput vs. response time.
– Implementation complexity vs. optimality.
– Fairness vs. priority/interactive guarantees.
• Modern OSes (Linux CFS, Windows NT, macOS) use sophisticated variations (priority + fairness + deadlines) building on these foundational ideas.