Fine-grained task reweighting on multiprocessors

We consider the problem of task reweighting\/ in fair-scheduled multiprocessor systems wherein each task's processor share is specified as a weight\/. When a task is reweighted, a new weight is computed for it, which is then used in future scheduling. Task reweighting can be used as a means for consuming (or making available) spare processing capacity. The responsiveness of a reweighting scheme can be assessed by comparing its allocations to those of an ideal scheduler that can reweight tasks instantaneously. A reweighting scheme is fine-grained if any additional per-task "error" (in comparison to an ideal allocation) caused by a reweighting event is constant. In prior work on uniprocessor\/ notions of fairness, a number of fine-grained reweighting schemes were proposed. However, in the multiprocessor case, prior work has failed to produce such a scheme. In this paper, we remedy this shortcoming by presenting a multiprocessor reweighting scheme that is fine-grained. We also present an experimental evaluation of this scheme that shows that it is often much more responsive than prior (non-fine-grained) schemes in enacting weight-change requests.