A scheduling algorithms like round-robin treat all processes as same. But if we consider other information about a process, some process is more important than the other. This is the motivation behind priority scheduling.
Each process carries a priority and process with the highest priority will be allocated CPU time. Since there is a chance that the current process may take a long time to finish, the scheduler decreases the priority of currently running with each clock tick. If a higher priority process is found in the ready queue, a process switch happens.
Gantt Chart for Priority Scheduling
Consider the following processes with priority assigned to them.
| Process | Burst time | Priority |
| p1 | 15 | 2 |
| p2 | 3 | 1 |
| p3 | 5 | 4 |
| p4 | 10 | 5 |
| p5 | 4 | 3 |
The following Gantt chart shows the new order of process execution.
The waiting time for p2 = 0.
The waiting time for p1 = 0 + 3 = 3.
The waiting time for p5 = 0 + 3 + 15 = 18.
The waiting time for p3 = 0 + 3 + 15 + 4 = 22.
The waiting time for p4 = 0 + 3 + 15 + 4 + 5 = 27.
The average waiting time = (0 + 3 + 18 + 22 + 27)/5 = 70/5 = 14 milliseconds.
Assigning Priority to Process
The priority can be assigned statically or dynamically. For example, UNIX has nice command to change the priority of the user process.
The process priority can be set internally or externally. When it is internal, then all internal factors such a memory, CPU time, number of open files, different ratios, etc are considered. External priority is factors such as the importance of process, department submitting the job, the fund allocated for computing resources, political factors and so on.
The processes can I/O bound, that means it takes most of its time at the device queue. If currently running CPU bound process takes time, then I/O bound process has to wait long time for CPU which is not necessary because these I/O processes have small CPU bursts. Hence, we can safely say that larger the CPU burst, lower the priority and lower CPU burst gets the higher priority.
A simple algorithm to set priority is q/f, where f the fraction of quantum that the process used. If 1 ms is used by the process with 50 ms, then its priority is 50. If 25 ms is used by the same process, its priority is 2.
You may group the process into priority classes and then set the round-robin algorithm on the class for scheduling.
If the CPU only runs higher priority processes, then the lower priority process never gets the CPU time and this results in starvation or indefinite blocking of lower priority processes.
A solution to this problem is aging where we priority is adjusted for lower priority processes waiting for a long time.
References
- Abraham Silberschatz, Peter B. Galvin, Greg Gagne (July 29, 2008) Operating System Concepts, 8 edn., : Wiley.
- Tanenbaum, Andrew S. (March 3, 2001) Modern Operating Systems, 2nd edn., : Prentice Hall.
