Raymond's algorithm

From Wikipedia, the free encyclopedia

Raymond's Algorithm is a token based algorithm for mutual exclusion on a distributed system. It imposes a logical structure (a K-ary tree) on distributed resources. As defined, each node has only a single parent, to which all requests to attain the token are made.

Contents

[edit] Algorithm

[edit] Nodal Properties

  1. Each node has only one parent to whom received requests are forwarded
  2. Each node maintains a FIFO queue of requests
  3. Makes only forwards only a single request for each time that it sees the token;

[edit] Algorithm

  1. If a node i wishes the receive the token in order to enter into its critical section, it sends a request to its parent, node j.
    • If node j FIFO is empty, node j shifts i into the its FIFO queue; j then issues a request to its parent, k, that it desires the token
    • If node j FIFO queue is not empty, it simply shifts i into the queue
  2. When node j receives the token from k, it forwards the token to i and i is removed from the queue of j
    • If the queue of j is not empty afterwarding the token to i, j must issue a request to i in order to get the token back

Note: If j wishes to request a token, and its queue is not empty, then it places itself into its own queue. Node j will utilize the token to enter into its critical section iff it is at the head of the queue when the token is received.

[edit] Complexity

Raymond's algorithm is guaranteed to be O(log n) per critical section entry if the processors are organized into a K-ary tree. Additionally, each processor needs to store at most O(log n) bits because it must track O(1) neighbors.[1]

[edit] References

  1. ^ R. Chow, T. Johnson; Distributed Operating Systems & Algorithms; Addison-Wesley, 1997.

[edit] See also