Maekawa's algorithm

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

• A requesting site sends a message to all sites in its quorum set.

• Upon reception of a message, the receiving site will:
• * If site does not have an outstanding message, then site sends a message to site.
• * If site has an outstanding message with a process with higher priority than the request, then site sends a message to site and site queues the request from site.
• * If site has an outstanding message with a process with lower priority than the request, then site sends an message to the process which has currently been granted access to the critical section by site.
• Upon reception of a message, the site will:
• * Send a message to site if and only if site has received a message from some other site or if has sent a yield to some other site but have not received a new.
• Upon reception of a message, site will:
• * Send a message to the request on the top of its own request queue. Note that the requests at the top are the highest priority.
• * Place into its request queue.
• Upon reception of a message, site will:
• * Delete from its request queue.
• * Send a message to the request on the top of its request queue.

• Site enters the critical section on receiving a message from all sites in.
• Upon exiting the critical section, sends a message to all sites in.

4. Site is contained in exactly request sets

   Performance

• Number of network messages; to
• Synchronization delay: 2 message propagation delays
• The algorithm can deadlock without protections in place.