Priority Scheduling Algorithm: Complete Implementation Guide with Examples

What is Priority Scheduling Algorithm?

Priority scheduling is a CPU scheduling algorithm where each process is assigned a priority value, and the CPU is allocated to the process with the highest priority. This algorithm ensures that critical system processes and time-sensitive applications receive CPU resources before less important tasks.

The priority scheduling algorithm operates on a simple principle: higher priority processes execute first. When multiple processes are ready for execution, the scheduler selects the one with the highest priority value (or lowest numerical priority, depending on the system’s convention).

Types of Priority Scheduling

Non-Preemptive Priority Scheduling

In non-preemptive priority scheduling, once a process starts executing, it continues until completion or until it voluntarily gives up the CPU. Even if a higher priority process arrives, the currently running process is not interrupted.

Characteristics:

• Simple implementation and lower overhead
• No context switching during process execution
• May cause starvation of low-priority processes
• Better for batch processing systems

Preemptive Priority Scheduling

In preemptive priority scheduling, if a new process with higher priority arrives while another process is executing, the currently running process is preempted and moved back to the ready queue.

Characteristics:

• More responsive to high-priority processes
• Higher overhead due to frequent context switching
• Better for interactive and real-time systems
• Requires careful priority assignment to prevent starvation

Priority Assignment Methods

Static Priority Assignment

Priorities are assigned when processes are created and remain constant throughout execution. Common methods include:

• User-defined priorities: Users specify priority levels
• Process type-based: System processes get higher priority than user processes
• Memory requirements: Processes with smaller memory footprint get higher priority

Dynamic Priority Assignment

Priorities change during process execution based on various factors:

• Aging technique: Gradually increase priority of waiting processes
• Resource usage: Adjust priority based on CPU usage patterns
• Waiting time: Increase priority for processes waiting longer

Implementation Example: Non-Preemptive Priority Scheduling

Let’s implement a non-preemptive priority scheduling algorithm in C:

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int process_id;
    int arrival_time;
    int burst_time;
    int priority;
    int completion_time;
    int waiting_time;
    int turnaround_time;
    int remaining_time;
} Process;

void sortByArrivalTime(Process processes[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (processes[j].arrival_time > processes[j + 1].arrival_time) {
                Process temp = processes[j];
                processes[j] = processes[j + 1];
                processes[j + 1] = temp;
            }
        }
    }
}

void nonPreemptivePriorityScheduling(Process processes[], int n) {
    int current_time = 0;
    int completed = 0;
    int is_completed[n];
    
    // Initialize completion status
    for (int i = 0; i < n; i++) {
        is_completed[i] = 0;
        processes[i].remaining_time = processes[i].burst_time;
    }
    
    printf("Execution Order:\n");
    printf("Time\tProcess\tPriority\n");
    
    while (completed != n) {
        int highest_priority = -1;
        int selected_process = -1;
        
        // Find process with highest priority among arrived processes
        for (int i = 0; i < n; i++) {
            if (processes[i].arrival_time <= current_time && 
                !is_completed[i]) {
                if (highest_priority == -1 || 
                    processes[i].priority < highest_priority) {
                    highest_priority = processes[i].priority;
                    selected_process = i;
                }
            }
        }
        
        if (selected_process == -1) {
            current_time++;
            continue;
        }
        
        // Execute selected process
        printf("%d\tP%d\t%d\n", current_time, 
               processes[selected_process].process_id,
               processes[selected_process].priority);
        
        current_time += processes[selected_process].burst_time;
        processes[selected_process].completion_time = current_time;
        processes[selected_process].turnaround_time = 
            processes[selected_process].completion_time - 
            processes[selected_process].arrival_time;
        processes[selected_process].waiting_time = 
            processes[selected_process].turnaround_time - 
            processes[selected_process].burst_time;
        
        is_completed[selected_process] = 1;
        completed++;
    }
}

