Round-robin scheduling
   HOME

TheInfoList



OR:

Round-robin (RR) is one of the algorithms employed by
process A process is a series or set of activities that interact to produce a result; it may occur once-only or be recurrent or periodic. Things called a process include: Business and management *Business process, activities that produce a specific se ...
and
network scheduler A network scheduler, also called packet scheduler, queueing discipline (qdisc) or queueing algorithm, is an arbiter on a node in a packet switching communication network. It manages the sequence of network packets in the transmit and receive q ...
s in
computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes, and development of both hardware and software. Computing has scientific, e ...
.
Guowang Miao Guowang Miao is an associate professor at KTH Royal Institute of Technology, Sweden, working on design and optimization of wireless communications and networking and the author of ''Fundamentals of Mobile Data Networks'' and ''Energy and Spectrum ...
, Jens Zander, Ki Won Sung, and Ben Slimane, Fundamentals of Mobile Data Networks, Cambridge University Press, , 2016.
As the term is generally used, time slices (also known as time quanta) are assigned to each process in equal portions and in circular order, handling all processes without priority (also known as
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. The basic scheme is t ...
). Round-robin scheduling is simple, easy to implement, and
starvation Starvation is a severe deficiency in caloric energy intake, below the level needed to maintain an organism's life. It is the most extreme form of malnutrition. In humans, prolonged starvation can cause permanent organ damage and eventually, dea ...
-free. Round-robin scheduling can be applied to other scheduling problems, such as data packet scheduling in computer networks. It is an
operating system An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs. Time-sharing operating systems schedule tasks for efficient use of the system and may also in ...
concept. 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 schedule processes fairly, a round-robin scheduler generally employs
time-sharing In computing, time-sharing is the sharing of a computing resource among many users at the same time by means of multiprogramming and multi-tasking.DEC Timesharing (1965), by Peter Clark, The DEC Professional, Volume 1, Number 1 Its emergence a ...
, 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. If the process terminates or changes its state to waiting during its attributed time quantum, the scheduler selects the first process in the ready queue to execute. 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 favored over other processes. 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 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 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: 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
best-effort Best-effort delivery describes a network service in which the network does ''not'' provide any guarantee that data is delivered or that delivery meets any quality of service. In a best-effort network, all users obtain best-effort service. Under ...
packet switching In telecommunications, packet switching is a method of grouping Data (computing), data into ''network packet, packets'' that are transmitted over a digital Telecommunications network, network. Packets are made of a header (computing), header and ...
and other
statistical multiplexing Statistical multiplexing is a type of communication link sharing, very similar to dynamic bandwidth allocation (DBA). In statistical multiplexing, a communication channel is divided into an arbitrary number of variable bitrate digital channels or ...
, round-robin scheduling can be used as an alternative to
first-come first-served Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...
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 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 In communication networks, multiplexing and the division of scarce resources, max-min fairness is said to be achieved by an allocation if and only if the allocation is feasible and an attempt to increase the allocation of any participant necessari ...
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 Weighted fair queueing (WFQ) is a network scheduling algorithm. WFQ is both a packet-based implementation of the generalized processor sharing (GPS) policy, and a natural extension of fair queuing (FQ). Whereas FQ shares the link's capacity in ...
(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 On a local area network, token passing is a channel access method where a packet called a ''token'' is passed between nodes to authorize that node to communicate. In contrast to polling access methods, there is no pre-defined "master" node. The most ...
channel access In telecommunications and computer networks, a channel access method or multiple access method allows more than two terminals connected to the same transmission medium to transmit over it and to share its capacity. Examples of shared physical med ...
schemes such as
Token Ring Token Ring network IBM hermaphroditic connector with locking clip. Screen contacts are prominently visible, gold-plated signal contacts less so. Token Ring is a computer networking technology used to build local area networks. It was introduc ...
, or by
polling Poll, polled, or polling may refer to: Figurative head counts * Poll, a formal election ** Election verification exit poll, a survey taken to verify election counts ** Polling, voting to make decisions or determine opinions ** Polling places o ...
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, comprising adaptive coding and modulation (ACM) and others (such as Power Control), is a term used in wireless communications to denote the matching of the modulation, coding and other signal and protocol parameters to the condit ...
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 Proportional-fair scheduling is a compromise-based scheduling algorithm. It is based upon maintaining a balance between two competing interests: Trying to maximize total throughput of the network (wired or not) while at the same time allowing all ...
algorithm, or
maximum throughput scheduling {{Short description, Procedure for scheduling data packets in a packet switched best-effort network Maximum throughput scheduling is a procedure for scheduling data packets in a packet-switched best-effort network, typically a wireless network, in ...
. Note that the latter is characterized by undesirable
scheduling starvation A schedule or a timetable, as a basic time-management tool, consists of a list of times at which possible tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order in which such things are i ...
. This type of scheduling is one of the very basic algorithms for Operating Systems in computers which can be implemented through a circular queue data structure.


See also

*
Multilevel queue Multi-level queueing, used at least since the late 1950s/early 1960s, is a queue with a predefined number of levels. Items get assigned to a particular level at insert (using some predefined algorithm), and thus cannot be moved to another level (un ...


References

{{Queueing theory Processor scheduling algorithms Network scheduling algorithms