Detailed Algorithms (with Numerical Problems)

CPU scheduling determines which process gets the CPU next when multiple processes are in the ready queue. Scheduling algorithms aim to maximize CPU utilization, reduce waiting time, and improve system responsiveness.

This section explores the five fundamental scheduling algorithms, explains their logic, and includes sample numerical problems to help students understand how these algorithms work in practice.

1. First-Come, First-Served (FCFS)

Definition: Processes are scheduled in the order they arrive. It’s a non-preemptive algorithm—once the CPU is allocated, the process runs to completion.

Example:
Consider 3 processes with the following burst times:

Waiting Time (WT):

• P1: 0
• P2: 5 – 1 = 4
• P3: 8 – 2 = 6

Average Waiting Time = (0 + 4 + 6) / 3 = 3.33 ms

2. Shortest Job First (SJF) — Non-Preemptive

Definition: The process with the shortest burst time is selected next. If arrival times differ, only processes that have already arrived are considered.

Example:

Waiting Time:

• P1: 0
• P3: 6 – 2 = 4
• P2: 8 – 1 = 7

Average WT = (0 + 4 + 7) / 3 = 3.67 ms

3. Shortest Remaining Time First (SRTF) — Preemptive

Definition: Similar to SJF, but preemptive. A process can be interrupted if a new process arrives with a shorter burst time remaining.

Example:

• At time 0: P1 starts
• At time 1: P2 arrives (shorter burst), preempts P1
• At time 2: P3 arrives (shortest), preempts P2
• Continue execution accordingly

Gantt Chart:

Calculate Waiting Time using Completion Time – Arrival Time – Burst Time

4. Round Robin (RR)

Definition: Each process is assigned a fixed time slice (quantum). If a process does not complete within its quantum, it’s added back to the queue.

Example:

Execution Order:

Waiting Time:

• P1: (6 – 0) + (9 – 6) = 9
• P2: (4 – 1) + (10 – 6) = 7
• P3: 4 – 2 = 2

Average WT = (9 + 7 + 2) / 3 = 6 ms

5. Priority Scheduling (Preemptive or Non-preemptive)

Definition: Processes are scheduled based on priority. Lower number = higher priority.

Waiting Time:

• P1: (1-0) + (4-1) = 4
• P2: 1 – 1 = 0
• P3: 7 – 2 = 5

Average WT = (4 + 0 + 5) / 3 = 3 ms

Summary