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.)

  • $\begingroup$ Tannenbaum wrote many books. Presumably you mean Operating Systems. $\endgroup$ Commented Mar 11, 2012 at 21:52
  • $\begingroup$ @DaveClarke Yes, thanks for pointing this out. (And actually, all I have here is a translation, but I don't think it's missing any part of the text.) $\endgroup$ Commented Mar 11, 2012 at 21:57

2 Answers 2


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.


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.

  • $\begingroup$ Does the desire to have priorities not contraindicate fairness? $\endgroup$
    – Raphael
    Commented Apr 10, 2012 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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