A priority is associated with each process, and the CPU is allocated to the process with the highest priority. Equal priorities are scheduled in FCFS order. Priorities are generally indicated by some fixed range of numbers and there is no general method of indicating which is the highest or lowest priority, it may be either increasing or decreasing order.

Priority can be defined either internally or externally.

  • Internally defined priorities use some measurable quantity to compute the priority of a For example, time limits, memory requirements, the number of open files and the ratio of average I/O burst to average CPU burst has been used in computing priorities.
  • External priorities are set by criteria outside the OS, such as importance of process, the type and amount of funds being paid for computer user, and other political factors.

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 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 simply put the new process at the head of the ready queue.

A major problem of such scheduling algorithm is indefinite blocking or starvation. A process that is ready to run but waiting for the CPU can be considered blocked. Such scheduling can leave some low priority process waiting indefinitely. The solution for this problem is aging. Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time.

Q1. Consider following set of processes, assumed to have arrived at time 0 in order P1, P2, …, P5 with the length of the CPU burst given in milliseconds

Example:

Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2

Priority scheduling Gantt chart

Average waiting time

= (6 + 0 + 16 + 18 + 1) / 5

= 41 / 5

= 8.2 milliseconds