Lesson 4 � Intermediate

OS: CPU Scheduling

CPU Scheduling decide karta hai ki kaunsa process CPU pehle run karega. Different algorithms hain � har algorithm ka apna approach hai.

? 18 min✓ Intermediate✓ Processes basics

CPU Scheduling hota kya hai?

WHAT

CPU Scheduling ek process hai jisme OS decide karta hai ready queue mein se kaunsa process CPU pe execute hoga. Multiple processes ready hain but CPU ek hi waqt pe ek process chala sakta hai (single core).

WHEN

Har baar jab CPU free hota hai � running process complete ya waiting mein jaata hai � tab scheduling decision hota hai. Context switch ke saath naya process load hota hai.

WHERE

Linux ka CFS (Completely Fair Scheduler), Windows ka thread scheduler, mobile OS ka scheduler � sab scheduling algorithms use karte hain.

Scheduling Types

# 1. Non-Preemptive Scheduling
✓ Ek process CPU chodega jab tak complete na ho jaaye
✓ Simple, but starvation ho sakta hai
✓ Example: FCFS, SJF (non-preemptive)

# 2. Preemptive Scheduling
✓ OS process ko forcefully CPU le sakta hai (time quantum expire)
✓ Fair, but context switch overhead
✓ Example: Round Robin, SRTF

# Key Metrics:
- Turnaround Time = Completion Time - Arrival Time
- Waiting Time = Turnaround Time - Burst Time
- Response Time = First Response - Arrival Time

# Goal: Minimize waiting time, maximize throughput

Scheduling Algorithms

# 1. FCFS (First Come First Serve)
✓ Jo pehle aaya, pehle chalega
✓ Non-preemptive, simple
✓ Problem: Convoy effect (ek bada process sabko wait karata hai)

Example: P1(24ms), P2(3ms), P3(3ms)
Gantt: |P1(0-24)|P2(24-27)|P3(27-30)|
Avg Waiting = (0+21+27)/3 = 16ms

# 2. SJF (Shortest Job First)
✓ Sabse chhota process pehle
✓ Non-preemptive, optimal for avg waiting time
✓ Problem: Prediction mushkil, starvation for long jobs

# 3. SRTF (Shortest Remaining Time First)
✓ SJF ka preemptive version
✓ New process aaye with shorter burst ✓ preempt current
✓ Optimal for avg waiting time

# 4. Round Robin
✓ Har process ko fixed time quantum milta hai
✓ Time quantum expire ✓ next process
✓ Fair, preemptive, widely used
✓ Problem: Context switch overhead, quantum size important

# 5. Priority Scheduling
✓ Har process ko priority milti hai
✓ High priority pehle
✓ Problem: Starvation for low priority (aging se solve)

# 6. Multilevel Queue
✓ Multiple queues with different priorities
✓ Foreground (interactive) ✓ Background (batch)
✓ Har queue ka apna algorithm

Mental Model: CPU Scheduling jaise hospital mein triage. Emergency (high priority) pehle, normal checkup baad mein. Round Robin jaise � har patient ko 5 minute, next patient. FCFS jaise � token number system.

Algorithm Comparison

| Algorithm | Preemptive | Optimal | Starvation | Use Case |
|-----------|------------|---------|------------|--------------------|
| FCFS | No | No | No | Batch systems |
| SJF | No | Yes(avg)| Yes | Batch systems |
| SRTF | Yes | Yes(avg)| Yes | Interactive |
| Round Robin| Yes | No | No | Time-sharing |
| Priority | Both | No | Yes | Real-time systems |
| Multilevel| Yes | No | Possible | General purpose |

# Real OS Scheduling:
- Linux: CFS (Completely Fair Scheduler) � virtual runtime based
- Windows: Multilevel feedback queue
- macOS: Multilevel feedback queue
- Mobile: Power-aware scheduling

Exercise

Question: Round Robin scheduling mein har process ko kya milta hai? (2 words)

Question: Convoy effect kis scheduling algorithm mein hota hai? (1 word ya acronym)

Common mistakes

Gantt chart nahi banana: Interview mein Gantt chart banao � visual se samajhna easy hota hai.
Quantum size ignore: Round Robin mein quantum bahut chhota = zyada context switch. Bahut bada = FCFS ban jaata hai.
Starvation vs Convoy: Starvation (priority scheduling) alag hai Convoy effect (FCFS) se. Confuse mat karo.
Arrival time skip: Waiting time = Turnaround - Burst. Arrival time zaroori hai calculation ke liye.

Lesson complete?

CPU Scheduling samajh aa gayi✓ Ab Deadlock Detection seekhte hain � jab processes ek doosre ko block karein.