Priority Scheduling in Kotlin

by

Priority scheduling is a CPU scheduling algorithm used in operating systems to determine the order in which processes are executed based on their priority levels. Each process is assigned a priority value, and the scheduler allocates CPU time to processes in a way that maximizes the utilization of system resources while respecting the defined priorities.

In priority scheduling, the processes with higher priority values are given precedence over processes with lower priority values. The scheduler selects the highest priority process that is ready to run and allocates the CPU to that process. If multiple processes have the same highest priority, the scheduler may use additional criteria, such as round-robin scheduling or First-Come, First-Served (FCFS) scheduling, to decide the order in which these processes are executed.

There are two common types of priority scheduling:

  1. Preemptive Priority Scheduling: In this approach, the scheduler can preempt a currently running process if a higher priority process becomes ready. Preemption means suspending the execution of the current process and allocating the CPU to the higher priority process. The preempted process is placed back in the ready queue for later execution.
  2. Non-preemptive Priority Scheduling: In this approach, once a process starts executing, it continues until it completes, blocks, or voluntarily yields the CPU. The scheduler does not preempt a running process, even if a higher priority process becomes ready. The currently running process continues execution until it finishes its time slice or gives up the CPU.

Priority scheduling has several advantages:

  1. Efficient Resource Utilization: Priority scheduling allows processes with higher priority, such as time-critical or important tasks, to be executed promptly. This improves the overall system efficiency and ensures that critical tasks are completed without unnecessary delay.
  2. Customization: Each process can be assigned a priority level that reflects its importance or urgency. This flexibility enables system administrators or users to customize the scheduling algorithm to meet specific requirements or performance goals.

However, priority scheduling also has potential drawbacks:

  1. Starvation: If a process with a lower priority never gets a chance to execute due to the continuous arrival of higher priority processes, it may suffer from starvation. Starvation occurs when a process is indefinitely delayed or postponed, leading to unfairness and reduced performance for low-priority tasks.
  2. Priority Inversion: Priority inversion can occur when a low-priority process holds a resource required by a high-priority process. In such cases, the low-priority process may delay the execution of the high-priority process, leading to unexpected priority inversions and compromising system responsiveness.

To mitigate these issues, various techniques, such as aging (increasing the priority of processes over time), priority inheritance (temporarily raising the priority of a process holding a resource required by a high-priority process), and priority ceiling protocols, can be employed.

Overall, priority scheduling is a commonly used CPU scheduling algorithm that prioritizes processes based on their importance. It balances resource allocation, responsiveness, and system efficiency to meet the needs of different types of processes in an operating system.

Non-Preemptive priority scheduling implemented in Kotlin:

Kotlin
data class Process(val id: Int, val burstTime: Int, val priority: Int)

fun main() {
    // Define the processes with their burst time and priority
    val processes = listOf(
        Process(1, 8, 3),
        Process(2, 6, 1),
        Process(3, 10, 4),
        Process(4, 4, 2)
    )

    // Sort the processes based on priority (lower values have higher priority)
    val sortedProcesses = processes.sortedBy { it.priority }

    var currentTime = 0
    var totalWaitingTime = 0
    var totalTurnaroundTime = 0

    println("Process\t\tBurst Time\tPriority\tWaiting Time\t\tTurnaround Time")

    for (process in sortedProcesses) {
        val waitingTime = currentTime
        val turnaroundTime = currentTime + process.burstTime

        totalWaitingTime += waitingTime
        totalTurnaroundTime += turnaroundTime

      println("${process.id}\t\t${process.burstTime}\t\t${process.priority}\t\t$waitingTime\t\t\t$turnaroundTime")

        currentTime += process.burstTime
    }

    val averageWaitingTime = totalWaitingTime.toDouble() / sortedProcesses.size
    val averageTurnaroundTime = totalTurnaroundTime.toDouble() / sortedProcesses.size

    println("\nAverage Waiting Time: $averageWaitingTime")
    println("Average Turnaround Time: $averageTurnaroundTime")
}
  1. Define the Process class: The Process class represents a process with properties like ID, burst time, and priority.
  2. Initialize the list of processes: Create a list of Process objects representing the processes to be scheduled. Each process is assigned an ID, burst time, and priority.
  3. Sort the processes based on priority: Use the sortedBy function to sort the list of processes in ascending order based on their priority. Lower priority values indicate higher priority.
  4. Initialize variables: Set the current time to 0, and initialize variables to track total waiting time and total turnaround time.
  5. Display the column headers: Print the column headers for the process details, including process ID, burst time, priority, waiting time, and turnaround time.
  6. Iterate through the sorted processes: Iterate over each process in the sorted list.
  7. Calculate waiting time and turnaround time: For each process, calculate the waiting time as the current time and the turnaround time as the sum of the current time and the process’s burst time.
  8. Update total waiting time and total turnaround time: Add the waiting time and turnaround time of the current process to the respective total variables.
  9. Display process details: Print the process details, including its ID, burst time, priority, waiting time, and turnaround time.
  10. Update the current time: Add the burst time of the current process to the current time.
  11. Calculate average waiting time and average turnaround time: Divide the total waiting time and total turnaround time by the number of processes to calculate the average values.
  12. Display average waiting time and average turnaround time.

The time complexity of this code is O(n log n) because the sorting operation takes O(n log n) time complexity, where n is the number of processes. The iteration and calculations for each process take linear time complexity, O(n). Overall, the dominant factor is the sorting operation.

The space complexity of this code is O(n) because it requires space to store the list of processes and additional variables for tracking time and calculations. The space complexity increases linearly with the number of processes.

Leave a Comment