Priority Scheduling – CPU Scheduling

Priority Scheduling

• In priority scheduling, a priority is associated with all processes.
• Process are executed in sequence according to their priority.
• The CPU time allocated to the process with highest priority.
• If the priority of two or more processes are equal than the process that has been inserted first into the ready queue is selected for execution. In other words, FCFS scheduling is performed when two or more processes have same priority.
• The priorities are implemented as a fixed range of numbers such as 0 to 7 or 0 to 4,095.
• In some systems, the highest number represents the highest priority. In such cases, processes with priority 7, is executed first.
• In other system, a low number indicates a high priority. In that case, a process with priority 0 is executed first.
• Priorities can be defined in two ways : internally or externally.

• Priority of a process can be defined by the user or an application or by the operating system itself.
• When a user or an application defines the priority of a process, this is called externally defined priority.
• It is called so because the criteria for assigning the priority to a process are external to the operating system. External defined priorities may be based on He importance of process, the type and amount of funds being paid for computer use etc.
• When an operating system itself assigns priority to a process, it is called internally defined priority. The internal defined priority uses some measurable quantity qualities to compute the priority of a process.
• For example, time limits, memory requirements, the number of open files and the ratio of diverge I/O bust to average CPU burst etc.
• Priority scheduling can be preemptive or non-preemptive.
• In preemptive priority scheduling, scheduler allocates the CPU to the new process if the priority of new process is higher than the priority of the running process.
• In non-preemptive priority scheduling, the running process is not interrupted even the new process has a higher priority. In this case the new process will be placed at the head of ready queue.

Advantage of Priority Scheduling

1. The main advantage of this scheduling is that it focuses on a particular aspect of a process. Processes are scheduled according to their importance.
2. SJF algorithm is a specific form of the priority scheduling algorithm in which priority is inverse of the (predicted) next CPU burst. The larger the CPU burst, the lower the priority.

Disadvantage of Priority Scheduling

1. In certain situations, a low priority process can be blocked infinitely if comparatively high priority processes arrive in the ready queue frequently. This situation in which low priority processes are block waiting indefinitely for CPU is known as starvation.

Starvation of low priority process can be prevented by using the concept of aging.

Aging is a technique of gradually increasing the priority of processes that wait in a system for a long time. For example, the range of priority in operating system is from 0 to 15. Priority of process X is 1. There are several processes with higher priority in the ready queue. Processes with higher priorities are inserted into ready queue frequently. In this situation, the process X will face starvation. The operating system increases priority of a process by 1 in every 5 minutes. Thus the process X, becomes a high priority process after some time and is selected for execution by the scheduler.

2. Another problem with priority scheduling is deciding which process gets which priority level assigned to it.

Examples of Priority Scheduling

Example 1

Consider the following set of processes, all of which have arrived at time 0. The priority of these processes is given in the table below:

Using priority scheduling, we would schedule these processes according to the following Gan chart :

Waiting time for P1 =6 milliseconds

Waiting time for P2 =0 milliseconds

Waiting time for P3 = 16 milliseconds

Waiting time for P4 = 18 milliseconds

Waiting time for P5 = 1 milliseconds

Average Waiting time = (6+0+16 + 18 +1)/5

= 41/5 = 8.2 milliseconds

Example 2

P1, P2, P3 are the processes with their arrival time, burst time and priorities listed in table below:

Process	Burst Time	Priority	Arrival Time
P1	10	3	0
P2	5	2	1
P3	2	1	2

Using priority scheduling, the process are scheduled according to the following Gantt Chart:

Waiting time for P1 = 0+ (8-1) = 7 milliseconds

Waiting time for P2 = (1-1) + (4 – 2) = 2 milliseconds

Waiting time for P3 = (2-2) = 0 milliseconds

Average waiting time = {0+(8-1)+ (1-1)+(4-2)+(2-2)}/3

  = (7+2+0)/3 =9/3 = 3 milliseconds