|
Abstract : |
We consider wait-free synchronization in multiprogrammed uniprocessor and multiprocessor systems in which "hybrid " schedulers are employed that use both priority information and a scheduling quantum in making scheduling decisions. The main contribution of this paper is to show that, in any hybrid-scheduled system, any object with consensus number C P in Herlihy's wait-free hierarchy is universal for any number of processes executing on P processors, provided the scheduling quantum is of a certain size. We also show that if a C-consensus object must be "hard-wired " to the processors that access it, then our characterization of the required quantum is asymptotically tight. If C = P or if C 2P, then this characterization is asymptotically tight regardless of whether objects must be "hard-wired". 1, |
