Priority Scheduling Policy
In Priority Scheduling, a priority value (an integer) is associated with each process, and the CPU is allocated to the process with the highest priority. If two processes have the same priority, they are usually scheduled in a First-Come, First-Served (FCFS) order.
Interestingly, Shortest-Job-First (SJF) is just a special case of priority scheduling where the priority is mathematically defined as the inverse of the next CPU burst length!
Real-Life Example
Think of a VIP line at an exclusive club or airport security. Even if a regular person has been waiting in the queue for an hour, the moment a VIP (high priority) arrives, they get to bypass the entire line and go straight to the front. Priority scheduling in operating systems works exactly the same way for critical system processes.
Example 1: Non-Preemptive Priority Scheduling
Priority scheduling can be either Preemptive or Non-Preemptive. Let's look at the Non-Preemptive version first. Once a process starts running, it cannot be interrupted until it finishes.
| Process | Arrival Time (ms) | Burst Time (ms) | Priority |
|---|---|---|---|
| P1 | 0 | 5 | 3 |
| P2 | 1 | 4 | 1 |
| P3 | 2 | 2 | 4 |
| P4 | 3 | 1 | 2 |
Here is how the non-preemptive scheduling unfolds:
1. At time 0, only P1 has arrived. It starts executing and runs to completion (time 5).
2. At time 5, P2, P3, and P4 have all arrived and are in the ready queue.
3. The OS checks their priorities: P2(1), P3(4), P4(2). Since lower number = higher priority, P2 gets the CPU next and runs to completion (time 9).
4. At time 9, P3 and P4 remain. P4 has a priority of 2, beating P3's priority of 4. P4 runs until time 10.
5. Finally, P3 runs from time 10 to 12.
Here is the Gantt chart:
+---------+--------+--+----+
| P1 | P2 |P4| P3 |
+---------+--------+--+----+
0 5 9 10 12Let's calculate the Waiting Time (Start Time - Arrival Time):
- P1: 0 - 0 = 0 ms.
- P2: 5 - 1 = 4 ms.
- P3: 10 - 2 = 8 ms.
- P4: 9 - 3 = 6 ms.
Average Waiting Time = (0 + 4 + 8 + 6) / 4 = 4.5 ms.
Let's calculate the Turnaround Time (Completion Time - Arrival Time):
- P1: 5 - 0 = 5 ms.
- P2: 9 - 1 = 8 ms.
- P3: 12 - 2 = 10 ms.
- P4: 10 - 3 = 7 ms.
Average Turnaround Time = (5 + 8 + 10 + 7) / 4 = 7.5 ms.
Example 2: Preemptive Priority Scheduling
Now let's use the exact same processes, but with Preemptive Priority Scheduling. If a newly arriving process has a higher priority than the currently running process, the CPU is preempted (taken away)!
| Process | Arrival Time (ms) | Burst Time (ms) | Priority |
|---|---|---|---|
| P1 | 0 | 5 | 3 |
| P2 | 1 | 4 | 1 |
| P3 | 2 | 2 | 4 |
| P4 | 3 | 1 | 2 |
Here is how preemptive scheduling changes the game:
1. At time 0, P1 starts running.
2. At time 1, P2 arrives with a Priority of 1. Because P2's priority (1) is better than P1's priority (3), P1 is preempted! P2 takes over. (P1 has 4 ms of burst left).
3. At time 2, P3 arrives with Priority 4. This is lower than P2's Priority 1, so P2 continues.
4. At time 3, P4 arrives with Priority 2. This is also lower than P2's Priority 1, so P2 continues.
5. At time 5, P2 finishes. The queue is: P1(Rem 4, Pr 3), P3(Rem 2, Pr 4), P4(Rem 1, Pr 2). P4 has the highest priority and runs until time 6.
6. At time 6, between P1 and P3, P1 has the higher priority. P1 resumes and finishes its remaining 4 ms at time 10.
7. Finally, P3 runs from time 10 to 12.
Here is the Gantt chart:
+--+--------+--+--------+----+
|P1| P2 |P4| P1 | P3 |
+--+--------+--+--------+----+
0 1 5 6 10 12Let's calculate the Turnaround Time (Completion Time - Arrival Time):
- P1 finishes at 10 ms: 10 - 0 = 10 ms.
- P2 finishes at 5 ms: 5 - 1 = 4 ms.
- P3 finishes at 12 ms: 12 - 2 = 10 ms.
- P4 finishes at 6 ms: 6 - 3 = 3 ms.
Average Turnaround Time = (10 + 4 + 10 + 3) / 4 = 6.75 ms.
Let's calculate the Waiting Time (Turnaround Time - Burst Time):
- P1: 10 - 5 = 5 ms.
- P2: 4 - 4 = 0 ms.
- P3: 10 - 2 = 8 ms.
- P4: 3 - 1 = 2 ms.
Average Waiting Time = (5 + 0 + 8 + 2) / 4 = 3.75 ms.
Preemption significantly improved both the average waiting time and average turnaround time!
The Problem: Starvation
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 if a steady stream of higher-priority processes keeps arriving.
The Solution: Aging
The solution to the problem of indefinite blockage of low-priority processes is a technique called aging. Aging involves gradually increasing the priority of processes that have been waiting in the system for a long time. Eventually, even a process with an initially terrible priority will be aged into a high priority and given the CPU.
Advantages of Priority Scheduling
- Provides a mechanism to ensure critical system processes always get CPU time when they need it.
- Highly flexible since priorities can be assigned dynamically based on system needs.
Disadvantages of Priority Scheduling
- Highly prone to Starvation for low-priority user processes.
- It can be complex to manage dynamically changing priorities and implement proper aging.