Raymond’s Algorithm Assignment Help

Raymond’s Algorithm:

• Forms the directed tree (logical) using the token-holder as root
• Each node has variable “Holder” that points to its parent on the path to the root. Root’s Holder variable points to itself
• Each node i has a FIFO request queue Qi

To request critical section:

• Send REQUEST to parent on the tree, provided i does not hold the token presently as well as Qi is actually empty. After that place request in Qi

When the non-root node j receives a request from i

• place request in Qj
• send REQUEST to parent if no previous REQUEST sent

When the root receives the REQUEST:

• send the token towards the requesting node
• set Holder variable to point to indicate which node

When the node receives the token:

• delete first entry in the queue
• send token to that particular node
• set Holder variable in order to indicate which node
• if queue is non-empty, send a REQUEST message to the parent

To execute critical section:

• enter if token is received and also own entry is at the top of the queue, delete the entry from the queue
• To release critical section
• if queue is non-empty, delete first entry from the queue, send token to that node and make Holder variable point to that node
• If queue is still non-empty, send a REQUEST message to the parent