E. A. Schneider

Synchronization of Finite State Shared Resources Degree Type: Ph.D. in Computer Science
Advisor(s): Nico Habermann
Graduated: December 1976

Abstract:

The problem of synchronizing a set of operations defined on a shared resource is studied. It is assumed that the decision as to which operations may be executed at some given time is dependent only on the sequence in which the operations have already executed. Equivalence classes of these sequences, called states, can then be used to define synchronization. A restriction is made such that only those resources for which the synchronization can be expressed using a finite number of states will be studied.

The states along with a successor function, which is defined for a state-operation pair if the operation may start execution when the resource is in that state, form what are called synchronization relationships. A distinction is made between resources on which only one process may execute an operation at a time, called serial resources, and resources on which several processes may execute operations in parallel, called concurrent sources.

To handle concurrent resources, the states must be modified so that they correspond to equivalence classes of sequences of perilogues instead of operations. A periologue is either the start or the finish of the execution of some operation. Several variations of regular expressions are presented with which the synchronization for a shared resource might be expressed. Also, a method which can be used to implement the synchronization relationships is given.

Thesis Committee:
Nico Habermann (Chair)

Joseph Traub, Head, Computer Science Department