Preemptive and Non-Preemptive Scheduling in OS

Preemptive and Non-Preemptive Scheduling are the two main types of CPU scheduling algorithms used by an operating system to allocate the CPU to processes. The key difference between them is whether the operating system can interrupt (preempt) a running process before it finishes. Choosing the appropriate scheduling method helps improve CPU utilization, response time, fairness, and overall system performance.

The above diagram says that

• Preemptive Scheduling: After a process (P1) goes for an input/output (I/O) operation, the process (P2) comes into the CPU and can utilize it.
• Non-Preemptive Scheduling: After process (P1) goes for an input/output (I/O) operation, the CPU remains idle until Process (P1) finishes an input/output (I/O) operation and comes back.
• What is Preemptive Scheduling?

Preemptive Scheduling is a CPU scheduling method in which the operating system can interrupt a running process and assign the CPU to another process before the current process completes.

Preemption usually occurs when:

• Some I/O operation needs to be performed
• A higher-priority process arrives.
• The time quantum expires (in Round Robin).
• The scheduler determines another process should execute.

Example

Suppose Process P1 is running for 10 ms.

• P1 starts execution.
• After 3 ms, a higher-priority process P2 arrives.
• The operating system immediately stops P1.
• P2 gets the CPU.
• After P2 finishes, P1 resumes execution.

This interruption is called preemption.

Advantages of Preemptive Scheduling

Preemptive scheduling improves CPU scheduling efficiency by allowing the operating system to interrupt a running process when necessary. Its major advantages are listed below.

• Provides Faster Response Time: High-priority or newly arrived processes can immediately receive the CPU, making the system more responsive. This is especially beneficial for interactive applications.
• Suitable for Real-Time and Interactive Systems: Real-time operating systems and interactive applications require quick responses. Preemptive scheduling ensures that time-critical tasks are executed without unnecessary delays.
• Improves CPU Utilization: When a process is waiting for I/O or a higher-priority process arrives, the CPU can be assigned to another ready process. This keeps the CPU busy and reduces idle time.
• Prevents CPU Monopolization: A single long-running process cannot occupy the CPU indefinitely. This allows other processes to execute and improves overall system performance.
• Provides Better Fairness: Every process gets an opportunity to use the CPU according to the scheduling policy. This helps distribute CPU time more fairly among multiple processes.

Disadvantages of Preemptive Scheduling

Although preemptive scheduling improves responsiveness, it also introduces additional overhead and complexity.

• Frequent Context Switching: Interrupting processes frequently increases the number of context switches. This consumes CPU time and may reduce overall system efficiency.
• Complex Implementation: The operating system must continuously monitor process priorities and scheduling events. As a result, preemptive scheduling is more difficult to implement than non-preemptive scheduling.
• Performance Overhead: Excessive preemption can spend more CPU time switching between processes instead of executing them. This may reduce overall system performance.
• Possible Starvation: Low-priority processes may wait for a long time if higher-priority processes continue to arrive. In extreme cases, they may experience starvation.

Examples of Preemptive Scheduling Algorithms

The following CPU scheduling algorithms use the preemptive scheduling approach.

• Round Robin (RR): Each process receives a fixed time quantum. When the time quantum expires, the CPU is preempted and assigned to the next process in the ready queue.
• Shortest Remaining Time First (SRTF): The process with the shortest remaining CPU burst time is selected for execution. A newly arrived process with a shorter remaining time can preempt the currently running process.
• Preemptive Priority Scheduling: The CPU is always assigned to the highest-priority process. If a higher-priority process arrives, it immediately preempts the currently running process.
• Multilevel Feedback Queue (MLFQ): Processes are organized into multiple priority queues. The operating system can move processes between queues and preempt lower-priority processes to improve responsiveness and fairness.

What is Non-Preemptive Scheduling?

Non-Preemptive Scheduling is a CPU scheduling method in which the operating system cannot interrupt a running process. Once a process gets the CPU, it continues executing until it terminates or voluntarily enters the waiting state (for example, by requesting an I/O operation).

Example

Suppose Process P1 starts execution and requires 10 ms.

• After 3 ms, a higher-priority process P2 arrives.
• Since scheduling is non-preemptive, P1 continues executing.
• P2 must wait until P1 finishes or blocks for I/O.
• After P1 completes, P2 gets the CPU.

Advantages of Non-Preemptive Scheduling

Non-preemptive scheduling is simple and efficient because a process continues executing until it completes or enters the waiting state. Its main advantages are given below.

• Simple and Easy to Implement: The operating system does not need to interrupt running processes. This makes non-preemptive scheduling easier to design and manage.
• Less Context-Switching Overhead: Since processes are not interrupted frequently, fewer context switches occur. This reduces CPU overhead and improves execution efficiency.
• Better CPU Efficiency for Long-Running Processes: Long CPU-bound processes can execute without interruption. This avoids unnecessary delays caused by repeated preemption.
• Predictable Process Execution: Once a process gets the CPU, it continues running until completion or I/O waiting. This makes process execution more predictable and easier to analyze.
• Suitable for Batch Systems: Batch operating systems execute jobs sequentially without requiring immediate user interaction. Non-preemptive scheduling works efficiently in such environments.

