Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
    
Tannenbaum wrote many books. Presumably you mean Operating Systems. –  Dave Clarke Mar 11 '12 at 21:52
    
@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.) –  Gilles Mar 11 '12 at 21:57

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
Does the desire to have priorities not contraindicate fairness? –  Raphael Apr 10 '12 at 7:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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