Distributed Systems 10. Mutual Exclusion & Election Algorithms Paul Krzyzanowski [email protected] 1 11/7/2012 © 2012 Paul KrzyzanowskiProcess Synchronization • Techniques to coordinate execution among processes – One process may have to wait for another – Shared resource (e.g. critical section) may require exclusive access 2 11/7/2012 © 2012 Paul KrzyzanowskiCentralized Systems • Mutual exclusion via: – Test & set in hardware – Semaphores – Messages (inter-process) – Condition variables 3 11/7/2012 © 2012 Paul KrzyzanowskiDistributed Mutual Exclusion • Assume there is agreement on how a resource is identified – Pass identifier with requests • Create an algorithm to allow a process to obtain exclusive access to a resource. 4 11/7/2012 © 2012 Paul KrzyzanowskiCategories • Centralized – A process can access a resource because a central coordinator allowed it to do so • Token-based – A process can access a resource if it is holding a token permitting it to do so • Contention-based – An process can access a resource via distributed agreement 5 11/7/2012 © 2012 Paul KrzyzanowskiCentralized algorithm • Mimic single processor system • One process elected as coordinator P C request(R) grant(R) 1. Request resource 2. Wait for response 3. Receive grant 4. access resource 5. Release resource release(R) 6 11/7/2012 © 2012 Paul KrzyzanowskiCentralized algorithm • If another process claimed resource: – Coordinator does not reply until release – Maintain queue • Service requests in FIFO order P0 C request(R) grant(R) release(R) P1 P2 request(R) Queue P1 request(R) P2 grant(R) 7 11/7/2012 © 2012 Paul KrzyzanowskiCentralized algorithm Benefits • Fair – All requests processed in order • Easy to implement, understand, verify Problems • Process cannot distinguish being blocked from a dead coordinator • Centralized server can be a bottleneck 8 11/7/2012 © 2012 Paul KrzyzanowskiToken Ring algorithm • Assume known group of processes – Some ordering can be imposed on group – Construct logical ring in software – Process communicates with neighbor P0 P1 P2 P3 P4 P5 9 11/7/2012 © 2012 Paul KrzyzanowskiToken Ring algorithm • Initialization – Process 0 gets token for resource R • Token circulates around ring – From Pi to P(i+1)mod N • When process acquires token – Checks to see if it needs to enter critical section – If no, send ring to neighbor – If yes, access resource • Hold token until done P0 P1 P2 P3 P4 P5 token(R) 10 11/7/2012 © 2012 Paul KrzyzanowskiToken Ring algorithm P0 P1 P2 P3 P4 P5 Your turn 11 11/7/2012 © 2012 Paul KrzyzanowskiToken Ring algorithm P0 P1 P2 P3 P4 P5 Your turn 12 11/7/2012 © 2012 Paul KrzyzanowskiToken Ring algorithm P0 P1 P2 P3 P4 P5 Your turn 13 11/7/2012 © 2012 Paul KrzyzanowskiToken Ring algorithm P0 P1 P2 P3 P4 P5 Your turn 14 11/7/2012 © 2012 Paul KrzyzanowskiToken Ring algorithm P0 P1 P2 P3 P4 P5 Your turn 15 11/7/2012 © 2012 Paul KrzyzanowskiToken Ring algorithm P0 P1 P2 P3 P4 P5 Your turn 16 11/7/2012 © 2012 Paul KrzyzanowskiToken Ring algorithm P0 P1 P2 P3 P4 P5 Your turn 17 11/7/2012 © 2012 Paul KrzyzanowskiToken Ring algorithm P0 P1 P2 P3 P4 P5 Your turn 18 11/7/2012 © 2012 Paul KrzyzanowskiToken Ring algorithm • Only one process at a time has token – Mutual exclusion guaranteed • Order well-defined – Starvation cannot occur • If token is lost (e.g., process died) – It will have to be regenerated • Does not guarantee FIFO order – sometimes this is undesirable 19 11/7/2012 © 2012 Paul KrzyzanowskiLamport’s Mutual Exclusion Each process maintains request queue – Contains mutual exclusion requests – Messages are sent reliably and in FIFO order – Messages are time stamped with Lamport timestamps – Queues are sorted by message timestamps 20 11/7/2012 © 2012 Paul KrzyzanowskiLamport’s Mutual Exclusion Request a critical section: – Process Pi sends request(i, Ti) to all nodes • … and places request on its own queue – When a process Pj receives a request: • It returns a timestamped ack • Places the request on its request queue Enter a critical section (accessing resource): – Pi has received acks from everyone – Pi’s request has the earliest timestamp in its queue Release a critical section: – Process Pi removes its request from its queue – sends release(i, Ti) to all nodes – Each process now checks if its request is the earliest in its queue • If so, that process now has the critical section Lamport time 21 11/7/2012 © 2012 Paul KrzyzanowskiLamport’s Mutual Exclusion • N points of failure • A lot of messaging traffic • Not great … but demonstrates that a fully distributed algorithm is possible 22 11/7/2012 © 2012 Paul KrzyzanowskiRicart & Agrawala algorithm • Distributed algorithm using reliable multicast and logical clocks • Process wants to enter critical section: 1. Compose message containing: • Identifier (machine ID, process ID) • Name of resource • Timestamp (e.g., totally-ordered Lamport) 2. Multicast request to all processes in group 3. Wait until everyone gives permission 4. Enter critical section / use resource 23 11/7/2012 © 2012 Paul KrzyzanowskiRicart & Agrawala algorithm • When process receives request: – If receiver not interested: • Send OK to sender – If receiver is in critical section • Do not reply; add request to queue – If receiver just sent a request as well: (potential race condition) • Compare timestamps on received & sent messages • Earliest wins • If receiver is loser, send OK • If receiver is winner, do not reply, queue it • When done with critical section – Send OK to all queued requests 24 11/7/2012 © 2012 Paul KrzyzanowskiRicart & Agrawala algorithm • N points of failure • A lot of messaging traffic • Demonstrates that a fully distributed algorithm is possible 25 11/7/2012 © 2012 Paul KrzyzanowskiLamport vs. Ricart & Agrawala • Lamport – Everyone responds (acks) … always - no hold-back – 3(N-1) messages • Request – ACK – Release – Process decides to go based on whether its request is the earliest in its queue • Ricart & Agrawala – If you are in the critical section (or won a tie) • Don’t respond with an ACK until you are done with the critical section – 2(N-1) messages • Request – ACK – Process decides to go if it gets ACKs from everyone 26 11/7/2012 © 2012 Paul KrzyzanowskiElection