Round-robin scheduling
Round-robin (RR) is one of the algorithms employed by
As the term is generally used,The name of the algorithm comes from the round-robin principle known from other fields, where each person takes an equal share of something in turn.
Process scheduling
To
Round-robin algorithm is a pre-emptive algorithm as the scheduler forces the process out of the CPU once the time quota expires.
For example, if the time slot is 100 milliseconds, and job1 takes a total time of 250 ms to complete, the round-robin scheduler will suspend the job after 100 ms and give other jobs their time on the CPU. Once the other jobs have had their equal share (100 ms each), job1 will get another allocation of
- Job1 = Total time to complete 250 ms (quantum 100 ms).
- First allocation = 100 ms.
- Second allocation = 100 ms.
- Third allocation = 100 ms but job1 self-terminates after 50 ms.
- Total CPU time of job1 = 250 ms
Consider the following table with the arrival time and execute time of the process with the quantum time of 100 ms to understand the round-robin scheduling:
Process name | Arrival time | Execute time |
---|---|---|
P0 | 0 | 250 |
P1 | 50 | 170 |
P2 | 130 | 75 |
P3 | 190 | 100 |
P4 | 210 | 130 |
P5 | 350 | 50 |
Another approach is to divide all processes into an equal number of timing quanta such that the quantum size is proportional to the size of the process. Hence, all processes end at the same time.
Network packet scheduling
In
A multiplexer, switch, or router that provides round-robin scheduling has a separate queue for every data flow, where a data flow may be identified by its source and destination address. The algorithm allows every active data flow that has data packets in the queue to take turns in transferring packets on a shared channel in a periodically repeated order. The scheduling is work-conserving, meaning that if one flow is out of packets, the next data flow will take its place. Hence, the scheduling tries to prevent link resources from going unused.
Round-robin scheduling results in max-min fairness if the data packets are equally sized, since the data flow that has waited the longest time is given scheduling priority. It may not be desirable if the size of the data packets varies widely from one job to another. A user that produces large packets would be favored over other users. In that case fair queuing would be preferable.
If guaranteed or differentiated quality of service is offered, and not only best-effort communication,
In
In a centralized wireless packet radio network, where many stations share one frequency channel, a scheduling algorithm in a central base station may reserve time slots for the mobile stations in a round-robin fashion and provide fairness. However, if
See also
- Multilevel queue
- SCHED_RR
References
- ^ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), Operating Systems: Three Easy Pieces [Chapter: Scheduling Introduction] (PDF), Arpaci-Dusseau Books
- ISBN 1107143217, 2016.
- ISBN 978-0-13-380591-8.
- ISBN 978-0-470-23399-3.
5.3.4 Round Robin Scheduling