New update is available. Click here to update.

Preemptive and Non-Preemptive Scheduling

Divyansh Jain
Last Updated: Oct 10, 2022
Difficulty Level :
MEDIUM
Operating Systems

Introduction

When the CPU is idle, it is the role of the CPU scheduler to assign a task to it. The CPU scheduler chooses a process from the ready queue and assigns it to the CPU. The short-term scheduler is in charge of selecting (or CPU scheduler) the process from the ready queue. The scheduler selects a process from the processes in memory that is ready to execute. And, Preemptive Scheduling and Non-Preemptive Scheduling are the two broad categories of process scheduling algorithms. We'll go over both of them in depth. So, let’s get started.

Types of CPU Scheduling

Types of Priority Based Scheduling

  1. Non- Preemptive Scheduling 
  2. Preemptive Scheduling

Preemptive Scheduling

Preemptive Scheduling is a scheduling technique in which tasks are assigned based on priority. Even though the lower priority activity is still running, it is sometimes necessary to run a higher priority task before a lower priority task.

The lower priority work is put on hold for a while and then continues when the higher priority process finishes its execution.

In Preemptive scheduling, the scheduler will execute a process for a specific amount of time before passing it on to the next process in line. It has to wait to be executed again by the scheduler. The process may go to the ready state from the running state or the waiting state to the ready state. If there is still any CPU burst time available, the resources are granted to the process for only a short period before being removed, and the process is moved to the ready queue. Some famous preemptive scheduling algorithms are SJF (preemptive), Round-robin, etc.

Example: 

Let’s look at an example of Preemptive scheduling, which will clarify the whole process. Here we have taken four processes, P0, P1, P2, and P3, to be executed using Preemptive scheduling as a priority scheduling algorithm (Lower the Number, Higher the priority).

Process

Arrival Time

Priority

CPU Burst time

P0

0

4

5

P1

1

1

2

P2

3

3

4

P3

4

2

3

 

Gantt chart:

Gnatt Chart

  • To begin, the process P0 appears at time 0. As a result, the CPU is assigned to P0.
  • Process P1 arrived at the time one unit, while process P0 was operating, and the Priority for P0 (4) is less than the priority of process P1 (1). As a result, P1 is allocated to the processor.
  • Now, At time 3ms, P1 completes its execution time, and the CPU has to choose a process from the ready queue. While at the ready queue, we have the P2 process arrive at time 3ms. 
  • Now, among P0 and P2, the CPU will be allocated to the process P2 due to higher priority. And the execution of the process P2 will be started.
  • The execution was in progress but at the same time, Process P3 arrived. The priority for P2 (3) is less than P3(2). So now, P3 started the execution till time equal to 7ms.
  • Now P2 again got the chance to complete its execution. So, P2 finishes the execution at time 10ms.
  • And finally, at last, process P0 completed its remaining execution till time 14ms.

 

To calculate Turn Around Time and Waiting time,

  • Turn around time = Completion time - Arrival time
  • Waiting time = Turn around time - Burst time

Process

Arrival Time

Priority

CPU Burst time

Completion Time

Turn Around Time

Waiting Time

P0

0

4

5

14

14

9

P1

1

1

2

3

2

0

P2

3

3

4

10

7

3

P3

4

2

3

7

3

0

 

Now, Average Waiting time = [WT(P0) + WT(P1) + WT(P2) + WT(P3)] / 4

= [ 9 + 0 + 3 + 0 ] / 4

= 3 ms.

 

Note:

Turnaround Time = Completion Time - Arrival Time   

Waiting Time = Turnaround Time - Burst Time  

Average waiting time = 

(Sum of waiting time of all processes)/(Number of Processes)
 

C++ Implementation

// C++ Implementation of Preemptive Priority Scheduling
#include <iostream>
using namespace std;
int main()
{
    int n = 5; //number of processes to be scheduled
    int arrivalTime[n] = {0, 0, 6, 11, 12};
    int burstTime[n] = {4, 3, 7, 4, 2};
    int priority[n + 1] = {1, 2, 1, 3, 2};
    int x[n];


    int waitingTime[n], turnaroundTime[n], completionTime[n];
    int i, j, smallest, count = 0, time; // count -> number of processes completed
    double avg = 0, tt = 0, end;


    for (i = 0; i < n; i++)
        x[i] = burstTime[i];


    priority[n] = 10000;


    for (time = 0; count != n; time++)
    {
        smallest = n;
        for (i = 0; i < n; i++)
        {
            if (arrivalTime[i] <= time && priority[i] < priority[smallest] && burstTime[i] > 0)
                smallest = i;
        }
        burstTime[smallest]--;
        if (burstTime[smallest] == 0)
        {
            count++;
            end = time + 1;
            completionTime[smallest] = end;
            waitingTime[smallest] = end - arrivalTime[smallest] - x[smallest];
            turnaroundTime[smallest] = end - arrivalTime[smallest];
        }
    }
    cout << "Process"
        << "\t  "
        << "burst-time"
        << "\t "
        << "arrival-time"
        << "\t "
        << "waiting-time"
        << "\t"
        << "turnaround-time"
        << "\t "
        << "completion-time"
        << "\t"
        << "Priority" << endl;
    for (i = 0; i < n; i++)
    {
        cout << "p" << i + 1 << "\t\t" << x[i] << "\t\t" << arrivalTime[i] << "\t\t" << waitingTime[i] << "\t\t" << turnaroundTime[i] << "\t\t" << completionTime[i] << "\t\t" << priority[i] << endl;
        avg = avg + waitingTime[i];
        tt = tt + turnaroundTime[i];
    }
    cout << "\n\nAverage waiting time time = " << avg / n;
    cout << "  Average turnaround time time = " << tt / n << endl;
}

