Back to search

University of North Texas

Semaphore Solutions for General Mutual Exclusion Problems

Abstract

dc:description

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.

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 × 5

Rights

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

Chain of custody

source
Harvested from
University of North Texas
Base URL
digital.library.unt.edu/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Yue, Kwok B. (Kwok Bun). Semaphore Solutions for General Mutual Exclusion Problems. University of North Texas, 1988. https://digital.library.unt.edu/ark:/67531/metadc331970/