Outline for February 8, 2001 1. Greetings and felicitations! 2. Maekawa's's a. Request sets satisfy the following conditions: i. for all 1 i, j n with i j, Ri Ť Rj ii. for all 1 i n, pi ? Ri iii. for all 1 i n, | Ri | = K iv. pj is contained in K number of Ri. b. Idea: every pair of processes has has a mediator (in both request sets) to mediate conflicts c. Only one outstanding REPLY per process, so each process gives permission to enter to only one other pro- cess d. Assumes messages delivered in order which they are sent e. To avoid deadlock, can INQUIRE whether someone cannot get it f. A FAILED message just means someone else is going in out of order g. Performance: between 3N and 5N messages 3. Sanders' generalized protocol a. Inform set Ii is set of processes to be informed when pi enters or leaves CS b. Status set STi contains pids for which pi maintains status information; note: pi ? Ij ? pj ? STi c. If pi ? Ii for all i, then necessary and sufficient conditions to guarantee mutual exclusion are: i. Ii Ő Ri ii. Ii Ť Ij or (pi ? Rj and pj ? Ri) 4. Suzuki-Kasami's broadcast protocol a. token-based b. uses sequence numbers, not clocks c. token has sequence numbers, associated queue d. how to handle stale requests? token's sequence number too high 5. Raymond's tree-based protocol a. token-based b. think of token as at root of tree, root moves around Maekawa's Distributed Mutual Exclusion Protocol Introduction Maekawa's algorithm uses sets Si of fewer than n processes. Also, a process pi locks all the nodes in Si by having only one reply message out at a time. Each process has a queue of unsatisfied requests ordered by timestamp. Notation ˇ n processes p1, -, pn ˇ tj timestamp Protocol 1. To enter the critical section, pi sends REQUEST(ti, i) to all sites in Si. 2. When pj receives a REQUEST(ti, i) message: a. if it has not sent a REPLYmessage to any site since the last RELEASE message pj received, pj sends REPLY(tj, ,j) to pi. b. Otherwise, there is a process pk such that pj has already sent a REPLY(tj, ,j) message to pk. Then: i. if (ti, i) < (tk, k), pj sends an INQUIRE(j) message to pk and places the REQUEST on its queue. ii. Otherwise, pj sends a FAILED(j) message to pi. 3. When pk receives an INQUIRE(j) message, it sends a YEILD(k) message if either of the following conditions are met: a. pk has received a FAILED message from a site in Sk b. pk has sent a YIELD(m) message to a site pm ? Sk and has not received a REPLY in reply. Otherwise pk does nothing. 4. When pj receives a YIELD(k) message, pj places REQUEST(tk, k) in the queue and sends a REPLY(tj, j) to the site whose request is first in the queue. 5. When pj receives a RELEASE(ti, i) message, it sends a REPLY(tj, ,j) message to the next site in the queue and deletes the entry from the queue. If the queue is empty, pj updates its state to reflect that no REPLY message has been sent to any site since the last RELEASE message pj received. 6. pi enters the critical section when it has received REPLY messages from all processes in Si. 7. When pi leaves the critical section, it sends RELEASE(ti, i) to all sites in Si. Example There are 13 processes. Initially, all logical clocks are set to 0. The sets are: S1 = { 1, 2, 3, 4 } S4 = { 4, 6, 10, 11 } S7 = { 2, 7, 10, 13 } S10 = { 3, 5, 10, 12 } S2 = { 2, 5, 8, 11 } S5 = { 1, 5, 6, 7 } S8 = { 1, 8, 9, 10 } S11 = { 1, 11, 12, 13 } S3 = { 3, 6, 8, 13 } S6 = { 2, 6, 9, 12 } S9 = { 3, 7, 9, 11 } S12 = { 4, 7, 8, 12 } S13 = { 4, 5, 9, 13 } p11 sends REQUEST(0, 11) to p1, p12, p13. p12 receives REQUEST(0, 11) and sends REPLY(1, 12) to p11. p13 receives REQUEST(0, 11) and sends REPLY(1, 13) to p11. p7 sends REQUEST(0, 7) to p2, p10, p13. p2 receives REQUEST(0, 7) and sends REPLY(1, 2) to p7. p10 receives REQUEST(0, 7) and sends REPLY(1, 10) to p7. p8 sends REQUEST(0, 8) to p1, p9, p10. p1 receives REQUEST(0, 8) and sends REPLY(1, 1) to p8. p9 receives REQUEST(0, 8) and sends REPLY(1, 9) to p8. p10 receives REQUEST(0, 8). It already sent a REPLY to p7. p7's request is timestamped (0, 7) < (0, 8). p10 sends FAILED(10) to p8. p1 receives REQUEST(0, 11). It already sent a REPLY to p8. p8's request is timestamped (0, 8) < (0, 11). p1 sends FAILED(1) to p11. p13 receives REQUEST(0, 7). It already sent a REPLY to p11. p11's request is timestamped (0, 11), and (0, 7) < (0, 11). p13 sends INQUIRE(13) to p11. p11 receives INQUIRE(13). It has received a FAILED(1) message from p1. p11 sends YIELD(11) to p13. p13 receives YIELD(11). It now sends REPLY(2, 7) to p7 and places REQUEST(0, 11) in its queue. p7 has received replies from all processes in S7. It enters the critical section. p7 leaves the critical section and sends RELEASE(1000, 7) to p2, p10, p13. p10 receives RELEASE(1000, 7). p10 sends REPLY(1001, 8). p8 has received replies from all processes in S8. It enters the critical section. p8 leaves the critical section and sends RELEASE(1003, 8) to p1, p9, p10. p1 receives RELEASE(1003, 8). p1 sends REPLY(1004, 1). p11 has received replies from all processes in S11. It enters the critical section. p11 leaves the critical section and sends RELEASE(1005, 11) to p1, p12, p13. Sanders' Generalized Protocol Introduction This protocol is a generalization of the previous protocols. Notation ˇ n processes ˇ pi process ˇ Ri request set for pi ˇ Ii inform set for pi ˇ STi status set for pi ˇ CSSTAT site's knowledge of state of critical section Protocol 1. To request entry, pi sends REQUEST(ti, i) to all sites in Ri. 2. When a site pi gets a REQUEST(tj, j) message: a. it places the request onto its queue, which is ordered by timestamps b. if CSSTAT says the critical section is free, pi sends a GRANT message to the first process pf in the queue and deletes its entry from the queue. If pf ? STi, then CSSTAT is set to indicate that pf is in the critical section. 3. When pi has received GRANT messages from all processes in Ri, pi enters the critical section. 4. When pi leaves the critical section, pi sends a RELEASE message to every site in Ii. 5. When pi receives a RELEASE message: a. CSSTAT is set to free b. If pi queue is not empty, pi sends a GRANT to the first process pf in the queue and deletes its entry from the queue. If pf ? STi, then CSSTAT is set to indicate that pf is in the critical section. c. Repeat step b until either CSSTAT indicates a process has entered the critical section, or pf's queue is empty. Example There are three processes, p1, p2, and p3. p1 and p3 seek mutually exclusive access to a shared resource. Let: I1 = { p1, p3 }, I2 = { p2 }, I3 = { p3 }, so ST1 = { p1 }, ST2 = { p2 }, ST3 = { p1, p3 }; and R1 = { p1, p2, p3 }, R2 = { p1, p2, p3 }, R3 = { p2, p3 } These satisfy the criteria that, for all i, pi ? Ii, Ii Ő Ri, and for all pairs (i, j), either Ii Ť Ij or (pi ? Rj and pj ? Ri). Initially: p1 state: C1 = 0, Q1 empty, CSSTAT1 empty p2 state: C2 = 0, Q2 empty, CSSTAT2 empty p3 state: C3 = 0, Q3 empty, CSSTAT3 empty p1 sends Q(0,1) to p1, p2 and p3; p1's state now C1 = 1, Q1 empty, CSSTAT1 empty, GRANTS1 empty p1 receives Q(0,1) from p1; p1's state now C1 = 1, Q1 = Q(0,1), CSSTAT1 empty, GRANTS1 empty p1 sends G(1,1) to p1; p1's state now C1 = 2, Q1 empty, CSSTAT1 = p1, GRANTS1 empty p1 receives G(1,1) to p1; p1's state now C1 = 2, Q1 empty, CSSTAT1 = p1, GRANTS1 G(1,1) p3 sends Q(0,3) to p2 and p3; p3's state now C3 = 1, Q3 empty, CSSTAT3 empty, GRANTS3 empty p3 receives Q(0,3) from p3; p3's state now C3 = 1, Q3 = Q(0,3), CSSTAT3 empty, GRANTS3 empty p3 sends G(1,3) to p3; p3's state now C3 = 2, Q3 empty, CSSTAT3 = p3, GRANTS3 empty p3 receives G(1,3) from p3; p3's state now C3 = 2, Q3 empty, CSSTAT3 = p3, GRANTS3 G(1,3) p2 receives Q(0,1) from p1; p2's state now C2 = 2, Q2 = Q(0,1), CSSTAT2 empty, GRANTS2 empty p2 sends G(2,2) to p1; p2's state now C2 = 3, Q2 empty, CSSTAT2 empty, GRANTS2 empty p2 receives Q(0,3) from p3; p2's state now C2 = 3, Q2 = Q(0,3), CSSTAT2 empty, GRANTS2 empty p2 sends G(3,2) to p3; p2's state now C2 = 4, Q2 empty, CSSTAT2 empty, GRANTS2 empty p3 receives Q(0,1) from p1; p3's state now C3 = 2, Q3 = Q(0,1), CSSTAT3 = p3, GRANTS3 G(1,3) p1 receives G(2,2) from p2; p1's state now C1 = 2, Q1 empty, CSSTAT1 = p1, GRANTS1 G(1,1), G(2,2) p3 receives G(3,2) from p2; p3's state now C3 = 3, Q3 = Q(0,1), CSSTAT3 = p3, GRANTS3 G(1,3), G(3,2) p3 enters its critical section p3 exits its critical section p3 sends R(3,3) to p3; p3's state now C3 = 4, Q3 empty, CSSTAT3 = p3, GRANTS3 empty p3 receives R(3, 3) from p3; p3's state now C3 = 4, Q3 = Q(0,1), CSSTAT3 empty, GRANTS3 empty p3 sends G(4, 3) to p1; p3's state now C3 = 5, Q3 empty, CSSTAT3 = p1, GRANTS3 empty p1 receives G(4,3) from p3; p1's state now C1 = 4, Q1 empty, CSSTAT1 = p1, GRANTS1 G(1,1), G(2,2), G(4,3) p1 enters its critical section p1 exits its critical section p1 sends R(4, 1) to p1, p3; p1's state now C1 = 5, Q1 empty, CSSTAT1 = p1, GRANTS1 empty p1 receives R(4,1) from p1; p1's state now C1 = 5, Q1 empty, CSSTAT1 empty, GRANTS1 empty p3 receives R(4,1) from p1; p3's state now C3 = 5, Q3 empty, CSSTAT3 empty, GRANTS3 empty Suzuki-Kasami Broadcast Protocol Introduction This is a token-based protocol. Unlike non-token-based ones, it uses the token's being possessed by a site to provide ordering of requests. Clocks and virtual time do not play a role; but order of arrival does. Notation ˇ n processes ˇ pi process ˇ Ri[j] largest sequence number pi has received in a REQUEST message from pj ˇ L[i] sequence number of request that pi has most recently executed ˇ Q queue (sequence) of sites requesting token ˇ T = (Q, L) token Protocol 1. To request entry, if pi does not have the token, it increments its sequence number Ri[i] and then sends REQUEST(i, s), s = Ri[i], to all other sites. 2. When pi receives REQUEST(i, s) from pj, pi sets Ri[j] = max(Ri[j], s). If pi has the token and Ri[j] = L[j] + 1, it sends the token to pj. 3. If pi is requesting entry and it has or receives the token, it enters the critical section. 4. When pi finishes executing the critical section: a. it sets L[i] = Ri[i]; b. for every j not in Q and for which Ri[j] = L[j] + 1, pi appends j to Q; and c. if Q is not empty, pi deletes the first element f of Q and sends the token to pf. Example There are three processes, p1, p2, and p3. p1 and p3 seek mutually exclusive access to a shared resource. Initially:the token is at p2 and the token's state is L = [0, 0, 0] and Q empty; p1's state is C1 = 0, R1 = [0, 0, 0]; p3's state is C1 = 0, R2 = [0, 0, 0]; and p3's state is C3 = 0, R3 = [0, 0, 0] p1 sends R(1, 1) to p2 and p3; p1's state is C1 = 1, R1 = [ 1, 0, 0 ] p3 sends R(3, 1) to p1 and p2; p3's state is C3 = 1, R3 = [ 0, 0, 1 ] p2 receives R(1, 1) from p1; p2's state is C2 = 1, R2 = [ 1, 0, 0 ], holding token p2 sends the token to p1 p1 receives R(3, 1) from p3; p1's state is C1 = 1, R1 = [ 1, 0, 1 ] p3 receives R(1, 1) from p1; p3's state is C3 = 1, R3 = [ 1, 0, 1 ] p1 receives the token from p2 p1 enters the critical section p1 exits the critical section and sets the token's state to L = [ 1, 0, 0 ] and Q = ( 3 ) p1sends the token to p3; p1's state is C1 = 2, R1 = [ 1, 0, 1 ], holding token, token's state is L = [ 1, 0, 0 ] and Q empty p3 receives the token from p1; p3's state is C3 = 1, R3 = [ 1, 0, 1 ], holding token p3 enters the critical section p3 exits the critical section and sets the token's state to L = [ 1, 0, 1 ] and Q empty Raymond's Tree-Based Protocol Introduction This is a token-based protocol. The nodes are arranged in a binary tree, and one acquires the token by going up the tree. The token is always kept at the root, so the tree needs to rearrange itself as the token floats from site to site. Notation ˇ n processes ˇ pi process ˇ Qi request queue (sequence) of sites associated with process pi ˇ Hi holder variable associated with process pi ˇ T token Protocol 1. To request entry, if pi does not have the token, it sends a REQUEST(i) message to the node named in Hi unless Qi is not empty (because then it has already sent a REQUEST(i) but has not yet received the token). It adds the request to Qi. 2. When pi receives REQUEST(j) from pj: a. if pi does not have the token, it places the REQUEST(j) on Qi and sends a REQUEST(i) message along (pro- vided that it is not waiting for a response to an earlier REQUEST(i). b. if pi has the token, it sends the token to pj and sets Hi to j. 3. If pi is requesting entry and receives the token: a. if i is not the first entry in Qi, it deletes the first entry j from Qi and forwards the token to pj. It then sets Hi to j. If Qi is not empty, pi sends REQUEST(i) to pj. b. if i is the first entry in Qi, pi deletes i from Qi and enters the critical section. 4. When pi finishes executing the critical section: a. if Qi is not empty, it deletes the first entry j from Qi, sends the token to pj, and sets Hi to j b. if after step a Qi is not empty, pi sends REQUEST(i) to pj. Example There are six processes, p1 through p6. p1 and p5 seek mutually exclusive access to a shared resource, and later p3 will request it. Initially: p4 has the token; p1's state is C1 = 0, HOLDER2 = p3, Q1 empty p2's state is C2 = 0, HOLDER2 = p3, Q2 empty p3's state is C3 = 0, HOLDER3 = p4, Q3 empty p4's state is C4 = 0, HOLDER4 = p4, Q4 empty, holding token p5's state is C5 = 0, HOLDER5 = p4, Q5 empty p6's state is C6 = 0, HOLDER6 = p5, Q6 empty p1 sends Q(1) to p3; p1's state is C1 = 1, HOLDER2 = p3, Q1 = Q(1). p5 sends Q(5) to p4; p5's state is C5 = 1, HOLDER5 = p4, Q5 = Q(5). p3 receives Q(1) from p1; p3's state is C3 = 0, HOLDER3 = p4, Q3 empty. p3 sends Q(3) to p4; p3's state is C3 = 1, HOLDER3 = p4, Q3 = Q(1). p4 receives Q(5) from p5; p4's state is C4 = 0, HOLDER4 = p4, Q4 empty, holding token. p4 sends token to p5; p4's state is C4 = 1, HOLDER4 = p5, Q4 empty. p4 receives Q(3) from p3; p4's state is C4 = 1, HOLDER4 = p5, Q4 empty. p4 sends Q(4) to p5; p4's state is C4 = 2, HOLDER4 = p5, Q4 = Q(3). p5 receives token from p4; p5's state is C5 = 1, HOLDER5 = p4, Q5 = Q(5). p5 resets state to C5 = 1, HOLDER5 = p4, Q5 empty, holding token. p5 enters the critical section p5 leaves the critical section p5 receives Q(4) from p4; p5's state is C5 = 1, HOLDER5 = p4, Q5 empty, holding token. p5 sends token to p4; p5's state is C5 = 2, HOLDER5 = p4, Q5 empty. p3 sends Q(3) to p4; p3's state is C3 = 2, HOLDER3 = p4, Q3 = Q(1) Q(3). p4 receives Q(3) from p3; p4's state is C4 = 2, HOLDER4 = p5, Q4 = Q(3). p4's state is C4 = 3, HOLDER4 = p5, Q4 = Q(3)Q(5) [it sends nothing as it is waiting for a response] p4 receives token from p5; p4's state is C4 = 3, HOLDER4 = p5, Q4 = Q(3) Q(5), holding token. p4 sends token to p3; p4's state is C4 = 3, HOLDER4 = p3, Q4 = Q(5). p4 sends Q(4) to p3; p4's state is C4 = 3, HOLDER4 = p3, Q4 = Q(5). p3 receives token from p4; p3's state is C3 = 2, HOLDER3 = p4, Q3 = Q(1) Q(3), holding token. p3 sends token to p1; p3's state is C3 = 3, HOLDER3 = p1, Q3 = Q(3). p3 sends Q(3) to p1; p3's state is C3 = 4, HOLDER3 = p1, Q3 = Q(3). p1 receives token from p3; p1's state is C1 = 1, HOLDER1 = p3, Q1 = Q(1), holding token. p1 resets state to C1 = 1, HOLDER1 = p3, Q1 empty, holding token. p1 enters the critical section p1 leaves the critical section p1 receives Q(3) from p3; p1's state is C1 = 1, HOLDER1 = p3, Q1 empty, holding token. p1 sends token to p3; p1's state is C1 = 2, HOLDER1 = p3, Q1 empty. p3 receives token from p1; p3's state is C3 = 4, HOLDER3 = p1, Q3 = Q(3), holding token. p3 receives Q(4) from p4; p3's state is C3 = 4, HOLDER3 = p1, Q3 = Q(3) Q(4). p3 resets state to C3 = 4, HOLDER3 = p1, Q3 = Q(4). p3 enters the critical section p3 leaves the critical section p3 sends token to p4; p3's state is C3 = 5, HOLDER3 = p4, Q3 empty, holding token. p4 receives token from p3; p4's state is p4's state is C4 = 3, HOLDER4 = p3, Q4 = Q(5). p4 sends token to p5; p4's state is C4 = 4, HOLDER4 = p5, Q4 empty. p5 receives token from p4; p5's state is C5 = 2, HOLDER5 = p4, Q5 empty.