Round-robin scheduling

From Wikipedia, the free encyclopedia

Round-robin is one of the simplest scheduling algorithms for processes in an operating system, which assigns time slices to each process in equal portions and in order, handling all processes without priority. Round-robin scheduling is both simple and easy to implement, and starvation-free. Round-robin scheduling can also be applied to other scheduling problems, such as data packet scheduling in computer networks.

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.

1 Process scheduling
2 Data packet scheduling
3 See also
4 External links

[edit] Process scheduling

Round-robin job scheduling may not be desirable if the size of the jobs or tasks are strongly varying. A process that produces large jobs would be favoured over other processes. This problem may be solved by time-sharing, i.e. by giving each job a time slot or quantum (its allowance of CPU time), and interrupt the job if it is not completed by then. The job is resumed next time a time slot is assigned to that process.

Example: The time slot could be 100 milliseconds. If a job1 takes a total time of 250ms to complete, the round-robin scheduler will suspend the job after 100ms and give other jobs their time on the CPU. Once the other jobs have had their equal share (100ms each), job1 will get another allocation of CPU time and the cycle will repeat. This process continues until the job finishes and needs no more time on the CPU.

Job1 = Total time to complete 250ms (quantum 100ms).

First allocation = 100ms.
Second allocation = 100ms.
Third allocation = 100ms but job1 self-terminates after 50ms.
Total CPU time of job1 = 250ms.

[edit] Data packet scheduling

In best-effort packet switching and other statistical multiplexing, round-robin scheduling can be used as an alternative to first-come first-served queuing.

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 lets every active data flow (that has data packets in queue) to take turns in transferring packets on a shared channel in a periodically repeated order. The scheduling is non-work conserving, meaning that if one flow is out of packets, next data flow will take its place.

Round-robin scheduling results in max-min fairness if the data packets are equally sized, since the data flow that has waited longest time is given scheduling priority.

Round-robin scheduling may not be desirable if the size of the jobs or tasks are strongly varying. A user that produces large jobs 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, deficit round robin scheduling, weighted round robin scheduling or weighted fair queuing may be considered.

In multiple access networks where several terminals are connected to a shared physical medium, round-robin scheduling may be provided by Token passing channel access schemes such as token ring, as well as by polling or resource reservation from a central control station.

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 link adaptation is used, it will take much longer time to transmit a certain amount of data to "expensive" users than to others since the channel conditions differ. It would be more efficient to wait with the transmission until the channel conditions are improved, or at least to give scheduling priority to less expensive users. Round-robin scheduling does not utilize this. Higher throughput and system spectrum efficiency may be achieved by channel-dependent scheduling, for example a proportionally fair algorithm, or maximum throughput scheduling. Note that the latter is characterized by undesirable scheduling starvation.