This article needs additional citations for
verification. (September 2014) |
The Suzuki–Kasami algorithm [1] 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 [2] in which a REQUEST and REPLY message are used for attaining the critical section, but in this algorithm, a method was introduced 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.
Let be the number of processes. Each process is identified by an integer in .
Each process maintains one data structure:
The token contains two data structures:
When process wants to enter the CS, if it does not have the token, it:
When process leaves the CS, it:
When process receives a request from with sequence number , it:
A process enters the CS when it has acquired the token.
The main design issues of the algorithm:
This article needs additional citations for
verification. (September 2014) |
The Suzuki–Kasami algorithm [1] 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 [2] in which a REQUEST and REPLY message are used for attaining the critical section, but in this algorithm, a method was introduced 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.
Let be the number of processes. Each process is identified by an integer in .
Each process maintains one data structure:
The token contains two data structures:
When process wants to enter the CS, if it does not have the token, it:
When process leaves the CS, it:
When process receives a request from with sequence number , it:
A process enters the CS when it has acquired the token.
The main design issues of the algorithm: