Chapter 9: Distributed Mutual Exclusion Algorithms

1 Chapter 9: Distributed Mutual Exclusion AlgorithmsAjay Kshemkalyani and Mukesh SinghalDistributed Computing: Principles, Algorithms , and SystemsCambridge University PressA. Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Mutual Exclusion AlgorithmsCUP 20081 / 93 Distributed Computing: Principles, Algorithms , and SystemsIntroductionMutual Exclusion : Concurrent access of processes to a shared resource ordata is executed in mutually exclusive one process is allowed to execute the critical section (CS) at any a Distributed system, shared variables (semaphores) or alocal kernelcannot be used to implement Mutual passing is the sole means for implementing Distributed Kshemkalyani and M.

2 Singhal ( Distributed Computing) Distributed Mutual Exclusion Algorithms2 / 93 Distributed Computing: Principles, Algorithms , and SystemsIntroductionDistributed Mutual Exclusion Algorithms must deal with unpredictablemessage delays and incomplete knowledge of the system basic approaches for Distributed Mutual Exclusion :1 Token based approach2 Non-token based approach3 Quorum based approachToken-based approach: A unique token is shared among the sites. A site is allowed to enter its CS if it possesses the token. Mutual Exclusion is ensured because the token is Kshemkalyani and M.

3 Singhal ( Distributed Computing) Distributed Mutual Exclusion Algorithms3 / 93 Distributed Computing: Principles, Algorithms , and SystemsIntroductionNon-token based approach: Two or more successive rounds of messages are exchanged among the sites todetermine which site will enter the CS based approach: Each site requests permission to execute the CS from a subset of sites (calleda quorum). Any two quorums contain a common site. This common site is responsible to make sure that only one request executesthe CS at any Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Mutual Exclusion Algorithms4 / 93 Distributed Computing: Principles, Algorithms , and SystemsPreliminariesSystem ModelThe system consists of N sites,S1,S2.

4 , assume that a single process is running on each site. The process at siteSiis denoted site can be in one of the following three states: requestingthe CS,executing the CS, or neither requesting nor executing the CS( , idle).In the requesting the CS state, the site is blocked and can not make furtherrequests for the CS. In the idle state, the site is executing outside the token-based Algorithms , a site can also be in a state wherea site holdingthe token is executing outside the CS (called theidle tokenstate).At any instant, a site may have several pending requests for CS.

5 A sitequeues up these requests and serves them one at a Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Mutual Exclusion Algorithms5 / 93 Distributed Computing: Principles, Algorithms , and SystemsRequirementsRequirements of Mutual Exclusion Algorithms1 Safety Property:At any instant, only one process can execute the Property:This property states the absence of deadlock andstarvation. Two or more sites should not endlessly wait for messages whichwill never :Each process gets a fair chance to execute the CS. Fairnessproperty generally means the CS execution requests are executed in the orderof their arrival (time is determined by a logical clock) in the Kshemkalyani and M.

6 Singhal ( Distributed Computing) Distributed Mutual Exclusion Algorithms6 / 93 Distributed Computing: Principles, Algorithms , and SystemsPerformance MetricsThe performance is generally measured by the following fourmetrics:Message complexity:The number of messages required per CS executionby a delay:After a site leaves the CS, it is the time requiredand before the next site enters the CS (see Figure 1).Last site exits the CSSynchronization delaytimeNext site enters the CSFigure 1: synchronization Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Mutual Exclusion Algorithms7 / 93 Distributed Computing: Principles, Algorithms , and SystemsPerformance MetricsResponse time:The time interval a request waits for its CS execution to beover after its request messages have been sent out (see Figure 2).

7 Messages sent out timeResponse TimeCS execution timeThe site exits the CSThe site entersthe CSCS Request arrivesIts requestFigure 2: Response throughput:The rate at which the system executes requests for throughput=1/(SD+E)whereSDis the synchronization delay andEis the average critical sectionexecution Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Mutual Exclusion Algorithms8 / 93 Distributed Computing: Principles, Algorithms , and SystemsPerformance MetricsLow and High Load Performance:We often study the performance of Mutual Exclusion Algorithms under twospecial loading conditions, viz.

8 , low load and high load .The load is determined by the arrival rate of CS execution loadconditions, there is seldom more than one request for thecritical section present in the system loadconditions, there is always a pending request for criticalsection at a Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Mutual Exclusion Algorithms9 / 93 Distributed Computing: Principles, Algorithms , and SystemsLamport s AlgorithmRequests for CS are executed in the increasing order of timestamps and timeis determined by logical siteSikeeps a queue,requestqueuei, which contains Mutual exclusionrequests ordered by their algorithm requires communication channels to delivermessages theFIFO Kshemkalyani and M.

9 Singhal ( Distributed Computing) Distributed Mutual Exclusion Algorithms10 / 93 Distributed Computing: Principles, Algorithms , and SystemsThe AlgorithmRequesting the critical section:When a siteSiwants to enter the CS, it broadcasts a REQUEST(tsi,i)message to all other sites and places the request onrequestqueuei. ((tsi,i)denotes the timestamp of the request.)When a siteSjreceives the REQUEST(tsi,i) message from siteSi,places siteSi s request onrequestqueuejand it returns a timestamped REPLY the critical section:SiteSienters the CS when the following twoconditions hold:L1:Sihas received a message with timestamp larger than (tsi,i) fromall other :Si s request is at the top Kshemkalyani and M.

10 Singhal ( Distributed Computing) Distributed Mutual Exclusion Algorithms11 / 93 Distributed Computing: Principles, Algorithms , and SystemsThe AlgorithmReleasing the critical section:SiteSi, upon exiting the CS, removes its request from the top of its requestqueue and broadcasts a timestamped RELEASE message to all other a siteSjreceives a RELEASE message from siteSi, it removesSi srequest from its request a site removes a request from its request queue, its own request may comeat the top of the queue, enabling it to enter the Kshemkalyani and M. Singhal ( Distributed Computing) Distributed Mutual Exclusion Algorithms12 / 93 Distributed Computing: Principles, Algorithms , and SystemscorrectnessTheorem: Lamport s algorithm achieves Mutual :Proof is by contradiction.