• In this article, we will explain another conmanly used CPU scheduling algorithm called “Priority Scheduling Algorithm”.
  • Operating System stores various information about each and every process in their PCB. One of them is is the priority of process.
  • Operating system assigns priority number whenever a new process is created so priority is associated with each process.
  • According to the Priority scheduling algorithm, the CPU is allocated to the process that has the highest priority.
  • If there is a tie among process then equal priority processes are scheduled in First Come First Serve order.
  • Priorities are rang of numbers between 0-7 or 0 – 4095.
  • Some system use lower numbers to represent low priority and others use lower numbers for high priority.
  • Time limits, memory requirements, the no. of opened files and the ratio of average I/O burst to avg. CPU burst have been used in computing priorities.
  • Priority scheduling can be either preemptive or non-preemptive.
  • When a process arrives at the ready queue, its priority is compared with the priority of currently running process.
  • A non-preemptive priority scheduling algorithm will simply start a new process at head of ready queue.
  • Let’s see this algorithm at work by the following example.

Non-Preemptive:

Consider the following processes and their CPU burst time and find out average waiting time and average turnaround time using priority scheduling algorithm (Lower number represents higher priority).

Priority Scheduling

  • Since all processes comes simultaneously our selection will be easy based on non-preemptive scheduling scheme.
  • According to priority scheme, process having highest priority will get the CPU first. In our example, process P3 has the highest priority (lower number) so P3 will be selected first for execution so waiting time for P3 will be zero. It will execute for five milliseconds after that next highest priority process is P4 so it will get the CPU next and waiting time for P4 will be five milliseconds i.e. the completion time of P3.
  • Next turn is for process P2 after the completion of both process P3 and P4 so waiting time for process P2 will be 5 + 7(burst time of P3 and P4 ) = 12 milliseconds. Next comes process P5 with priority number 4 and having burst time of 3 milliseconds. Waiting time for P5 will be 5 + 7 + 4 = 16.
  • Finally process P1 will get the CPU after waiting for 19 milliseconds (5 + 7 + 4 + 3). It will execute for 9 milliseconds so all process will be completed in total 28 milliseconds (i.e. 5 + 7 + 4 + 3 + 9  =  28 ).
  • It can be represented in gantt chart as follow:

Priority Scheduling

Notation:

T.W.T = Total Waiting Time

A.W.T = Average Waiting Time

T.T.T = Total Turnaround Time

A.T.T = Average Turnaround Time

Preemptive:

Consider the following processes and their CPU burst time and find out average waiting time and average turnaround time using preemptive form of priority scheduling algorithm (Lower number represents higher priority).

Preemptive Priority Scheduling

  • Here, we also have to consider arrival time of processes as they arrive at different time period. At zero milliseconds we have only one process available in ready queue i.e. process P1 as it arrives first so obviously there is no need to compare priority. CPU will be allocated to P1 and thus waiting time for P1 is zero.
  • after the execution of one milliseconds, new process P2 arrives at ready queue with priority of 3 at this moment P1 has finished execution of one milliseconds so its remaining burst time will be 8 (9-1). With the arrival of process P2, ready queue contains two processes so now system has to take decision to which process CPU will be allocated based on their priority level assuming preemptive priority scheme. Since priority of newly arrived process P2 (3) is higher than the priority of process P1 (5), system will deallocated the CPU from P1 and allocate to P2.
  • As another millisecond passed, new process P3 arrives at the time of 2 milliseconds with priority of 1. At this moment, P2 has finished execution of about one milliseconds and so remaining burst time of process P2 will be 3 (4-1). As per rule, whenever new process arrives at ready queue, we have to compare their priority for process selection. Since process P3 has the highest priority (1) among all three processes, so execution of currently running process P2 will be suspended and CPU will  be assigned to process P3. At the time period of 3 milliseconds, new process P4 arrives with priority of 2. Process P3 will continue to execute as again it has the highest priority. Similarly at 4 milliseconds, process P5 arrives with priority of 4 but due to low priority of other processes P3 will continue its execution. At this moment remaining burst time of P3 will be 3 and since we don’t have any new processes, process P3 will continue to execute for another 3 milliseconds and will finish its task at 7 milliseconds (3 + 4).
  • Notice that now we have only four processes available and after comparing their priority next highest priority process is P4 ( priority 2) so P4 will get CPU next at the time of 7 milliseconds and it will continue to execute for another 7 milliseconds after that next process is P2 to get the CPU. It will finish its execution at 17 milliseconds and CPU will be given to P5. At last process P1 will have chance for execution at it will continue for 8 milliseconds.
  • The complete chart can be given as below:

Preemptive Priority Scheduling Example

Average Waiting Time

Waiting Time =Total waiting Time – No.of Milisec. Process executed – Arrival Time

P1 = 20 - 1 - 0 = 19
P2 = 14 - 1 - 1 = 12
P3 = 4 -  2 - 2 = 0
P4 = 7 -  0 - 3 = 4
P5 = 17 - 0 - 4 = 13

------------------------
Total             48 Mills.

Average Waiting Time = Total Waiting Time / No.of Process

48 / 5 (No.of Process)

= 9.6 Mills.

Average Turnaround Time

Turnaround Time = Total Turnaround Time – Arrival Time

P1 = 28 - 0 = 28
P2 = 17 - 1 = 16
P3 = 7 -  2 = 5
P4 = 14 - 3 = 11
P5 = 20 - 4 = 16

------------------------
Total         76 Mills.

Average Turnaround Time = Total Turnaround Time / No.of Process

76 / 5

=15.2 Mills.

Limitations

  • A major problem with priority scheduling is indefinite blocking or starvation.
  • In priority scheduling some low priority process may keep waiting indefinitely for CPU. In a heavily loaded system continuous arrival of higher priority processes can prevent low priority process from getting the CPU.
  • In this condition two things will happen, either we can run the process when system becomes lightly loaded, or the computer system will crash and lose all unfinished low priority processes.
  • One solution to the problem of starvation is aging.
  • Aging is a technique of gradually increasing the priority of process that waits in the system for a longer period of time.
  • Eg:- If priority range from 127(low) – 0(high) we could decremented the priority of waiting process by every 15 minutes.
  • Eventually when a process with an initial priority of 127 will have a highest priority in the system and it would be executed.