1. Definition
CPU scheduling selects which process in the ready queue gets the CPU next. Goal: maximize CPU utilization, throughput, and minimize turnaround time, waiting time, response time.
2. Key Terms
- Burst Time (BT): CPU time required by process
- Arrival Time (AT): Time process enters ready queue
- Completion Time (CT): Time process finishes
- Turnaround Time (TAT): CT − AT
- Waiting Time (WT): TAT − BT
- Response Time: Time from arrival to first CPU allocation
3. Scheduling Algorithms (Very Important)
FCFS (First Come First Serve)
- Non-preemptive. Processes served in arrival order.
- Convoy effect: short processes wait behind long ones
- Simple but poor average waiting time
SJF (Shortest Job First)
- Non-preemptive. Shortest burst time goes first.
- Optimal average waiting time among non-preemptive
- Problem: starvation of long processes, burst time not known in advance
SRTF (Shortest Remaining Time First)
- Preemptive version of SJF
- Optimal average waiting time among ALL algorithms
- Higher context switch overhead
Round Robin (RR)
- Preemptive. Each process gets time quantum q.
- If q → ∞: behaves like FCFS. If q → 0: processor sharing
- Good response time, suitable for time-sharing
- Higher q → less context switch but worse response time
Priority Scheduling
- Lower number = higher priority (convention varies)
- Preemptive or non-preemptive variant
- Problem: starvation → solution: aging (gradually increase priority of waiting processes)
Multilevel Queue
- Ready queue divided into separate queues (foreground, background)
- Each queue has its own scheduling algorithm
- No movement between queues
Multilevel Feedback Queue (MLFQ)
- Processes can move between queues
- I/O bound and short processes promoted to higher queues
- Most flexible, most complex - used in practice
4. Scheduling Criteria Comparison
| Algorithm | Preemptive | Starvation | Overhead | Best For |
|---|---|---|---|---|
| FCFS | No | No | Low | Batch |
| SJF | No | Yes | Low | Batch (known BT) |
| SRTF | Yes | Yes | High | Optimal WT |
| RR | Yes | No | Medium | Time-sharing |
| Priority | Both | Yes | Low | Real-time |
5. Formulas
- TAT = CT − AT
- WT = TAT − BT
- Average WT = Σ WT / n
- CPU Utilization = CPU busy time / Total time
- Throughput = processes completed / unit time
6. GATE Trick
SRTF gives minimum average waiting time - always. For RR, draw Gantt chart carefully tracking quantum expiry and new arrivals. If processes arrive at same time in SJF, break tie by process ID or order given. Aging prevents starvation in priority scheduling - examiner often asks what prevents starvation.