1. Introduction
Priority Scheduling is a CPU scheduling algorithm in which each process is assigned a priority value, and the CPU is allocated to the process with the highest priority. Unlike FCFS, which schedules processes based on arrival order, or SJF/SRTF, which schedule based on burst time, Priority Scheduling makes decisions based on the relative importance of processes.
The fundamental idea is:
More important processes should receive CPU service before less important processes.
Priority Scheduling is widely used in modern operating systems because not all processes have equal importance. For example:
System processes are often more critical than user applications.
Real-time tasks may require immediate execution.
Background jobs can tolerate delays.
By assigning different priority levels, the operating system can ensure that critical tasks receive faster access to CPU resources.
Priority Scheduling can be implemented in two forms:
Non-Preemptive Priority Scheduling
Preemptive Priority Scheduling
Both versions use priority values to determine execution order, but they differ in how they handle newly arriving high-priority processes.
2. Basic Concept
In Priority Scheduling, every process is assigned a priority value.
The scheduler examines all processes in the ready queue and selects:
The process with the highest priority.
The selected process receives the CPU according to the scheduling policy.
Scheduling Rule
Ready Queue
P1 (Priority 3)
P2 (Priority 1)
P3 (Priority 2)
Select → P2
because P2 has the highest priority.
The exact interpretation of priority values depends on the operating system.
Some systems use:
Smaller Number
↓
Higher Priority
while others use:
Larger Number
↓
Higher Priority
The important requirement is consistency.
3. Priority Representation
Priority values are numerical indicators used to rank processes.
Common Convention
Most operating systems use:
Priority 1 → Highest
Priority 2
Priority 3
Priority 4
Priority 5 → Lowest
Thus:
Lower Number
↓
Higher Priority
Alternative Convention
Some systems reverse this relationship:
Priority 100 → Highest
Priority 50
Priority 20
Priority 1 → Lowest
Thus:
Higher Number
↓
Higher Priority
Regardless of convention, the scheduler always selects the process considered highest priority.
4. Working Mechanism
Whenever the CPU becomes available, the scheduler performs the following steps:
Examine all ready processes.
Compare priority values.
Select highest-priority process.
Allocate CPU.
Repeat whenever a scheduling event occurs.
Execution Rule
Select Process
With Highest Priority
Conceptual Example
Ready Queue:
P1 Priority = 4
P2 Priority = 1
P3 Priority = 3
Execution order:
P2 → P3 → P1
because:
1 < 3 < 4
5. Types of Priority Scheduling
Priority Scheduling can operate in either non-preemptive or preemptive mode.
5.1 Non-Preemptive Priority Scheduling
In Non-Preemptive Priority Scheduling:
Once a process receives the CPU, it continues execution until completion or blocking.
Even if a higher-priority process arrives, the running process is not interrupted.
Example
| Process | AT | BT | Priority |
|---|---|---|---|
| P1 | 0 | 5 | 2 |
| P2 | 1 | 3 | 1 |
| P3 | 2 | 4 | 3 |
Time = 0
Only P1 is available.
Execute P1
Time = 1
P2 arrives.
Although P2 has higher priority:
P2 Priority = 1
P1 Priority = 2
P1 continues because scheduling is non-preemptive.
Execution Order
P1 → P2 → P3
Gantt Chart
0 5 8 12
| P1 | P2 | P3 |
Characteristics
No interruption of running process
Lower overhead
Simpler implementation
5.2 Preemptive Priority Scheduling
In Preemptive Priority Scheduling:
A newly arriving higher-priority process can immediately preempt the currently running process.
Whenever a new process arrives, the scheduler compares priorities.
If the new process has higher priority:
Current Process Stopped
and CPU is reassigned.
Example
Suppose:
P1 Running
Priority = 3
A new process arrives:
P2 Priority = 1
Since:
1 < 3
the scheduler performs:
P1 → Preempted
P2 → Running
This improves responsiveness for important processes.
6. Gantt Chart Example (Preemptive)
Consider the following processes:
| Process | AT | BT | Priority |
|---|---|---|---|
| P1 | 0 | 6 | 2 |
| P2 | 1 | 3 | 1 |
| P3 | 4 | 4 | 3 |
Execution
Time 0:
P1 Starts
Time 1:
P2 Arrives
Higher Priority
P1 is preempted.
P2 executes until completion.
P1 resumes.
Then P3 executes.
Gantt Chart
0 1 4 9 13
|P1| P2 | P1 | P3 |
This illustrates dynamic priority-based preemption.
7. Characteristics
Priority Scheduling possesses several important characteristics.
Priority-Based Selection
Execution order depends on process importance.
Flexible Design
Priorities may be:
Static
Dynamic
Supports Preemption
Can be implemented as:
Preemptive
Non-preemptive
Widely Used
Forms the basis of many real operating system schedulers.
8. Advantages
8.1 Important Processes Execute First
Critical tasks receive CPU resources before less important tasks.
Example:
System Task
↓
User Task
System task executes first.
8.2 Suitable for Real-Time Systems
Many real-time systems require:
Fast execution
Predictable behavior
Priority Scheduling naturally supports such requirements.
8.3 Flexible Scheduling Policy
Priorities can be assigned based on:
Importance
Resource requirements
User level
Process type
This provides significant flexibility.
8.4 Supports Critical Applications
Examples include:
Medical systems
Industrial controllers
Aerospace software
where certain tasks must receive immediate CPU attention.
9. Major Problem: Starvation
The most serious drawback of Priority Scheduling is:
Starvation
What is Starvation?
Starvation occurs when a process waits indefinitely because higher-priority processes continuously receive CPU service.
Example
Suppose:
P1 Priority = 10
is waiting.
Meanwhile:
P2 Priority = 1
P3 Priority = 2
P4 Priority = 1
P5 Priority = 3
keep arriving.
The scheduler always chooses:
Higher Priority Processes
Result:
P1 Never Executes
Consequences
Unfair scheduling
Unbounded waiting time
Poor predictability
Starvation is one of the most frequently discussed drawbacks in operating system interviews and examinations.
10. Solution: Aging
The standard solution to starvation is:
Aging
Concept
Aging gradually increases the priority of processes that have been waiting for a long time.
The longer a process waits:
Waiting Time ↑
↓
Priority ↑
Eventually the process becomes important enough to receive CPU time.
Example
Initially:
P1 Priority = 10
After waiting:
Priority = 9
Later:
Priority = 8
Eventually:
Priority = 1
At that point the scheduler selects the process.
Key Insight
Aging ensures:
Every process eventually receives CPU service.
Therefore:
Aging Prevents Starvation
while preserving the benefits of priority-based scheduling.
11. Implementation Approaches
Several techniques are used to implement Priority Scheduling.
Priority Queue
Processes are stored according to priority.
Example:
Priority Queue
P2
P3
P1
P4
Highest-priority process remains at the front.
Multiple Ready Queues
Separate queue maintained for each priority level.
Example:
Priority 1 Queue
Priority 2 Queue
Priority 3 Queue
Scheduler always checks higher-priority queues first.
Dynamic Priority Adjustment
Operating systems may modify priorities based on:
Waiting time
CPU usage
I/O behavior
Aging
This approach improves fairness and responsiveness.
12. Comparison with Previous Algorithms
| Feature | FCFS | SJF | SRTF | Priority |
|---|---|---|---|---|
| Scheduling Basis | Arrival Time | Burst Time | Remaining Time | Priority |
| Preemptive | No | No | Yes | Both |
| Waiting Time | Moderate | Low | Lowest | Depends on Priorities |
| Response Time | Poor | Good | Excellent | Good |
| Starvation | No | Possible | Possible | Possible |
| Complexity | Low | Medium | High | Medium |
| Fairness | High | Moderate | Moderate | Variable |
Key Difference
FCFS
First Arrive
↓
First Execute
SJF
Shortest Job
↓
First Execute
SRTF
Shortest Remaining Time
↓
First Execute
Priority
Most Important Process
↓
First Execute
13. Real-World Usage
Priority Scheduling is extensively used in modern systems.
Operating Systems
Most operating systems assign process priorities.
Examples:
Kernel processes
User processes
Background services
may all have different priority levels.
Embedded Systems
Critical control tasks receive higher priorities.
Examples:
Sensor monitoring
Device control
Real-Time Systems
Priority Scheduling is fundamental in:
Industrial automation
Medical equipment
Aerospace systems
where deadlines and criticality determine execution order.
Performance Summary
| Criterion | Priority Scheduling Performance |
|---|---|
| CPU Utilization | Good |
| Throughput | Good |
| Waiting Time | Variable |
| Response Time | Good for High-Priority Processes |
| Fairness | Moderate |
| Starvation | Possible |
| Scheduling Overhead | Moderate |