Proportionate fair processor scheduling:
        worst-case analysis of a simple scheme

                  Mike Paterson

   Dept. of Computer Science, Univ. of Warwick, UK

A set of n jobs is being run concurrently. Each job has an 
associated weight which gives the proportion of processor 
time which should ideally be allocated to it. In each time 
quantum, p of the jobs receive one unit of service, and we 
need a rule to select the p jobs at each quantum. 
Proportionate fairness means that, over time, each job should
receive service proportional to its weight. Since the units 
are discrete, this ideal cannot always be achieved, and in 
addition any practical rule must be very fast to evaluate.

We consider a very simple variant of Surplus Fair Scheduling 
(Chandra, Adler, Goyal and Shenoy) and give tight bounds on 
its worst-case deviation from fairness. We show that this 
deviation is approximately p + log n.

(This is joint work with Micah Adler, Petra Berenbrink, Tom 
Friedetzky, Leslie Ann Goldberg and Paul Goldberg.)