Output 

Process   burst-time     arrival-time    waiting-time   turnaround-time  completion-time        Priority

p1              4                       0               0                           4                         4                            1

p2              3                       0               11                        14                        14                           2

p3              7                       6               0                           7                         13                           1

p4              4                       11              5                           9                         20                           3

p5              2                       12              2                           4                         16                           2

 

Average waiting time time = 3.6  Average turnaround time time = 7.6

Advantages of Preemptive Scheduling

  • Each occurrence resulted in the disruption of ongoing tasks.
  • When used in a multiprogramming environment, preemptive scheduling is advantageous.
  • The average response time is also improved by using this scheduling strategy.
  • The operating system makes sure that all processes use the same amount of CPU.
  • Preemptive scheduling is a more reliable approach that prevents one process from dominating the CPU.

 

Disadvantages of Preemptive Scheduling

  • If many high-priority processes arrive simultaneously, the low-priority process will have to wait longer.
  • The scheduler spends more time suspending the ongoing job, switching the context, and dispatching the new incoming task.
  • Scheduling requires a limited amount of computational resources.

Non-Preemptive Scheduling

If a resource is allocated to a process under non-preemptive scheduling, that resource will not be released until the process is completed. Other tasks in the ready queue will have to wait their time, and it will not get the CPU forcefully. After a process has been assigned to it, it will hold the CPU until it has completed its execution or until an I/O action is required.

When a non-preemptive process with a long CPU burst time runs, the other process must wait for an extended period, increasing the average waiting time in the ready queue. Non-preemptive scheduling, on the other hand, contains no overhead when switching processes from the ready queue to the CPU. The execution process isn't even interrupted by a higher-priority task, implying that the scheduling is rigorous.

Example: 

Let's look at the above preemptive scheduling problem we have solved and see how we can handle it in a non-preemptive method. In contrast, the same four processes are P0, P1, P2, and P3, with the same arrival time and CPU burst time.

So, by using a Non-preemptive scheduler, the Gantt chart would look like-

Process

Arrival Time

CPU Burst time

P0

0

5

P1

1

2

P2

3

4

P3

4

3

 

Gantt chart:

Gantt chart
  • The processor is allocated to process P0 since it arrives at 0 and takes five milliseconds to complete.
  • Meanwhile, all of the processes, P1, P2, and P3, arrive in the ready queue. All operations, however, must wait until Process P0 finishes their CPU burst period.
  • Process P0 will complete its execution at time = 5ms. The burst times are compared for the rest of the processes in the ready queue. Process P1 is executed because it has a shorter burst duration than other processes.
  • And similarly, following P1, P3, and then P2 will complete its execution.

 

So, let’s calculate the average waiting time for the non-preemptive method.

Process

Arrival Time

CPU Burst time

Completion Time

Turn Around Time

Waiting Time

P0

0

5

5

5

0

P1

1

2

7

6

4

P2

3

4

14

11

7

P3

4

3

10

6

3

 

Average waiting time = [WT(P0) + WT(P1) + WT(P2) + WT(P3)] / 4

= [ 0 + 4 + 7 + 3 ] / 4

= 3.5 ms.

So, the average waiting time for the preemptive method is less than the non-preemptive method which can further conclude that the preemptive method is more efficient in terms of time efficiency for the CPU.

 

Advantages of Non-Preemptive Scheduling

  • Low overhead in terms of scheduling is being offered.
  • It has a tendency to have a high throughput.
  • The approach is relatively easier to implement than other scheduling methods.
  • Very few computational resources are required in Non-preemptive scheduling.

Disadvantages of Non-Preemptive Scheduling

  • The response time is relatively much slower and inefficient.
  • It can make a priority and real-time scheduling challenging.
  • It can result in starvation, particularly for those real-time tasks.
  • The Bugs due to this scheduling can cause a system to become unresponsive.

