2
$\begingroup$

I understand that 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, and the length of the quantum and the number of processes in the run queue.

How do time slice duration and context switching affect each other in a round robin scheduling algorithm?

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Apr 9 '17 at 18:46
1
$\begingroup$

You're confusing three aspects of scheduling that can be chosen independently: preemptivity, ordering strategy, and time slice duration.

Preemptive vs non-preemptive determines when a context switch may happen. With a non-preemptive scheduler, a task¹ keeps executing until it voluntarily yields the processor back to the operating system², and at this point the operating system may schedule another task. With a preemptive scheduler, the operating system interrupts tasks whenever it wants — interrupting a task is called preemption. In practice, preemption happens when a hardware interrupt is triggered, and one of these interrupts is a timer interrupt that the operating system programs in order to limit how long a task will execute without interruption.

Round-robin is a scheduling strategy (also called scheduling discipline), i.e. a way to decide which task gets scheduled once the current task yields control to the operating system. Most scheduling strategies, including round-robin, make sense whether yielding is voluntary (non-preemptive scheduling) or forced (preemptive scheduling).

Round-robin is a simple strategy where the scheduler maintains a queue of tasks. On a context switch, the task that just stopped goes to the back of the queue, and the task at the front of the queue is resumed. In other words, the next task to execute is the one that has been stopped for the longest time. This strategy is fair³ in the sense that every task gets to execute eventually (no task is starved, waiting forever for CPU time): no task can prevent another task from executing (except in a non-preemptive setting, by never yielding).

Exercise: suppose that tasks can create other tasks. The new task has to be added to the scheduler's queue. Where do you put it?

This description above only considers ready tasks, i.e. tasks that have something to do. If a task is blocked, i.e if it can't do anything because it's waiting for an external event, then the task is removed from the scheduler's queue until it becomes unblocked because that event happened. Tasks become blocked because they're waiting for I/O — either communication with another task or communication with a peripheral.

Where do you put a task when it becomes unblocked? Even if you try to keep a “pure” round-robin scheme, there are several choices. A simple choice is to put the unblocked task at the back of the queue. This choice preserves the fairness property of round-robin. Another choice is to keep all the tasks in the queue, even the blocked ones, but skip over blocked ones when scheduling. This also preserves fairness.

However, schedulers usually deviate from a simple round-robin when it comes to I/O, because round-robin is bad for latency. Scheduling is often a compromise between throughput (getting as much work done as possible in total) and latency (responding to specific events quickly). Throughput is what matters for computational tasks, but I/O tasks often need low latency. If the CPU needs to read data from a peripheral, or to display the next frame of a video, or to send a signal to the brakes because the brake pedal was pressed, then a fast response is needed, and waiting for the task's next turn through a queue may not be acceptable. In practice, schedulers are often round-robin at the core, but with modifications to schedule tasks earlier when they're involved in I/O, in order to reduce latency.

So far I've discussed when preemption occurs and which task gets scheduled next. Time slice duration is another aspect of the scheduling strategy. Time slice duration is another example of a compromise between latency and throughput. Context switching has a cost. If the system performs a lot of context switches, the time spent doing context switches instead of useful work is wasted. To maximize throughput, there must be as few context switches as possible, meaning long time slices. On the other hand, a long time slice means high latency. Scheduling tasks immediately on I/O solves part of the latency aspect, but only part. For example, a video player needs CPU time to prepare for the next frame, even if it doesn't receive many I/O events. Complex schedulers tend to classify tasks as I/O-bound or CPU-bound. CPU-bound tasks get long time slices, but infrequently. I/O-bound get frequent but short time slices. Hardware events can always interrupt a time slice, which makes the interrupted task eligible for a longer time slice later or for an earlier re-schedule. The design space is very large. If you're interested in that, I recommend reading the literature around the Linux kernel in places like LWN, which has several different scheduling strategies (you'd pick a different one for an interactive device, for a networked server or for a number cruncher), with people actively working at improving them and writing up their findings.

¹ or thread. In this context, task and thread are synonymous.
² In this context, operating system and kernel are synonymous.
³ Note that this is a technical sense of the word “fairness”, which ignores the fact that some tasks may need more time than others. There are many more complex notions of fairness which I won't go into in this answer.

$\endgroup$
0
$\begingroup$

Ideally we could ignore context switching and say its certain constant C, but generally you would want for the time quanta to be bigger than the context switching time C. This in order for the CPU to keep the process as along as possible compared to the time of the context switch.

$\endgroup$
0
$\begingroup$

if your quantum is longer, your system will be less fair, but if your quantum is to small, the the time used for context switching will become larger and your yield lower.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.