What is round-robin scheduling?

Question

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?

Solution 1

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

Solution 2

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.

Solution 3

The answers here and even the Wikipedia article describe round-robin scheduling to inherently include periodic timeslicing. While this is very common, I believe that Round-Robin scheduling and timeslicing are not exactly the same thing. Certainly, for timeslicing to make sense, round-robin schedling is implied when rotating to each task, however you can do round-robin scheduling without having timeslicing. That is, each task at the same priority in the round-robin rotation can be allowed to run until they reach a resource block condition and only then having the next task in the rotation run. In other words, when equal priority tasks exist, the reschedling points are not time pre-emptive.

The above idea is actually realized specifically in the case of Wind River's VxWorks kernel. Within their priority scheme, tasks of each priority run round robin but do not timeslice without specifically enabling that feature in the kernel. The reason for this flexibility is to avoid the overhead of timeslicing tasks that are already known to run into a block within a well bounded time.

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

Solution 4

An opinion. It seems that we are intertwining two mechanisms into one. Assuming only the OP's original assertion "In a multitasking operating system context" then

1 - A round robin scheduler always schedules the next item in a circular queue.

2 - How the scheduler regains control to perform the scheduling is separate and unrelated.

I don't disagree that the most prevalent method for 2 is time-slicing / yield waiting for resource, but as has been noted there are others. If I am not mistaken the first Mac's didn't utilize time-slicing, they used voluntary yield / yield waiting for resource (20+ year old brain cells can be wrong sometimes;).

View more solutions

Comments

[Tall Jeff]

You can't turn off preemption in VxWorks. It is inherent because if a higher priority task becomes runnable, it will PREEMPT the lower priority thread. Preemption is not tied to timeslicing, it involves any situation where a thread can be interrupted without explicitly having to yield the CPU.

[Tall Jeff]

Well, to be clear - in case somebody gets very literal - preemption is inherent in VxWorks....assuming you don't disable interrupts and/or lock the scheduler.

[Tall Jeff]

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

[Tall Jeff]

RE Edit: To me the preemptive in preemptive scheduling or preemptive multi-tasking just refers to the fact/feature of the kernel in that it facilitates asynchronous deschedling of the thread without the thread having to call a kernel API method to allow a task switch to occur.

[Tall Jeff]

RE Edit: In non-preemptive systems, for task switches to occur, the thread MUST call a kernel blocking primitive for a switch to occur or it must explicitly make some sort of task_yield() call to cause the switch.

[Donal Fellows]

It isn't. RR is a method of distributing execution time among tasks that are runnable. Preëmptive scheduling characterizes the fact that a task can be interrupted at arbitrary points. RR can be used with coöperative scheduling too, and there are other alternatives to RR (e.g., priority-based).

[Ankur Sinha]

It is preemptive at time quantum partially according to William Stallings.