Wait-free synchronization in multiprogrammed systems
James Horton Anderson, Mark J. Moir · 1999
We consider wait-free synchronization in multipro grammed 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 2 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 2 2P, then this characterization is asymptotically tight regardless of whether objects must be "hard-wired".