Preemptive and Non-Preemptive Scheduling

In multiprogramming environments, process scheduling is performed by the CPU to decide the next process to be executed. This allows multiple CPU processes to exist simultaneously while optimizing utilization of system resources as well as the time of execution. A scheduling strategy defines a procedure to select one process among the processes waiting at the ready queue for execution.

Categories of Process Scheduling

Process scheduling algorithms are broadly classified as Preemptive Scheduling and Non-preemptive Scheduling. The different types of preemptive and non-preemptive scheduling algorithms are represented in the following diagram −

Non-preemptive Scheduling

Non-preemptive scheduling algorithms refer to the class of CPU scheduling technique where once a process is allocated the CPU, it holds the CPU till the process gets terminated or is pushed to the waiting state. No process is interrupted until it runs to completion. The scheduler allocates another process to the CPU only after the currently allocated process terminates and relinquishes control on the CPU.

Example of Non-preemptive Scheduling

• First-Come-First-Serve (FCFS) Scheduling
• Shortest Job First (SJF) Scheduling
• Priority Non-preemptive Scheduling
• Highest Response Ratio Next (HRRN) Scheduling

Advantages of Non-preemptive Scheduling

• Non-preemptive scheduling methods are simpler to design and implement.
• These techniques need lesser resources and have lower overhead.
• They require lesser number of context switches. So, the amount of time expended for scheduling is very less in comparison to execution of the processes.
• They are deterministic in nature and the scheduling outputs are easily predictable.

Disadvantages of Non-preemptive Scheduling

• Non-preemptive scheduling cannot respond to dynamically changing system.
• It may result in deadlock if there are processes in the system which are holding some resources which waiting for other resources that are held by other processes.
• If the executing process erroneously enter infinite loop, it may cause system crash since no other process can interrupt the execution.

Preemptive Scheduling

Preemptive scheduling algorithms fall under the category of process scheduling technique in which a running process can be interrupted by another process and sent to the ready queue even when it has not completed its entire execution in CPU.

An executing process may be pre-empted under the following situations −

• The first scenario is when the process has reached the limit of the time slot allotted to it. If the burst time of the process is greater than CPU cycle, it is placed back into the ready queue and will execute in the next chance.
• The second scenario is when a higher priority process enters the system. The process state of the executing process is saved in the process table and the higher priority process starts to execute.
• Another scenario is when a short process enters the system which uses Shortest Remaining Time Next scheduling algorithm. If a longer process is executing, it is pre-empted out to let the shorter process execute.

Example of Preemptive Scheduling

• Round Robin (RR) Scheduling
• Shortest Remaining Time Next (SJF Preemptive)
• Priority Preemptive Scheduling

Advantages of Preemptive Scheduling

• No process can monopolize the CPU.
• Fair scheduling can be applied.
• Preemptive scheduling improves the average response time.
• They allow reconsideration of scheduling decision after each pre-emption, thus making the scheduling decision more adaptive to change.
• Deadlocks can be avoided by preempting processes.

Disadvantages of Preemptive Scheduling

• Preemptive scheduling require frequent context switching which is time-consuming.
• This requires more memory since all context information for each process needs to be stored and updated frequently.
• Often a low priority process or a long process has to wait for long time due to influx of many higher priority or shorter processes in the system.
• The processes must be appropriately coded so that they can be switched at all times without information loss. This leads to complex processes.

Difference Between Preemptive and Non-Preemptive Scheduling

The following table lists the key differences between preemptive and Non-pScheduling −