Suzuki–Kasami algorithm

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.

Algorithm description

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

Data structures

Each process maintains one data structure:

  • an array (for Request Number), being the ID of the process containing this array, where stores the last Request Number received by from

The token contains two data structures:

  • an array (for Last request Number), where stores the most recent Request Number of process for which the token was successfully granted
  • a queue , storing the ID of processes waiting for the token

Requesting the critical section (CS)

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

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

Releasing the CS

When process leaves the CS, it:

  • sets of the token equal to . This indicates that its request has been executed
  • for every process not in the token queue , it appends to if . This indicates that process has an outstanding request
  • if the token queue is not empty after this update, it pops a process ID from and sends the token to
  • otherwise, it keeps the token

Receiving a request

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

  • sets to (if , the message is outdated)
  • if process has the token and is not in CS, and if (indicating an outstanding request), it sends the token to process

Executing the CS

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

Performance

  • Either or messages for CS invocation (no messages if process holds the token; otherwise requests and reply)
  • Synchronization delay is or ( requests and reply)

Notes on the algorithm

  • Only the site currently holding the token can access the CS
  • All processes involved in the assignment of the CS
  • Request messages sent to all nodes
  • Used to keep track of outdated requests
  • They advance independently on each site

The main design issues of the algorithm:

  • Telling outdated requests from current ones
  • Determining which site is going to get the token next

References

  1. Ichiro Suzuki, Tadao Kasami, , ACM Transactions on Computer Systems, Volume 3 Issue 4, Nov. 1985 (pages 344 - 349)
  2. Ricart, Glenn, and Ashok K. Agrawala. "An optimal algorithm for mutual exclusion in computer networks." Communications of the ACM 24.1 (1981): 9-17.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.