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

Resumo


Este trabalho faz uma comparação por simulação de dois algoritmos de exclusão mútua para sistemas distribuídos. Os algoritmos avaliados (Mackawa) e (Carvalho e Campos) utilizam um esquema de comunicação definido através de um plano projetivo finito a fim de minimizar o número de mensagens enviadas por pedido de exclusão mútua. A comparação aborda o número de mensagens gastas por cada pedido de exclusão mútua, o tempo de espera pelo recurso compartilhado, a carga sobre este e o tempo total de ciclo. Decorre deste trabalho que o algoritmo de Carvalho e Campos deveria ser usado em situações de carga alta sobre o recurso e sistemas não balanceados enquanto que o algoritmo de Maekawa é preferível nas situações de carga baixa e sistemas balanceados.

Referências

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.
Publicado
07/09/1993
COUTO, Kêmio de Oliveira; MENDES, Marco Aurélio de Souza; CARVALHO, Osvaldo S. F.. Uma Comparação Entre Dois Algoritmos de Exclusão Mútua para Redes de Computadores. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 5. , 1993, Florianópolis/SC. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 1993 . p. 358-367. DOI: https://doi.org/10.5753/sbac-pad.1993.23044.