Empirical Evaluation of Mutual Exclusion Algorithms for Distributed Systems

Abstract

Mutual exclusion in distributed memory systems is realized by passing messages among sites to establish a sequence for the waiting sites to enter the critical section. We have evaluated various distributed mutual exclusion algorithms on the IBM SP2 machine and the Intel iPSC/860 system, with their empirical results compared in terms of such criteria as the number of message exchanges and response time. The results take into account the effects of critical section request rate, critical section duration, and system size. Our results indicate that the Star algorithm (1991, M. L. Neilsen and M. Mizuno, in "Proc. 11th Int. Conf. Distributed Computing Systems," pp. 354-360) achieves the shortest response time in most cases among all the algorithms on a small to medium-sized system, when sites request the critical section many times before involving any barrier synchronization. This is because (1) it requires the exchange of no more than three messages per critical section entry, and (2) contention can quickly be alleviated after several entries into the critical section, if no barrier synchronization is involved in the meantime. On the other hand, if every site enters the critical section only once before encountering a barrier, the improved Ring algorithm (1995, S. S. Fu and N.-F. Tzeng, "Efficient Token-Based Approach to Mutual Exclusion in Distributed Memory Systems," Tech. Rep. TR-95-8-1, CACS, Univ. Southwestern Louisiana, Lafayette) is found to outperform others under a heavy load; but the Star algorithm and the CSL algorithm (1990, Y. I. Chang, M. Singhal, and M. T. Liu, in "Proc. 1990 Int. Conf. Parallel Processing," Vol. III, pp. 295-302) prevail when the request rate becomes light. The best solution to mutual exclusion in distributed memory systems is determined by how participating sites generate their mutual exclusion requests. © 2000 Academic Press.