| Szymanski's Mutual Exclusion Algorithm |
|
|
|
Szymanski's algorithm is a mutual exclusion algorithm that works using shared memory and multiple assynchronous processors. It only requires that all participating processors have access to a common region of shared memory, and that only a single read and a single write operation be supported to access that shared memory; no atomic read-modify-write operations are needed, such as increment a memory location, swap the contents of a memory location with the contents of a cpu register, etc. It only requires a single task to be able to write to any particular memory location, but all tasks must have read access to all memory locations. This is called a "single writer, multiple reader" implementation. Szymanski's algorithm is modeled on a waiting room with an entry and exit doorway. Initially the entry door is open and the exit door is closed. All processes which request entry into the critical section at roughly the same time enter the waiting room; the last of them closes the entry door and opens the exit door. The processes then enter the critical section one by one. The last process to leave the critical section closes the exit door and reopens the entry door, so the next batch of processes may enter. [From Wikipedia.] The implementation provided here is modelled after Figure 5 of his paper "Mutual Exclusion Revisited", published in "Proceedings of the Fifth Jerusalem Conference on Information Technology", Jerusalem, Israel, October 1990, IEEE Computer Society Press, Los Alamitos, CA, pp. 110-117. A copy of this paper is available at http://cgi2.cs.rpi.edu/~szymansk/papers/jerus.93.pdf. This implementation is written in C, using good coding standards and plenty of comments. It is keyed to Szymanski's original paper, which, apparently due to publication size limits, used very terse and obfuscatingly formatted psuedo-C to describe the algorithm. The present implementation permits multiple mutexes to be easily dealt with, and allows user-assignable symbolic names for both tasks and mutexes.
|
|
