Misplaced Pages

Maekawa's algorithm

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

Maekawa's algorithm is an algorithm for mutual exclusion on a distributed system. The basis of this algorithm is a quorum-like approach where any one site needs only to seek permissions from a subset of other sites.

Algorithm

Terminology

  • A site is any computing device which runs the Maekawa's algorithm
  • For any one request of entering the critical section:
    • The requesting site is the site which is requesting to enter the critical section.
    • The receiving site is every other site which is receiving the request from the requesting site.
  • ts refers to the local time stamp of the system according to its logical clock

Algorithm

Requesting site:

  • A requesting site P i {\displaystyle P_{i}} sends a message request ( t s , i ) {\displaystyle {\text{request}}(ts,i)} to all sites in its quorum set R i {\displaystyle R_{i}} .

Receiving site:

  • Upon reception of a request ( t s , i ) {\displaystyle {\text{request}}(ts,i)} message, the receiving site P j {\displaystyle P_{j}} will:
    • If site P j {\displaystyle P_{j}} does not have an outstanding grant {\displaystyle {\text{grant}}} message (that is, a grant {\displaystyle {\text{grant}}} message that has not been released), then site P j {\displaystyle P_{j}} sends a grant ( j ) {\displaystyle {\text{grant}}(j)} message to site P i {\displaystyle P_{i}} .
    • If site P j {\displaystyle P_{j}} has an outstanding grant {\displaystyle {\text{grant}}} message with a process with higher priority than the request, then site P j {\displaystyle P_{j}} sends a failed ( j ) {\displaystyle {\text{failed}}(j)} message to site P i {\displaystyle P_{i}} and site P j {\displaystyle P_{j}} queues the request from site P i {\displaystyle P_{i}} .
    • If site P j {\displaystyle P_{j}} has an outstanding grant {\displaystyle {\text{grant}}} message with a process with lower priority than the request, then site P j {\displaystyle P_{j}} sends an inquire ( j ) {\displaystyle {\text{inquire}}(j)} message to the process which has currently been granted access to the critical section by site P j {\displaystyle P_{j}} . (That is, the site with the outstanding grant {\displaystyle {\text{grant}}} message.)
  • Upon reception of a inquire ( j ) {\displaystyle {\text{inquire}}(j)} message, the site P k {\displaystyle P_{k}} will:
    • Send a yield ( k ) {\displaystyle {\text{yield}}(k)} message to site P j {\displaystyle P_{j}} if and only if site P k {\displaystyle P_{k}} has received a failed {\displaystyle {\text{failed}}} message from some other site or if P k {\displaystyle P_{k}} has sent a yield to some other site but have not received a new grant {\displaystyle {\text{grant}}} .
  • Upon reception of a yield ( k ) {\displaystyle {\text{yield}}(k)} message, site P j {\displaystyle P_{j}} will:
    • Send a grant ( j ) {\displaystyle {\text{grant}}(j)} message to the request on the top of its own request queue. Note that the requests at the top are the highest priority.
    • Place P k {\displaystyle P_{k}} into its request queue.
  • Upon reception of a release ( i ) {\displaystyle {\text{release}}(i)} message, site P j {\displaystyle P_{j}} will:
    • Delete P i {\displaystyle P_{i}} from its request queue.
    • Send a grant ( j ) {\displaystyle {\text{grant}}(j)} message to the request on the top of its request queue.

Critical section:

  • Site P i {\displaystyle P_{i}} enters the critical section on receiving a grant {\displaystyle {\text{grant}}} message from all sites in R i {\displaystyle R_{i}} .
  • Upon exiting the critical section, P i {\displaystyle P_{i}} sends a release ( i ) {\displaystyle {\text{release}}(i)} message to all sites in R i {\displaystyle R_{i}} .

Quorum set ( R x {\displaystyle R_{x}} ):
A quorum set must abide by the following properties:

  1. ∀ i ∀ j [ R i ⋂ R j ≠ ∅ ] {\displaystyle \forall i\,\forall j\,}
  2. ∀ i [ P i ∈ R i ] {\displaystyle \forall i\,}
  3. ∀ i [ | R i | = K ] {\displaystyle \forall i\,}
  4. Site P i {\displaystyle P_{i}} is contained in exactly K {\displaystyle K} request sets
Therefore:
  • | R i | ≥ N − 1 {\displaystyle |R_{i}|\geq {\sqrt {N-1}}}

Performance

  • Number of network messages; 3 N {\displaystyle 3{\sqrt {N}}} to 6 N {\displaystyle 6{\sqrt {N}}}
  • Synchronization delay: 2 message propagation delays
  • The algorithm can deadlock without protections in place.

See also

References

  1. "Maekawa's Mutual Exclusion Algorithm: Voting approach".
  2. "Distributed Mutual Exclusion" (PDF).
  • M. Maekawa, "A √N algorithm for mutual exclusion in decentralized systems”, ACM

Transactions in Computer Systems, vol. 3., no. 2., pp. 145–159, 1985.

  • Mamoru Maekawa, Arthur E. Oldehoeft, Rodney R. Oldehoeft (1987). Operating Systems: Advanced Concept. Benjamin/Cummings Publishing Company, Inc.
  • B. Sanders (1987). The Information Structure of Distributed Mutual Exclusion Algorithms. ACM Transactions on Computer Systems, Vol. 3, No. 2, pp. 145–59.
Category: