Abstract
dc:descriptionAutomatic 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.
Degree
thesis:*- Grantor dc:publisher
- University of North Texas
- Year dc:date
- 1988
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Yue, Kwok B. (Kwok Bun)
- Contributors dc:contributor
-
- Jacob, Roy Thomas
- Appling, William D. L.
- Yang, Chao-Chih
- Conrady, Denis A.
- Renka, Robert J.
- Knezek, Gerald A.
Subjects
dc:subject × 5Rights
dc:rights- Statement dc:rights
-
- Public
- Yue, Kwok B. (Kwok Bun)
- Copyright
- Copyright is held by the author, unless otherwise noted. All rights reserved.
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
-
local-cont-no: 1002714718-Yue
call-no: 379 N81d no.2916
untcat: b1439551
ark: ark:/67531/metadc331970