Maekawa's algorithm

The Mamoru Maekawa 1985 presented Maekawa algorithm comes in a distributed system for use to control access to a critical section and to guarantee mutual exclusion. The basic idea of this algorithm is to not ask all processes ( such as the Ricart - Agrawala algorithm), but only a subset.

The algorithm guarantees the safety property ( only one process is in the critical section, but can without using vector timestamps lead to deadlocks ( Life violated the Ness property) ).

This one uses Voting sets. Each process has a voting set ( ) and is located in at least two voting sets. In any voting set contains K processes (), and two different voting sets have at least one common element () As an approximation for the optimum ( smallest possible K) will be used. It arranges the processes in a matrix and defines the voting set as all the processes are in the same column or row as.

Algorithm

Each process has an internal state STATE with the values ​​RELEASED (start value) WANTED (the process would the critical section entered) HERO (the process is in the critical section ) and a Boolean variable VOTED ( another process the permit has been issued to enter the critical section ).

If a process has a desire to enter the critical section:

  • Set STATE = WANTED
  • Request ( Request) to all processes in the Voting Set
  • Wait until K answers
  • Set STATE = HERO

When leaving:

  • Set STATE = RELEASED
  • Release (Release) to all processes in the Voting Set

Upon receipt of a request:

  • If STATE = HELD or VOTED = TRUE then Sort request in queue
  • Reply
  • Set VOTED = TRUE

When receiving a share:

  • If the queue is empty set VOTED = FALSE
  • Send answer to the first process in the queue ( and remove him from it )
  • Set VOTED = TRUE

Message complexity

With every process in three messages are exchanged:

  • An inquiry
  • Consent
  • A release

Overall, therefore, messages are required.

Ricart–Agrawala algorithm Association for Computing Machinery
539003
de