int main() {
    Process processes[] = {
        {1, 0, 4, 2, 0, 0, 0, 0},  // P1: AT=0, BT=4, Priority=2
        {2, 1, 3, 1, 0, 0, 0, 0},  // P2: AT=1, BT=3, Priority=1
        {3, 2, 1, 3, 0, 0, 0, 0},  // P3: AT=2, BT=1, Priority=3
        {4, 3, 2, 1, 0, 0, 0, 0}   // P4: AT=3, BT=2, Priority=1
    };
    
    int n = sizeof(processes) / sizeof(processes[0]);
    
    sortByArrivalTime(processes, n);
    nonPreemptivePriorityScheduling(processes, n);
    
    // Display results
    printf("\nProcess\tAT\tBT\tPriority\tCT\tTAT\tWT\n");
    for (int i = 0; i < n; i++) {
        printf("P%d\t%d\t%d\t%d\t\t%d\t%d\t%d\n",
               processes[i].process_id,
               processes[i].arrival_time,
               processes[i].burst_time,
               processes[i].priority,
               processes[i].completion_time,
               processes[i].turnaround_time,
               processes[i].waiting_time);
    }
    
    return 0;
}

Output Explanation

For the example above with processes P1(AT=0, BT=4, P=2), P2(AT=1, BT=3, P=1), P3(AT=2, BT=1, P=3), P4(AT=3, BT=2, P=1):

Execution Order:
Time    Process Priority
0       P1      2
4       P2      1
7       P4      1
9       P3      3

Process AT  BT  Priority    CT  TAT WT
P1      0   4   2           4   4   0
P2      1   3   1           7   6   3
P3      2   1   3           10  8   7
P4      3   2   1           9   6   4

Preemptive Priority Scheduling Implementation

Here’s an implementation of preemptive priority scheduling:

#include <stdio.h>
#include <limits.h>

void preemptivePriorityScheduling(Process processes[], int n) {
    int current_time = 0;
    int completed = 0;
    int is_completed[n];
    
    // Initialize
    for (int i = 0; i < n; i++) {
        is_completed[i] = 0;
        processes[i].remaining_time = processes[i].burst_time;
    }
    
    printf("Time\tProcess\tRemaining Time\n");
    
    while (completed != n) {
        int highest_priority = INT_MAX;
        int selected_process = -1;
        
        // Find process with highest priority
        for (int i = 0; i < n; i++) {
            if (processes[i].arrival_time <= current_time && 
                !is_completed[i] && 
                processes[i].priority < highest_priority) {
                highest_priority = processes[i].priority;
                selected_process = i;
            }
        }
        
        if (selected_process == -1) {
            current_time++;
            continue;
        }
        
        // Execute for 1 time unit
        printf("%d\tP%d\t%d\n", current_time, 
               processes[selected_process].process_id,
               processes[selected_process].remaining_time);
        
        processes[selected_process].remaining_time--;
        current_time++;
        
        // Check if process is completed
        if (processes[selected_process].remaining_time == 0) {
            processes[selected_process].completion_time = current_time;
            processes[selected_process].turnaround_time = 
                processes[selected_process].completion_time - 
                processes[selected_process].arrival_time;
            processes[selected_process].waiting_time = 
                processes[selected_process].turnaround_time - 
                processes[selected_process].burst_time;
            
            is_completed[selected_process] = 1;
            completed++;
        }
    }
}

Advantages and Disadvantages

Advantages

• Flexible scheduling: Allows prioritization of critical processes
• Good response time: High-priority processes get quick response
• Suitable for real-time systems: Critical tasks can be prioritized
• Easy to understand: Simple concept and implementation

Disadvantages

• Starvation problem: Low-priority processes may never execute
• Priority inversion: High-priority process waiting for low-priority resource
• Complexity in priority assignment: Difficult to determine optimal priorities
• Context switching overhead: Frequent preemption increases overhead

Solving the Starvation Problem

Aging Technique

The aging technique is the most common solution to prevent starvation in priority scheduling. It gradually increases the priority of processes that have been waiting for a long time.

void agingTechnique(Process processes[], int n, int current_time) {
    for (int i = 0; i < n; i++) {
        if (!is_completed[i] && processes[i].arrival_time <= current_time) {
            int waiting_time = current_time - processes[i].arrival_time;
            
            // Increase priority every 5 time units of waiting
            if (waiting_time > 0 && waiting_time % 5 == 0) {
                if (processes[i].priority > 1) {
                    processes[i].priority--;  // Lower number = higher priority
                    printf("Process P%d priority increased to %d\n", 
                           processes[i].process_id, processes[i].priority);
                }
            }
        }
    }
}

Priority Inheritance

For priority inversion problems, priority inheritance temporarily elevates the priority of a low-priority process holding a resource needed by a high-priority process.

Real-World Applications

Operating System Examples

• Windows: Uses priority-based scheduling with 32 priority levels
• Linux: Completely Fair Scheduler (CFS) with nice values
• Real-time systems: Rate Monotonic Scheduling (RMS)
• Embedded systems: Fixed-priority preemptive scheduling

