Samuel Ahn

Roopesh Boyapati

CECS 526

November 27, 2006

 

Simulation of Raymond’s Tree-Based Distributed Mutual Exclusion Algorithm

Objective

 

Experiments on will be performed on a simulation of Raymond’s tree-based mutual exclusion algorithm to determine the effect of network size and load (frequency of requests for the critical section) on the performance of the algorithm primarily in terms of the number of messages required per critical section, but also in terms of response time, synchronization delay, and throughput.

 

The Program

 

The simulation program will be written in C# for .NET 2.0. As inputs, it will take the size of the network, the frequency of requests for the critical section for each node, the duration of the message delay, and the duration of the critical sections. It will output the actions executed by the simulation including the sending and receiving of messages, the execution of the critical sections, the movement of the tokens, synchronization delays, and response times. The total number of messages will be compared against the number of number of critical sections executed to determine the number of messages passed per critical section.

 

The Tests and Analysis of the Results

 

Tests will be run on the simulation varying the network size and the network load. The results from each test (number of messages per critical section, synchronization delay, response time, and throughput) will be analyzed to determine the effect of network size and load on the performance of the algorithm and compared against the theoretical results. If T is the message delay, N is the network size, and E is the duration of the critical section, the theoretical results are T(log N)+E for the response time, T log(N)/2 for the synchronization delay, log(N) for the number of messages per critical section under low load, and 4 for the number of messages per critical section under high load.