Priority Scheduling

• The SJF algorithm is a special case of the general priority scheduling algorithm. A priority is associated with each process, and the CPU is allocated to the process with the highest priority. Equal-priority processes are scheduled in FCFS order.
• An SJF algorithm is simply a priority algorithm where the priority (p) is the inverse of the (predicted) next CPU burst. The larger the CPU burst, the lower the priority, and vice versa.
• Priorities are generally indicated by some fixed range of numbers, such as 0 to 7 or 0 to 4095. However, there is no general agreement on whether 0 is the highest or lowest priority. Some systems use low numbers to represent low priority; others use low numbers for high priority. We use as low numbers represent high priority.
• As an example, consider the following set of processes, assumed to have arrived at time 0, in the order $P_1, P_2,\ldots P_5$, with the length of the CPU burst given in milliseconds:
  

  	Burst		Waiting	Turnaround
  Process	Time	Priority	Time	Time
  $P_1$	10	3	6	16
  $P_2$	1	1	0	1
  $P_3$	2	4	16	18
  $P_4$	1	5	18	19
  $P_5$	5	2	1	6
  Average	-	-	8.2	12

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

  
• Priorities can be defined either internally or externally.
  • Internally defined priorities use some measurable quantity or quantities to compute the priority of a process. For example, time limits, memory requirements, the number of open files, and the ratio of average I/O burst to average CPU burst have been used in computing priorities.
  • External priorities are set by criteria outside the OS, such as the importance of the process, the type and amount of funds being paid for computer use, the department sponsoring the work, and other, often political, factors.
• Priority scheduling can be either pre-emptive or nonpreemptive. When a process arrives at the ready queue, its priority is compared with the priority of the currently running process.
  • A pre-emptive 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 nonpreemptive priority scheduling algorithm will simply put the new process at the head of the ready queue.
• A major problem with priority scheduling algorithms is indefinite blocking, or starvation. A process that is ready to run but waiting for the CPU can be considered blocked.
  • A priority scheduling algorithm can leave some low priority processes waiting indefinitely.
  • In a heavily loaded computer system, a steady stream of higher-priority processes can prevent a low-priority process from ever getting the CPU.
• It is often convenient to group processes into priority classes and use priority scheduling among the classes but round-robin scheduling within each class. Figure 5 shows a system with four priority classes.
• The scheduling algorithm is as follows: as long as there are runnable processes in priority class 4, just run each one for one quantum, round-robin fashion, and never bother with lower priority classes, if priority class 4 is empty, then run the class 3 processes round robin. If classes 4 and 3 are both empty, then run class 2 round robin, and so on. If priorities are not adjusted occasionally, lower priority classes may all starve to death.

  Figure 5: A scheduling algorithm with four priority classes.

  
• 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.
  • For example, if priorities range from 127 (low) to 0 (high), we could increase the priority of a waiting process by 1 every 15 minutes.
  • Eventually, even a process with an initial priority of 127 would have the highest priority in the system and would be executed.

  Figure 6: An example to Priority-based Scheduling.