Raymond's algorithm

Raymond's Algorithm is a lock 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

Nodal properties
  1. Each node has only one parent to whom received requests are forwarded
  2. Each node maintains a FIFO queue of requests each time that it sees the token;
  3. If any node is forwarding privilege to other node and has non-empty queue then it forwards a request message along

Algorithm
  1. If a node i (not holding the token) wishes to 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 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 k has token and receives the request from j it sends token to j and sets j as its parent
  3. 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.[1]

gollark: You can also get a ***!!FREE!!*** PotatOS OmniDisk\™ for debugging or random fiddling around or whatever.
gollark: https://pastebin.com/RM13UGFaAt the top of this code file.
gollark: From the official docs.
gollark: "Features:- Fortunes/Dwarf Fortress output/Chuck Norris jokes on boot (wait, IS this a feature?)- (other) viruses (how do you get them in the first place? running random files like this?) cannot do anything particularly awful to your computer - uninterceptable (except by crashing the keyboard shortcut daemon, I guess) keyboard shortcuts allow easy wiping of the non-potatOS data so you can get back to whatever nonsense you do fast- Skynet (rednet-ish stuff over websocket to my server) and Lolcrypt (encoding data as lols and punctuation) built in for easy access!- Convenient OS-y APIs - add keyboard shortcuts, spawn background processes & do "multithreading"-ish stuff.- Great features for other idio- OS designers, like passwords and fake loading (est potatOS.stupidity.loading [time], est potatOS.stupidity.password [password]).- Digits of Tau available via a convenient command ("tau")- Potatoplex and Loading built in ("potatoplex"/"loading") (potatoplex has many undocumented options)!- Stack traces (yes, I did steal them from MBS)- Backdoors- er, remote debugging access (it's secured, via ECC signing on disks and websocket-only access requiring a key for the other one)- All this useless random junk can autoupdate (this is probably a backdoor)!- EZCopy allows you to easily install potatOS on another device, just by sticking it in the disk drive of any potatOS device!- fs.load and fs.dump - probably helpful somehow.- Blocks bad programs (like the "Webicity" browser).- Fully-featured process manager.- Can run in "hidden mode" where it's at least not obvious at a glance that potatOS is installed.- Convenient, simple uninstall with the "uninstall" command.- Turns on any networked potatOS computers!- Edits connected signs to use as ad displays.- A recycle bin.- An exorcise command, which is like delete but better.- Support for a wide variety of Lorem Ipsum."
gollark: You would need to get rid of the autoupdate capabilities of potatOS itself, or swap them to your own pastebins/github stuff, and then keep everything in line with the current versions.

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

See also
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.