Priority Scheduling

Abstract 

In priority scheduling, processes are scheduled according to their priorities. The process with the highest priority is scheduled first. It is one of the most common scheduling algorithms in batch systems.

Scope

This article talks about priority scheduling in detail.

Definition

In priority scheduling, every job is assigned a priority and the CPU is assigned to the highest priority job among all the jobs in the ready queue. If two processes have the same priority, then we give priority to the process that came first. Priority scheduling can be preemptive or non-preemptive. A preemptive priority scheduling algorithm will preempt the CPU if the priority of the newly arrived process is higher than the priority of the currently running process. A non-preemptive priority scheduling algorithm will put the new process at the head of the ready queue. 

Let’s consider an example of non-preemptive priority scheduling:

PROCESS ARRIVAL TIMEPRIORITY BURST TIME
        P0            0        5          3
        P1            1        3          5
        P2            2        15          8
        P3            3        12          6

Here P0 is scheduled first since it arrives first. After its completion, the other three processes arrive. Now the process with the highest priority which is P2 is scheduled. 

Gnatt chart :

Final chart 

PROCESSARRIVAL TIMEPRIORITY BURST TIMETURN AROUND TIMEWAITING TIME
P005330
P11352116
P2215891
P33126148

Now let us consider an example of preemptive priority scheduling 

PROCESS ARRIVAL TIMEPRIORITY BURST TIME
        P0            0        5          3
        P1            1        3          5
        P2            2        15          8
        P3            3        12          6

P0 being the first is scheduled and it runs for 1 unit. At t = 1, P1 arrives. Since P1 has less priority, P0 continues to run for 1 more unit. At t = 2, P2 arrives. Since it has greater priority, it gets scheduled. It runs until completion. After this P3 which has a greater priority is scheduled. After its completion, the remaining processes are compared. P0 having greater priority is scheduled and it finishes its remaining 1 unit followed by P1.

PROCESS ARRIVAL TIMEPRIORITY BURST TIME
        P0            0        5          3     1 
        P1            1        3          5
        P2            2        15          8
        P3            3        12          6

Gantt chart 

Final chart

PROCESSARRIVAL TIMEPRIORITY BURST TIMETURN AROUND TIMEWAITING TIME
P0      0531714
P1      1352116
P2      215880
P3      3126137

Average waiting time and average response time depend on the priority processes. If there are many priority processes that are coming first and then there is a low priority process that has been waiting for so long, then the average between time and also response time might go up.

Some important points 

  • A major problem with priority scheduling algorithms is indefinite block or starvation. A process that is ready to run but waiting for the CPU can be blocked. It can leave some low-priority processes waiting indefinitely.
  • In a heavily loaded system, a steady stream of high-priority processes can prevent a low-priority process from ever getting the CPU.
  • A solution to the problem of indefinite blockage of low priority processes is aging. Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time. 

Summary

 In priority scheduling, the process with the highest priority is executed first, and so on. It can be preemptive and non-preemptive. A major problem with priority scheduling is starvation and it can be solved by the process called aging. 

Special thanks to Ami Jangid for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article