Neural Sync Active

CPU Scheduling — Round Robin, Priority, MLFQ

Registry Synced

CPU Scheduling — Round Robin, Priority, MLFQ

872 words

4 min read

Reading compass

Now · 🎯 Learning Objectives

CPU Scheduling — Round Robin, Priority, MLFQ

🎯 Learning Objectives

Trace Round Robin scheduling with different time quanta
Analyze priority scheduling and the starvation problem
Explain the design and behavior of Multilevel Feedback Queue
Compare scheduling algorithms across multiple criteria

1. Round Robin (RR)

1.1 Intuition

Round Robin is like dealing cards: each process gets a small slice of CPU time (time quantum), then goes to the back of the queue. This ensures fairness and responsiveness — no process waits too long.

1.2 Algorithm

(Diagram)

1.3 Worked Example: q = 4

Process	Arrival	Burst
P1	0	10
P2	0	5
P3	0	2

Gantt Chart (q=4):


pseudo
| P1(4) | P2(4) | P3(2) | P1(4) | P2(1) | P1(2) |
0       4       8       10      14     15      17

Tracing Table:

Time	Event	Queue	Running
0	Start	P1(10), P2(5), P3(2)	P1
4	P1 preempted (6 remaining)	P2(5), P3(2), P1(6)	P2
8	P2 preempted (1 remaining)	P3(2), P1(6), P2(1)	P3
10	P3 done (burst=2)	P1(6), P2(1)	P1
14	P1 preempted (2 remaining)	P2(1), P1(2)	P2
15	P2 done	P1(2)	P1
17	P1 done	--	--

Calculations:

Process	TAT	WT
P1	17	7
P2	15	10
P3	10	8

Average TAT = 14, Average WT = 8.33

1.4 Time Quantum Selection

(Diagram)

Quantum	Pros	Cons
Small (< 10ms)	Good response time	High context switch overhead (>50% CPU wasted)
Large (> 100ms)	Low overhead	Poor response time, approaches FCFS
Typical (10-50ms)	Balanced	1-10% overhead, good interactive performance

Context switch overhead formula:

\text{CPU Utilization} = \frac{q}{q + \text{overhead}}

For q = 10ms and overhead = 1ms:

\text{Utilization} = \frac{10}{10 + 1} = 90.9\%

2. Priority Scheduling

2.1 Intuition

Each process has a priority (lower number = higher priority in Unix/Linux). The highest-priority ready process runs. Can be preemptive (new higher priority preempts) or non-preemptive.

2.2 Worked Example (Preemptive Priority)

Process	Arrival	Burst	Priority
P1	0	8	3 (low)
P2	1	4	1 (high)
P3	2	2	2 (mid)
P4	3	1	1 (high)

Gantt Chart:


pseudo
| P1(1) | P2(1) | P4(1) | P2(3) | P3(2) | P1(7) |
0       1       2       3       6       8      15

Tracing (preemptive priority):

Time	Running	Event	Ready Queue
0	P1(8)	P1 starts	--
1	P2(4)	P2 (pri=1) preempts P1 (pri=3)	P1(7)
2	P4(1)	P4 (pri=1) preempts P2? P2(3) pri=1, P4 pri=1 — tie, FCFS? Actually P4 arrives, priority=1 same as P2's. Usually same priority uses RR	P1(7), P2(3)
3	P4 done	--	P1(7), P2(3)
6	P2 done	--	P1(7), P3(2)
8	P3 done	--	P1(7)
15	P1 done	--	--

Problem: Starvation. Low-priority processes may never run if high-priority processes keep arriving.

2.3 Aging Solution


c
while (true) {
    for each process p in ready_queue:
        p.priority++;  // Increase priority of waiting processes
    schedule();
}

Aging gradually increases the priority of waiting processes, ensuring they eventually get the CPU.

3. Multilevel Queue (MLQ)

3.1 Intuition

Partition the ready queue into multiple queues, each with its own scheduling algorithm. Processes are assigned permanently to a queue based on their type (foreground interactive, background batch). (Diagram)

3.2 Scheduling Between Queues

