Day 3 – CPU Scheduling

1. What is CPU Scheduling?

The method used by the OS to decide which process gets the CPU next when multiple processes are in the ready queue.

2. CPU Scheduling Types

Preemptive – CPU can be taken away from a process before completion.
Non-Preemptive – CPU is given until the process finishes or voluntarily releases it.

3. Scheduling Criteria

CPU Utilization – Keep CPU busy.
Throughput – Number of processes completed per unit time.
Turnaround Time (TAT) – Time from process submission to completion.
```
TAT = Completion Time - Arrival Time
```
Waiting Time (WT) – Time spent in ready queue.
```
WT = TAT - Burst Time
```
Response Time – Time from submission to first CPU allocation.

4. Common Scheduling Algorithms

(1) First Come First Serve (FCFS)

Non-preemptive.
Processes served in order of arrival.

Example:
Processes: P1(5), P2(3), P3(8) (Burst Times, Arrival Time = 0)


Order: P1 → P2 → P3  
TAT: P1=5, P2=8, P3=16  
WT:  P1=0, P2=5, P3=8

(2) Shortest Job First (SJF)

Picks process with smallest burst time.
Can be preemptive (SRTF) or non-preemptive.

(3) Priority Scheduling

Highest priority first.
May be preemptive or non-preemptive.

(4) Round Robin (RR)

Preemptive.
Fixed time slice (quantum).
Fair allocation.

(5) Multilevel Queue Scheduling

Different queues for different priority types.

5. Example – Round Robin (RR)

Time Quantum = 4
Processes: P1(6), P2(8), P3(7) (All arrival time 0)

Execution order:


P1(4) → P2(4) → P3(4) → P1(2) → P2(4) → P3(3)

Practice Questions with Answers

Q1. Which scheduling algorithm can cause starvation?

Answer: SJF and Priority Scheduling (non-preemptive).

Q2. Which scheduling gives minimum average waiting time?

Answer: SJF (non-preemptive).

Q3. In Round Robin, what happens if the time quantum is too large?

Answer: It behaves like FCFS.

Q4. In Round Robin, what happens if the time quantum is too small?

Answer: More context switching → less CPU efficiency.

Q5. Which scheduling is fair for all processes?

Answer: Round Robin.

Q6. Define Turnaround Time formula.

Answer:


TAT = Completion Time – Arrival Time

Q7. Define Waiting Time formula.