Priority Scheduling

Introduction

Priority scheduling is a CPU scheduling technique in operating systems where processes are assigned priorities. The scheduler selects the process with the highest priority for execution first. It optimizes resource allocation by considering the relative importance of processes rather than just their arrival time or burst duration.

"The essence of priority scheduling lies in balancing system responsiveness with process importance, ensuring critical tasks receive timely CPU access." -- A. Silberschatz et al.

Core Concepts

Priority

Numerical or categorical value indicating process importance. Lower number often means higher priority or vice versa depending on system design.

Process Scheduling

CPU allocated based on priority, not arrival or burst time alone. Higher priority preempts lower priority processes in preemptive variants.

Priority Assignment

Static: fixed at process creation. Dynamic: varies during process lifetime based on criteria like aging or resource consumption.

Preemption

In preemptive priority scheduling, running process can be interrupted if a higher priority process arrives.

Queue Management

Multiple priority queues or a single queue sorted by priority. Scheduling selects from highest priority queue first.

Types of Priority Scheduling

Preemptive Priority Scheduling

Process currently running is preempted when a higher priority process arrives. Enables more responsive systems but may cause starvation.

Non-Preemptive Priority Scheduling

Running process continues until completion or blocking, even if higher priority process arrives. Simpler but less flexible.

Static Priority Scheduling

Priorities assigned once and remain fixed. Easier implementation but less adaptive to workload changes.

Dynamic Priority Scheduling

Priorities change during execution to prevent starvation and adjust to system state. Techniques include aging and feedback.

Implementation Details

Data Structures

Priority queue implemented with heaps, balanced trees, or linked lists. Efficient extraction of highest priority process essential for performance.

Context Switching

Triggered when a process of higher priority arrives (preemptive) or process terminates/waits (non-preemptive). Overhead must be minimized.

Priority Inversion Handling

Priority inversion occurs when low priority process holds resources needed by high priority process. Solutions include priority inheritance protocols.

Scheduler Algorithm

Steps: select highest priority process ready, dispatch, preempt if higher priority arrives (if preemptive), update priorities (dynamic).

Priority Assignment Methods

Based on process type (system/user), resource needs, deadlines, or user input. May be static or dynamically adjusted.

Advantages

Responsiveness

Critical processes receive CPU time promptly, improving system responsiveness.

Flexibility

Supports both static and dynamic priority schemes tailored to system requirements.

Efficiency

Optimizes CPU utilization by prioritizing important tasks.

Preemption Support

Allows interruption of lower priority processes, enabling rapid adaptation to workload changes.

Disadvantages

Starvation

Low priority processes may never get CPU time if higher priority processes dominate.

Complexity

Priority assignment and dynamic adjustment add overhead and complexity to scheduler design.

Priority Inversion

Can degrade system performance if not properly managed.

Fairness Issues

Processes with similar priorities may experience unfair delays if newer higher priority processes continuously arrive.

Problem of Starvation

Definition

Situation where low priority processes wait indefinitely for CPU due to continuous arrival of higher priority processes.

Causes

Unbounded priority differences, lack of priority adjustment, high system load with many high-priority tasks.

Consequences

Degraded system fairness, potential process failure, resource underutilization.

Detection

Monitoring wait times, queue lengths, and process states to identify starvation symptoms.

Aging Technique

Concept

Gradually increasing priority of waiting processes to prevent starvation.

Implementation

Increment priority value based on wait time or scheduling cycles.

Benefits

Ensures fairness, reduces indefinite blocking, balances responsiveness and equity.

Limitations

May lead to priority inversion if not carefully controlled; needs tuning of increment rates.

Comparison with Other Algorithms

First-Come, First-Served (FCFS)

Priority scheduling offers better responsiveness and flexibility than FCFS, which is strictly FIFO without prioritization.

Shortest Job Next (SJN)

SJN optimizes average waiting time; priority scheduling optimizes process importance but may not minimize wait time.

Round Robin (RR)

RR ensures fairness via time quanta; priority scheduling may sacrifice fairness for priority but can implement aging to mitigate.

Multilevel Queue Scheduling

Priority scheduling is a component of multilevel queues, which segregate processes by priority classes with distinct scheduling policies.

Practical Applications

Real-Time Systems

Ensures time-critical tasks receive CPU access promptly to meet deadlines.

Interactive Systems

Gives higher priority to user-facing processes for better responsiveness.

Batch Processing

Prioritizes system or administrative jobs over less critical background tasks.

Embedded Systems

Manages task importance efficiently in resource-constrained environments.

Example Scenarios

Preemptive Priority Scheduling Example

Process P1 (priority 2) running; Process P2 (priority 1) arrives → P1 preempted, P2 runs.

Non-Preemptive Priority Scheduling Example

Process P1 (priority 2) running; Process P2 (priority 1) arrives → P1 completes before P2 runs.

Starvation Example

Low priority process continuously delayed by newly arriving high priority processes.

Aging Example

Process waiting long time; priority incremented from 5 to 1, eventually scheduled.

Mathematical Model

Priority Function

Assign priority value P(i) to each process i. Lower P(i) indicates higher priority.

Waiting Time Calculation

Waiting time W(i) depends on sum of burst times of all processes with higher priority executed before i.

Scheduling Decision

At time t, select process i such that:

i = argmin P(j) for all j in ReadyQueue at time t

Aging Formula

Priority updated over time:

P(i, t) = P(i, 0) - α × waiting_time(i, t)

where α is aging rate constant, ensuring priority increases with waiting time.

References

• A. Silberschatz, P.B. Galvin, G. Gagne, Operating System Concepts, 9th ed., Wiley, 2013, pp. 145-180.
• W. Stallings, Operating Systems: Internals and Design Principles, 9th ed., Pearson, 2018, pp. 220-260.
• H. M. Deitel, P. J. Deitel, Operating Systems, 3rd ed., Pearson, 2004, pp. 352-380.
• R. S. Hall, "Priority Scheduling in Real-Time Systems," IEEE Trans. Computers, vol. 35, no. 6, 1986, pp. 550-556.
• J. Liu, Real-Time Systems, Prentice Hall, 2000, pp. 120-160.