Priority Assignment Examples

Performance Metrics Calculation

Let’s calculate important performance metrics for priority scheduling:

Average Waiting Time

float calculateAverageWaitingTime(Process processes[], int n) {
    float total_waiting_time = 0;
    
    for (int i = 0; i < n; i++) {
        total_waiting_time += processes[i].waiting_time;
    }
    
    return total_waiting_time / n;
}

Average Turnaround Time

float calculateAverageTurnaroundTime(Process processes[], int n) {
    float total_turnaround_time = 0;
    
    for (int i = 0; i < n; i++) {
        total_turnaround_time += processes[i].turnaround_time;
    }
    
    return total_turnaround_time / n;
}

Interactive Example: Priority Queue Simulation

Here’s an interactive simulation showing how priority scheduling works:

<!DOCTYPE html>
<html>
<head>
    <title>Priority Scheduling Simulator</title>
    <style>
        .process-queue {
            display: flex;
            gap: 10px;
            margin: 20px 0;
        }
        .process {
            padding: 10px;
            border: 2px solid #333;
            border-radius: 5px;
            text-align: center;
            min-width: 80px;
        }
        .high-priority { background-color: #ff6b6b; }
        .medium-priority { background-color: #feca57; }
        .low-priority { background-color: #48dbfb; }
        .executing { animation: pulse 1s infinite; }
        
        @keyframes pulse {
            0% { transform: scale(1); }
            50% { transform: scale(1.1); }
            100% { transform: scale(1); }
        }
    </style>
</head>
<body>
    <h3>Priority Scheduling Queue</h3>
    <div id="queue" class="process-queue"></div>
    <button onclick="addProcess()">Add Process</button>
    <button onclick="executeNext()">Execute Next</button>
    <button onclick="reset()">Reset</button>
    
    <script>
        let processes = [];
        let processCounter = 1;
        
        function addProcess() {
            const priority = Math.floor(Math.random() * 3) + 1;
            const process = {
                id: processCounter++,
                priority: priority,
                burstTime: Math.floor(Math.random() * 5) + 1
            };
            processes.push(process);
            updateDisplay();
        }
        
        function executeNext() {
            if (processes.length === 0) return;
            
            // Sort by priority (lower number = higher priority)
            processes.sort((a, b) => a.priority - b.priority);
            const executing = processes.shift();
            
            console.log(`Executing Process ${executing.id} (Priority: ${executing.priority})`);
            updateDisplay();
        }
        
        function updateDisplay() {
            const queue = document.getElementById('queue');
            queue.innerHTML = '';
            
            processes.forEach(process => {
                const div = document.createElement('div');
                div.className = 'process';
                div.innerHTML = `P${process.id}<br>Priority: ${process.priority}`;
                
                if (process.priority === 1) div.classList.add('high-priority');
                else if (process.priority === 2) div.classList.add('medium-priority');
                else div.classList.add('low-priority');
                
                queue.appendChild(div);
            });
        }
        
        function reset() {
            processes = [];
            processCounter = 1;
            updateDisplay();
        }
    </script>
</body>
</html>

Best Practices and Optimization Tips

Priority Assignment Guidelines

• Use meaningful priority ranges: Define clear priority levels for different process types
• Implement aging mechanisms: Prevent starvation through gradual priority elevation
• Monitor system performance: Adjust priorities based on system behavior
• Consider process characteristics: I/O-bound vs CPU-bound processes need different priorities

Implementation Optimizations

• Use priority queues: Implement efficient data structures for faster process selection
• Minimize context switching: Group similar priority processes when possible
• Cache priority calculations: Avoid recalculating priorities frequently
• Implement priority inheritance: Handle priority inversion scenarios

Comparison with Other Scheduling Algorithms

Conclusion

Priority scheduling is a powerful and flexible CPU scheduling algorithm that allows operating systems to prioritize critical processes and provide better response times for important tasks. While it offers excellent control over process execution order, careful implementation is required to prevent starvation and priority inversion problems.

The choice between preemptive and non-preemptive priority scheduling depends on system requirements: preemptive scheduling provides better responsiveness for real-time systems, while non-preemptive scheduling offers lower overhead for batch processing environments.

By implementing proper aging mechanisms, priority inheritance, and performance monitoring, priority scheduling can be an effective solution for modern operating systems requiring sophisticated process management capabilities.