CPU Scheduling Algorithms Solved with Gantt Charts: FCFS, SJF, SRTF, Priority & Round Robin for TU BCA

Author: Bhuban Subedi | Subject: Operating Systems (CACS251) | Semester: Fourth Semester

In a multiprogramming operating system, the CPU is the most critical computing resource. When multiple processes reside in the Ready Queue waiting for execution, the OS CPU Scheduler (Short-Term Scheduler) must decide which process gets allocated the CPU and for how long.

In the Tribhuvan University (TU) BCA Fourth Semester Operating Systems (CACS251) board examination, a comprehensive CPU Scheduling numerical problem carrying 8 to 10 full marks is guaranteed in every exam paper.

In this guide, we will define all key scheduling metrics, explain Preemptive vs Non-Preemptive execution, construct Gantt Charts, and solve past TU examination problems step-by-step.

1. Fundamental CPU Scheduling Metrics & Formulas

Before drawing Gantt charts, you must memorize these five standard formulas:

+------------------------------------+---------------------------------------------------------------+
| Metric                             | Formula & Mathematical Definition                             |
+------------------------------------+---------------------------------------------------------------+
| **Arrival Time (AT)**              | The exact time instance when a process enters the Ready Queue.|
+------------------------------------+---------------------------------------------------------------+
| **Burst Time (BT)**                | Total CPU execution time required by the process.             |
+------------------------------------+---------------------------------------------------------------+
| **Completion Time (CT)**           | The exact time instance when the process completes execution. |
+------------------------------------+---------------------------------------------------------------+
| **Turnaround Time (TAT)**          | $\mathbf{TAT = CT - AT}$ (Total time spent in the system).    |
+------------------------------------+---------------------------------------------------------------+
| **Waiting Time (WT)**              | $\mathbf{WT = TAT - BT}$ (Total time spent waiting in Ready Q)|
+------------------------------------+---------------------------------------------------------------+
| **Average Waiting Time (Avg WT)**  | $\mathbf{\text{Avg } WT = \frac{\sum WT}{\text{Total Processes}}}$ |
+------------------------------------+---------------------------------------------------------------+

2. Preemptive vs. Non-Preemptive Scheduling

+------------------------------------+------------------------------------+
| Non-Preemptive Scheduling          | Preemptive Scheduling              |
+------------------------------------+------------------------------------+
| Once the CPU is allocated to a     | The CPU can be interrupted and     |
| process, it holds the CPU until it | preempted if a higher-priority or  |
| terminates or requests I/O.        | shorter process enters Ready Queue.|
+------------------------------------+------------------------------------+
| Simpler design, zero context-switch| Responsive, but introduces higher  |
| overhead during execution.         | context-switching overhead.        |
+------------------------------------+------------------------------------+
| Examples: FCFS, Non-Preemptive SJF.| Examples: SRTF, Round Robin, Pri.  |
+------------------------------------+------------------------------------+

3. Solved Numerical: Past TU Board Exam Question

The Problem:

“Consider the following set of 4 processes with their Arrival Times and Burst Times (in milliseconds):

Process	Arrival Time (AT)	Burst Time (BT)
P1	0	8
P2	1	4
P3	2	9
P4	3	5

Draw Gantt Charts and calculate the Average Waiting Time (AWT) and Average Turnaround Time (ATAT) for:
1. First-Come, First-Served (FCFS)
2. Shortest Job First (SJF – Non-Preemptive)
3. Round Robin (Time Quantum = 4 ms)” (TU BCA 10 Marks)

Algorithm 1: First-Come, First-Served (FCFS)

In FCFS, processes are served strictly in order of their arrival ($P1 \to P2 \to P3 \to P4$).

Gantt Chart:

+--------+--------+--------+--------+
|   P1   |   P2   |   P3   |   P4   |
+--------+--------+--------+--------+
0        8        12       21       26

Calculation Table:

+---------+----+----+----+-------------+------------+
| Process | AT | BT | CT | TAT (CT-AT) | WT (TAT-BT)|
+---------+----+----+----+-------------+------------+
| **P1**  | 0  | 8  | 8  | 8 - 0 = 8   | 8 - 8 = 0  |
| **P2**  | 1  | 4  | 12 | 12 - 1 = 11 | 11 - 4 = 7 |
| **P3**  | 2  | 9  | 21 | 21 - 2 = 19 | 19 - 9 = 10|
| **P4**  | 3  | 5  | 26 | 26 - 3 = 23 | 23 - 5 = 18|
+---------+----+----+----+-------------+------------+

$$\mathbf{Average\ Turnaround\ Time\ (ATAT)} = \frac{8 + 11 + 19 + 23}{4} = \frac{61}{4} = \mathbf{15.25\ ms}$$
$$\mathbf{Average\ Waiting\ Time\ (AWT)} = \frac{0 + 7 + 10 + 18}{4} = \frac{35}{4} = \mathbf{8.75\ ms}$$

