SJF Preemptive in Kotlin | Shortest Job First CPU scheduling

by

CPU scheduling is the process of selecting a process from the queue of processes in the ready state and allocating the CPU to it. The primary goal of CPU scheduling is to make sure that the CPU is utilized effectively and efficiently. There are several scheduling algorithms available to manage the CPU scheduling, and one of them is the Shortest Job First (SJF) algorithm.

The SJF algorithm selects the process with the shortest burst time from the ready queue to allocate the CPU to it. This algorithm is suitable for systems where the job sizes are known beforehand. SJF scheduling algorithm can be of two types:

  1. Non-preemptive SJF: Once a process is assigned to the CPU, it runs until it completes its execution or goes into the waiting state.
  2. Preemptive SJF: The process with the shortest burst time can be interrupted by another process with even shorter burst time.

Let’s take an example to explain SJF scheduling algorithm. We have four processes with their burst times as follows:

ProcessBurst Time
P16
P28
P37
P43

Suppose we have a non-preemptive SJF scheduling algorithm, and all the processes arrive at the same time. The Gantt chart below shows the sequence in which the processes will be executed.

| P4 | P1 | P3 | P2 |

Here, the process P4 will be executed first because it has the shortest burst time. After P4 completes its execution, P1 with the next shortest burst time will be executed, followed by P3 and then P2.

In case we have a preemptive SJF scheduling algorithm, the Gantt chart will look like the following:

| P4 | P1 | P4 | P3 | P4 | P2 |

Here, the process P4 will be executed first because it has the shortest burst time. While P4 is running, P1 arrives with a shorter burst time, so P4 is preempted, and P1 starts executing. After P1 completes its execution, P4 resumes its execution, followed by P3 and then P2.

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

fun main() {
    val processes = listOf(
        Process(1, 3, 1),
        Process(2, 1, 4),
        Process(3, 4, 2),
        Process(4, 0, 6),
        Process(5 ,2, 3)
    )
    sjf(processes)
}

fun sjf(processes: List<Process>) {
    val n = processes.size
    val burst = processes.map { it.burstTime }.toMutableList()
    val remainingTime = IntArray(n) { burst[it] }
    val completionTime = IntArray(n)
    val waitingTime = IntArray(n)
    val turnaroundTime = IntArray(n)

    var time = 0
    var minBurst = Int.MAX_VALUE
    var shortest = -1
    var check = false
    var finished = 0

    while (finished != n) {
        for (i in 0 until n) {
            if (processes[i].arrivalTime <= time && remainingTime[i] < minBurst && remainingTime[i] > 0) {
                minBurst = remainingTime[i]
                shortest = i
                check = true
            }
        }

        if (!check) {
            time++
            continue
        }

        remainingTime[shortest]--

        minBurst = remainingTime[shortest]
        if (minBurst == 0) {
            minBurst = Int.MAX_VALUE
        }

        if (remainingTime[shortest] == 0) {
            finished++
            completionTime[shortest] = time + 1
            turnaroundTime[shortest] = completionTime[shortest] - processes[shortest].arrivalTime
            waitingTime[shortest] = turnaroundTime[shortest] - processes[shortest].burstTime
            if (waitingTime[shortest] < 0) {
                waitingTime[shortest] = 0
            }
        }
        time++
    }

    val totalWaitingTime = waitingTime.sum()
    val averageWaitingTime = totalWaitingTime.toFloat() / n
    val totalTurnaroundTime = turnaroundTime.sum()
    val averageTurnaroundTime = totalTurnaroundTime.toFloat() / n
    println("SJF Scheduling:")
    println("Process\t Arrival Burst\t Completion\t Waiting\t Turnaround")
    for (i in 0 until n) {
        println("${processes[i].id}\t ${processes[i].arrivalTime}\t ${processes[i].burstTime}\t ${completionTime[i]}\t\t ${waitingTime[i]}\t\t ${turnaroundTime[i]}")
    }
    println("Average waiting time: $averageWaitingTime")
    println("Average turnaround time: $averageTurnaroundTime")
}
  1. Define a data class named Process that has id, arrivalTime, and burstTime as properties. The id is an integer that identifies the process, arrivalTime is the time at which the process arrives in the ready queue, and burstTime is the amount of CPU time required by the process.
  2. In the main function, create a list of Process objects with different id, arrivalTime, and burstTime values.
  3. Define the sjf function that takes a list of Process objects as input.
  4. Get the number of processes from the input list.
  5. Create a mutable list burst that contains the burst times of all processes.
  6. Create an integer array remainingTime that initially contains the burst time of each process.
  7. Create three integer arrays completionTime, waitingTime, and turnaroundTime to store the completion time, waiting time, and turnaround time of each process.
  8. Initialize the variables time, minBurst, shortest, check, and finished to 0, Int.MAX_VALUE, -1, false, and 0 respectively.
  9. Enter a while loop that continues until all processes have been executed.
  10. Inside the loop, use a for loop to iterate through all processes.
  11. Check if a process has arrived and has remaining burst time less than the current minimum burst time. If yes, update the minBurst and shortest variables to track the process with the shortest remaining burst time.
  12. Set the check variable to true if a process has been found.
  13. If no process has been found, increment the time variable by 1 and continue the loop.
  14. If a process has been found, decrement its remaining burst time by 1.
  15. If the remaining burst time of the current process is 0, update the finished variable to track the number of completed processes.
  16. Set the completionTime of the current process to time + 1.
  17. Calculate the turnaroundTime of the current process by subtracting its arrivalTime from its completionTime.
  18. Calculate the waitingTime of the current process by subtracting its burstTime from its turnaroundTime.
  19. If the waitingTime of the current process is negative, set it to 0.
  20. Update the minBurst variable to find the next process with the shortest remaining burst time.
  21. Increment the time variable by 1 and continue the loop.
  22. After the loop, calculate the total waiting time and average waiting time of all processes.
  23. Calculate the total turnaround time and average turnaround time of all processes.
  24. Print the results of the SJF scheduling algorithm along with the average waiting time and average turnaround time.

Output :

SJF Scheduling:
Process     Arrival     Burst       Completion       Waiting       Turnaround
1               3             1              4                        0                 1                        
2               1             4              6                        1                 5
3               4             2              8                        2                 4
4               0             6              16                      10               16
5               2             3              11                      6                 9
Average waiting time: 3.8
Average turnaround time: 7.0

Leave a Comment