SJF Non-preemptive in Kotlin | Shortest Job First CPU scheduling

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:

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.

data class Process(val name: String, val arrivalTime: Int, val burstTime: Int)

fun sjf(processes: List<Process>) {
    val sortedProcesses = processes.sortedBy { it.arrivalTime }
    var currentTime = 0
    var totalTime = 0
    val waitTimes = mutableListOf<Int>()

    println("Process\tArrival Time\tBurst Time\tWaiting Time\tTurnaround Time")

    while (sortedProcesses.isNotEmpty()) {
        val availableProcesses = sortedProcesses.filter { it.arrivalTime <= currentTime }
        if (availableProcesses.isEmpty()) {
            currentTime++
            continue
        }
        val shortestJob = availableProcesses.minByOrNull { it.burstTime }!!
        sortedProcesses -= shortestJob
        val waitTime = currentTime - shortestJob.arrivalTime
        waitTimes += waitTime
        currentTime += shortestJob.burstTime
        totalTime += currentTime - shortestJob.arrivalTime
        val turnaroundTime = currentTime - shortestJob.arrivalTime
        println("${shortestJob.name}\t\t${shortestJob.arrivalTime}\t\t${shortestJob.burstTime}\t\t${waitTime}\t\t\t${turnaroundTime}")
    }

    val avgWaitTime = waitTimes.average()
    val avgTurnaroundTime = totalTime.toDouble() / processes.size
    println("Average Waiting Time: $avgWaitTime")
    println("Average Turnaround Time: $avgTurnaroundTime")
}

fun main() {
    val processes = listOf(
        Process("P1", 0, 3),
        Process("P2", 1, 5),
        Process("P3", 2, 2),
        Process("P4", 3, 4)
    )
    sjf(processes)
}

1. A Process data class is defined with three properties: name, arrivalTime, and burstTime. This class represents the processes to be scheduled.
2. A sjf function is defined that takes a list of Process objects as input. This function will implement the shortest job first scheduling algorithm.
3. The input list of processes is sorted by their arrival times, so that they can be scheduled in the order of their arrival.
4. Variables for the current time, total time, and a list to store the waiting times of each process are initialized.
5. The table headers for the process information are printed.
6. A while loop is used to iterate through the sorted list of processes and schedule them.
7. For each iteration, a list of available processes that have arrived by the current time is filtered from the sorted list.
8. If no processes are available, the current time is incremented by one and the loop continues to the next iteration.
9. If there are available processes, the one with the shortest burst time is selected.
10. The selected process is removed from the sorted list of processes.
11. The waiting time of the selected process is calculated by subtracting its arrival time from the current time.
12. The waiting time is added to the list of waiting times.
13. The current time is incremented by the selected process’s burst time.
14. The total time is incremented by the difference between the current time and the selected process’s arrival time.
15. The turnaround time of the selected process is calculated by subtracting its arrival time from the current time.
16. The information for the selected process, including its waiting time and turnaround time, is printed in a table row.
17. After all processes have been scheduled, the average waiting time and average turnaround time are calculated and printed.

Output:

Process Arrival Time Burst Time Waiting Time Turnaround Time
P1 0 3 0 3
P3 2 2 1 3
P4 3 4 2 6
P2 1 5 8 13

Average Waiting Time: 2.75
Average Turnaround Time: 6.25