ALGORITMO DE ANILLO

Algoritmo de anillo de token

Este algoritmo distribuido fue propuesto por Lann [1977] para alcanzar exclusión mutua en un sistema distribuido. En este algoritmo los procesos pueden estar desordenados y opera como sigue:

Premisas: Todos los equipos conectados forman un anillo lógico.  Cada proceso es un nodo del anillo y se le asigna una posición en el anillo.  Cada nodo del anillo debe de saber cuál es la dirección de su vecino.

Operación: Al arrancar el sistema, al proceso de posición 1 se le da un token, el cual irá circulando por el anillo.  Cuando el proceso k tenga el token, debe transferirlo mediante un mensaje al proceso k+1.  Así, el token irá pasando por todos los nodos del anillo.  Cuando un proceso recibe el token, si quiere entrar a la región crítica, retiene el token y entra en la región crítica.  Cuando el proceso sale de la región crítica le pasa el token al siguiente nodo del anillo.

Este algoritmo no respeta el orden y puede requerir de 1 mensaje (en el mejor de los casos) a n-1 mensajes (en el peor de los casos) para conseguir entrar a la región crítica. En caso de perderse un mensaje con el token sería difícil detectarlo, porque se puede suponer que algún proceso está usando el token. Si falla cualquier proceso del anillo estando en la región crítica también es un problema en este algoritmo, ya que es difícil de detectarlo.

Hay dos desventajas principales:

·         La primera, que el fallo de cualquiera de los nodos provocará el fallo del sistema completo, ya que romperá el anillo circular con el que se conectan todos los nodos.

·         La segunda, que no se consigue el acceso en el orden en el que los nodos se añaden al anillo, ya que dependerá del lugar donde se encuentre el testigo. Si el testigo se encuentra en el lado contrario del anillo al lugar donde se introduce un nuevo nodo puede ser que dicho nodo reciba el permiso para acceder a la sección crítica después que otro que se haya incluido posteriormente, si este último se introdujo entre el testigo y el primero.

Una solución a este segundo inconveniente, consiste en una implementación de un anillo "justo", en el que el testigo contiene el tiempo de la petición de acceso con una marca de tiempo menor. Cuando un nodo se une al anillo adjunta su marca de tiempo (timestamp) a su petición, de forma que cuando le llega el testigo comparará su marca con la que posee el anillo pudiéndose dar tres situaciones:

·         Si ambas marcas son iguales, es el nodo que lo posee el que tiene permiso para acceder a la sección crítica.

·         Si la marca del nodo es superior a la que posee el testigo, el nodo pasará el testigo y volverá a esperar por él.

·         Si la marca del testigo es superior o no existe, se establece que es igual a la marca del nodo y se pasa al siguiente nodo.

Para marcar que un nodo sale de la sección crítica, antes de pasar el testigo al siguiente, deberá borrar la marca de tiempo del testigo (ponerla a null) para poder repetir el algoritmo.

Algoritmo de anillo

Otros algoritmos de elección se basan en topologías de anillo, ya sea lógico o físico. Existen varios algoritmos de elección basados en anillo. Sin embargo, aquí se describe el algoritmo de anillo de Chang & Roberts [1974] basado en el principio de extinción selectiva. Este algoritmo se usa cuando:

 Los procesos están física o lógicamente ordenados en anillo. No se conoce el número total de procesos (n). Cada proceso se comunica con su vecino (izquierda o derecha).

Operación:

1. Inicialmente todos los procesos son “no participantes”.

 2. Cualquier proceso P decide arrancar una elección en cualquier momento.

 3. Este proceso P se pone en estado “participante” y envía un mensaje de elección M a su vecino. 4. El mensaje M enviado contiene el ID (identificador) del proceso que ha iniciado la elección.

5. Cuando el vecino recibe el mensaje de elección M, establece su estado como participante y comprueba el ID del mensaje.

 6. Si es mayor que su propio ID, entonces se lo envía directamente a su vecino.

 7. Si su ID es mayor al ID recibido, entonces lo coloca en el mensaje M y lo envía a su vecino.

 8. Así se circula el mensaje M sucesivamente hasta que llega a un proceso Pn que comprueba que el ID recibido es el propio. Eso indica que solo ha sobrevivido el mayor ID, que es la del proceso Pn.81S sincronización

9. Entonces, este proceso Pn es el coordinador y lo notifica a su vecino. Cuando un proceso recibe un mensaje de coordinador debe de poner su estado como “no participante” y enviar el mensaje a su vecino.

10. Cuando el mensaje de coordinador retorna al proceso que lo emitió (el coordinador), entonces todos los procesos saben quién es el coordinador y todos quedan en estado “no participantes”.

En caso de que dos procesos inicien al mismo tiempo una elección y se envíen mensajes de elección, un proceso en estado de “participante” debe de verificar el ID del proceso que envía el mensaje de elección. Si es menor al propio, el mensaje se descarta. Así, todos los mensajes de elección se extinguirán, excepto el que lleva el ID más alto.

JOEL.S.V