Discuss Raymond Tree Based Algorithm of token based distributed mutual exclusion. (May 17 / Dec 16) (10 Marks)

Q. Discuss Raymond Tree Based Algorithm of token based distributed mutual exclusion. (May 17 / Dec 16) (10 Marks)

Ans -  Raymond’s tree based algorithm is lock based algorithm for mutual exclusion in a distributed system in which a site is allowed to enter the critical section if it has the token. In this algorithm, all sites are arranged as a directed tree such that the edges of the tree are assigned direction towards the site that holds the token. Site which holds the token is also called root of the tree.

Data structure and Notations

Every site Si keeps a FIFO queue, called request_q

This queue stores the requests of all neighboring sites that have sent a request for the token to site Si but have not yet been sent token. A non-empty request_q at any site indicates that the site has sent a REQUEST message to the root node.

Every site Si has a local variable, called holder 

This variable points to an immediate neighbor node on a directed path to the root node.

 

Algorithm

To enter Critical section:

1. When a site Si wants to enter the critical section it sends a REQUEST message to the node along the directed path to the root, provided it does not hold the token and its request_q is empty. After sending REQUEST message it add its request to its request_q.
2. When a site Sj on the path to the root receives the REQUEST message of site Si, it places the REQUEST in its request_q and sends the REQUEST message along the directed path to the root, if it has not sent any REQUEST message for previously received REQUEST message.
3. When the root site Sr( having token) receives the REQUEST message, it sends the token to the requesting site and sets its holder variable to point at that site.
4.  On receiving the token, Site Sj deletes the top entry from its request_q and sends the token to the site indicated by deleted entry. holder variable of Site Sj is set to point at that site.
5.  After deleting the topmost entry of the request_q, if it is still non-empty Site Sj sends a REQUEST message to the site indicated by holder variable in order to get token back.

To execute the critical section:

1. Site Si executes the critical section if it has received the token and its own entry is at the top of its request_q.

To release the critical section: 

After finishing the execution of the critical section, site Si does the following:

1.  If its request_q is non-empty, then it deletes the top most entry from its <request_q and then it sends the token to that site indicated by deleted entry and also its holder variable is set to point at that site.
2. After performing above action, if the request_q is still non-empty, then site Si sends a REQUEST message to the site pointed by holder variable in order to get token back