Distributed Mutual Exclusion

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: <T, pi >

^–         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]