Affiliations: Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, U.S.A.
Note: [] Address for correspondence: Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, U.S.A.
Note: [] work done while on leave from the Jodrey School of Computer Science, Acadia University, Wolfville, NS, Canada B0P 1X0, eugene.eberbach@acadiau.ca, research supported in part by NSERC under grant OGP0046501
Note: [] Address for correspondence: Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, U.S.A.
Abstract: The paper deals with a generic solution of the Mutual Exclusion Problem using semaphores only. We use in the solution weakly fair binary semaphores and (not necessarily fair) semaphores with initial value k. All semaphores are simple in that the P and V operations on them are paired in the natural way avoiding split semaphores. No auxiliary shared variables are used. We define a general form of the mutual exclusion problem. We claim: (1) All mutual exclusion problems can be solved using only simple semaphores. (2) All mutual exclusion problems can be solved fairly (with bounded waiting) using simple semaphores (weakly fair binary and initially–k; semaphores). We give some bounds on how many semaphores are needed for standard problems. The solutions given may be inefficient: a mutual exclusion problem which can be solved in linear time and space with shared variables may require exponentially many semaphores.
