Preemptive Priority Scheduling Algorithm: Optimizing CPU Utilization with Process Prioritization

Understand the preemptive priority scheduling algorithm for efficient CPU utilization. This tutorial provides a detailed explanation of the algorithm's operation, a step-by-step example with calculations of turnaround and waiting times, and a visual Gantt chart for improved understanding.

Preemptive Priority Scheduling Algorithm

Understanding Preemptive Priority Scheduling

Preemptive priority scheduling is a CPU scheduling algorithm where processes are assigned priorities. When a new process arrives, its priority is compared to the currently running process and all other processes in the ready queue. The highest-priority process is then selected to run next. The key difference between preemptive and non-preemptive priority scheduling is that in preemptive scheduling, a currently running process can be interrupted (preempted) if a higher-priority process arrives.

Once all processes are in the ready queue, the algorithm functions like non-preemptive priority scheduling; the currently running process executes to completion without interruption.

Example: Preemptive Priority Scheduling

Let's consider seven processes (P1-P7) with their priorities, arrival times, and burst times as shown below:

Process Id Priority Arrival Time Burst Time
P1 2 (Low) 0 1
P2 6 1 7
P3 3 2 3
P4 5 3 3
P5 4 4 5
P6 10 (High) 5 15
P7 9 6 8

Let's trace the execution:

  1. Time 0: P1 arrives and runs for 1 unit.
  2. Time 1: P2 arrives but P1 has already finished.
  3. Time 2: P3 arrives; it has higher priority than P2, so P3 runs.
  4. Time 2-5: P3 runs. P4, P5, and P6 arrive but have lower priority than P3.
  5. Time 5: P3 completes. P5 (highest remaining priority) runs.
  6. Time 5-10: P5 runs. All processes are now in the ready queue, so the algorithm becomes non-preemptive.
  7. Time 10-13: P6 (highest remaining priority) runs.
  8. Time 13-20: P2 (highest remaining priority) runs.
  9. Time 20-28: P7 (highest remaining priority) runs.
  10. Time 28-43: P4 (highest remaining priority) runs.

Results and Calculations

Using the Gantt chart created from the above steps, we can calculate the completion time, turnaround time, and waiting time for each process:

Turnaround Time = Completion Time - Arrival Time

Waiting Time = Turnaround Time - Burst Time

Process Id Priority Arrival Time Burst Time Completion Time Turnaround Time Waiting Time
P1 2 0 1 1 1 0
P2 6 1 7 20 19 12
P3 3 2 3 5 3 0
P4 5 3 3 43 40 37
P5 4 4 5 10 6 1
P6 10 5 15 13 8 -7
P7 9 6 8 28 22 14

Average Waiting Time: (0 + 12 + 0 + 37 + 1 + (-7) + 14) / 7 ≈ 8.14 units