Round-Robin Scheduling
Our Work
We'll stick with the processes we've been using.
| Process | Required Time |
|---|
This time, we've set the seed randomly, but as usual, you can change the seed to get different times for the processes.
Round-Robin Scheduling
Round-Robin (RR) scheduling is a scheduling algorithm that assigns a fixed time unit per process. It's like being at the grocery store and lots of checkout are open, but there's only one cashier who has to keep running back and forth between them. Each person gets a fixed amount of time to check out before the cashier moves on to the next person.
Meh, this grocery store analogy is getting stretched a bit thin.
I like it! I can totally relate to grocery stores.
Round-robin is a form of preemptive scheduling, where the CPU can be taken away from a process before the process has finished. In this case, the CPU is taken away after a fixed time unit, and the preempted process is put at the end of the queue to wait for its next turn. The amount of time each process gets is called the quantum. We've set the quantum to 2 but you can adjust it using the slider below the chart.
Statistics
Here are all the statistics for the processes in this run:
| Process | Response Time | Turnaround Time | Wait Time | Context Switches |
|---|
This is nice. The response time is so much better than FCFS!
Hay! There's a new column in our statistics table! What's a “context switch”?
Good point!
Context Switches
A context switch is the process of saving the state of the current process or thread (so it can be reloaded later when that process's turn comes around again) and then loading the saved state for the next process or thread. FCFS and SJF don't have context switches because they were non-preemptive scheduling algorithms, but we do see them in RR because it is preemptive.
Context switches have a cost. Not only the time it takes to save and restore the state of a process, but also because CPUs have caches. The cache is a small amount of memory that's much faster than main memory, and the CPU uses it to store frequently accessed data. When a process is switched out, the cache is usually flushed, which means that the next process has to get data from slower memory until the cache is populated.
Our graphs don't actually reflect these slowdowns—for simplicity's sake we show processes requiring the same amount of time regardless of how many context switches they have.
-
That's true. While these slowdowns can be important issues in practice, it wasn't worth trying to model it here.
-
Meh. Worse is better strikes again.
Prof. Melissa ran the simulation one million times and found the response time dropped down to 2 which was vastly better than FCFS and SJF. However, the wait time rose to 15.9, and the turnaround time was 21.9, which was worse than both FCFS and SJF, but all the standard deviations were lower than the other two algorithms.
Why isn't there just one winner?
-
We always have trade-offs in computer science. It's about finding the best fit for the situation.
-
I like the algorithms where there is no chance of starvation!
To summarize:
- RR is a preemptive scheduling algorithm.
- RR scheduling has a better response time than FCFS and SJF.
- RR scheduling has a worse wait time and turnaround time than FCFS and SJF.
- RR scheduling has context switch overhead to consider.
- RR scheduling doesn't require foreknowledge of how long each process will run and can't starve a process.
- RR scheduling is a good fit when we want to give each process a fair share of the CPU.
- RR scheduling is very predictable as it goes through the processes in order.
Predictable seems a bit boring. Where's the fun?
-
Okay… We can mix it up a bit…
Adding Randomness
We can add a bit of randomness to our Round-Robin schedule by choosing the process to run next randomly. There are more complex variations on this scheme known as lottery scheduling, but we'll keep things simple for now.
Click the checkbox below to turn on random mode, and then scroll back up to the chart to see the new schedule. You can click the regenerate button to get a new set of random times for the processes.
That seems less fair to me. What if a process gets picked over and over again?
-
Well, randomness generally means the absense of any pattern. Although we're not quite as neat and tidy as we were before, over the long term, we'll still be fair, on average.
-
Meh. Too many algorithms. Are we done yet?
-
We're done for today, but there's more scheduling algoruthms to come!
-
MORE!!?? I can't wait!
(When logged in, completion status appears here.)