Round-robin scheduling

Round-robin scheduling

Round-robin (RR) 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.

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 favored 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.

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 (DRR) scheduling, weighted round robin (WRR) scheduling or weighted fair queuing (WFQ) 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.

ee also

*Scheduling algorithm
*round-robin
*Weighted round robin
*Deficit round robin

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Round robin (disambiguation) — Round robin may mean:* Round robin (taking turns) * Round robin tournament (sports) * Round robin scheduling (computer science) * Deficit round robin (computer networking) * Weighted round robin (computer networking) …   Wikipedia

  • Round-robin tournament — A round robin tournament (or all play all tournament) is a competition in which each contestant meets all other contestants in turn .[1] Contents 1 Terminology 2 Use 3 Evaluation …   Wikipedia

  • Round-robin (алгоритм) — У этого термина существуют и другие значения, см. Round robin. Round robin (от англ. round robin циклический)  алгоритм распределения нагрузки распределённой вычислительной системы методом перебора и упорядочения её элементов по… …   Википедия

  • Round-robin — The term round robin describes correspondence to a single address authored or signed by numerous individuals (as found in a petition). Colloquially, however, round robin is frequently given an opposite meaning, being used to describe a letter… …   Wikipedia

  • Round-Robin (Informatik) — Der Begriff Rundlauf Verfahren oder englisch Round Robin bezeichnet ein Scheduling Verfahren, d. h. es ordnet mehreren konkurrierenden Prozessen begrenzte Ressourcen zu. Das Round Robin Verfahren gewährt allen Prozessen nacheinander für jeweils… …   Deutsch Wikipedia

  • Round Robin (EDV) — Der Begriff Rundlauf Verfahren oder englisch Round Robin bezeichnet ein Scheduling Verfahren, d. h. es ordnet mehreren konkurrierenden Prozessen begrenzte Ressourcen zu. Das Round Robin Verfahren gewährt allen Prozessen nacheinander für jeweils… …   Deutsch Wikipedia

  • Round Robin (Informatik) — Der Begriff Rundlauf Verfahren oder englisch Round Robin bezeichnet ein Scheduling Verfahren, d. h. es ordnet mehreren konkurrierenden Prozessen begrenzte Ressourcen zu. Das Round Robin Verfahren gewährt allen Prozessen nacheinander für… …   Deutsch Wikipedia

  • Deficit round robin — DWRR redirects here. For the radio station in Philippines, see DWRR FM. Deficit round robin (DRR),[1] also deficit weighted round robin (DWRR), is a modified weighted round robin scheduling discipline. DRR was proposed by M. Shreedhar and G.… …   Wikipedia

  • Weighted round robin — (WRR) is a best effort connection scheduling discipline. Each packet flow or connection has its own packet queue in a network interface card. It is the simplest emulation of generalized processor sharing (GPS) discipline. While GPS serves… …   Wikipedia

  • Scheduling (computing) — This article is about processes assignment in operating systems. For other uses, see Scheduling (disambiguation). Scheduling is a key concept in computer multitasking, multiprocessing operating system and real time operating system designs.… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”