CPU Scheduling Algorithms

Key metrics: Turnaround Time (TAT) = Completion Time - Arrival Time; Waiting Time (WT) = TAT - Burst Time; Response Time = first CPU allocation time - Arrival Time. Average WT and average TAT are computed over all processes. Throughput = processes completed per unit time; CPU Utilization should be maximized. Memory aid: 'TAT = WT + BT' and 'WT = TAT - BT'. For non-preemptive algorithms, response time often equals waiting time. Goal: minimize WT, TAT, and response time; maximize throughput and utilization. Note arrival times carefully: idle CPU time before the first arrival is not counted as waiting for any process.

FCFS: non-preemptive, by arrival order; suffers convoy effect (short jobs wait behind long ones). SJF: non-preemptive, picks shortest burst; provably gives minimum average waiting time. SRTF: preemptive SJF; optimal preemptive WT but causes starvation of long jobs. Priority: highest priority first; starvation fixed by aging. Round Robin (RR): preemptive FCFS with time quantum q; if q is very large, RR to FCFS; if q to 0, overhead dominates. RR response time is good; it is fair. Memory aid: 'SJF/SRTF minimize average waiting time'. Both SJF and SRTF need burst-length knowledge (estimated via exponential averaging).

Processes (Arrival, Burst): P1(0,8), P2(1,4), P3(2,9), P4(3,5). SRTF (preemptive): At t=0 run P1 (rem 8). At t=1, P2 arrives (4) < P1 rem(7), so P2 runs. At t=2 P3(9) vs P2 rem(3): P2 continues. At t=3 P4(5) vs P2 rem(2): P2 continues, finishes t=5. Then choose smallest among P1(7), P4(5): P4 runs to t=10. Then P1(7) to t=17, then P3(9) to t=26. Completion: P1=17, P2=5, P3=26, P4=10. TAT = C - A: P1=17, P2=4, P3=24, P4=7. WT = TAT - BT: P1=9, P2=0, P3=15, P4=2. Average WT = (9+0+15+2)/4 = 6.5.

Cover the answer, recall, then check. 12 cards on specific CPU scheduling algorithms for GATE OS.

Q1. FCFS with bursts P1=24, P2=3, P3=3 arriving at t=0 (in that order) — average waiting time?
A1. WT: P1=0, P2=24, P3=27 → avg = (0+24+27)/3 = 17. Reordering as P2,P3,P1 gives avg 3 — showing FCFS is order-sensitive (convoy effect).

Q2. In SJF, how are ties in burst length broken (GATE convention)?
A2. Usually by FCFS (earlier arrival first). Always follow the tie-break stated in the question; the default assumption is arrival order.

Q3. SRTF (preemptive SJF) — when is a scheduling decision made?
A3. At every new arrival (and at completion): compare remaining time of the running process with the new arrival's burst; preempt if the newcomer is shorter.

Q4. Round Robin, quantum q, n processes — worst-case time before a process is scheduled again?
A4. At most (n−1)·q time units (ignoring context-switch cost). This bounds response time.

Q5. How is Round Robin implemented with the ready queue?
A5. Ready queue as a FIFO circular queue. A newly arrived process and a preempted process are added to the tail; convention (GATE) usually places an arriving process before the just-preempted one at the same instant.

Q6. Preemptive vs non-preemptive priority scheduling difference?
A6. Non-preemptive: a higher-priority arrival waits until the running process finishes. Preemptive: it immediately preempts the running lower-priority process.

Q7. What is a Multilevel Queue scheduler?
A7. Ready queue is partitioned into separate queues (e.g., system, interactive, batch), each with its own algorithm; fixed priority (or time-slice) between queues. Processes do not move between queues.

Q8. What is Multilevel Feedback Queue (MLFQ) and its advantage?
A8. Like multilevel queue but processes move between queues based on behaviour (CPU-bound jobs demoted, I/O-bound favoured). It approximates SJF and prevents starvation via aging. It is the most general scheme.

Q9. Does a smaller RR quantum always improve performance?
A9. No. Smaller q improves response time but increases context-switch overhead; too small a q wastes CPU on switching. There is a trade-off around burst sizes.

Q10. For a given process set, which algorithm gives the SAME result whether preemptive or not?
A10. If all processes arrive at t=0, SJF and SRTF give identical schedules (no later arrival can preempt). Preemption only matters with staggered arrivals.

Q11. How do you compute average turnaround time from a Gantt chart?
A11. For each process TAT = CompletionTime − ArrivalTime; average over all. Read completion times directly off the chart's right edges.

Q12. LJF / HRRN — what is Highest Response Ratio Next?
A12. Non-preemptive; picks the process with the largest response ratio = (waiting time + burst)/burst. It favours short jobs but prevents starvation of long ones by boosting their ratio as they wait.

This topic is the numerical heart of OS scheduling: given arrival and burst times, produce the Gantt chart under a named algorithm and compute averages. Precision on tie-breaks and arrival handling separates full marks from lost marks.

The five core algorithms

Algorithm	Selection rule	Preemptive?	Note
FCFS	Earliest arrival	No	Convoy effect
SJF	Smallest burst	No	Min avg WT (arrival=0)
SRTF	Smallest remaining time	Yes	Decision at each arrival
Priority	Highest priority	Both	Starvation → aging
Round Robin	FIFO with quantum q	Yes	Response bound (n−1)q

Multilevel schemes

Multilevel queue partitions ready processes into fixed queues, no movement between them. Multilevel feedback queue (MLFQ) lets processes migrate based on CPU usage, approximating SJF while avoiding starvation — the most flexible general-purpose scheduler.

Working the numbers

For each process compute TAT = CT − AT and WT = TAT − BT. In SRTF, re-evaluate at every arrival. In RR, maintain a FIFO ready queue and decide the queue-insertion order for simultaneous events per the question's convention.

Exam Tricks & Tips

• 🎯 When all arrivals are at t=0, SJF and SRTF coincide — don't waste time doing preemptive bookkeeping.
• 🎯 RR ready-queue ordering is the #1 trap: at the same instant, GATE usually inserts the arriving process before the preempted one. Read the paper's stated convention.
• 🎯 Count context-switch time only if the question gives it — otherwise assume it is zero.
• 🎯 SRTF requires a decision at each new arrival, not only at completion — miss an arrival and the whole chart shifts.
• 🎯 HRRN's ratio (W+B)/B prevents long-job starvation while still favouring short jobs — a favourite conceptual MCQ.
• ❌ Common mistake: in RR, forgetting that a process finishing exactly at a quantum boundary leaves before a newly arrived process is queued, changing subsequent order.

Expected exam pattern

A 2-mark numerical: a 4–5 process table with staggered arrivals, asked for average WT or TAT under SRTF or RR. Or a 1-mark MCQ comparing algorithms (which minimises WT, which starves, RR quantum effect).

Quick recap

Master the Gantt-chart mechanics: FCFS (order-sensitive), SJF/SRTF (WT-optimal), Priority (needs aging), RR (response-bounded, quantum trade-off), and MLFQ (adaptive). Watch the tie-break and simultaneous-arrival conventions — they decide the answer.