Return to search

Semaphore Solutions for General Mutual Exclusion Problems

Automatic generation of starvation-free semaphore solutions to general mutual exclusion problems is discussed. A reduction approach is introduced for recognizing edge-solvable problems, together with an O(N^2) algorithm for graph reduction, where N is the number of nodes. An algorithm for the automatic generation of starvation-free edge-solvable solutions is presented. The solutions are proved to be very efficient. For general problems, there are two ways to generate efficient solutions. One associates a semaphore with every node, the other with every edge. They are both better than the standard monitor—like solutions. Besides strong semaphores, solutions using weak semaphores, weaker semaphores and generalized semaphores are also considered. Basic properties of semaphore solutions are also discussed. Tools describing the dynamic behavior of parallel systems, as well as performance criteria for evaluating semaphore solutions are elaborated.

Identiferoai:union.ndltd.org:unt.edu/info:ark/67531/metadc331970
Date08 1900
CreatorsYue, Kwok B. (Kwok Bun)
ContributorsJacob, Roy Thomas, Appling, William D. L., Yang, Chao-Chih, Conrady, Denis A., Renka, Robert J., Knezek, Gerald A.
PublisherUniversity of North Texas
Source SetsUniversity of North Texas
LanguageEnglish
Detected LanguageEnglish
TypeThesis or Dissertation
Formatvii, 181 leaves : ill., Text
RightsPublic, Yue, Kwok B. (Kwok Bun), Copyright, Copyright is held by the author, unless otherwise noted. All rights reserved.

Page generated in 0.002 seconds