Strict priority: Serve all of Q1 before Q2, all of Q2 before Q3. Risk: Q2 and Q3 starve.
Time slice: 80% CPU to Q1, 20% to Q2, etc.

4. Multilevel Feedback Queue (MLFQ)

4.1 Intuition

MLFQ is the most general scheduling algorithm. Like MLQ but processes move between queues based on their behavior. Short CPU bursts → high priority (interactive). Long CPU bursts → low priority (batch).

4.2 MLFQ Rules

(Diagram) Classic 3-level MLFQ:

Queue	Quantum	Scheduling	Behavior
Q0 (highest)	5ms	RR	Interactive processes
Q1	10ms	RR	Short jobs
Q2 (lowest)	FCFS	FCFS	Long-running batch

4.3 Worked Example

Process	Arrival	Burst
P1	0	15
P2	0	3
P3	1	6

Queues: Q0 (q=5ms, RR), Q1 (q=10ms, RR), Q2 (FCFS) Tracing:

Time	Event	Q0	Q1	Q2	Running
0	P1, P2 arrive	P1(15), P2(3)	--	--	P1 starts (Q0)
5	P1 quantum expired, moved to Q1	P2(3)	P1(10)	--	P2 starts (Q0)
8	P2 done (ran 3ms)	--	P1(10)	--	P1 starts (Q1)
9	P3 arrives	P3(6)	P1(10)	--	P3 preempts? No, Q0 > Q1
9	--	P3(6)	P1(10)	--	P3 starts (Q0)
14	P3 quantum expired, moved to Q1	--	P1(10), P3(1)	--	P1 starts (Q1)
24	P1 done (ran 10ms)	--	P3(1)	--	P3 starts (Q1)
25	P3 done	--	--	--	--

TAT: P1=24, P2=8, P3=24. Avg TAT = 18.67

5. Algorithm Comparison

Algorithm	Avg WT	Response	Overhead	Starvation	Preemptive
FCFS	High	Poor	Low	No	No
SJF (NP)	Low	Poor	Medium	Yes	No
SRTF	Lowest	Best	High	Yes	Yes
RR	Medium	Good	Medium	No	Yes
Priority	Medium	Good	Medium	Yes	Optional
MLFQ	Low	Good	High	Possible	Yes

6. 📝 Practice Questions

Q1: For RR with q=5 and processes P1(BT=10), P2(BT=5), P3(BT=2), compute average TAT.

Gantt: P1(5) | P2(5) | P3(2) | P1(5) → 0-5, 5-10, 10-12, 12-17

TAT: P1=17, P2=10, P3=12. Avg = 39/3 = 13 Q2: What happens to RR performance if the time quantum approaches 0? Approaches infinity?

Answer: q→0: High context switch overhead (CPU near 0% utilization). q→∞: Degrades to FCFS, response time becomes very poor. Q3: How does MLFQ prevent starvation of long-running processes?

Answer: MLFQ uses aging: processes that wait too long at lower-priority queues can be promoted back to higher queues. Some implementations also reserve a minimum CPU share for the lowest queue. Q4: Compare priority scheduling with SJF. Which is better for interactive systems?

Answer: Priority scheduling with external priorities (e.g., I/O-bound processes get higher priority) works better for interactive systems because it can favor processes that respond to user input. SJF minimizes average WT but doesn't consider interactivity. Q5: A system uses MLFQ with Q0(RR, q=4), Q1(FCFS). Draw the Gantt chart for P1(BT=10), P2(BT=3).

Tracing:

t=0: P1, P2 arrive. Q0: P1, P2. P1 runs.

t=4: P1 quantum expires → Q1. Q0: P2. P2 runs.

t=7: P2 done. Q1: P1. P1 runs.

t=17: P1 done.

Gantt: P1(0-4) | P2(4-7) | P1(7-17)

7. 🔗 Cross-References

Week 3 - FCFS/SJF: Compare with RR and MLFQ
Week 7 - Memory Management: Page replacement algorithms (similar to scheduling)
BSCS4021 (Advanced Algorithms): Scheduling theory Join Discord PreviousCPU Scheduling: FCFS, SJFNextSynchronization