Raymond's Algorithm is a lock based algorithm for
mutual exclusion
In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions. It is the requirement that one thread of execution never enters a critical section while a concurrent ...
on a
distributed system
A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another from any system. Distributed computing is a field of computer sci ...
. 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.
Algorithm
Nodal properties
# Each node has only one parent to whom received requests are forwarded
# Each node maintains a
FIFO queue of requests each time that it sees the token;
# If any node is forwarding privilege to other node and has non-empty queue then it forwards a request message along
Algorithm
# If a node ''i'' (not holding the token) wishes to receive the token in order to enter into its
critical section
In concurrent programming, concurrent accesses to shared resources can lead to unexpected or erroneous behavior, so parts of the program where the shared resource is accessed need to be protected in ways that avoid the concurrent access. One way ...
, it sends a request to its parent, node ''j''.
#* If node ''j'' FIFO is empty, node ''j'' shifts ''i'' into 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
# When node ''k'' has token and receives the request from ''j'' it sends token to ''j'' and sets ''j'' as its parent
# 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 after forwarding 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 if it is at the head of the queue when the token is received.
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.
[R. Chow, T. Johnson; ''Distributed Operating Systems & Algorithms''; Addison-Wesley, 1997.]
References
See also
*
Ricart-Agrawala algorithm
*
Lamport's bakery algorithm
Lamport's bakery algorithm is a computer algorithm devised by computer scientist Leslie Lamport, as part of his long study of the formal correctness of concurrent systems, which is intended to improve the safety in the usage of shared resou ...
*
Lamport's distributed mutual exclusion algorithm
*
Maekawa's algorithm Maekawa's algorithm is an algorithm for mutual exclusion on a distributed system. The basis of this algorithm is a quorum-like approach where any one site needs only to seek permissions from a subset of other sites.
Algorithm Terminology
* A ''si ...
*
Suzuki-Kasami's algorithm
*
Naimi-Trehel's algorithm
Concurrency control algorithms