Maekawa's algorithm

Maekawa's algorithm

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.

Contents

Algorithm

Terminology

  • A site is any computing device which is running the Maekawa's Algorithm
  • For any one request of the critical section:
    • The requesting site is the site which is requesting entry into 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 Pi sends a message request(ts,i) to all sites in its quorum set Ri.

Receiving site:

  • Upon reception of a request(ts,i) message, the receiving site Pj will:
    • If site Pj does not have an outstanding grant message (that is, a grant message that has not been released), then site Pj sends a grant(j) message to site Pi.
    • If site Pj has an outstanding grant message with a process with higher priority than the request, then site Pj sends a failed(j) message to site Pi and site Pj queues the request from site Pi.
    • If sites Pj has an outstanding grant message with a process with lower priority than the request, then site Pj sends an inquire(j) message to the process which has currently been granted access to the critical section by site Pj. (That is, the site with the outstanding grant message.)
  • Upon reception of a inquire(j) message, the site Pk will:
    • Send a yield(k) message to site Pj if and only if site Pk has received a failed message from some other site or if Pk has sent a yield to some other site but have not received a new grant.
  • Upon reception of a yield(k) message, site Pj will:
    • Send a 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 Pk into its request queue.
  • Upon reception of a release(i) message, site Pj will:
    • Delete Pi from its request queue.
    • Send a grant(j) message to the request on the top of its request queue.

Critical section:

  • Site Pi enters the critical section on receiving a grant message from all sites in Ri.
  • Upon exiting the critical section, Pi sends a release(i) message to all sites in Ri.

Quorum set (Rx):
A quorum set must abide by the following properties:

  1. \forall i \,\forall j\, [R_i \bigcap R_j \ne \empty ]
  2. \forall i\, [ P_i \in R_i ]
  3. \forall i\, [ |R_i| = K ]
  4. Site Pi is contained in exactly K request sets
Therefore:
  • |R_i| \geq \sqrt{N-1}

Performance

  • Number of network messages; 3 \sqrt{N} to 6 \sqrt{N}
  • Synchronization delay: 2 message propagation delays

See also

References

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

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Maekawa — (前川?) is a Japanese family name. People Kazuya Maekawa Kunio Maekawa Shinpei Mykawa, namesake of Mykawa, Texas Yasuo Maekawa Fictional characters Ai Maekawa of Doubt!! Akio Maekawa of …   Wikipedia

  • Maekawa-Algorithmus — Der von Mamoru Maekawa 1985 vorgestellte Maekawa Algorithmus kommt in einem verteilten System zur Anwendung, um den Zugang zu einem kritischen Abschnitt zu regeln und dabei wechselseitigen Ausschluss zu garantieren. Die Grundidee dieses… …   Deutsch Wikipedia

  • Ricart-Agrawala algorithm — The Ricart Agrawala Algorithm is an algorithm for mutual exclusion on a distributed system. This algorithm is an extension and optimization of Lamport s Distributed Mutual Exclusion Algorithm, by removing the need for release messages. It was… …   Wikipedia

  • Raymond's algorithm — is a token based algorithm for mutual exclusion on a distributed system. It imposes a logical structure (a K ary tree) on distributed resources. As defined, each node has only a single parent, to which all requests to attain the token are made.… …   Wikipedia

  • Lamport's Distributed Mutual Exclusion Algorithm — is a contention based algorithm for mutual exclusion on a distributed system. Algorithm Nodal Properties# Every process maintains a queue of pending requests for entering critical section ordered according to the logical time… …   Wikipedia

  • Algorithme de Naimi-Trehel — L algorithme de Naimi Trehel assure l exclusion mutuelle dans les systèmes distribués. Cet algorithme réduit le nombre moyen de messages à log(n)en introduisant une structure arborescente logique et un jeton. L algorithme a été présenté en 1987… …   Wikipédia en Français

  • Psychoacoustics — is the study of subjective human perception of sounds. Alternatively it can be described as the study of the psychological correlates of the physical parameters of acoustics. Background Hearing is not a purely mechanical phenomenon of wave… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”