Subscribe by Email

Wednesday, June 19, 2013

Explain the Priority CPU scheduling algorithm

A number of scheduling algorithms are available today and all are appropriate for some different kinds of scheduling environments. In this article we give a brief explanation about the ‘priority CPU scheduling algorithm’. 

For those who are not familiar with this scheduling algorithm, a special case of the priority algorithm is the shortest job first scheduling algorithm (SJF). 

- This algorithm involves associating a priority with each and every thread or process. 
- Out of all the processes, the one with the highest priority is chosen and given to the processor for execution. 
- Thus, it is decided by the priority that which process has to be executed first. 
There are cases when the two or more processes might have the same priority. 
- In such case FCFS (first come first served) scheduling algorithm is applied. 
The process first in the queue is then executed first. 
- The SJF is essentially a modification of the priority algorithm. 
- Here, the priority of a process (indicated by p) is simply taken as the inverse of the following CPU burst as predicted. 
- This implies if a process is having a large CPU burst, then its priority will be low accordingly and similarly if the CPU burst is small, the priority will be high. 
Numbers in some fixed range are used for indicating the priorities such as from 0 to 4095 or from 0 to 7 etc. 
- One thing to be noted is that there has been no general agreement up on whether the number 0 indicates lowest priority or highest priority.
- In some systems the lower priorities are indicated by the low numbers while in some systems low numbers mean higher priorities. 
- The latter case i.e., using low numbers for representing high priorities is more common.
For example, consider the 5 processes P1, P2, P3, P4 and P5 having CPU burst as 10, 1, 2, 1, 5 respectively and priority also respectively as 3, 1, 4, 5, 2. Using the priority scheduling algorithms, the processes will be executed in the following order:
P2, P5, P1, P3, P4

There are two ways of defining the priorities i.e., either externally or internally. This gives two types of priorities:

  1. Internally defined priorities: These priorities make use of some quantities that can be measured for computing a process’s priority. These quantities include memory requirements, time limits, ration of the I/O burst and CPU burst, number of files and so on.
  2. Externally defined priorities: These priorities are defined by some criteria that are external to the operating system. Such factors include political factors, department leading the work; importance of the process, amount of money paid and so on.
The priority scheduling can be itself divided in to two types namely non – preemptive or preemptive. The priority of the process waiting in the ready queue is compared with that of the executing process.

Ø  Preemptive priority scheduling: Here the CPU is preempted if the waiting process has a priority higher than that of the currently executing process.
Ø  Non – preemptive priority scheduling: Here the new process will be let waiting in the ready queue till the execution of the current process is complete.

Starvation or the indefinite blocking presents a major problem in priority scheduling. A process will be considered blocked if it is ready for execution but has to wait for CPU. It is very likely that the low priority processes will be left waiting indefinitely for CPU. In a system that is heavily loaded most of the time, if the number of high priority processes is large, the low priority processes will be prevented from getting processor. 

No comments:

Facebook activity