Token based Algorithms
Single token circulates, enter CS when token is present
Mutual exclusion obvious
Algorithms differ in how to find and get the token
Uses sequence numbers rather than timestamps to differentiate
between old and current requests
1
Suzuki Kasami Algorithm
Broadcast a request for the token
Process with the token sends it to the requestor if it does not need it
Issues:
– Current versus outdated requests
– Determining sites with pending requests
– Deciding which site to give the token to
2
Suzuki Kasami Algorithm – data structures
The token has two parts in it:
– Queue (FIFO) Q of requesting processes
– LN[1..n] : where LN[j] is sequence number of request that j
executed most recently
The request message by a process i:
– REQUEST(i, k): request message from node i for its kth
critical section execution
With each process
– RNi[1..n] for each node i, where RNi[ j ] is the largest
sequence number received so far by i in a REQUEST
message from j.
3
Suzuki Kasami Algorithm
To request critical section:
– If i does not have token, increment RNi[ i ] and send REQUEST(i,
RNi[ i ]) to all nodes
– If i has token already (means he got it to do a CS and now he is done
with one CS but may not have released the token and wants to do
the next CS), enter critical section if the token is idle (no pending
requests), else follow rule to release critical section
On receiving REQUEST(i, sn) at j:
– Set RNj[ i ] = max(RNj[ i ], sn)
– If j has the token and the token is idle, then send it to i if RNj[ i ] =
LN[ i ] + 1. If token is not idle, follow rule to release critical section
4
Suzuki Kasami Algorithm
To enter critical section:
– Enter CS if token is present
To release critical section:
– Set LN[ i ] = RNi[ i ]
– For every node j which is not in Q (in token), add node j to Q if
RNi[ j ] = LN[ j ] + 1 (these are requests that arrived while CS
was executing)
– If Q is non empty after the above, delete first node from Q and
send the token to that node
5
Data Structures Week 1
Questions
0 Does it work for FIFO channels and non FIFO channels ?
1. Pi has token. Pj has sent a request for the token. Can Pj enter
CS before Pj’s request reaches Pk?
2. Say Pj wants to get into CS again later. Can this request reach
Pk before the earlier one which has not reached ?
0 How do I know that an outdated request has reached me?
1. Why am I broadcasting my request to everyone ?
2. Starvation possible ?
Data Structures Week 1
Pi has token. When Pi done he gets request from Pj and gives Pj
the token. Pj’s request to Pk has not reached Pk yet but Pj gets
token and executes. Pj wants to get into CS again later and this
request might reach you before the earlier one which has not
reached....this is possible!
Every node should know my request so that whoever has token
can update my request on token. Thats the only way I can get a
chance.
How to know if an outdated request has reached me? In that
case Rni[j] <= LN[j]. So you just store whatever you get and
when you get the token you allow that request only if Rni[j]=Lni[j]
+1 since that is the next request after last time token was given
to j.
Data Structures Week 1
Show no starvation
- Process j who is interested broadcasts its request. If it reaches
Pk when token with Pk then token will update the request in its
queue. Else, eventually one of the processes that the token is
with will either already have got the token or will get the token.
So eventually Process j will make it to the tokens queue.
Notable features
No. of messages:
– 0 if node holds the token already, n otherwise
Synchronization delay:
– 0 (node has the token) or max. message delay (token is
elsewhere)
No starvation
9
Raymond’s Algorithm
Forms a directed tree (logical) with the token-holder as root which will
keep reorienting itself
Each node has variable “Holder” that points to its parent on the path
to the root.
– Root’s Holder variable points to itself
Each node i has a FIFO request queue Qi
10
Raymond’s Algorithm
To request critical section:
– place request in Qi
– If i does not hold the token currently and Qi is empty then
send REQUEST to parent on the tree.
When a non-root node j receives a request from i
– place request in Qj
– send REQUEST to parent if no previous REQUEST sent
11
Raymond’s Algorithm
When the root receives a REQUEST:
– send the token to the requesting node
– set Holder variable to point to that node
When a node receives the token:
– delete first entry from the queue
– send token to that node
– set Holder variable to point to that node
– if queue is non-empty, send a REQUEST message to the
parent (node pointed at by Holder variable) {because you want
it to come back to serve the pending request}
requests in the queue of a process are requests by whom ?
12
Raymond’s Algorithm
To execute critical section:
– enter if token is received and own entry is at the top of the
queue; delete the entry from the queue
To release critical section
– if queue is non-empty, delete first entry from the queue, send
token to that node and make Holder variable point to that node
– If queue is still non-empty, send a REQUEST message to the
parent (node pointed at by Holder variable) {because you want
it to come back to serve the pending request}
13
Raymond’s Algorithm
Note:
When the root receives a REQUEST:
– send the token to the requesting node
– set Holder variable to point to that node
When a node receives the token:
– delete first entry from the queue
– send token to that node
– set Holder variable to point to that node
– if queue is non-empty, send a REQUEST message to the parent
(node pointed at by Holder variable)
When a token is received, the last line of the subroutine ensures that a
request is passed along with the token if there are further requests
to be attended to. Hence, the root has to send the token back to this
node to attend to its pending requests
14
Data Structures Week 1
When a node receives the token:
– delete first entry from the queue
– send token to that node
– set Holder variable to point to that node
– if queue is non-empty, send a REQUEST message to the
parent (node pointed at by Holder variable) {because you
want it to come back to serve the pending request}
Notable features
Average message complexity: O(log n)
Sync. delay = (T log n)/2, where T = max. message delay
Starvation ?
16
