CPU Scheduling Algorithms: FCFS, SJF, SRTN, Round Robin & Priority

1. Overview of Classical CPU Scheduling Algorithms

In DAVV BCA exams, Unit 2 always includes an 8-mark theory + Gantt chart numerical question on these five core CPU scheduling algorithms:

2. First-Come, First-Served (FCFS) Scheduling

• Mode: Strictly Non-Preemptive.
• How It Works: The simplest scheduling algorithm. Whichever process requests the CPU first is allocated the CPU first (just like a queue at a railway ticket counter). Implemented using a standard FIFO (First-In, First-Out) queue.
• Major Drawback — The Convoy Effect: If one huge CPU-bound process (e.g., Burst Time = 100 ms) arrives first, followed by 5 tiny processes (Burst Time = 1 ms each), all 5 tiny processes get stuck waiting behind the giant process! This causes the average waiting time to skyrocket and is called the Convoy Effect.

Solved Numerical Example (FCFS):

Suppose 3 processes arrive at time AT = 0 in the order P1, P2, P3:

• Gantt Chart: | P1 (0–24) | P2 (24–27) | P3 (27–30) |
• Average Waiting Time: (0 + 24 + 27 / 3) = 17.0 ms
• Average Turnaround Time: (24 + 27 + 30 / 3) = 27.0 ms

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

• Mode: Non-Preemptive.
• How It Works: Among all available processes in the Ready Queue, the CPU is assigned to the process that has the smallest (shortest) next CPU Burst Time. If two processes have the exact same burst time, FCFS is used to break the tie.
• Key Advantage: SJF is mathematically proven to be Optimal—it gives the minimum possible Average Waiting Time for a given set of processes!
• Disadvantage: In practice, it is difficult to know the exact future CPU burst length of a process in advance, and long processes may suffer from Starvation if short jobs keep arriving.

Solved Numerical Example (Non-Preemptive SJF):

Using the exact same 3 processes (P1 = 24 ms, P2 = 3 ms, P3 = 3 ms) arriving at AT = 0, SJF runs the shortest jobs (P2, P3) first!

• Gantt Chart: | P2 (0–3) | P3 (3–6) | P1 (6–30) |
• Waiting Times: P2 = 0 ms, P3 = 3 ms, P1 = 6 ms.
• Average Waiting Time: (0 + 3 + 6 / 3) = 3.0 ms (Dropped from 17 ms in FCFS down to just 3 ms!)

4. Shortest Remaining Time Next (SRTN / SRTF)

• Mode: Preemptive version of SJF!
• How It Works: At any moment, the CPU executes the process with the shortest remaining burst time.
• Whenever a new process arrives in the Ready Queue, the scheduler compares its Burst Time with the remaining time of the currently running process. If the newly arrived process requires less time than what is left of the current process, the OS immediately preempts (interrupts) the current process and gives the CPU to the new shorter process!

Solved Numerical Example (SRTN):

• Step-by-Step Execution & Gantt Chart:
  • At t=0: Only P1 is present (BT=8). P1 starts running.
  • At t=1: P2 arrives with BT=4, while P1 still has 7 ms remaining! Since 4 < 7, P1 is preempted and P2 runs from 1 to 5.
  • At t=5: P2 finishes. Remaining times: P1=7, P3=9, P4=5. Shortest is P4 (5 ms), so P4 runs from 5 to 10, then P1 (10 to 17), then P3 (17 to 26).
  • Gantt Chart: | P1 (0–1) | P2 (1–5) | P4 (5–10) | P1 (10–17) | P3 (17–26) |
• Average Waiting Time: (9 + 0 + 15 + 2 / 4) = 6.5 ms

5. Round Robin (RR) Scheduling

• Mode: Preemptive (Designed specifically for Time-Sharing Systems).
• How It Works:
  1. A small fixed unit of time called a Time Quantum (q) or Time Slice (typically 10 ms to 100 ms) is defined.
  2. The Ready Queue is treated as a circular FIFO queue.
  3. The scheduler gives the first process in the queue the CPU for at most 1 Time Quantum. If the process’s burst time is still not finished when the timer goes off, the process is preempted and placed at the tail (back) of the Ready Queue, and the next process gets its turn!
• Effect of Time Quantum Size:
  • If Time Quantum is too large (∞): Round Robin degenerates into simple FCFS.
  • If Time Quantum is too small (1 ms): Causes excessive Context Switch Overhead, slowing down the CPU.

Solved Numerical Example (Round Robin with Time Quantum q = 4 ms):

Processes arriving at AT = 0: P1 (BT = 10 ms), P2 (BT = 4 ms), P3 (BT = 5 ms).

• Gantt Chart (q = 4): | P1 (0–4) | P2 (4–8) | P3 (8–12) | P1 (12–16) | P3 (16–17) | P1 (17–19) |
• Completion Times: P2 = 8, P3 = 17, P1 = 19.
• Waiting Times (CT - BT):
  • P1 = 19 - 10 = 9 ms
  • P2 = 8 - 4 = 4 ms
  • P3 = 17 - 5 = 12 ms
• Average Waiting Time: (9 + 4 + 12 / 3) = 8.33 ms

6. Priority Scheduling (Starvation & Aging)

• Mode: Can be either Preemptive or Non-Preemptive.
• How It Works: A Priority Number (an integer) is associated with each process, and the CPU is allocated to the process with the Highest Priority (e.g., Priority 1 = Highest). Equal-priority processes are scheduled in FCFS order.
• Major Problem — Starvation (Indefinite Blocking): In a heavily loaded system where high-priority processes keep arriving continuously, a low-priority process may wait in the Ready Queue forever and never get the CPU! This is called Starvation.
• The Solution — Aging: Aging is a technique that gradually increases the priority of processes that have been waiting in the system for a long time (e.g., increasing a waiting process’s priority by +1 every 15 minutes). Eventually, even the lowest-priority process reaches top priority and gets executed!

💡 Exam Preparation Tips for DAVV BCA

• Always draw a Gantt Chart in every CPU scheduling answer—even in a theory question! A 1-line Gantt chart with timestamps (0...4...8...) guarantees full marks.
• Memorize these two pairs of Problem → Solution for 2-mark/viva questions:
  • FCFS Problem: Convoy Effect (short processes stuck behind a huge process).
  • Priority/SJF Problem: Starvation → Solved by Aging!