Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is round-robin scheduling?

In a multitasking operating system context, sometimes you hear the term round-robin scheduling. What does it refer to?
What other kind of scheduling is there?

like image 887
Benoit Avatar asked Sep 17 '08 02:09

Benoit


People also ask

What do you mean by round robin scheduling?

Round-robin scheduling (Figure 7.151) allocates each task an equal share of the CPU time. In its simplest form, tasks are in a circular queue and when a task's allocated CPU time expires, the task is put to the end of the queue and the new task is taken from the front of the queue.

Where is round robin scheduling used?

Round robin is a nice scheduling for processes with the same priority or in an OS without priorities or priorities based only on groups (Minix 2). It is also ok, when you use a few independent programs, because process starvation is not likely to happen.

What is round robin scheduling algorithm Why is it used?

Round Robin is a CPU scheduling algorithm where each process is assigned a fixed time slot in a cyclic way. It is basically the preemptive version of First come First Serve CPU Scheduling algorithm. Round Robin CPU Algorithm generally focuses on Time Sharing technique.

Why round robin scheduling is best?

A big advantage of round robin scheduling over non-preemptive schedulers is that it dramatically improves average response times. By limiting each task to a certain amount of time, the operating system can ensure that it can cycle through all ready tasks, giving each one a chance to run.


2 Answers

Round Robin Scheduling

If you are a host in a party of 100 guests, round-robin scheduling would mean that you spend 1 minute (a fixed amount) per guest. You go through each guest one-by-one, and after 100 minutes, you would have spent 1 minute with each guest. More on Wikipedia.

There are many other types of scheduling, such as priority-based (i.e. most important people first), first-come-first-serve, earliest-deadline-first (i.e. person leaving earliest first), etc. You can start off by googling for scheduling algorithms or check out scheduling at Wikipedia

like image 65
Swati Avatar answered Sep 20 '22 14:09

Swati


Timeslicing is inherent to any round-robin scheduling system in practice, AFAIK.

I disagree with InSciTek Jeff's implication that the following is round-robin scheduling:

That is, each task at the same priority in the round-robin rotation can be allowed to run until they reach a resource blocking condition before yeilding to the next task in the rotation.

I do not see how this could be considered round-robin. This is actually preemptive scheduling. However, it is possible to have a scheduling algorithm which has elements of both round-robin and preemptive scheduling, which VxWorks does if round-robin scheduling and preemption are both enabled (round-robin is disabled by default). The way to enable round-robin scheduling is to provide a non-zero value in kernelTimeSlice.

I do agree with this statement:

Therefore, while timeslicing based scheduling implies round-robin scheduling, round-robin scheduling does not require equal time based timeslicing.

You are right that it doesn't require equal time. Preemption can muck with that. And actually in VxWorks, if a task is preempted during round-robin scheduling, when the task gets control again it will execute for the rest of the time it was allocated.

Edit directed at InSciTek Jeff (I don't have comment privileges) Yes, I was referring to task locking/interrupt disabling, although I obviously didn't express that very well. You preempted me (ha!) with your second comment. I hope to debate the more salient point, that you believe round-robin scheduling can exist without time slicing. Or did you just mean equal time based time slicing? I disagree with the former, but agree with the latter. I am eager to learn. Thanks.

Edit2 directed at Jeff:

Round-robin can exist without timeslicing. That is exactly what happens in VxWorks when kernelTimeSlice is disabled (zero).

I disagree with this statement. See this document section 2.2.3 with the heading Round-Robin Scheduling.

Round-robin scheduling uses time slicing to achieve fair allocation of the CPU to all tasks with the same priority. Each task, in a group of tasks with the same priority, executes for a defined interval or time slice. Round-robin scheduling is enabled by calling kernelTimeSlice( ), which takes a parameter for a time slice, or interval. [...] If round-robin scheduling is enabled, and preemption is enabled for the executing task, the system tick handler increments the task's time-slice count.

Timeslicing is inherent in round-robin scheduling. Otherwise you are relying on a task to give up CPU control, which round-robin scheduling is intended to solve.

like image 38
unwieldy Avatar answered Sep 21 '22 14:09

unwieldy