Process Scheduling Algorithms

In a multitasking operating system, the CPU scheduler plays a critical role in deciding which process gets to use the CPU next. This decision is based on scheduling algorithms that aim to balance fairness, efficiency, response time, and system throughput.

Let’s explore the most widely used CPU scheduling algorithms, along with the tools to measure their effectiveness.

Common Scheduling Algorithms

1. FCFS – First Come, First Served

• Concept: Processes are executed in the order they arrive.
• Type: Non-preemptive
• Advantage: Simple and easy to implement.
• Limitation: Can lead to convoy effect, where shorter processes wait behind longer ones.

2. SJF – Shortest Job First

• Concept: The process with the shortest burst time (CPU time) is scheduled first.
• Types:

• • Non-preemptive: Once a process starts, it runs till completion.

  • Preemptive (also known as Shortest Remaining Time First): The running process can be interrupted if a new process with a shorter burst time arrives.

• Advantage: Reduces average waiting time.
• Limitation: Requires knowledge of future burst times, which is not always possible.

3. Round Robin

• Concept: Each process gets a fixed time slice (quantum). After its time expires, it goes to the back of the queue.
• Type: Preemptive
• Advantage: Ensures fairness and responsiveness.
• Best suited for: Time-sharing systems.
• Limitation: Performance depends heavily on the chosen time quantum.

4. Priority Scheduling

• Concept: Processes are assigned priorities, and the highest-priority process is scheduled first.
• Types:

  • Preemptive: Can interrupt a lower-priority process.

  • Non-preemptive: Waits until the running process finishes.

• Advantage: Useful for differentiating critical tasks.
• Limitation: Can cause starvation of low-priority processes. Solution: Aging (gradually increasing priority of waiting processes).

Evaluating Scheduling Performance

To assess how efficient a scheduling algorithm is, we use Gantt charts and calculate key timing metrics:

1. Gantt Chart

• A visual representation of how processes are scheduled over time.
• Shows when each process starts and ends execution.
• Helps visualize the scheduling order and CPU idle times.

2. Waiting Time

• Time a process spends in the ready queue before it gets the CPU.
• Formula:
  Waiting Time = Turnaround Time - Burst Time

3. Turnaround Time

• Total time taken from process arrival to its completion.
• Formula:
  Turnaround Time = Completion Time - Arrival Time

These values are averaged over all processes to compare scheduling strategies.

Example Illustration (Conceptual)

Suppose we have 3 processes with the following burst times:

• P1: 5ms
• P2: 3ms
• P3: 1ms

In FCFS, the order might be P1 → P2 → P3.
In SJF, the order becomes P3 → P2 → P1.

This switch can significantly change the average waiting and turnaround times, demonstrating the impact of algorithm choice.

Summary

Process scheduling is a core function of the OS, ensuring all processes get CPU time in an orderly, efficient, and fair manner. Different scheduling algorithms suit different goals—from minimizing wait time to ensuring responsiveness. Understanding and evaluating these methods using Gantt charts and time metrics helps in selecting the right strategy for a given system.