Round Robin in Kotlin | CPU Scheduling

Round-robin scheduling is a CPU scheduling algorithm that is commonly used in multitasking operating systems. It is a pre-emptive scheduling algorithm, which means that the CPU is allocated to a process for a fixed time period, known as a time slice, and then the CPU is switched to another process.

In round-robin scheduling, each process is assigned a time slice, which is typically a small unit of time, such as 10-100 milliseconds. The processes are then scheduled in a circular order, with each process running for one time slice before being preempted and the CPU being allocated to the next process in the queue. The process that was preempted is placed at the end of the queue, so that it will be scheduled again after all the other processes have run.

Round-robin scheduling ensures that all processes get a fair share of the CPU time, as each process is allocated a fixed amount of time before being preempted. This prevents any single process from monopolizing the CPU and ensures that all processes have a chance to run. Round-robin scheduling is commonly used in time-sharing systems and is also used in real-time systems where a response time guarantee is required.

Let’s consider the following set of processes with their arrival time and burst time:

Assume that the time slice (quantum) for the round-robin scheduling algorithm is 2 units.

The Gantt chart for the round-robin scheduling algorithm will look like this:

0    1    2    3    4    5    6    7    8    9    10
P1  P1  P2  P1  P3  P5  P4  P5  P5  P5  P5
   P1  P2  P1  P3  P5  P4  P5  P5  P5  P5
       P1  P1  P3  P4  P5  P5  P5  P5
           P1  P3  P4  P5  P5  P5
               P3  P4  P5  P5
                   P4  P5
                       P5

In the Gantt chart, each row represents a time unit, and each process is allocated a time slice of 2 units. The process that is currently executing is highlighted with its process ID.

Now, let’s calculate the waiting time and turnaround time for each process:

The completion time for each process is the time at which the process completes execution, which can be obtained from the Gantt chart. The turnaround time is the time taken by a process to complete, from its arrival to completion. The waiting time is the time for which a process waits in the ready queue before it gets scheduled.

In this example, we have used a time slice of 2 units. If we had used a different time slice, we would have obtained different waiting and turnaround times for each process. However, the round-robin scheduling algorithm ensures that all processes get a fair share of the CPU time, regardless of their burst time, and prevents any single process from monopolizing the CPU.

data class Process(val id: Int, val arrivalTime: Int, val burstTime: Int, var completionTime: Int = 0, var turnaroundTime: Int = 0, var waitingTime: Int = 0)

fun roundRobin(processes: List<Process>, quantum: Int): List<Process> {
    val remainingTime = processes.map { it.burstTime }.toMutableList()
    val waitingTime = IntArray(processes.size) { 0 }
    val completionTime = IntArray(processes.size) { 0 }
    var time = 0
    var index = 0
    
    while (true) {
        var done = true
        for (i in processes.indices) {
            if (remainingTime[i] > 0) {
                done = false
                if (remainingTime[i] > quantum) {
                    time += quantum
                    remainingTime[i] -= quantum
                } else {
                    time += remainingTime[i]
                    waitingTime[i] = time - processes[i].burstTime - processes[i].arrivalTime
                    remainingTime[i] = 0
                    completionTime[i] = time
                }
            }
        }
        if (done) break
    }
    
    return processes.mapIndexed { index, process ->
        process.copy(
            arrivalTime = process.arrivalTime,
            burstTime = process.burstTime,
            completionTime = completionTime[index],
            turnaroundTime = completionTime[index] - process.arrivalTime,
            waitingTime = waitingTime[index]
        )
    }
}

fun main() {
    val processes = listOf(
        Process(id = 1, arrivalTime = 0, burstTime = 5),
        Process(id = 2, arrivalTime = 1, burstTime = 3),
        Process(id = 3, arrivalTime = 2, burstTime = 1),
        Process(id = 4, arrivalTime = 3, burstTime = 2),
        Process(id = 5, arrivalTime = 4, burstTime = 4),
    )
    val quantum = 2
    
    val scheduledProcesses = roundRobin(processes, quantum)
    
    println("Process\tArrival Time\tBurst Time\tCompletion Time\tTurnaround Time\tWaiting Time")
    scheduledProcesses.forEach {
        println("${it.id}\t\t${it.arrivalTime}\t\t${it.burstTime}\t\t${it.completionTime}\t\t${it.turnaroundTime}\t\t${it.waitingTime}")
    }
}