Disadvantages of Non-Preemptive Scheduling

Although non-preemptive scheduling has low overhead, it may reduce system responsiveness in certain situations.

• High-Priority Processes May Wait Longer: If a long process is already running, newly arrived high-priority processes must wait until the current process finishes or blocks.
• Poor Response Time: Interactive applications may experience delays because the CPU cannot be reassigned until the running process releases it.
• Long Processes Delay Short Processes: A CPU-bound process with a long execution time can keep shorter processes waiting, increasing their waiting time.
• Higher Waiting and Turnaround Time: Since processes execute without interruption, the average waiting time and turnaround time may increase, especially in mixed workloads.

Examples of Non-Preemptive Scheduling Algorithms

The following CPU scheduling algorithms use the non-preemptive scheduling approach.

• First Come First Served (FCFS): Processes are executed in the order they arrive in the ready queue. Once a process starts, it continues until completion or I/O waiting.
• Non-Preemptive Shortest Job First (SJF): The process with the shortest CPU burst is selected first. After execution begins, it cannot be interrupted by another process.
• Non-Preemptive Priority Scheduling: The process with the highest priority is selected for execution. Once it starts running, it continues until it finishes or enters the waiting state.

Difference Between Preemptive and Non-Preemptive Scheduling

Preemptive and Non-Preemptive Scheduling differ in how the operating system allocates the CPU to processes. The major differences are given below.

When Does Preemption Occur?

In a preemptive scheduling system, the operating system can interrupt a running process and assign the CPU to another process when certain conditions occur. The most common situations are listed below.

• A Higher-Priority Process Arrives: If a process with a higher priority enters the ready queue, the operating system immediately interrupts the currently running process and assigns the CPU to the higher-priority process.
• The Time Quantum Expires: In Round Robin (RR) scheduling, each process is given a fixed time slice called the time quantum. When this time expires, the running process is preempted, and the CPU is allocated to the next ready process.
• A Real-Time Process Requires Immediate CPU Access: In real-time operating systems, time-critical processes must execute without delay. The operating system preempts the current process to ensure that the real-time task meets its deadline.
• The Scheduling Algorithm Selects Another Process: Some preemptive scheduling algorithms, such as Shortest Remaining Time First (SRTF), continuously evaluate the ready queue. If another process is considered more suitable according to the scheduling policy, the currently running process is interrupted and the CPU is reassigned.

When Does a Non-Preemptive Process Release the CPU?

In a non-preemptive scheduling system, the operating system cannot forcibly interrupt a running process. Once a process is assigned the CPU, it continues executing until one of the following conditions occurs.

• The Process Completes Execution: When the process finishes all its instructions, it terminates and automatically releases the CPU. The operating system then assigns the CPU to the next process in the ready queue.
• The Process Requests an I/O Operation: If the running process requests an input/output operation, such as reading a file or accessing a printer, it enters the Waiting (Blocked) state and releases the CPU. Another ready process is then scheduled for execution.
• The Process Voluntarily Yields the CPU (If Supported): Some operating systems allow a running process to voluntarily give up the CPU before completing its execution. In this case, the process moves to the ready state, and the scheduler selects another process to run.

Real-Life Example of Preemptive and Non-Preemptive Scheduling

Consider a bank with a single cashier serving customers.

Preemptive Scheduling

The cashier is serving Customer A. Suddenly, an emergency customer (such as a VIP or someone with urgent service) arrives. The cashier temporarily stops serving Customer A, assists the emergency customer first, and then resumes serving Customer A.

• Operating System Concept: The running process is interrupted (preempted) so that a higher-priority process can use the CPU immediately.

Non-Preemptive Scheduling

The cashier starts serving Customer A. Even if a VIP or emergency customer arrives, the cashier continues serving Customer A until the transaction is completed. Only after finishing does the cashier serve the next customer.

• Operating System Concept: Once a process gets the CPU, it continues executing until it completes or requests an I/O operation. The operating system does not interrupt the running process.

Key Points for Exams

• Preemptive Scheduling allows the operating system to interrupt a running process.
• Non-Preemptive Scheduling does not allow interruption of a running process.
• Preemptive scheduling provides better response time but increases context-switching overhead.
• Non-preemptive scheduling is simpler and has lower overhead, but it may increase waiting time.
• Round Robin, SRTF, Preemptive Priority, and MLFQ are preemptive scheduling algorithms.
• FCFS, Non-Preemptive SJF, and Non-Preemptive Priority are non-preemptive scheduling algorithms.
• Preemptive scheduling is preferred for interactive and real-time operating systems.
• Non-preemptive scheduling is commonly used in batch processing systems.

Conclusion

Preemptive and Non-Preemptive Scheduling are the two fundamental approaches to CPU scheduling in operating systems. In preemptive scheduling, the operating system can interrupt a running process to improve responsiveness and fairness, making it suitable for interactive and real-time environments. In non-preemptive scheduling, a process keeps the CPU until it finishes or blocks for I/O, resulting in lower overhead and simpler implementation. Understanding the differences between these scheduling methods is essential for selecting the most appropriate CPU scheduling algorithm based on system requirements.