Process Scheduling

In a modern multitasking operating system, the CPU is the most precious and high-speed resource. However, a fundamental

In a modern multitasking operating system, the CPU is the most precious and high-speed resource. However, a fundamental bottleneck exists: CPU processing speeds vastly outpace the speed of I/O devices, and a single CPU core can typically execute only one instruction stream at any given moment. To prevent the processor from sitting idle while waiting for slow I/O operations, the operating system employs a mechanism known as Process Scheduling.

The fundamental mission of the scheduler is to act as a sophisticated traffic controller, deciding which process gains access to the CPU, for how long, and in what order. By doing so, it aims to maximize CPU utilization, increase system throughput, and minimize response times to ensure a seamless user experience.
To determine the efficiency of a scheduling algorithm, several key performance indicators are used:

  • CPU Utilization: The percentage of time the CPU is actively performing useful work. High utilization is a primary goal in batch processing systems.
  • Throughput: The number of processes completed per unit of time. This measures the overall productivity of the system.
  • Turnaround Time: The total interval from the moment a process is submitted to the moment it is fully completed.
  • Waiting Time: The cumulative amount of time a process spends sitting in the ready queue, waiting for its turn to execute.
  • Response Time: The duration between a request being submitted and the first response being produced. This is the most critical metric for interactive, user-facing systems.

The Three Levels of Scheduling

Scheduling does not happen at a single layer; rather, it is categorized into three distinct types based on the timing and the scope of the decisions made:

1. High-Level Scheduling (Long-Term Scheduler)

The long-term scheduler determines which jobs are admitted into the system to be transformed into processes in memory. Its primary responsibility is to control the degree of multiprogramming—the number of processes residing in memory at once. A delicate balance is required here: admitting too many CPU-intensive processes can lead to system congestion and sluggishness, while admitting too few results in underutilized hardware.

2. Low-Level Scheduling (Short-Term Scheduler)

This is the most frequent and critical operation in the operating system. The short-term scheduler selects a process from the ready queue and allocates the CPU to it. Because this happens millions of times per second, the algorithm must be exceptionally fast and efficient to minimize overhead.

3. Medium-Term Scheduling (Memory Scheduler)

Medium-term scheduling manages the balance between memory usage and CPU efficiency through a process called swapping. When memory becomes overcommitted, the medium-term scheduler moves inactive or blocked processes from the main memory to the disk (placing them in a "suspended" state). These processes are later swapped back into memory when resources become available, helping to alleviate memory pressure.

Common Scheduling Algorithms

Scheduling strategies are generally classified into two categories: Non-preemptive (where a process holds the CPU until it terminates or blocks for I/O) and Preemptive (where the OS can forcibly interrupt a running process to give the CPU to another).

First-Come, First-Served (FCFS)

The simplest approach, FCFS, processes tasks in the exact order they arrive in the ready queue.

  • Type: Non-preemptive.
  • The Downside: It is highly susceptible to the Convoy Effect. If a single, massive, CPU-bound process arrives first, all subsequent short processes are stuck waiting behind it, drastically increasing the average waiting time.

Shortest Job First (SJF)

This algorithm prioritizes processes with the smallest upcoming execution time.

  • Type: Can be non-preemptive or preemptive (the latter is known as Shortest Remaining Time First or SRTF).
  • The Benefit: It is theoretically optimal for minimizing the average waiting time.
  • The Downside: It is difficult to predict exactly how long a process will run. Furthermore, long processes may suffer from starvation, where they are perpetually bypassed by newer, shorter tasks.

Priority Scheduling

Each process is assigned a priority level, and the CPU is allocated to the process with the highest priority.

  • The Benefit: It allows the system to prioritize critical tasks or real-time processes.
  • The Solution to Starvation: To prevent low-priority processes from waiting indefinitely, systems use a technique called Aging. This involves gradually increasing the priority of a process the longer it remains in the waiting queue.

Round Robin (RR)

Designed specifically for time-sharing systems, RR assigns each process a fixed time interval called a Time Quantum.

  • Type: Preemptive. Once the quantum expires, the process is moved to the back of the ready queue.
  • The Balancing Act: The choice of time quantum is vital. If the quantum is too large, the system behaves like FCFS. If it is too small, the system spends too much time on context switching, wasting precious CPU cycles.

Multilevel Feedback Queue (MLFQ)

MLFQ is the sophisticated standard used in modern operating systems like Linux and Windows. Instead of a single queue, it utilizes multiple queues with different priority levels and time quanta.

  • How it works: New processes enter the highest-priority queue. If a process uses up its entire time quantum without finishing, it is demoted to a lower-priority queue. Conversely, if a process yields the CPU to wait for I/O, it may eventually be promoted back to a higher queue.
  • The Advantage: It dynamically adapts to the behavior of processes, providing fast response times for interactive tasks while still ensuring long-running batch tasks eventually complete.

Comparative Analysis: FCFS vs. SJF

To illustrate the impact of these algorithms, consider three processes ($P_1, P_2, P_3$) with execution times of 24ms, 3ms, and 3ms, all arriving at time 0.

  • FCFS Execution Order: $P_1 \rightarrow P_2 \rightarrow P_3$
    • Waiting times: $P_1(0), P_2(24), P_3(27)$
    • Average Waiting Time: $(0 + 24 + 27) / 3 = \mathbf{17\text{ms}}$
  • SJF Execution Order: $P_2 \rightarrow P_3 \rightarrow P_1$
    • Waiting times: $P_2(0), P_3(3), P_1(6)$
    • Average Waiting Time: $(0 + 3 + 6) / 3 = \mathbf{3\text{ms}}$

This comparison highlights how SJF significantly optimizes system efficiency by reducing the average wait time.

The Overhead of Context Switching

Whenever the scheduler decides to switch from one process to another, the system must perform a Context Switch. This is a necessary but "expensive" operation because it does not contribute to the actual execution of user code. The process involves:

  1. State Saving: The current state of the running process—including CPU registers, the Program Counter (PC), and the stack pointer—is saved into its Process Control Block (PCB).
  2. State Update: The status of the current process is updated (e.g., from "Running" to "Ready" or "Blocked").
  3. State Loading: The OS retrieves the previously saved state of the next process from its respective PCB.
  4. Resumption: The Program Counter is updated to the restored address, and the CPU begins executing the new process.

Because context switching consumes resources, an effective scheduling algorithm must strike a perfect balance between rapid responsiveness and the minimization of switching overhead.