Rev. Fac. Ing. - Univ. Tarapacá, vol. 13 no. 1, 2005, pp. 89-98

UN NUEVO ALGORITMO DISTRIBUIDO DE EXCLUSIÓN MUTUA QUE MINIMIZA EL INTERCAMBIO DE MENSAJES

Jorge Pérez Rojas¹ Christian F. Orellana²

1 Departamento de Ingeniería de Sistemas, Universidad de Talca, Camino Los Niches Km. 1, Curicó, Chile. jperez@utalca.cl

2 Departamento de Ciencias de la Computación, Pontificia Universidad Católica de Chile, Vic. Mackenna 4860, Santiago, Chile. cforella@ing.puc.cl

---

RESUMEN

En este artículo presentamos un nuevo algoritmo de exclusión mutua distribuida basado en paso de token. Nuestro algoritmo utiliza dos estructuras dinámicas y distribuidas para proveer exclusión mutua: el Bosque de Naimi para dirigir las peticiones por el token y el Árbol Virtual de Raymond para servirlas. La estrategia utilizada combina las mejores características de dos algoritmos anteriores, citados en la literatura como los más eficientes en cuanto al tráfico de mensajes. Presentamos un estudio de desempeño mediante técnicas de simulación. Los resultados indican que nuestro algoritmo es el de mejor desempeño en cuanto al número de mensajes intercambiados por ingreso a sección crítica.

Palabras clave: Exclusión mutua distribuida, sincronización, algoritmos distribuidos.

ABSTRACT

In this paper we present a new token-based distributed mutual exclusion algorithm. The algorithm relies on two distributed dynamic structures in order to provide mutual exclusion: the "Naimi Forest" to route token requests, and the "Raymond Virtual Tree" to serve token requests. Our strategy combines the best characteristics of two algorithms cited as the most efficient in the literature concerning message traffic. We present a performance simulation study. Results show that our algorithm has better performance considering the number of message exchanged per critical section entry.

Keywords: Distributed mutual exclusion, distributed synchronization, distributed algorithms.

---

REFERENCIAS

[1] D. Agrawal and A. El Abbadi. "Efficient solution to the distributed mutual exclusion problem". In Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, pages 193 – 200, Edmonton, Alberta, Canada, August 1989. ACM Press.         [ Links ]

[2] S. Banerjee and P.K. Chrysanthis. "A New Token Passing Distributed Mutual Exclusion Algorithm". In Proc. of the 16th. International Conference on Distributed Computing Systems (ICDCS 96), pages 717-725. IEEE Computer Society, May 1996.         [ Links ]

[3] Ye-In Chang. "A Simulation Study on Distributed Mutual Exclusion". Journal of Parallel and Distributed Computing, 33(2):107-121, 15 March 1996.         [ Links ]

[4] Theodore Johnson. "A Performance Comparison of Fast Distributed Mutual Exclusion Algorithms". In Proceedings of the 9th International Symposium on Parallel Processing (IPPS’95), pages 258-264, Los Alamitos, CA, USA, April 1995. IEEE Computer Society Press.         [ Links ]

[5] Mamoru Maekawa. "A √¯N Algorithm for Mutual Exclusion in Decentralized Systems". ACM Transactions  on Computer Systems, 3(2):145-159, May 1985.         [ Links ]

[6] Mohamed Naimi, Michel Trehel and Andre Arnold. "A log(N) Distributed Mutual Exclusion Algorithm based on Path Reversal". Journal of Parallel and Distributed Computing, 34(1):1-13, April 1996.         [ Links ]

[7] M.L. Neilsen and M. Mizuno. "A DAG-Based Algorithm for Distributed Mutual Exclusion". In Proc. of the 11th. International Conference on Distributed Computing Systems (ICDCS 91), pages 354-360, Arlington, Texas, USA, May 1991. IEEE Computer Society.         [ Links ]

[8] Kerry Raymond. "A Tree-Based Algorithm for Distributed Mutual Exclusion". ACM Transactions on Computer Systems, 7(1):61-77, February 1989.         [ Links ]

[9] Michel Raynal. "A Simple Taxonomy for Distributed Mutual Exclusion Algorithms". ACM SIGOPS Operating Systems Review, 25(2):47-50, April 1991.         [ Links ]

[10] Glenn Ricart and Ashok K. Agrawala. "An Optimal Algorithm for Mutual Exclusion in Computer Networks". Communications of the ACM, 24(1): 9-17, January 1981.         [ Links ]

[11] Michel Trehel and Mohamed Naimi. "An Improvement of the log(n) Distributed Algorithm for Mutual Exclusion". In 7th International Conference on Distributed Computing Systems (ICDCS ’87), pages 371-377, Washington, D.C., USA, September 1987. IEEE Computer Society Press.         [ Links ]

[12] Min-You Wu and Wei Shu. "An Efficient Distributed Token-Based Mutual Exclusion Algorithm with Central Coordinator". Journal of Parallel and Distributed Computing, 62(10):1602-1613, October 2002.         [ Links ]

Recibido el 7 de enero de 2004, aceptado el 5 de noviembre de 2004