- LPU MCA Semester 1
- CAP366
- Unit 4
CAP366 · Unit 4: CPU scheduling
Priority and round-robin scheduling
13 practice questions · in the MTE and ETE syllabus
Key points
- Priority + aging prevents starvation
- RR: large q = FCFS, tiny q = overhead
- Wait between turns <= (n - 1) q
- Tie at quantum expiry: arrival first by convention
Priority scheduling runs the highest-priority process (lower number = higher priority in most textbooks, so always read the question). It may be preemptive; starvation of low-priority processes is cured by aging.
Round robin gives each process a quantum q and cycles through the ready queue. Large q behaves like FCFS; very small q wastes time on context switches. Each process waits at most (n - 1) q between turns.
Example (q = 2): P1(0,5), P2(1,3), P3(2,1) gives order P1, P2, P3, P1, P2, P1 and average waiting 10 / 3 = 3.33 ms when P3 (arriving at 2) is queued before the preempted P1.
| Case | Result |
|---|---|
| Preempted process queued first | Average waiting 4 ms |
| Arriving process queued first | Average waiting 3.33 ms |
Exam pitfall: state the tie rule for a process that arrives exactly when a quantum expires; the usual convention is the arrival goes first.
Try two questions
Preemptive priority (lower number = higher priority): P1(arrival 0, burst 5, priority 3), P2(1, 4, 1), P3(2, 2, 2). What is the average waiting time?
- 4 ms
- 3.67 ms
- 2.5 ms
- 3 ms
Show the answer
D. Gantt: P1 0-1, P2 1-5, P3 5-7, P1 7-11; waits 6, 0, 3 give 9/3 = 3. The non-preemptive result of 3.67 ms ignores preemption of P1.
Round robin, quantum 2: P1(arrival 0, burst 5), P2(1, 3), P3(2, 1). Assume a process arriving at the same instant a quantum expires is queued before the preempted process. What is the average waiting time?
- 3.33 ms
- 4.67 ms
- 3 ms
- 4 ms
Show the answer
A. Gantt: P1 0-2, P2 2-4, P3 4-5, P1 5-7, P2 7-8, P1 8-9; waits 4, 4, 2 give 10/3 = 3.33. If P1 were queued before P3 the answer would be 4, the tie trap.