Ricart Agrawala Distributed Mutual Exclusion Algorithm
Lowkya Pothineni
Computer Science Department
Kent State University
Kent, Ohio
Email:
Abstract- Ricart Agrawala's Distributed Mutual Exclusion Algorithm is implemented to conduct experiments to study performance of Ricart Agrawala algorithm. The message complexity of Ricart Agrawala is 2*(n-1). Analysis of the algorithm is done using simulation under different number of processes (N). The simulation allows analysis of the data in message exchanges required to enter critical section per node and behavior of algorithm under different conditions.
I.INTRODUCTION
The Ricart- Agrawala Algorithm is an algorithm for mutual exclusion on a distributed system. It was developed by Glenn Ricart and Ashok Agrawala.Implementation of Distributed mutual exclusion(DMX) are of two types: Lockbased (or Non-Token based) and Token based. Lock based DMX algorithm uses locks. To enter Critical Section (CS) a process needs to obtain permission from other processes in the system. Whereas in token based DMX algorithm is done by using a unique token circulated in the system.The process possessing this unique token enters Critical Section. In Lamport's DMX Algorithm when a process wants to enter the Critical Section, it sends messages to all processes including itself and waits for reply whether it is allowed to enter critical section or not. Once the process is done accessing the Critical Section, it will notify all processes by releasing the request. The Lamport Algorithm uses the followingmessages:REQUEST, REPLY, andRELEASE per CS. Since three messages are required per critical section, the message complexity is 3*(N-1), where (N-1) for REQUEST, (N-1) for REPLY and (N-1) for RELEASE.
Ricart Agrawala algorithm is optimization of Lamport's Algorithm that overdoes RELEASE messages with REPLY messages. A process is only allowed to enter critical section when it receives all REPLY messages from all processes, a REPLY can be delayed to a node only when a node is done with its critical section. Hence number of messages required to enter critical section are reduced from 3*(N-1) to 2*(N-1) where (N-1) for REQUEST and (N-1) for REPLY.
This report is presented as follows: In section II, I presented the experimental parameters used. I described the program flow for realistic simulation engine. In section III, the result has been obtained.
Finally in section IV, I described the implementation areas of this algorithm and my future research interest in the same.
II. EXPERIMENTATION SETUP
The objective of this experiment was to implement Ricart Agrawala algorithm andto understand the purpose and behavior of the algorithm under different number of nodes (N). The program has been implemented to show how the Algorithm works and to collect statistical data by varying the experimental parameters.
A. Experiment Parameters and Expectation:
The parameters used in Ricart Agrawala simulation started by varying the number of nodes (N). The number of nodes used varies from 10 to 100. In each increment of 10 nodes, I then varied the size of the contending nodes, load size (L) with low load 1(node) and high load (all nodes). It is expected, that in Ricart Agrawala, the change in Load Size will not affect the number of messages being exchanged between nodes. In fact, I expect it to have a constant number of messages exchanged despite change in load. However change in number of nodes should reflect linear change in number of messages per critical section access.
B. Simulation Engine:
The simulator implemented is responsible to handle creation of nodes, selection of nodes by random to be run, and assigning channels to the nodes. Here I used 6 channels. I used a random number generator to generate a random process to run.
To ensure that the simulation executed as according to the specifications of the algorithm, receive request function should be implemented such that when process Pireceives a request from process Pj , it sends a REPLY message to process Pi, if process Pj is neither requesting nor executing the CS or if process Pjis requesting and then process Pj’s own request timestamp. This implementation is done using function Receivereq as following:
public void Receivereq(int p, int n)
{
System.out.println("Received request from node” + n);
boolean bDefer = false;
highPNum = Math.max(highPNum, p);
bDefer = pRequestcs & ((p > processNum) || (p== processNum & n > nod));
if(bDefer)
{
System.out.println("Deferred sending message to” + n);
if(n > nod)
DefReply[n - 2] = true;
else
DefReply[n - 1] = true;
}
else
{
System.out.println("Sent reply message to” + n);
replyTo(n);
}
}
The process trying to access the CS, sends requests to other generated processes using the function Reqto( ). The processes obtaining the request executes the method Receivereq( ). The processes receiving the request would either reply back using the method Replyto( ) and would defer the reply depending on the fulfilment of the condition. The requesting process after getting replies from all processes using the method receiveReply ( ) accesses or waits for access to the CS depending on the conditions fulfilled.
public void Reqto(int processNum, int nod, int j)
{
System.out.println("send request to node" + (((j))));
if(j > nod)
{
w[j-2].println("request," + processNum + "," + nod);
}
else
{
w[j-1].println("request,"+processNum + "," + nod);
}
}
public void Replyto(int n)
{
System.out.println("send reply to node " + n);
if(n > nod)
{
w[n-2].println("reply," + n);
}
else
{
w[n-1].println("reply," + n);
}
}
public void receiveReply(){
totalAwaitedReplies=Math.max((totalAwaitedReplies - 1), 0);
//System.out.println("remaining replies: " + totalAwaitedReplies);
}
III. RESULTS:
The results of the experiment for Ricart Agrawala Algorithm shows the implementation of the algorithm. The end result is still yet to be obtained However I am trying to obtain the relation between the number of processes and the messages trying to access the CS.
IV. CONCLUSION:
Depending on the results I obtain that the message complexity of Ricart Agrawala solely depends on the number of processes in the system. The Ricart Agrawala Algorithm is completely distributed and decentralized. However for each request O(N) messages is still required.
Ricart Agrawala can be extended to work on practical network applications. The correctness of the Ricart Agrawala Algorithm should not be affected when inserting new nodes into the network. In practical network insertion of new nodes. Whenever new nodes are added it should be able to update the sequence number, request received and the requests it is going to reply back or acknowledge.
Ricart Agrawala can be extended to solve Dining Philosopher's Problem where there are several sites and several number of processes working in each site.
REFERENCES:
[1] L. Lamport, “Time, clocks, and the ordering of events in a distributed system,” Commun. ACM, vol. 21, no. 7, pp. 558–565, 1978.
[2] G. Ricart and A. K. Agrawala, “An optimal algorithm for mutual exclusion in computer networks,” Commun. ACM, vol. 24, no. 1, pp.9–17, 1981.
[3]
[4] Referred most and obtained some information from “
[5] google.co.in