Chapter9
93 pág.

Chapter9


DisciplinaAlgorítimos Distribuídos28 materiais273 seguidores
Pré-visualização9 páginas
and Systems
continuation..
Challenges
The design of adaptive mutual exclusion algorithms is challenging:
How does a site efficiently know what sites are currently actively invoking
mutual exclusion?
When a less frequently invoking site needs to invoke mutual exclusion, how
does it do it?
How does a less frequently invoking site makes a transition to more
frequently invoking site and vice-versa.
How to insure that mutual exclusion is guaranteed when a site does not take
the permission of every other site.
How to insure that a dynamic mutual exclusion algorithm does not waste
resources and time in collecting systems state, offsetting any gain.
A. Kshemkalyani and M. Singhal (Distributed Computing) Distributed Mutual Exclusion Algorithms 24 / 93
Distributed Computing: Principles, Algorithms, and Systems
System Model
We consider a distributed system consisting of n autonomous sites, say, S1,
S2, ..., Sn, connected by a communication network.
We assume that the sites communicate completely by message passing.
Message propagation delay is finite but unpredictable.
Between any pair of sites, messages are delivered in the order they are sent.
The underlying communication network is reliable and sites do not crash.
A. Kshemkalyani and M. Singhal (Distributed Computing) Distributed Mutual Exclusion Algorithms 25 / 93
Distributed Computing: Principles, Algorithms, and Systems
Data Structures
Information-structure at a site Si consists of two sets. The first set Ri , called
request set, contains the sites from which Si must acquire permission before
executing CS.
The second set Ii , called inform set,contains the sites to which Si must send
its permission to execute CS after executing its CS.
Every site Si maintains a logical clock Ci , which is updated according to
Lamport\u2019s rules.
Every site maintains three boolean variables to denote the state of the site:
Requesting, Executing, and My priority.
Requesting and executing are true if and only if the site is requesting or
executing CS, respectively. My priority is true if pending request of Si has
priority over the current incoming request.
A. Kshemkalyani and M. Singhal (Distributed Computing) Distributed Mutual Exclusion Algorithms 26 / 93
Distributed Computing: Principles, Algorithms, and Systems
Initialization
The system starts in the following initial state:
For a site Si (i = 1 to n),
Ri := {S1, S2,..., Si \u2212 1, Si}
Ii := {Si}
Ci := 0
Requestingi = Executingi := False
A. Kshemkalyani and M. Singhal (Distributed Computing) Distributed Mutual Exclusion Algorithms 27 / 93
Distributed Computing: Principles, Algorithms, and Systems
continuation..
If we stagger sites Sn to S1 from left to right, then the initial system state has the
following two properties:
For a site, only all the sites to its left will ask for its permission and it will ask
for the permission of only all the sites to its right.
The cardinality of Ri decreases in stepwise manner from left to right. Due to
this reason, this configuration has been called \u201dstaircase pattern\u201d in
topological sense .
A. Kshemkalyani and M. Singhal (Distributed Computing) Distributed Mutual Exclusion Algorithms 28 / 93
Distributed Computing: Principles, Algorithms, and Systems
The Algorithm
Step 1: (Request Critical Section)
Requesting = true;
Ci = Ci + 1;
Send REQUEST(Ci , i) message to all sites in Ri ;
Wait until Ri = \u2205;
/* Wait until all sites in Ri have sent a reply to Si */
Requesting = false;
Step 2: (Execute Critical Section)
Executing = true;
Execute CS;
Executing = false;
A. Kshemkalyani and M. Singhal (Distributed Computing) Distributed Mutual Exclusion Algorithms 29 / 93
Distributed Computing: Principles, Algorithms, and Systems
The Algorithm
Step 3: (Release Critical Section)
For every site Sk in Ii (except Si ) do
Begin
Ii= Ii \u2013 {Sk};
Send REPLY(Ci , i) message to Sk ;
Ri= Ri + {Sk}
End
A. Kshemkalyani and M. Singhal (Distributed Computing) Distributed Mutual Exclusion Algorithms 30 / 93
Distributed Computing: Principles, Algorithms, and Systems
The Algorithm
REQUEST message handler
/* Site Si is handling message REQUEST(c, j) */
Ci := max{Ci, c};
Case
Requesting = true:
Begin if My priority then Ii := Ii + {j}
/*My Priority true if pending request of Si has priority over incoming request */
Else
Begin
Send REPLY(Ci , i) message to Sj ;
If not (Sj \u2208 Ri ) then
Begin
Ri= Ri + {Sj};
Send REQUEST(Ci , i) message to site Sj ;
End;
End;
Executing = true: Ii = Ii + {Sj};
Executing = false \u2227 Requesting = false:
Begin
Ri= Ri + {Sj};
Send REPLY(Ci , i) message to Sj ;
End;
A. Kshemkalyani and M. Singhal (Distributed Computing) Distributed Mutual Exclusion Algorithms 31 / 93
Distributed Computing: Principles, Algorithms, and Systems
The Algorithm
REPLY message handler
/* Site Si is handling a message REPLY(c, j) */
Begin
Ci := max{Ci , c};
Ri = Ri \u2013 {Sj};
End;
Note that REQUEST and REPLY message handlers and the steps of the
algorithm access shared data structures, viz., Ci , Ri , and Ii .
To guarantee the correctness, it\u2019s important that execution of REQUEST and
REPLY message handlers and all three steps of the algorithm (except \u201dwait
for Ri = \u2205 to hold\u201d in Step 1) mutually exclude each other.
A. Kshemkalyani and M. Singhal (Distributed Computing) Distributed Mutual Exclusion Algorithms 32 / 93
Distributed Computing: Principles, Algorithms, and Systems
An Explanation of the Algorithm
Si acquires permission to execute the CS from all sites in its request set Ri
and it releases the CS by sending a REPLY message to all sites in its inform
set Ii .
If site Si which itself is requesting the CS, receives a higher priority
REQUEST message from a site Sj , then Si takes the following actions:
1 (i) Si immediately sends a REPLY message to Sj ,
2 (ii) if Sj is not in Ri , then Si also sends a REQUEST message to Sj , and
3 (iii) Si places an entry for Sj in Ri . Otherwise, Si places an entry for Sj into Ii
so that Sj can be sent a REPLY message when Si finishes with the execution
of the CS.
If Si receives a REQUEST message from Sj when it is executing the CS, then
it simply puts Sj in Ii so that Sj can be sent a REPLY message when Si
finishes with the execution of the CS.
If Si receives a REQUEST message from Sj when it is neither requesting nor
executing the CS, then it places an entry for Sj in Ri and sends Sj a REPLY
message.
A. Kshemkalyani and M. Singhal (Distributed Computing) Distributed Mutual Exclusion Algorithms 33 / 93
Distributed Computing: Principles, Algorithms, and Systems
Correctness
Achieving Mutual Exclusion:
The initial state of the information-structure satisfies the following condition:
for every Si and Sj , either Sj \u2208 Ri or Si \u2208 Rj .
Therefore, if two sites request CS, one of them will always ask for the
permission of the another.
However, whenever there is a conflict between two sites, the sites dynamically
adjust their request sets such that both request permission of each other
satisfying the condition for mutual exclusion.
Freedom from Deadlocks:
The algorithm is free from deadlocks because sites use timestamp ordering
(which is unique system wide) to decide request priority and a request is
blocked by only higher priority requests.
A. Kshemkalyani and M. Singhal (Distributed Computing) Distributed Mutual Exclusion Algorithms 34 / 93
Distributed Computing: Principles, Algorithms, and Systems
Performance Analysis
-The synchronization delay in the algorithm is T.
The message complexity:
Low load condition:
Most of the time only one or no request for the CS will be present in the
system.
The staircase pattern will reestablish between two successive requests for CS.
Sites will send 0, 1, 2, ..., (n-1) number of REQUEST messages