Processor Scheduling

At the heart of any modern operating system lies the processor scheduling mechanism. In a multitasking environment, multiple processes or threads constantly compete for the limited attention of the Central Processing Unit (CPU). The scheduler acts as the arbiter of this competition, deciding which task gains execution rights and for how long. An efficient scheduling strategy is not merely a matter of organization; it is critical for maximizing system throughput, minimizing latency, and ensuring that resources are distributed fairly among all competing tasks.
Scheduling is not a monolithic process but rather a tiered operation that occurs at different levels of the system architecture. Depending on the scope of the decision, scheduling is typically categorized into three distinct layers:

• High-Level Scheduling (Job Scheduling): This layer manages the transition of jobs from the backing store (secondary storage) into the main memory. Its primary role is to control the degree of multiprogramming—the number of processes residing in memory at any given time. This is most commonly observed in batch processing systems.
• Medium-Level Scheduling (Memory Scheduling): When memory resources become strained, the system employs medium-level scheduling to manage the swapping of processes between main memory and the disk. By suspending certain processes and activating others, the system can alleviate memory pressure and maintain stability.
• Low-Level Scheduling (CPU Scheduling): This is the most granular and frequent form of scheduling. It involves selecting a process from the ready queue to be executed by the CPU. Because this occurs every few milliseconds, low-level scheduling is the most performance-critical component of the operating system.

In most technical discussions regarding "processor scheduling," the focus is almost exclusively on this low-level, CPU-centric operation.

Scheduling Modes and Performance Metrics

Before examining specific algorithms, it is essential to understand the two fundamental modes of operation and how we measure their success.

Preemptive vs. Non-Preemptive Scheduling

The distinction between these two modes lies in whether a running process can be forcibly interrupted:

• Non-Preemptive Scheduling: Once a process is allocated the CPU, it retains control until it either completes its execution or voluntarily enters a waiting state (e.g., due to an I/O request). This approach is simpler to implement but can lead to inefficiency if a long process monopolizes the processor.
• Preemptive Scheduling: The operating system has the authority to interrupt a running process to allocate the CPU to another task, based on criteria such as priority or time slices. This is the standard for modern, general-purpose operating systems (like Windows, Linux, and macOS) because it ensures high responsiveness.

Key Performance Indicators

To evaluate the effectiveness of a scheduling algorithm, engineers rely on several mathematical metrics:

1. Turnaround Time: The total interval from the moment a process is submitted to the moment it is completed ($Turnaround\ Time = Completion\ Time - Arrival\ Time$).
2. Weighted Turnaround Time: A ratio used to evaluate efficiency relative to the workload ($\frac{Turnaround\ Time}{Actual\ Burst\ Time}$).
3. Waiting Time: The total time a process spends residing in the ready queue without CPU access ($Waiting\ Time = Turnaround\ Time - Actual\ Burst\ Time$).
4. Response Time: The duration between the initial request submission and the first time the system provides a response. This is the most vital metric for interactive and user-facing systems.

Core Scheduling Algorithms

Various algorithms have been developed to optimize different system goals. No single algorithm is perfect; each involves a trade-off between complexity and efficiency.

First-Come, First-Served (FCFS)

The simplest approach, FCFS, processes tasks in the exact order they arrive in the ready queue. While it is inherently fair and easy to implement, it suffers from the convoy effect, where several short processes are stuck behind one massive, long-running process, significantly increasing the average waiting time.

Shortest Job First (SJF)

SJF prioritizes tasks with the smallest predicted execution time. Theoretically, this algorithm provides the minimum average waiting time for a given set of processes. However, it faces two major practical hurdles: it is difficult to predict the exact duration of a future CPU burst, and it can lead to starvation, where long-running processes are perpetually pushed back by a steady stream of shorter tasks.

Round Robin (RR)

Designed specifically for time-sharing systems, RR assigns each process a small unit of CPU time called a time quantum (or time slice). Once the quantum expires, the process is preempted and moved to the back of the queue.

• If the quantum is too large, the system degrades into FCFS.
• If the quantum is too small, the overhead caused by frequent context switching (the process of saving and loading process states) becomes prohibitive.

Priority Scheduling

In this model, each process is assigned a priority level. The scheduler always selects the process with the highest priority. To prevent the starvation of low-priority tasks, modern systems implement aging—a technique that gradually increases the priority of a process the longer it waits in the ready queue.

Multilevel Feedback Queue (MLFQ)

MLFQ is a sophisticated, highly adaptive approach used in many modern operating systems. It utilizes multiple ready queues, each with a different priority level and time quantum. New processes enter at the highest priority queue with a short quantum. If they fail to complete within that time, they are demoted to a lower-priority queue with a larger quantum. This allows the system to favor interactive, short tasks while still providing throughput for long-running, CPU-bound tasks without requiring prior knowledge of their execution times.

Comparative Analysis: FCFS vs. SJF

To illustrate the impact of these algorithms, consider three processes arriving at different times:

Scenario A: FCFS Scheduling
The execution order is P1 $\rightarrow$ P2 $\rightarrow$ P3.

• P1: Turnaround = 8, Wait = 0
• P2: Turnaround = 11, Wait = 7
• P3: Turnaround = 12, Wait = 10
• Average Turnaround Time: $\approx 10.33$
• Average Waiting Time: $\approx 5.67$

Scenario B: Non-Preemptive SJF Scheduling
Since P1 arrives first and must run, the order becomes P1 $\rightarrow$ P3 $\rightarrow$ P2 (as P3 is shorter than P2).

• P1: Turnaround = 8, Wait = 0
• P3: Turnaround = 8, Wait = 6
• P2: Turnaround = 13, Wait = 9
• Average Turnaround Time: $\approx 9.67$
• Average Waiting Time: $5.0$

Conclusion from Example: While SJF yields a lower average waiting time and turnaround time, we observe that P2's individual waiting time is extended. This highlights the fundamental tension in scheduling: optimizing for the "average" often comes at the expense of "fairness" for specific tasks.

Summary

Processor scheduling is a balancing act. There is no "perfect" algorithm; instead, there is only the "most appropriate" algorithm for a specific use case. Batch systems prioritize throughput and turnaround time, time-sharing systems prioritize response time and fairness, and real-time systems prioritize strict adherence to deadlines. Mastering these scheduling principles is essential for anyone seeking to understand system performance and optimize the efficiency of complex computing environments.