El algoritmo de Raymond es un algoritmo basado en bloqueos para la exclusión mutua en un sistema distribuido . Impone una estructura lógica (un árbol K-ario ) a los recursos distribuidos. Tal como se define, cada nodo tiene un solo padre, al que se envían todas las solicitudes para obtener el token.
Algoritmo
Propiedades nodales
- Cada nodo tiene solo un padre al que se reenvían las solicitudes recibidas.
- Cada nodo mantiene una cola FIFO de solicitudes cada vez que ve el token;
- Si algún nodo está reenviando privilegios a otro nodo y tiene una cola no vacía, reenvía un mensaje de solicitud.
Algoritmo
- Si un nodo i (que no tiene el token) desea recibir el token para ingresar a su sección crítica , envía una solicitud a su padre, el nodo j .
- Si el nodo j FIFO está vacío, el nodo j desplaza a i a su cola FIFO; luego, j emite una solicitud a su padre, k , de que desea el token.
- Si la cola FIFO del nodo j no está vacía, simplemente desplaza i a la cola
- Cuando el nodo k tiene un token y recibe la solicitud de j, envía el token a j y establece a j como su padre.
- Cuando el nodo j recibe el token de k , lo reenvía a i y i se elimina de la cola de j.
- Si la cola de j no está vacía después de reenviar el token a i , j debe emitir una solicitud a i para recuperar el token.
Nota : Si j desea solicitar un token y su cola no está vacía, se coloca en su propia cola. El nodo j utilizará el token para ingresar a su sección crítica si está al principio de la cola cuando recibe el token.
Complejidad
Se garantiza que el algoritmo de Raymond sea O(log n) por entrada de sección crítica si los procesadores están organizados en un árbol K-ario . Además, cada procesador necesita almacenar como máximo O(log n) bits porque debe rastrear O(1) vecinos. [1]
Referencias
- ^ R. Chow, T. Johnson; Sistemas operativos distribuidos y algoritmos ; Addison-Wesley, 1997.
Véase también
