Process Scheduling Performance Analysis

The Language of Scheduling: Key Metrics

Before we dive into the algorithms, we must define the terms we'll use to measure their performance. For any given set of processes, you'll typically be provided with:

• Process ID: A unique identifier for the process.
• Arrival Time (AT): The time at which the process enters the ready queue, becoming available for execution.
• Burst Time (BT): The total amount of CPU time the process requires to complete its execution.

From these, we will calculate:

• Completion Time (CT): The time at which the process finishes its execution.
• Turnaround Time (TAT): The total time a process spends in the system, from arrival to completion. It's the measure of total time spent, including both waiting and running.
  $\text{TAT}=\text{CT}-\text{AT}$
• Waiting Time (WT): The total time a process spends in the ready queue waiting for its turn on the CPU.
  $\text{WT}=\text{TAT}-\text{BT}$
• Response Time (RT): The time from a process's arrival until it gets the CPU for the first time. This is particularly important for interactive systems.
  $\text{RT}=(\text{Time of first CPU allocation})-\text{AT}$

Our primary tool for solving these problems will be the Gantt Chart, a timeline diagram that illustrates which process is running on the CPU at any given moment.

A crucial distinction that applies to most scheduling algorithms is their mode:

• Non-Preemptive: Once a process is given the CPU, it runs to completion without interruption.
• Preemptive: A running process can be interrupted (preempted) and moved back to the ready queue if a higher-priority process arrives or its time slice expires.

Let's begin with the simplest algorithm.

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

As the name suggests, FCFS is a non-preemptive algorithm that processes jobs in the order they arrive. It's analogous to a queue at a ticket counter.

• Criterion: Arrival Time.
• Mode: Non-preemptive.

The main advantage of FCFS is its simplicity. However, it can suffer from the convoy effect, where a short process gets stuck waiting behind a very long process, leading to poor average waiting times.

The following video provides a clear, step-by-step walkthrough of an FCFS problem, exactly like one you might see in the GATE exam.

2. Shortest Job First (SJF) Scheduling

SJF prioritizes processes with the shortest burst times. This algorithm is provably optimal in terms of minimizing the average waiting time. However, its pure form requires knowing the future (the burst time), which is not always possible in real systems. It comes in two flavors.

a) Non-Preemptive SJF

Once a process starts, it runs to completion. When the CPU becomes free, the scheduler selects the process from the ready queue with the smallest burst time.

• Criterion: Burst Time.
• Mode: Non-preemptive.
• Tie-breaker: If two processes have the same burst time, FCFS is used.

Example: Consider the following processes:

Gantt Chart:

1. At time t=0, only P1 is in the ready queue. We must run it.
2. P1 runs from t=0 to t=7.
3. At t=7, the CPU is free. Processes P2, P3, and P4 have all arrived. We check their burst times: P2(4), P3(1), P4(4).
4. P3 has the shortest burst time (1). So, P3 runs from t=7 to t=8.
5. At t=8, the CPU is free. P2 and P4 are remaining, both with burst time 4. We use FCFS as a tie-breaker. P2 arrived before P4, so P2 runs next.
6. P2 runs from t=8 to t=12.
7. P4 runs from t=12 to t=16.

The final Gantt Chart is: | P1 (0-7) | P3 (7-8) | P2 (8-12) | P4 (12-16) |

You can then calculate TAT and WT for each process and find the average.

b) Preemptive SJF (Shortest Remaining Time First - SRTF)

This is the preemptive version. The scheduler always chooses the process with the shortest remaining burst time. A running process can be preempted if a new process arrives with a burst time shorter than the current process's remaining time.

• Criterion: Remaining Burst Time.
• Mode: Preemptive.

SRTF problems require careful, step-by-step tracking at every time unit where an event (a process arrival or completion) occurs. This makes them a GATE favorite.

3. Priority Scheduling

In Priority Scheduling, a priority is associated with each process. The CPU is allocated to the process with the highest priority. Like SJF, it can be preemptive or non-preemptive. A common convention in GATE is that a lower number implies higher priority.

• Criterion: Priority.
• Mode: Preemptive or Non-preemptive.
• Tie-breaker: If priorities are equal, use FCFS.

A major problem with priority scheduling is starvation, where low-priority processes may never execute. A solution is aging, where the priority of a process increases gradually over time.

Example (Preemptive Priority):

Gantt Chart:

1. At t=0, only P1 is available. P1 starts running.
2. At t=1, P2 arrives. P2's priority (1) is higher than P1's (2). P1 is preempted (remaining BT=3). P2 starts running.
3. P2 runs from t=1 to t=2 and completes.
4. At t=2, the ready queue has P1 (Priority 2). P3 also arrives (Priority 3). P1 has higher priority, so P1 resumes.
5. At t=3, P1 is running. P4 arrives. P4's priority (1) is higher than P1's (2). P1 is preempted again (remaining BT=2). P4 starts running.
6. P4 runs from t=3 to t=5 and completes.
7. At t=5, the ready queue has P1 (Priority 2, remaining BT=2) and P3 (Priority 3, BT=5). P1 has higher priority and resumes.
8. P1 runs from t=5 to t=7 and completes.
9. Finally, P3 runs from t=7 to t=12.

Gantt Chart: | P1(0-1) | P2(1-2) | P1(2-3) | P4(3-5) | P1(5-7) | P3(7-12) |

4. Round Robin (RR) Scheduling

Round Robin is a preemptive algorithm designed for time-sharing systems. Each process gets a small unit of CPU time, a time quantum (or time slice), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.

• Criterion: Time Slice.
• Mode: Preemptive.

If the time quantum is very large, RR behaves like FCFS. If it's very small, the overhead from frequent context switches can degrade performance.

Example (Time Quantum q=2):

Gantt Chart:

• t=0-2: P1 runs for 2 units. P1 is preempted (remaining BT=3) and goes to the back of the queue. Ready Queue: [P2, P3, P1]
• t=2-4: P2 runs. It arrived at t=1, P3 at t=2. P2 runs for 2 units, preempted (remaining BT=1). Ready Queue: [P3, P1, P2]
• t=4-6: P3 runs for 2 units, preempted (remaining BT=2). Ready Queue: [P1, P2, P3]
• t=6-8: P1 runs for 2 units, preempted (remaining BT=1). Ready Queue: [P2, P3, P1]
• t=8-9: P2 runs for 1 unit and completes. Ready Queue: [P3, P1]
• t=9-11: P3 runs for 2 units and completes. Ready Queue: [P1]
• t=11-12: P1 runs for 1 unit and completes.

Gantt Chart: | P1(0-2) | P2(2-4) | P3(4-6) | P1(6-8) | P2(8-9) | P3(9-11) | P1(11-12) |

Summary of Key Takeaways

You have now learned the mechanics of four fundamental CPU scheduling algorithms, a high-yield topic for GATE.

• Gantt Chart is Key: Always start by drawing the Gantt chart. It is the single source of truth from which all metrics can be derived.
• Preemption vs. Non-preemption: This is the most important distinction. In preemptive algorithms (SRTF, Preemptive Priority, RR), you must re-evaluate the scheduling decision whenever a new process arrives.
• Formulas are Simple: The calculations for TAT and WT are straightforward once you have the Completion Times from the Gantt chart. The complexity lies in creating the Gantt chart correctly.
• Practice is Everything: The only way to master these is by solving numerous numerical problems. Pay attention to arrival times and tie-breaking rules.

In our next lesson, we will move from managing time to managing space. We will explore Memory Management, another core OS function. We'll delve into concepts like paging, segmentation, and the crucial idea of virtual memory, which allows processes to be larger than the physical RAM available.