Round-robin scheduling: allow listing a process multiple times?

Question

In a round-robin scheduler, adding a process multiple times to the process list is a cheap way to give it higher priority.

I wonder how practical an approach this might be. What benefit does it have over other techniques such as giving the process a longer time slice (benefit: less switching time) or maintaining a separate list of high-priority processes. In particular, how does listing a process multiple times influence fairness and reactivity?

(From exercise 2.16 in Andrew Tanenbaum's Operating Systems: Design and Implementation 1st ed.)

Answer 1

The advantage of this approach is that round robin scheduling is very efficient, so you don't need to rely on a more complex scheduler, which would steal cycles. Introducing longer time slices for higher priority processes would decrease the responsiveness of other threads and make it harder for the OS to jump in to deal with an interrupt and so forth. Maintaining separate lists of processes would require a much more complex scheduler, which would be more expensive in terms of cycles. I don't see how there would be any problem with fairness, though. I guess the problem is that the granularity is fairly course: processes can only have integer multiples of the basic time-slice.

One negative point is that removing a process would be more costly, as each occurrence of the process would have to be removed from the queue. Perhaps this can be done lazily, though.

Answer 2

Adding the task to a round-robin scheduling queue multiple times opens up the problem of ensuring that the entries remain reasonably evently distributed. This is easy to ensure if the system does not permit dynamic task creation or deletion, but not possible in general.

In addition to the more complex process of removing the items from the queue, the eventual skewing of the process entries in the queue will result in unbalanced behaviour that is easier to make fair with multiple priority levels.