Distributed Systems: Mutual Exclusion

Distributed Systems
Mutual Exclusion*
*referred to slides by Prof. Paul Krzyzanowski at Rutgers University and

Prof. Mary Ellen Weisskopf at University of Alabama in Huntsville
Page 1
Mutual Exclusion?
A condition in which there is a set of
processes, only one of which is able to
access a given resource or perform a given
function at any time
Page 2
Centralized Systems
Mutual exclusion via:
Test & set

Semaphores
Messages
Monitors
Page 3
Distributed Mutual Exclusion

Assume there is agreement on how a resource
is identified
Pass identifier with requests
Create an algorithm to allow a process to

obtain exclusive access to a resource
Page 4
Distributed Mutual Exclusion
Centralized Algorithm
Token Ring Algorithm
Distributed Algorithm
Decentralized Algorithm
Page 5
Centralized algorithm
Mimic single processor system
One process elected as coordinator
1.
2.
3.
4.
5.
Request resource
Wait for response
Receive grant
access resource
Release resource
request(R)
grant(R)
P
release(R)
Page 6
If another process claimed resource:
Coordinator does not reply until release
Maintain queue
Service requests in FIFO order
Queue
P1
P2
request(R)
P0
request(R)
grant(R)
grant(R)
release(R)
P2
request(R)
P1
Page 7
Benefits
Fair
All requests processed in order
Easy to implement, understand, verify

Problems
Process cannot distinguish being blocked from
a dead coordinator
Centralized server can be a bottleneck
Page 8
Token Ring algorithm

Assume known group of processes
Some ordering can be imposed on group
Construct logical ring in software
Process communicates with neighbor
P0
P1
P5
P4
P2
P3
Page 9

Initialization
Process 0 gets token for resource R
Token circulates around ring

From Pi to P(i+1)mod N
When process acquires token

Checks to see if it needs to enter critical section
If no, send token to neighbor
P
P
P
If yes, access resource
0
Hold token until done
P4
P2
P3
token(R)
Page 10

Only one process at a time has token
Mutual exclusion guaranteed
Order well-defined
Starvation cannot occur
If token is lost (e.g. process died)

It will have to be regenerated
Does not guarantee FIFO order
Page 11
Ricart & Agrawala algorithm

Distributed algorithm using reliable multicast
and logical clocks
Process wants to enter critical section:
Compose message containing:
Identifier (machine ID, process ID)
Name of resource
Timestamp (totally-ordered Lamport)
Send request to all processes in group

Wait until everyone gives permission
Enter critical section / use resource
Page 12

When process receives request:
If receiver not interested:
Send OK to sender
If receiver is in critical section

Do not reply; add request to queue
If receiver just sent a request as well:
Compare timestamps: received & sent messages

Earliest wins
If receiver is loser, send OK
If receiver is winner, do not reply, queue
When done with critical section

Send OK to all queued requests
Page 13

N points of failure
A lot of messaging traffic
Demonstrates that a fully distributed
algorithm is possible
Page 14
Lamports Mutual Exclusion

Each process maintains request queue
Contains mutual exclusion requests
Requesting critical section:

Process Pi sends request(i, Ti) to all nodes
Places request on its own queue
Lamport time
When a process Pj receives
a request, it returns a timestamped ack
Page 15

Entering critical section
(accessing resource):
Pi received a message (ack or release) from every

other process with a timestamp larger than Ti
Pis request has the earliest timestamp in its queue
Difference from Ricart-Agrawala:

Everyone responds always - no hold-back
Process decides to go based on whether its
request is the earliest in its queue
Page 16

Releasing critical section:
Remove request from its own queue
Send a timestamped release message
When a process receives a release message
Removes request for that process from its queue
This may cause its own entry have the earliest timestamp in
the queue, enabling it to access the critical section
Page 17
Characteristics of Decentralized
Algorithms
No machine has complete information about the system state
Machines make decisions based only on local information
Failure of one machine does not ruin the algorithm
Three is no implicit assumption that a global clock exists
Decentralized Algorithm
Based on the Distributed Hash Table (DHT)
system structure previously introduced
Peer-to-peer
Object names are hashed to find the successor
node that will store them
Here, we assume that n replicas of each

object are stored
Page 19
Placing the Replicas

The resource is known by a unique name:
rname
Replicas: rname-0, rname-I, , rname-(n-1)

rname-i is stored at succ(rname-i), where names
and site names are hashed as before
If a process knows the name of the resource it
wishes to access, it also can generate the hash
keys that are used to locate all the replicas
Page 20
The Decentralized Algorithm

Every replica has a coordinator that controls
access to it (the coordinator is the node that
stores it)
For a process to use the resource it must
receive permission from m > n/2 coordinators
This guarantees exclusive access as long as a
coordinator only grants access to one process
at a time
Page 21
The Decentralized Algorithm

The coordinator notifies the requester when
it has been denied access as well as when it is
granted
Requester must count the votes, and decide
whether or not overall permission has been
granted or denied
If a process (requester) gets fewer than m

votes it will wait for a random time and then
ask again
Page 22
Analysis
If a resource is in high demand, multiple
requests will be generated
Its possible that processes will wait a long
time to get permission
Deadlock?
Resource usage drops
Page 23
Analysis
More robust than the central coordinator
approach and the distributed approaches. If
one coordinator goes down others are
available.
If a coordinator fails and resets then it will not

remember having granted access to one requestor,
and may then give access to another. According to
the authors, it is highly unlikely that this will lead
to a violation of mutual exclusion. (See the text
for a probabilistic argument.)
Page 24

Distributed Systems: Mutual Exclusion

Uploaded by

Copyright:

Available Formats

Distributed Systems: Mutual Exclusion

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Distributed Systems: Mutual Exclusion

Uploaded by

Copyright:

Available Formats

Distributed Systems

*referred to slides by Prof. Paul Krzyzanowski at Rutgers University and

Test & set

Distributed Mutual Exclusion

Create an algorithm to allow a process to

Distributed Mutual Exclusion

Easy to implement, understand, verify

Token Ring algorithm

Token Ring algorithm

Token circulates around ring

When process acquires token

Hold token until done

Token Ring algorithm

If token is lost (e.g. process died)

Does not guarantee FIFO order

Ricart & Agrawala algorithm

Send request to all processes in group

Ricart & Agrawala algorithm

If receiver is in critical section

If receiver just sent a request as well:

Compare timestamps: received & sent messages

When done with critical section

Ricart & Agrawala algorithm

Lamports Mutual Exclusion

Requesting critical section:

Lamports Mutual Exclusion

Pi received a message (ack or release) from every

Difference from Ricart-Agrawala:

Lamports Mutual Exclusion

No machine has complete information about the system state

Machines make decisions based only on local information

Failure of one machine does not ruin the algorithm

Three is no implicit assumption that a global clock exists

Here, we assume that n replicas of each

Placing the Replicas

Replicas: rname-0, rname-I, , rname-(n-1)

The Decentralized Algorithm

The Decentralized Algorithm

If a process (requester) gets fewer than m

If a coordinator fails and resets then it will not

You might also like