Scheduling Algorithms

This lesson covers the CPU scheduling algorithms required by the OCR H446 specification. The OS scheduler decides which process gets the CPU and for how long. You must understand how each algorithm works, its advantages and disadvantages, and when each is appropriate.

---

Why Scheduling Is Needed

In a multi-tasking system, multiple processes compete for CPU time. The scheduler decides the order in which processes are executed. Good scheduling aims to:

Goal	Explanation
Maximise CPU utilisation	Keep the CPU busy as much as possible
Maximise throughput	Complete as many processes as possible per unit of time
Minimise waiting time	Reduce the time processes spend in the ready queue
Minimise response time	Reduce the delay between a user action and the system's response
Fairness	Ensure every process gets a reasonable share of CPU time

---

Preemptive vs Non-Preemptive Scheduling

Type	Description
Non-preemptive	Once a process starts executing, it runs until it finishes or voluntarily gives up the CPU (e.g. for I/O). The scheduler cannot interrupt it
Preemptive	The scheduler can interrupt a running process and move it back to the ready queue to give the CPU to another process. This allows fairer sharing of CPU time

---

First Come First Served (FCFS)

Aspect	Detail
Type	Non-preemptive
Rule	Processes are executed in the order they arrive in the ready queue
Data structure	Simple FIFO queue

Worked Example

Process	Arrival Time	Burst Time
P1	0	6
P2	1	3
P3	2	8
P4	3	4

Timeline: |--P1--|--P2--|----P3----|--P4--|
          0     6     9         17    21

Process	Waiting Time	Turnaround Time
P1	0	6
P2	5	8
P3	7	15
P4	14	18
Average	6.5	11.75

Advantages and Disadvantages

Advantages	Disadvantages
Very simple to implement	Convoy effect — short processes wait behind long ones
No starvation — every process eventually runs	Poor average waiting time
No overhead from context switching	Not suitable for interactive or time-sharing systems

---

Shortest Job First (SJF)

Aspect	Detail
Type	Non-preemptive
Rule	The process with the shortest burst time in the ready queue is executed next

Worked Example (same processes)

Timeline: |--P1--|--P2--|--P4--|----P3----|
          0     6     9     13        21

Process	Waiting Time	Turnaround Time
P1	0	6
P2	5	8
P4	10	14
P3	11	19
Average	6.5	11.75

Advantages and Disadvantages

Advantages	Disadvantages
Optimal average waiting time for non-preemptive scheduling	Requires knowledge of burst times in advance (often estimated)
Reduces the convoy effect	Starvation — long processes may never run if shorter ones keep arriving
Good for batch systems	Not practical for interactive systems

---

Shortest Remaining Time (SRT)

Aspect	Detail
Type	Preemptive (preemptive version of SJF)
Rule	When a new process arrives, if its burst time is shorter than the remaining time of the currently running process, the current process is preempted

Worked Example

Process	Arrival Time	Burst Time
P1	0	6
P2	1	3
P3	2	8
P4	3	4

Timeline: |P1|--P2--|--P4--|----P1----|----P3----|
          0  1     4     8        13        21

At time 1: P2 arrives (remaining 3) < P1 remaining (5). P1 preempted. At time 2: P3 arrives (remaining 8) > P2 remaining (2). P2 continues. At time 3: P4 arrives (remaining 4) > P2 remaining (1). P2 continues. At time 4: P2 finishes. P4 (4) < P1 (5) < P3 (8). P4 runs. At time 8: P4 finishes. P1 (5) < P3 (8). P1 runs. At time 13: P1 finishes. P3 runs.

Advantages and Disadvantages

Advantages	Disadvantages
Optimal average waiting time overall	High overhead from frequent context switching
Better response time than SJF	Starvation of long processes
Good for time-sharing systems	Must estimate remaining burst times

---

Round Robin (RR)