Round-robin scheduling
Encyclopedia
Round-robin is one of the simplest scheduling algorithms for processes in an operating system
. As the term is generally used, time slices are assigned to each process in equal portions and in circular order, handling all processes without priority
(also known as cyclic executive
). Round-robin scheduling is simple, 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.
, giving each job a time slot or quantum (its allowance of CPU time), and interrupting the job if it is not completed by then. The job is resumed next time a time slot is assigned to that process. In the absence of time-sharing, or if the quanta were large relative to the sizes of the jobs, a process that produced large jobs would be favoured over other processes.
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 CPU time and the cycle will repeat. This process continues until the job finishes and needs no more time on the CPU.
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.
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 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, 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, or 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 a 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.
Round-Robin Scheduling in UNIX:
this can also be the same concept of round-robin scheduler, and it can be created by using semaphores.
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
. As the term is generally used, time slices are assigned to each process in equal portions and in circular order, handling all processes without priority
Priority
Priority may refer to:* Priority date, a concept of establishing waiting times in the immigration process by United States Department of State* Priority level, the priority of emergency communications...
(also known as cyclic executive
Cyclic executive
A cyclic executive is an alternative to a real-time operating system. It is a form of cooperative multitasking, in which there is only one task. The sole task is typically realized as an infinite loop in main, e.g. in C/C++....
). Round-robin scheduling is simple, easy to implement, and starvation
Resource starvation
In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. Without those resources, the program can never finish its task....
-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
Round-robin
The term round-robin was originally used to describe a document signed by multiple parties in a circle to make it more difficult to determine the order in which it was signed, thus preventing a ringleader from being identified...
principle known from other fields, where each person takes an equal share of something in turn.
Process scheduling
In order to schedule processes fairly, a round-robin scheduler generally employs time-sharingTime-sharing
Time-sharing is the sharing of a computing resource among many users by means of multiprogramming and multi-tasking. Its introduction in the 1960s, and emergence as the prominent model of computing in the 1970s, represents a major technological shift in the history of computing.By allowing a large...
, giving each job a time slot or quantum (its allowance of CPU time), and interrupting the job if it is not completed by then. The job is resumed next time a time slot is assigned to that process. In the absence of time-sharing, or if the quanta were large relative to the sizes of the jobs, a process that produced large jobs would be favoured over other processes.
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 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 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.
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.
Data packet scheduling
In best-effort packet switchingPacket switching
Packet switching is a digital networking communications method that groups all transmitted data – regardless of content, type, or structure – into suitably sized blocks, called packets. Packet switching features delivery of variable-bit-rate data streams over a shared network...
and other statistical multiplexing
Statistical multiplexing
Statistical multiplexing is a type of communication link sharing, very similar to dynamic bandwidth allocation . In statistical multiplexing, a communication channel is divided into an arbitrary number of variable bit-rate digital channels or data streams. The link sharing is adapted to the...
, 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 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
Max-min fairness
In communication networks and multiplexing, a division of the bandwidth resources is said to be max-min fair when: firstly, the minimum data rate that a dataflow achieves is maximized; secondly, the second lowest data rate that a dataflow achieves is maximized, etc.In best-effort statistical...
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, deficit round-robin
Deficit round robin
Deficit round robin , also deficit weighted round robin , is a modified weighted round robin scheduling discipline. DRR was proposed by M. Shreedhar and G. Varghese in 1995. It can handle packets of variable size without knowing their mean size...
(DRR) scheduling, weighted round-robin
Weighted round robin
Weighted round robin is a scheduling discipline. Each packet flow or connection has its own packet queue in a network interface card. It is the simplest approximation of generalized processor sharing...
(WRR) scheduling, or weighted fair queuing
Weighted fair queuing
Weighted fair queuing is a data packet scheduling technique allowing different scheduling priorities to statistically multiplexed data flows.WFQ is a generalization of fair queuing . Both in WFQ and FQ, each data flow has a separate FIFO queue...
(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
Token passing
In telecommunication, token passing is a channel access method where a signal called a token is passed between nodes that authorizes the node to communicate. The most well-known examples are token ring and ARCNET....
channel access schemes such as token ring, or by polling
Polling (computer science)
Polling, or polled operation, in computer science, refers to actively sampling the status of an external device by a client program as a synchronous activity. Polling is most often used in terms of input/output , and is also referred to as polled or software driven .Polling is sometimes used...
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
Link adaptation
Link adaptation, or adaptive coding and modulation , is a term used in wireless communications to denote the matching of the modulation, coding and other signal and protocol parameters to the conditions on the radio link Link adaptation, or adaptive coding and modulation (ACM), is a term used in...
is used, it will take a 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
Proportionally Fair
Proportional fair is a compromise-based scheduling algorithm. It's based upon maintaining a balance between two competing interests: Trying to maximize total wireless network throughput while at the same time allowing all users at least a minimal level of service...
algorithm, or maximum throughput scheduling
Maximum throughput scheduling
Maximum throughput scheduling is a procedure for scheduling data packets in a packet-switched best-effort communications network, typically a wireless network, in view to maximize the total throughput of the network, or the system spectral efficiency in a wireless network...
. Note that the latter is characterized by undesirable scheduling starvation.
Round-Robin Scheduling in UNIX:
this can also be the same concept of round-robin scheduler, and it can be created by using semaphores.
See also
- Scheduling algorithm
- round-robinRound-robinThe term round-robin was originally used to describe a document signed by multiple parties in a circle to make it more difficult to determine the order in which it was signed, thus preventing a ringleader from being identified...
- Weighted round robinWeighted round robinWeighted round robin is a scheduling discipline. Each packet flow or connection has its own packet queue in a network interface card. It is the simplest approximation of generalized processor sharing...
- Deficit round robinDeficit round robinDeficit round robin , also deficit weighted round robin , is a modified weighted round robin scheduling discipline. DRR was proposed by M. Shreedhar and G. Varghese in 1995. It can handle packets of variable size without knowing their mean size...
- Process scheduling