Suzuki Kasami algorithm - Alchetron, the free social encyclopedia

The Suzuki-Kasami algorithm is a token-based algorithm for achieving mutual exclusion in distributed systems. The process holding the token is the only process able to enter its critical section.

This is a modification to Ricart–Agrawala algorithm in which a REQUEST and REPLY message are used for attaining the critical section. but in this algorithm they introduced a method in which a seniority vise and also by handing over the critical section to other node by sending a single PRIVILEGE message to other node. So, the node which has the privilege it can use the critical section and if it does not have one it cannot. If a process wants to enter its critical section and it does not have the token, it broadcasts a request message to all other processes in the system. The process that has the token, if it is not currently in a critical section, will then send the token to the requesting process. The algorithm makes use of increasing Request Numbers to allow messages to arrive out-of-order.

Algorithm description

Let n be the number of processes. Each process is identified by an integer in 1 , . . . , n .

Data structures

Each process maintains one data structure:

an array R N [ n ] (for Request Number), where R N i [ j ] stores the last Request Number received from j

The token contains two data structures:

an array L N [ n ] (for Last request Number), where L N [ j ] stores the most recent Request Number of process j for which the token was successfully granted

a queue Q, storing the ID of processes waiting for the token

Requesting the critical section (CS)

When process i wants to enter the CS, if it does not have the token, it:

increments its sequence number R N i [ i ]

sends a request message containing new sequence number to all processes in the system

Releasing the CS

When process i leaves the CS, it:

sets L N [ i ] of the token equal to R N i [ i ] . This indicates that its request R N i [ i ] has been executed

for every process k not in the token queue Q , it appends k to Q if R N i [ k ] = L N [ k ] + 1 . This indicates that process k has an outstanding request

if the token queue Q is nonempty after this update, it pops a process ID j from Q and sends the token to j

otherwise, it keeps the token

Receiving a request

When process i receives a request from j with sequence number s , it:

sets R N i [ j ] to m a x ( R N i [ j ] , s ) (if s < R N i [ j ] , the message is outdated)

if process i has the token and is not in CS, and if R N i [ j ] == L N [ j ] + 1 (indicating an outstanding request), it sends the token to process j

Executing the CS

A process enters the CS when it has acquired the token.

References

Suzuki-Kasami algorithm Wikipedia

(Text) CC BY-SA

Contents