Generalized Mutual Exclusion with semaphores only

• Autorzy: Ordman E.T. , Eberbach E. , Anwar A.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

mutual exclusion; semaphore; weakly fair semaphore; bounded waiting

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 1999
• Tom: Vol. 40, Nr 4
• Strony: 407--422
• Opis fizyczny: bibliogr. 16 poz.

Twórcy

autor

Ordman E.T.

autor

Eberbach E.

autor

Anwar A.

• Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, USA