SKR 5302: Advanced Distributed Computing

6.2. Distributed Mutual Exclusion

Distributed Mutual Exclusion

• Mutual exclusion is required to prevent interference and ensure consistency when accessing the shared resources. 
• Distributed mutual exclusion – based solely on message passing. 
• In some cases, shared resources are managed by servers that also provide mechanisms for mutual exclusion. 
  • UNIX systems provide file-locking service, implemented by the daemon lockd, to handle locking requests from clients.
• When there is no server, and a collection of peer processes must coordinate their accesses to shared resources amongst themselves. 
• It is useful to have a generic mechanism for distributed mutual exclusion – one that is independent of the particular management scheme.
  • Mutual exclusion algorithms

Algorithms for mutual exclusion

• A system of N processes pi, i = 1, 2, …, N, that do not share variables.
• The processes access common resources, but they do so in a critical section.
• Assume there is only one critical section. 
• Assume that the system is asynchronous, that processes do not fail and that message delivery is reliable. 
• Application-level protocol for executing a critical section:
  • enter()  // enter critical section – block if necessary
  • resourceAccesses() // access shared resources in critical section
  • exit() // leave critical section – other processes may now enter
• Essential requirements for mutual exclusion:
  • ME1: (safety) – at most one process may execute in the critical section (CS) at a time.
  • ME2: (liveness) – request to enter and exit the critical section eventually succeed.
  • ME3: (-> ordering) – if one request enter the CS happened-before another, then entry to the CS is granted in that order. 
• Evaluation of the performance for mutual exclusion algorithms is according to the following criteria:
  • The bandwidth consumed, which is proportional to the number of messages sent in each entry and exit operation;
  • The client delay incurred by a process at each entry and exit operation;
  • The algorithm’s effect upon the throughput of the system.
    • Using synchronization delay between one process exiting the critical section and the next process entering it
    • The throughput is greater when the synchronization delay is shorter.
• Also assumes that the client processes are well behaved and spend a finite time accessing resources within their critical sections. 
  
  
• The central server algorithm
  • Employ a server that grants permission to enter the critical section. 
  • To enter a critical section, a process sends a request message to the server and awaits a reply from it. 
  • The reply constitutes a token signifying permission to enter the critical section. 
  • If no other process has the token at the time of the request, then the server replies immediately, granting the token.
  • If the token is currently held by another process, then the server does not reply, but queues the request. 
  • When a process exits the critical section, it sends a message to the server, giving it back the token. 
  • If the queue of waiting processes is not empty, then the server chooses the oldest entry in the queue, removes it and replies to the corresponding process.
    
    

    Figure 6.2: Server managing a mutual exclusion token for a set of processes

• Performance of this algorithm
  • Entering the critical section – even when no process currently occupies it – takes two messages (a request followed by a grant) and the delays the requesting process by the time required for this round-trip.
  • Exiting the critical section takes one release message. 
  • Assuming asynchronous message passing, the release message does not delay the exiting process. 
  • Server may become a performance bottleneck for the system as a whole. 
  • Synchronization delay -> time taken for a round-trip: a release message to the server, followed by a grant message to the next process to enter the critical section. 
• A ring-based algorithm
• Arrange mutual exclusion between the N processes without requiring an additional process.
• Arrange the processes in a logical ring.
• Requires only that each process pi has a communication channel to the next process in the ring, p(i+1)modN. 
• Exclusion is conferred by obtaining a token in the form of a message passed from process to process in a single direction around the ring. 
• If a process does not require to enter the critical section when it receives the token, then it immediately forwards the token to its neighbour. 
• A process that requires the token waits until it receives it, but retains it. 
• To exit the critical section, the process sends the token on to its neighbour. 
• This algorithm continuously consumes network bandwidth (except when a process is inside the critical section):
  • The processes send messages around the ring even when no process requires entry to the critical section.
• The delay experienced by a process requesting entry to the critical section is between 0 message (when it has just received the token) and N messages (when it has just passed on the token). 
• To exit the critical section, required only one message. 
• Synchronization delay between one process’s exit from the critical section and the next process’s entry is anywhere from 1 to N message transmissions
  
  

  Figure 6.3: A ring of processes transferring a mutual exclusion token
  
  
  

• An algorithm using multicast and logical clocks
• Implement mutual exclusion between N peer processes that is based upon multicast. 
• Processes that require entry to a critical section multicast a request message, and can enter it only when all the other processes have replied to this message. 
• The processes p1, p2, …, pN bear distinct numeric identifiers. 
• They are assumed to possess communication channels to one another. 
• Message requesting entry are of the form <T, pi>, where T is the sender’s timestamp and pi is the sender’s identifier. 
• Each process records its state of being outside the critical section (RELEASED), wanting entry (WANTED) or being in the critical section (HELD) in a variable state. 
  
  

  Figure 6.4: Ricart and Agrawala’s algorithm
  

• If a process requests entry and the state of all other processes is RELEASED, then all processes will reply immediately to the request and the requester will obtain entry. 
• If process is in the state HELD, that that process will not reply to requests until it has finished with the critical section, and so the requester cannot gain entry. 
• If two or more processes request entry at the same time, then whichever process’s request bears the lowest timestamp will be the first to collect N – 1 replies, granting it entry next. 
• Gaining entry takes 2(N – 1) messages in this algorithm:
• N – 1 to multicast the request, followed by N – 1 replies.
• It is a more expensive algorithm, in terms of bandwidth consumption.
• Synchronization delay is only one message transmission time.
   
  

  Figure 6.5: Multicast synchronization