Szymanski's Algorithm
Encyclopedia
Szymanski's Mutual Exclusion Algorithm is a mutual exclusion algorithm
devised by computer scientist Dr. Boleslaw Szymanski
, which has many favorable properties including linear wait, and which extension solved the open problem posted by Leslie Lamport
whether there is an algorithm with a constant number of communication bits per process that satisfies every reasonable fairness and failure-tolerance requirement that Lamport conceived of (Lamport's solution used n factorial communication variables vs. Szymanski's 5).
The 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 (or in larger groups if the critical section permits this). 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.
The implementation consists of each process having a flag variable which is written by that process and read by all others (this single-writer property is desirable for efficient cache
usage). The status of the entry door is computed by reading the flags of all processes. Pseudo-code is given below:
Note that the order of the "all" and "any" tests must be uniform.
Despite the intuitive explanation, the algorithm was not easy to prove correct
, however due to its favorable properties a proof of correctness was desirable and multiple proofs have been presented.
Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
devised by computer scientist Dr. Boleslaw Szymanski
Boleslaw Szymanski
Boleslaw Karl Szymanski is a Professor at the Department of Computer Science and the Founding Head of the Center for Pervasive Computing and Networking, Rensselaer Polytechnic Institute. He's known for multiple contributions into computer science, including Szymanski's Algorithm.-Current Work:Dr...
, which has many favorable properties including linear wait, and which extension solved the open problem posted by Leslie Lamport
Leslie Lamport
Leslie Lamport is an American computer scientist. A graduate of the Bronx High School of Science, he received a B.S. in mathematics from the Massachusetts Institute of Technology in 1960, and M.A. and Ph.D. degrees in mathematics from Brandeis University, respectively in 1963 and 1972...
whether there is an algorithm with a constant number of communication bits per process that satisfies every reasonable fairness and failure-tolerance requirement that Lamport conceived of (Lamport's solution used n factorial communication variables vs. Szymanski's 5).
The 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 (or in larger groups if the critical section permits this). 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.
The implementation consists of each process having a flag variable which is written by that process and read by all others (this single-writer property is desirable for efficient cache
Cache
In computer engineering, a cache is a component that transparently stores data so that future requests for that data can be served faster. The data that is stored within a cache might be values that have been computed earlier or duplicates of original values that are stored elsewhere...
usage). The status of the entry door is computed by reading the flags of all processes. Pseudo-code is given below:
Note that the order of the "all" and "any" tests must be uniform.
Despite the intuitive explanation, the algorithm was not easy to prove correct
Formal verification
In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics .- Usage :Formal verification can be...
, however due to its favorable properties a proof of correctness was desirable and multiple proofs have been presented.