CPU Scheduling: Preemptive vs. Non-Preemptive

Preemptive vs. Non-Preemptive Scheduling

At its core, every scheduling algorithm must adhere to one of two philosophies: non-preemptive or preemptive.

• Non-preemptive scheduling is cooperative. Once a process is given the CPU, it keeps it until it voluntarily releases it—either by finishing its task or by performing an I/O operation.
• Preemptive scheduling is forceful. The operating system can interrupt a running process, take the CPU away, and give it to another process. This is typically done using a hardware timer.

This single difference has profound implications for system responsiveness, fairness, and protection against misbehaving programs.

The video below offers a clear and concise explanation of this core distinction and introduces the concept of a "quantum," which is fundamental to preemptive scheduling.

The table in the following document also provides a useful side-by-side comparison of their characteristics.

In essence, non-preemptive schedulers are simpler but risk having the entire system performance dictated by a single long-running or uncooperative process. Preemptive schedulers are more complex but provide the fairness and responsiveness expected of modern interactive operating systems.

First-Come, First-Served (FCFS): The Simple but Flawed Approach

First-Come, First-Served (FCFS) is the most straightforward scheduling algorithm. It operates exactly as its name implies: processes are served in the order they arrive in the ready queue. It is a non-preemptive algorithm.

• Mechanism: Implemented with a simple First-In, First-Out (FIFO) queue. When the current process releases the CPU, the process at the head of the queue gets it next.
• Advantage: Very simple to understand and implement.
• Disadvantage: FCFS can lead to poor performance due to the convoy effect. If a long, CPU-bound process arrives just before several short, I/O-bound processes, the short processes are forced to wait, leaving I/O devices idle. This results in poor utilization of system resources and high average waiting times.

The following video provides an excellent intuitive explanation of FCFS and visualizes the convoy effect.

To see this in practice, let's look at a concrete example.

Shortest Job First (SJF): An Optimal but Impractical Solution

To address the convoy effect, we can use the Shortest Job First (SJF) algorithm. The core idea is to prioritize processes with the shortest upcoming CPU burst.

SJF can be either non-preemptive or preemptive:

• Non-preemptive SJF: When the CPU becomes free, the scheduler selects the process with the shortest next CPU burst from the entire ready queue.
• Preemptive SJF (Shortest Remaining Time First - SRTF): This is a more aggressive version. If a new process arrives in the ready queue with a CPU burst shorter than the remaining time of the currently executing process, the scheduler preempts the current process and runs the new, shorter one.

Advantages & Disadvantages:

• Advantage: SJF (specifically, the preemptive SRTF variant) is provably optimal in minimizing the average waiting time for a given set of processes.
• Disadvantage 1 (Impracticality): Its greatest weakness is that it's impossible to implement perfectly. There is no way to know the exact length of a process's next CPU burst in advance. Schedulers must rely on predicting future behavior based on past performance, typically using an exponential average of previous burst lengths.
• Disadvantage 2 (Starvation): SJF can lead to starvation. A process with a long CPU burst might never get to run if there is a continuous stream of shorter jobs arriving.

This video provides an excellent overview of SJF, including the formula used for prediction.

The exponential average formula for predicting the next burst length, ${\tau }_{n+1}$, is:

Where:

• $t_n$ is the duration of the actual $n$-th CPU burst.
• ${\tau }_n$ was the predicted duration for that $n$-th burst.
• $\alpha$ is a weighting factor between 0 and 1.

Now, let's compare the non-preemptive and preemptive versions with a worked example.

Round Robin (RR): Preemption for Fairness

While SJF optimizes for average waiting time, it can be unfair to long processes. For interactive systems where responsiveness is key, a different approach is needed. Round Robin (RR) is a preemptive algorithm designed specifically for time-sharing environments.

• Mechanism: RR is essentially FCFS with preemption. Each process is allowed to run for a small, fixed time interval called a time quantum (or time slice), typically 10-100 milliseconds.
• Execution Flow:
  1. The scheduler picks the first process from the ready queue and lets it run.
  2. If the process finishes its CPU burst before the time quantum expires, it releases the CPU voluntarily.
  3. If the process is still running when the quantum expires, a hardware timer triggers an interrupt, and the OS preempts the process, placing it at the tail of the ready queue.
  4. The scheduler then proceeds to the next process at the head of the queue.

The performance of RR is highly dependent on the size of the time quantum:

• Too large: RR degenerates into FCFS, and responsiveness suffers.
• Too small: The overhead from frequent context switching becomes significant, reducing overall throughput.

Let's see the calculations for RR in action.

Conclusion

In this lesson, we have dissected three foundational CPU scheduling algorithms, each embodying a different set of trade-offs. There is no single "best" algorithm; the choice depends entirely on the system's goals, whether that's maximizing throughput, minimizing response time, or ensuring fairness.

Here is a summary of our comparison:

You've now grasped the fundamental principles that govern how an OS allocates its most critical resource: the CPU.

In our next lesson, we will apply this knowledge in a more practical context. We will move from simply comparing algorithms to analyzing a given workload to determine which scheduling algorithm minimizes average waiting time, a common exercise in system performance tuning.