Semaphore primitives and starvation-free mutual exclusion

Abstract

Most discussions of semaphore primitives m the literature provide only an informal description of their behavtor, rather than a more prectse definition. These informal descriptions may be incorrect, incomplete, or subject to m~smterpretation. As a result, the literature actually contains several different defimtlons of the semaphore primmves. The differences are important, since the particular choice of definition can affect whether a soluuon to the mutual exclusion problem using semaphore primitives allows the possibility of process starvation. An attempt is made to alleviate some of the confusion by gtving precise defmittons of two varteties of semaphore prtmtttves, here called weak and blocked-set primitives. It is then shown that under certain natural condttious, although it is possible to implement starvation-free mutual exclusion with blocked-set semaphores, it is not possible to do so with weak semaphores. Thus weak semaphores are strictly less "powerful" than blocked-set semaphores.