Content deleted Content added
Link suggestions feature: 2 links added. |
|||
| (5 intermediate revisions by 5 users not shown) | |||
Line 1:
'''Maekawa's algorithm''' is an algorithm for [[mutual exclusion]] on a [[distributed system]]. The basis of this algorithm is a [[quorum
==Algorithm==
=== Terminology ===
* A ''site'' is any computing device which runs the Maekawa's
* 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===
Line 19:
** If site <math>P_j</math> has an outstanding <math>\text{grant}</math> message with a process with lower priority than the request, then site <math>P_j</math> sends an <math>\text{inquire}(j)</math> message to the process which has currently been granted access to the critical section by site <math>P_j</math>. (That is, the site with the outstanding <math>\text{grant}</math> message.)
* Upon reception of a <math>\text{inquire}(j)</math> message, the site <math>P_k</math> will:
** Send a <math>\text{yield}(k)</math> message to site <math>P_j</math> [[if and only if]] site <math>P_k</math> has received a <math>\text{failed}</math> message from some other site or if <math>P_k</math> has sent a yield to some other site but have not received a new <math>\text{grant}</math>.
* Upon reception of a <math>\text{yield}(k)</math> message, site <math>P_j</math> will:
** Send a <math>\text{grant}(j)</math> message to the request on the top of its own request queue. Note that the requests at the top are the highest priority.
Line 38:
# Site <math>P_i</math> is contained in exactly <math>K</math> request sets
:Therefore: <math>|R_i| \geq \sqrt{N-1}</math>
===Performance===
| |||