Key Differences

  • The major difference between both the scheduling is that the CPU is allotted to the processes for a certain amount of time in preemptive scheduling. At the same time, the CPU is allotted to the process in non-preemptive scheduling until it quits or changes to the other state.
  • Whenever a higher priority task arrives, the preemptive scheduling execution is interrupted in the middle of its execution. Non-preemptive scheduling, on the other hand, does not interrupt the execution process in the middle of it and waits until it is finished.
  • Preemptive Scheduling has the overhead of transferring a process from the ready state to the running state and vice versa and managing the ready queue. In contrast, non-preemptive scheduling has no overhead associated with switching from a running to a ready state.
  • If a high-priority process emerges in the ready queue on a regular basis, the low-priority process will have to wait a long time and may have to starve. In non-preemptive scheduling, if the CPU is assigned to a process with a large burst time, processes with lesser burst periods may be forced to starve.
  • Preemptive scheduling offers flexibility by offering access to the CPU to critical processes as soon as they join the ready queue, regardless of what job is currently running. Non-preemptive scheduling is considered stiff since the CPU of a critical process is unaffected if it joins the ready queue.
  • Preemptive Scheduling is cost associative because it must preserve the integrity of shared data, which is not the case with Non-preemptive Scheduling.

Head-to-Head Comparison

ParameterPREEMPTIVE SCHEDULINGNON-PREEMPTIVE SCHEDULING
BasicIn preemptive, resources (CPU Cycle) are allotted to a process for a limited time.While in Non-preemptive, Once resources (CPU Cycles) are allotted to a process, it is held until the burst time is completed or the process transitions to the waiting state.
InterruptThe process can be interrupted at any time.The process cannot be interrupted until it has been completed or the timer has expired.
StarvationA low priority process may starve if a high priority process often appears in the ready queue.If a process with a long burst time consumes CPU, subsequent processes with shorter burst times may suffer.
OverheadIt contains overheads associated with process scheduling.There are no overheads in Non-preemptive scheduling.
CostThere is a cost associated with preemptive scheduling.There is no cost associated with non-preemptive scheduling.
CPU UtilizationCPU consumption is high in preemptive scheduling.CPU consumption is low in Non-preemptive scheduling.
ExamplesSome of the preemptive scheduling is Shortest Remaining Time First and Round Robin.Some non-preemptive scheduling is Shortest Job First and First Come First Serve.

Advantages of Priority Based Scheduling

  • Processes having higher priority need not wait for a longer time due to other processes running.
  • The relative importance of processes can be defined.
  • The applications in which the requirements of time and resources fluctuate are useful.

Disadvantages of Priority Based Scheduling

  • One of the major problems with this algorithm is indefinite blocking or starvation.
  • A process that is ready to run but waiting for the CPU can be considered blocked.
  • This algorithm may leave some low priority processes to wait indefinitely.
  • All the low priority tasks may get lost when the system crashes eventually.

Frequently Asked Questions

What is priority scheduling with examples?

Priority scheduling is a CPU scheduling algorithm in which the CPU is assigned to the process having the highest priority.

What is priority based preemptive scheduling?

It is a priority scheduling algorithm in which the CPU is preempted when the newly arrived process is of higher priority than the currently running process. So, the currently running process is stopped, and the newly arrived process is executed.

How is priority scheduling calculated?

We schedule the processes by making a Gantt chart. In this, the process that arrives first is scheduled first, and if two or more processes arrive at the same time, they are scheduled according to their priority.

What is a Dispatcher?

A dispatcher gives control of the CPU to the process selected by the short-term scheduler. The dispatch latency is considered as the time it takes for the dispatcher to terminate one process and start another.

Which priority criteria are being considered in the shortest jobs first algorithm?

The amount of CPU burst time is considered a priority in the shortest jobs first algorithm basis on which the CPU is being allocated to the processes that belong to the Non-preemptive scheduling.

In Preemptive scheduling, what happens when several high-priority processes arrive simultaneously.

When many high-priority processes arrive at the CPU ready queue, then the low-priority processes need to wait for a long time. It is one of the disadvantages of preemptive scheduling.

Which scheduling is better: Preemptive or Non-preemptive Scheduling? 

It's not a question of whether preemptive scheduling is better than non-preemptive scheduling or vice versa. It all relies on how a scheduling algorithm reduces average process waiting time while increasing CPU usage.

Conclusion

To summarize the article, we learned both the scheduling methods in detail, got a clear idea about the priority scheduling used in both scheduling methods, and discussed the key differences between preemptive and non-preemptive scheduling. And finally, by head-to-head comparison, we cleared the basic parametric differences followed by the conclusion. But the knowledge never stops, so to better understand the operating systems, you can go through many articles on our platform.

Recommended Readings: 


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on CodeStudio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on CodeStudio.

Happy learning :)

Was this article helpful ?
0 upvotes