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
– 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]
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.