Um Algoritmo Eficiente para Exclusão Mútua Distribuída
Resumo
Este trabalho apresenta um novo algoritmo para exclusão mútua distribuída. O algoritmo aqui proposto é baseado nas idéias de grafos acíclicos de Chandy and Misra, do token com muitas informações de Suzuki-Kazami e na idéia do holder de Rymond. O número de mensagens trocadas por seção crítica é O(log N) em carga baixa, onde N é o número de nodos da rede. Na situação de saturação, entretanto, somente duas mensagens são necessárias por invocação de seção crítica. É também proposto aqui um modelo de simulação para algoritmos distribuídos de exclusão mútua. Baseado nele, uma comparação é realizada entre vários algoritmos propostos na literatura e o nosso.
Referências
Lamport, L. Time, clocks, and ordering of events in a distributed system. Commun. ACM 21,7 (July, 1978), 558-565.
Raymond, K. A Tree-Based Algorithm for Distributed Mutual Exclusion. Commun. ACM 1,7 (February, 1989), 61-77.
Suzuki, I., and Kasami, T. A distributed mutual exclusion algorithm ACM Trans. Comput. Syst. 3,4 (November, 1985), 344-349.
Chandy, K.M., and Misra J. The drinking philosophers. ACM Trans. Program. Lang. Syst. 6,4 (October, 1984), 632-646.
Dijkstra, E.W. Co-operating sequential processes. in Programming Languages, Genuys, F. (ed.), Academic Press, London, 1965
Dijkstra, E. W. Guarded commands, nondeterminacy and formal derivation of programa. Commun. ACM 18,8 (August, 1975), 453-457.
Ricart, G., and Agrawala, A.K. An Optimal algorithm for mutual exclusion in computer networks. Commun. ACM 24,1 (January, 1981), 9-17.
Carvalho, O.S.F., and Roucairol, G. On mutual exclusion in computer networks. Commun. ACM 26,2 (February, 1983), 146-147.
Carvalho, Osvaldo S.F. and Campos, Sérgio V.A. A O.. √2 distributed mutual exclusion algorithm. Personal Notes.
Maekawa, Mamoru. A √N algorithm for mutual exclusion in decentralized systems. ACM trans. Comp. Syst. 3,2 (May, 1985), 145-159.
Bernabéu-Aubán, J. M., and Ahamad, M. Applying a path compression technique to obtain an efficient distributed mutual exclusion algorithm. In Proceedings of Third International Worksbop on Distributed Algorithms (September, 1989), 33-44
Dupuis, Alan and Hebuterne, Grard and Pitie, Jean-Marc. A Comparison of Two Mutual Exclusion Algorithms for Computer Noteworks. Note Technique CNET/LAA/SLÇ 1985.
Couto, K.O., Mendes, M.A.S., e Carvalho, O.S.F. Uma Comparação Entre Dois Algoritmos de Exclusão Mútua para Redes de Computadores. ANAIS of V SBAC-PAD, Vol I, 358-367.
Couto, K.O., Mendes, M.A.S., e Carvalho, O.S.F. Ambiente de Desenvolvimento e Análise de Algoritmos de Exclusão Mútua para Sistemas Distribuídos. ANAIS of VI SBAC-PAD, 123-135.
Raymond, K. A Tree-Based Algorithm for Distributed Mutual Exclusion. Commun. ACM 1,7 (February, 1989), 61-77.
Suzuki, I., and Kasami, T. A distributed mutual exclusion algorithm ACM Trans. Comput. Syst. 3,4 (November, 1985), 344-349.
Chandy, K.M., and Misra J. The drinking philosophers. ACM Trans. Program. Lang. Syst. 6,4 (October, 1984), 632-646.
Dijkstra, E.W. Co-operating sequential processes. in Programming Languages, Genuys, F. (ed.), Academic Press, London, 1965
Dijkstra, E. W. Guarded commands, nondeterminacy and formal derivation of programa. Commun. ACM 18,8 (August, 1975), 453-457.
Ricart, G., and Agrawala, A.K. An Optimal algorithm for mutual exclusion in computer networks. Commun. ACM 24,1 (January, 1981), 9-17.
Carvalho, O.S.F., and Roucairol, G. On mutual exclusion in computer networks. Commun. ACM 26,2 (February, 1983), 146-147.
Carvalho, Osvaldo S.F. and Campos, Sérgio V.A. A O.. √2 distributed mutual exclusion algorithm. Personal Notes.
Maekawa, Mamoru. A √N algorithm for mutual exclusion in decentralized systems. ACM trans. Comp. Syst. 3,2 (May, 1985), 145-159.
Bernabéu-Aubán, J. M., and Ahamad, M. Applying a path compression technique to obtain an efficient distributed mutual exclusion algorithm. In Proceedings of Third International Worksbop on Distributed Algorithms (September, 1989), 33-44
Dupuis, Alan and Hebuterne, Grard and Pitie, Jean-Marc. A Comparison of Two Mutual Exclusion Algorithms for Computer Noteworks. Note Technique CNET/LAA/SLÇ 1985.
Couto, K.O., Mendes, M.A.S., e Carvalho, O.S.F. Uma Comparação Entre Dois Algoritmos de Exclusão Mútua para Redes de Computadores. ANAIS of V SBAC-PAD, Vol I, 358-367.
Couto, K.O., Mendes, M.A.S., e Carvalho, O.S.F. Ambiente de Desenvolvimento e Análise de Algoritmos de Exclusão Mútua para Sistemas Distribuídos. ANAIS of VI SBAC-PAD, 123-135.
Publicado
29/07/1995
Como Citar
TEIXEIRA, Guilherme Pádua; COUTO, Kêmio de Oliveira; MENDES, Marco Aurélio de Souza; CARVALHO, Osvaldo S. F..
Um Algoritmo Eficiente para Exclusão Mútua Distribuída. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 7. , 1995, Canela.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1995
.
p. 243-255.
DOI: https://doi.org/10.5753/sbac-pad.1995.19866.
