Abstract
In priority scheduling, processes are scheduled according to their priorities. The process with the highest priority is scheduled first. It is one of the most common scheduling algorithms in batch systems.
Scope
This article talks about priority scheduling in detail.
Definition
In priority scheduling, every job is assigned a priority and the CPU is assigned to the highest priority job among all the jobs in the ready queue. If two processes have the same priority, then we give priority to the process that came first. Priority scheduling can be preemptive or non-preemptive. 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 put the new process at the head of the ready queue.
Let’s consider an example of non-preemptive priority scheduling:
| PROCESS | ARRIVAL TIME | PRIORITY | BURST TIME |
| P0 | 0 | 5 | 3 |
| P1 | 1 | 3 | 5 |
| P2 | 2 | 15 | 8 |
| P3 | 3 | 12 | 6 |
Here P0 is scheduled first since it arrives first. After its completion, the other three processes arrive. Now the process with the highest priority which is P2 is scheduled.
Gnatt chart :
Final chart
| PROCESS | ARRIVAL TIME | PRIORITY | BURST TIME | TURN AROUND TIME | WAITING TIME |
| P0 | 0 | 5 | 3 | 3 | 0 |
| P1 | 1 | 3 | 5 | 21 | 16 |
| P2 | 2 | 15 | 8 | 9 | 1 |
| P3 | 3 | 12 | 6 | 14 | 8 |
Now let us consider an example of preemptive priority scheduling
| PROCESS | ARRIVAL TIME | PRIORITY | BURST TIME |
| P0 | 0 | 5 | 3 |
| P1 | 1 | 3 | 5 |
| P2 | 2 | 15 | 8 |
| P3 | 3 | 12 | 6 |
P0 being the first is scheduled and it runs for 1 unit. At t = 1, P1 arrives. Since P1 has less priority, P0 continues to run for 1 more unit. At t = 2, P2 arrives. Since it has greater priority, it gets scheduled. It runs until completion. After this P3 which has a greater priority is scheduled. After its completion, the remaining processes are compared. P0 having greater priority is scheduled and it finishes its remaining 1 unit followed by P1.
| PROCESS | ARRIVAL TIME | PRIORITY | BURST TIME |
| P0 | 0 | 5 | |
| P1 | 1 | 3 | 5 |
| P2 | 2 | 15 | 8 |
| P3 | 3 | 12 | 6 |
Gantt chart
Final chart
| PROCESS | ARRIVAL TIME | PRIORITY | BURST TIME | TURN AROUND TIME | WAITING TIME |
| P0 | 0 | 5 | 3 | 17 | 14 |
| P1 | 1 | 3 | 5 | 21 | 16 |
| P2 | 2 | 15 | 8 | 8 | 0 |
| P3 | 3 | 12 | 6 | 13 | 7 |
Average waiting time and average response time depend on the priority processes. If there are many priority processes that are coming first and then there is a low priority process that has been waiting for so long, then the average between time and also response time might go up.
Some important points
- A major problem with priority scheduling algorithms is indefinite block or starvation. A process that is ready to run but waiting for the CPU can be blocked. It can leave some low-priority processes waiting indefinitely.
- In a heavily loaded system, a steady stream of high-priority processes can prevent a low-priority process from ever getting the CPU.
- 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.
Summary
In priority scheduling, the process with the highest priority is executed first, and so on. It can be preemptive and non-preemptive. A major problem with priority scheduling is starvation and it can be solved by the process called aging.
Special thanks to Ami Jangid for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article