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.
| Identifer | oai:union.ndltd.org:unt.edu/info:ark/67531/metadc331970 |
| Date | 08 1900 |
| Creators | Yue, Kwok B. (Kwok Bun) |
| Contributors | Jacob, Roy Thomas, Appling, William D. L., Yang, Chao-Chih, Conrady, Denis A., Renka, Robert J., Knezek, Gerald A. |
| Publisher | University of North Texas |
| Source Sets | University of North Texas |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
| Format | vii, 181 leaves : ill., Text |
| Rights | Public, Yue, Kwok B. (Kwok Bun), Copyright, Copyright is held by the author, unless otherwise noted. All rights reserved. |
Page generated in 0.002 seconds