Uma Comparação Entre Dois Algoritmos de Exclusão Mútua para Redes de Computadores

• Kêmio de Oliveira Couto UFMG
• Marco Aurélio de Souza Mendes UFMG
• Osvaldo S. F. Carvalho UFMG

DOI: https://doi.org/10.5753/sbac-pad.1993.23044

Abstract

This work compares two mutual exclusion algorithms for distributed systems by simulation. The two evaluated algorithms (Mackawa) and (Carvalho and Campos) use a communication scheme defined by a finite projective plane in order to minimize the number of sent messages by exclusion mutual request. The comparison takes into account the number of messages by mutual exclusion request, the waiting time and the load over the shared resource and the total cycle time. We conclude that the algorithm of Carvalho and Campos should be used in situations of high load over the resource and not balanced systems while the algorithm of Maekawa should be used in low load and balanced system situations.

References

Lamport, L. Time, clocks, and ordering of events in a distributed system. Commun. ACM 21,7 (July 1978), 558-565.

Maekawa, Mamoru. A √N algorithm for mutual exclusion in decentralized systems. ACM trans. Comp. Syst. 3,2 ( May 1985), 145-159.

Carvalho, Oswaldo S. F. and Campos, Sérgio V. A. A 0..√n distributed mutual exclusion algorithm.

Dupuis, Alan and Hebuterne, Gérard and Pitie, Jean-Marc A Comparison of Two Mutual-Exclusion Algorithms for Computer Networks. Note Technique CNET/LAA/SLÇ 1985.

Albert, A.A., and Sandler, R. An introduction to finite projective planes. Holt, Rinehart, and Winston, New York, 1968.

Carvalho, O.S.F., and Roucairol, G. On mutual exclusion in computer networks. Commun. ACM 26,2 (Feb. 1983), 146-147.

Chandy, K.M., and Misra J. The drinking philosophers. ACM Trans. Program. Lang. Syst. 6,4 (Oct. 1984), 632-646.