Unit :5 Distributed mutual exclusion Distributed Systems

Unit :5 Distributed mutual exclusion Distributed Systems

• 1.
  UNIT :5 DISTRIBUTED MUTUALEXCLUSION  Introduction,  Classification of Mutual Exclusion Algorithms,  Preliminaries,  A simple solution to Distributed Mutual Exclusion,  Non-Token-Based Algorithms,  Lamport’s Algorithm,  The Ricart-Agrawala Algorithm,  Token-Based Algorithms,  Suzuki-Kasami’s Broadcast Algorithms
• 2.
  INTRODUCTION:  Concurrent accessto shared resources by several unconditional user requests  This problem frequently arises in DS when concurrent access to shared resources by several sites is involved
• 3.
  THE CLASSIFICATION OFMUTUAL EXCLUSION ALGORITHMS  The algorithms are grouped into 2 classes:  1. non-token based  These algorithms require 2 or more successive rounds of message exchange among the sites.  Algo. are assertion based because a site can enter its critical section when assertion defined on its local variable becomes true.  2. token based  A unique token(PRIVILEDGE message) is shared among the sites  A site is allowed to enter its CS if it possesses the token and it continues to hold the token until the execution of the CS is over.
• 4.
  PRELIMINARIES  System model: A site can be in state: 1. Requesting CS 2. Executing CS 3. Neither requesting nor executing CS  In a token-based algorithm, a site can also be in a state where a site holding the token is outside the CS. Such a state is referred to a sidle token state.
• 5.
   Requirements ofmutual exclusion algorithm: 1. Freedom from deadlock- 2 or more sites should not endlessly wait for message that will never arrive. 2. Freedom from starvation: a site should not be forced to wait indefinitely to execute CS while other sites are repeatedly executing CS. 3. Fairness: request must be executed in the order they are made 4. Fault tolerance: if in the wake of a failure, it can recognize itself so that it continues to function without any (prolonged) disruption. PRELIMINARIES
• 6.
   How tomeasure the performance:  System throughput = 1/(sd+E)  Where sd: synchronization delay E: average critical section execution time. PRELIMINARIES
• 7.
  A SIMPLE SOLUTIONTO DISTRIBUTED MUTUAL EXCLUSION  A control site is assigned the task of granting permission for the CS execution.  To request the CS, a site sends a REQUEST message to the control site.  The control site queues up the requests for the CS and grants them permission, one by one.  This requires only 3 messages per CS execution.  If the synchronization delay is reduced to T, the system throughput is almost doubled to 1/(T+E).
• 8.
  NON-TOKEN-BASED ALGORITHMS  Inthis a site communicates with a set of other sites to arbitrate who should execute the CS next.  For a site Si, request set Ri contains ids for all those sites from which site Si must acquire permission before entering the CS.  These algorithm use timestamp to order requests for the CS and to resolve conflicts between simultaneous requests for the CS.
• 9.
  LAMPORT’S ALGORITHM  Lamportwas the first to give a distributed mutual algo. as an illustration  This algorithm requires messages to be delivered in the FIFO order between every pair of sites.  Algorithm:  Requesting the critical section 1. When a site Si wants to enter the CS, it sends REQUEST message to all sites in its request set Ri and places the request on request queue. 2. When a site rejects a REQUEST message from site Si, it returns a timestamp REPLY message to Si and places site Si’s request on request queue.
• 10.
   Executing thecritical section [L1]: Si has received a message with timestamp larger then (tsi,i) from all other sites [L2]: Si’s request is at the top of request queue. LAMPORT’S ALGORITHM
• 11.
   Releasing thecritical section 3. Site Si, upon exiting the CS, removes its request from the top of its request queue and sends a timestamp RELEASE message to all the sites in its request set. 4. When a site Sj, receives a RELEASE message from site Si, it removes Si’s request from its request queue. • This algorithm requires 3(N-1) messages per CS invocation. LAMPORT’S ALGORITHM
• 12.
  THE RICART-AGRAWALA ALGORITHM It is optimization of Lamport’s algorithm.  It dispenses with RELEASE message be cleverly merging them with REPLY messages.  The algorithm:  Requesting the critical section. 1. When a site Si wants to enter the CS, it sends REQUEST message to all sites in its request set Ri and places the request on request queue. 2. When a site rejects a REQUEST message from site Si, it returns a timestamp REPLY message to Si and places site Si’s request on request queue.
• 13.
   Executing thecritical section: 3. Site Si enters the CS after it has received REPLY messages from all the sites in its request set.  Releasing the critical section: 4. When site Si, exits the CS, it sends REPLY messages to all the deferred requests. THE RICART-AGRAWALA ALGORITHM
• 14.
  TOKEN-BASED ALGORITHMS  Aunique token is shared among all sites.  A site is allowed to enter its CS if it possesses the token.  Token based algorithms use sequence numbers instead of timestamps. Every request for the token contains a sequence number and sequence number of sites advance independently.  A correctness proof of token-based algorithm to ensure that mutual exclusion is enforced is trivial because an algorithm guarantees mutual exclusion
• 15.
  SUZUKI-KASAMI’S BROADCAST ALGORITHMS  Ifa site attempting to enter the CS does not have the token, it broadcasts a REQUEST message for the token to all other sites.  The algorithm:  Requesting the critical section:  1. if the requesting site Si does not have the token, then it increments its sequence number, RiNi[i] and sends a REQUEST (i,sn) message to all other sites.  2. when a site Sj receives this message, is sets RNj[i] to max(RNj[i],sn). If Sj has the idle token, then is sends the token to Si if RNj[i]=LN[i]+1