Algorithm 2: Shortest Job First (SJF – Non-Preemptive)

1. At $t = 0$, only P1 has arrived $\implies$ P1 runs until completion ($t = 8$).
2. At $t = 8$, processes P2 (BT=4), P3 (BT=9), and P4 (BT=5) have all arrived.
3. Compare remaining burst times: $P2 (4) < P4 (5) < P3 (9)$.
4. Execution Order: $P1 \to P2 \to P4 \to P3$.

Gantt Chart:

+--------+--------+--------+--------+
|   P1   |   P2   |   P4   |   P3   |
+--------+--------+--------+--------+
0        8        12       17       26

Calculation Table:

+---------+----+----+----+-------------+------------+
| Process | AT | BT | CT | TAT (CT-AT) | WT (TAT-BT)|
+---------+----+----+----+-------------+------------+
| **P1**  | 0  | 8  | 8  | 8 - 0 = 8   | 8 - 8 = 0  |
| **P2**  | 1  | 4  | 12 | 12 - 1 = 11 | 11 - 4 = 7 |
| **P4**  | 3  | 5  | 17 | 17 - 3 = 14 | 14 - 5 = 9 |
| **P3**  | 2  | 9  | 26 | 26 - 2 = 24 | 24 - 9 = 15|
+---------+----+----+----+-------------+------------+

$$\mathbf{Average\ Turnaround\ Time\ (ATAT)} = \frac{8 + 11 + 14 + 24}{4} = \frac{57}{4} = \mathbf{14.25\ ms}$$
$$\mathbf{Average\ Waiting\ Time\ (AWT)} = \frac{0 + 7 + 9 + 15}{4} = \frac{31}{4} = \mathbf{7.75\ ms}$$

Algorithm 3: Round Robin (Time Quantum $TQ = 4\text{ ms}$)

Execution Trace:

• $0 – 4$: P1 executes 4 ms (Remaining BT: 4). Ready Q: P2, P3, P4, P1.
• $4 – 8$: P2 executes 4 ms $\implies$ P2 finishes at $t=8$.
• $8 – 12$: P3 executes 4 ms (Remaining BT: 5). Ready Q: P4, P1, P3.
• $12 – 16$: P4 executes 4 ms (Remaining BT: 1). Ready Q: P1, P3, P4.
• $16 – 20$: P1 executes 4 ms $\implies$ P1 finishes at $t=20$.
• $20 – 24$: P3 executes 4 ms (Remaining BT: 1). Ready Q: P4, P3.
• $24 – 25$: P4 executes 1 ms $\implies$ P4 finishes at $t=25$.
• $25 – 26$: P3 executes 1 ms $\implies$ P3 finishes at $t=26$.

Gantt Chart:

+----+----+----+----+----+----+----+----+
| P1 | P2 | P3 | P4 | P1 | P3 | P4 | P3 |
+----+----+----+----+----+----+----+----+
0    4    8    12   16   20   24   25   26

Final Results Table:

+---------+----+----+----+-------------+------------+
| Process | AT | BT | CT | TAT (CT-AT) | WT (TAT-BT)|
+---------+----+----+----+-------------+------------+
| **P1**  | 0  | 8  | 20 | 20 - 0 = 20 | 20 - 8 = 12|
| **P2**  | 1  | 4  | 8  | 8 - 1 = 7   | 7 - 4 = 3  |
| **P3**  | 2  | 9  | 26 | 26 - 2 = 24 | 24 - 9 = 15|
| **P4**  | 3  | 5  | 25 | 25 - 3 = 22 | 22 - 5 = 17|
+---------+----+----+----+-------------+------------+

$$\mathbf{Average\ Turnaround\ Time\ (ATAT)} = \frac{20 + 7 + 24 + 22}{4} = \frac{73}{4} = \mathbf{18.25\ ms}$$
$$\mathbf{Average\ Waiting\ Time\ (AWT)} = \frac{12 + 3 + 15 + 17}{4} = \frac{47}{4} = \mathbf{11.75\ ms}$$

Frequently Asked Questions (FAQ)

Q1: What is the Convoy Effect in FCFS?

The Convoy Effect occurs when a CPU-bound process with a huge burst time holds the CPU, forcing many small I/O-bound processes to wait for long periods, severely degrading overall system throughput.

Q2: What is Starvation and how does Aging solve it?

In Priority and SJF scheduling, a long or low-priority process may wait indefinitely if shorter/higher-priority jobs keep arriving (Starvation). Aging gradually increases the priority of processes as they wait in the ready queue, ensuring eventual execution.