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 concurr ...
on a
distributed system
Distributed computing is a field of computer science that studies distributed systems, defined as computer systems whose inter-communicating components are located on different networked computers.
The components of a distributed system commun ...
. It imposes a logical structure (a
K-ary tree
In graph theory, an ''m''-ary tree (for nonnegative integers ''m'') (also known as ''n''-ary, ''k''-ary, ''k''-way or generic tree) is an Arborescence (graph theory), arborescence (or, for some authors, an ordered tree) in which each node has no ...
) 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. Thus, the parts of the program where the shared resource is accessed need to be protected in ways that avoid the concurrent access. One ...
, 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 resource ...
*
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