RISC-Linz logo

Maekawa's Mutual Exclusion Algorithm: Voting approach

Christian Mittermaier
Igor Rents
Thomas Prokosch


Description of the Algorithm

The main idea of the algorithm is to let the processors that want to enter the critical section to compete for votes, in analogy to candidates for public office. Every processor P has a voting district Sp. It is required that for all i and j Si and Sj have at least one common element. On the figure below we show S14 in a 36 processor system.

1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 34 35 36

When a processor wishes to enter the critical section, it sends a vote request to every member of its voting district. When the processor receives replies from all the members of the district, it can enter the critical section. When a processor receives a vote request, it responds with a "YES" vote if it has not already cast its vote. When a processor exits the critical section, it informs the voting district, which can then vote for other candidates.

Deadlock can be avoided by using the following mechanism: when a processor makes a request, it assigns a (Lamport) timestamp to the request. The voters will prefer to vote for the earliest candidates. If a processor V has cast its ballot for processor B and then processor C, which has an earlier timestamp than B's, asks for V's vote, V will try to retrieve its vote from B with an INQUIRE message. If B has not yet received all the votes of its voting district, it will relinguish V's vote, which can then be given to C. Lamport timestamps impose a total order, so either the candidate with the lowest timestamp eventually gets all of the votes or the candidate with the lowest timestamp is blocked by a candidate that enters the critical section. In either case, some candidate enters the critical section, so deadlock is avoided.

There is one point at which we need to match up the messages with protocol invocations. Because the INQUIRE messages are generated by the voters asynchronously, a candidate might receive an INQUIRE message that was generated in response to a previous critical section request. The usual method for preventing ambiguous messages is to use sequence numbers. Since the candidate samples a timestamp for the algorithm, we use the timestamp as a sequence number to match INQUIRE messages with critical section request.

Program

You should see a button labelled "Press Me" embedded below. If you do not see this button but the string "Please enable Java!" instead, you must enable Java on your Web browser and then reload the page.

Please enable Java!
Source Code     [ mutex.java] [ Prog.java ] [ Msg.java ]
Key Invariants       I/O Automaton

Maintained by: Igor Rents Last modified: Mon Mar 1 17:44:15 CET 1999
[DAJ ] [RISC-Linz] [ University] [Search]