Raymond's algorithm: Difference between revisions
Content deleted Content added
←Created page with ''''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 dis...' |
No edit summary |
||
| Line 1: | Line 1: | ||
'''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. |
'''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. |
||
<!-- |
|||
== Algorithm == |
== Algorithm == |
||
===Nodes Properties=== |
===Nodes Properties=== |
||
# Each node has only one parent |
# Each node has only one parent to whom received requests are forwarded |
||
# Each node maintains a [[FIFO]] queue of requests |
# Each node maintains a [[FIFO]] queue of requests |
||
# Makes only forwards only a single request for each time that it sees the token |
# Makes only forwards only a single request for each time that it sees the token; |
||
===Algorithm=== |
===Algorithm=== |
||
| Line 14: | Line 13: | ||
# 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 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 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 |
#* If node ''j'' FIFO queue is ''not'' empty, it simply shifts ''i'' into the queue |
||
# When node ''j'' receives the token from ''k'', it forwards the token to ''i'' and ''i'' is removed from the queue of ''j'' |
|||
# ... need to finish |
|||
#* 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. |
|||
== 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.<ref>R. Chow, T. Johnson; ''Distributed Operating Systems & Algorithms; Addison-Wesley, 1997.</ref> |
|||
== References == |
|||
<references /> |
|||
== See also == |
== See also == |
||
Revision as of 23:34, 21 November 2007
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.
Algorithm
Nodes Properties
- Each node has only one parent to whom received requests are forwarded
- Each node maintains a FIFO queue of requests
- Makes only forwards only a single request for each time that it sees the token;
Algorithm
- 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
- 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.
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]
References
- ^ R. Chow, T. Johnson; Distributed Operating Systems & Algorithms; Addison-Wesley, 1997.