Distributed Mutual Exclusion

Process coordination in a multitasking OS

 –       Race condition: several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access take place

 –       critical section: when one process is executing in a critical section, no other process is to be allowed to execute in its critical section

 –       Mutual exclusion: If a process is executing in its critical section, then no other processes can be executing in their critical sections

         –       Distributed mutual exclusion

        –       Provide critical region in a distributed environment

       –       message passing

      –       for example, locking files, locked daemon in UNIX (NFS is stateless, no file-locking at

    –       the NFS level) Algorithms for mutual exclusion

       –       Problem: an asynchronous system of N processes

 –       processes don't fail

 –       message delivery is reliable; not share variables

 –       only one critical region

 –       application-level protocol: enter(), resourceAccesses(), exit()

 –       Requirements for mutual exclusion

 –       Essential

 –       [ME1] safety: only one process at a time

 –       [ME2] liveness: eventually enter or exit

 –       Additional

 –       [ME3] happened-before ordering: ordering of enter() is the same as HB ordering

 –       Performance evaluation

 –       overhead and bandwidth consumption: # of messages sent

 –       client delay incurred by a process at entry and exit

 –       throughput measured by synchronization delay: delay between one's exit and next's entry

 –       A central server algorithm

 –       server keeps track of a token---permission to enter critical region

 –       a process requests the server for the token

 –       the server grants the token if it has the token

 –       a process can enter if it gets the token, otherwise waits

 –       when done, a process sends release and exits

 

 –       A central server algorithm: discussion

–         Properties

 –         safety, why?

 –         liveness, why?

 –         HB ordering not guaranteed, why?

 –         Performance

 –         enter overhead: two messages (request and grant)

 –         enter delay: time between request and grant

 –         exit overhead: one message (release)

 –         exit delay: none

 –         synchronization delay: between release and grant

 –         centralized server is the bottleneck

 –       ring-based algorithm

o     Arrange processes in a logical ring to rotate a token

 

o     Wait for the token if it requires to enter the critical section

 

o     The ring could be unrelated to the physical configuration

 

o     pi sends messages to p(i+1) mod N

 

o     when a process requires to enter the critical section, waits for the token

 

o     when a process holds the token

 

o     If it requires to enter the critical section, it can enter

 

o     when a process releases a token (exit), it sends to its neighbor

 

o     If it doesn‘t, just immediately forwards the token to its neighbor

 

 

–       An algorithm using multicast and logical clocks

–         Multicast a request message for the token (Ricart and Agrawala [1981]

–         enter only if all the other processes reply 

–         totally-ordered timestamps: <Tpi > 

–         Each process keeps a state: RELEASED, HELD, WANTED 

–         if all have state = RELEASED, all reply, a process can hold the token and enter 

–         if a process has state = HELD, doesn't reply until it exits 

–         if more than one process has state = WANTED, process with the lowest timestamp will get all 

–         N-1 replies first

 

–       An algorithm using multicast: discussion

–    Properties 

–    safety, why? 

–    liveness, why? 

–    HB ordering, why? 

–    Performance 

–    bandwidth consumption: no token keeps circulating 

–    entry overhead: 2(N-1), why? [with multicast support: 1 + (N -1) = N] 

–    entry delay: delay between request and getting all replies 

–    exit overhead: 0 to N-1 messages 

–    exit delay: none

 o   synchronization delay: delay for 1 message (one last reply from the previous holder) 

–       Maekawa‘s voting algorithm

–    •Observation: not all peers to grant it access 

–    Only obtain permission from subsets, overlapped by any two processes 

–    •Maekawa‘s approach 

–    subsets Vi,Vj for process Pi, Pj 

–    Pi ∈ Vi, Pj ∈ Vj 

–    Vi ∩ Vj ≠ ∅ , there is at least one common member 

–    subset |Vi|=K, to be fair, each process should have the same size 

–    Pi cannot enter the critical section until it has received all K reply messages 

–    Choose a subset 

–    Simple way (2√N): place processes in a √N by √N matrix and let Vi be the union of the row and column containing Pi 

–    If P1, P2 and P3 concurrently request entry to the critical section, then its possible that each process has received one (itself) out of two replies, and none can proceed

–    adapted and solved by [Saunders 1987]