Exclusión mutua en sistemas distribuidos

Se denomina exclusión mutua al acceso concurrente de varios procesos a un dato o recurso compartido. En un determinado instante, únicamente uno de estos procesos será capaz de ejecutar la sección crítica del código, que es la sección donde se accede al recurso compartido o se modifica el mismo. Esta exclusión mutua puede ser resuelta utilizando una cola compartida que modere el acceso, un semáforo compartido, o una variable compartida que indique que proceso puede acceder.

La exclusión mutua distribuida se produce cuando los procesos y el recurso no se encuentran en el mismo equipo, por lo que en este caso, para coordinar el acceso al recurso las variables compartidas mencionadas anteriormente no pueden ser utilizadas. Es por esto que el único medio para controlar la sección crítica es la comunicación mediante el paso de mensajes.

Hay distintos grupos de algoritmos que se pueden utilizar para resolver esta exclusión mutua distribuida, y según su funcionamiento podrían clasificarse en tres categorías:

Basados en tokens: un elemento único es compartido por todos los nodos, permitiendo el acceso a la sección crítica únicamente al nodo que lo posee.
No basados en tokens: el nodo con acceso a la sección crítica se establece mediante el intercambio de mensajes en dos o más rondas.
Basados en quorum: para que un nodo pueda acceder a la sección crítica tiene que tener permiso de todos los nodos de su subconjunto.

Algoritmo centralizado[editar]

Este algoritmo pertenece a los no basados en tokens y es quizá el más fácil de implementar para crear la exclusión mutua distribuida. En esta solución, cuando uno de los procesos quiera acceder a la sección crítica, deberá enviar un mensaje de tipo REQUEST a un servidor central que será el encargado de recibir todas las peticiones de acceso y de ir concediendo los permisos a las distintas peticiones. Cuando el proceso reciba el mensaje de permiso, podrá acceder a la sección crítica y cuando acabe, deberá enviar un nuevo mensaje al servidor central para avisar de que ha finalizado y ya se encuentra disponible la sección crítica para otro proceso (mensaje de tipo RELEASE).

Ventajas de este algoritmo:

Facilidad de implementación.
La poca cantidad de mensajes que es necesario generar por cada acceso (solamente 3).

En cuanto a las desventajas:

Un fallo en el servidor central provocaría la caída del sistema completo.
Se pueden producir los llamados cuellos de botella, debidos a numerosas peticiones por distintos nodos que pueden provocar que el servidor central no sea capaz de procesar todas ellas y colapse.

Los problemas de este algoritmo se presentan cuando el coordinador falla o cuando falla el poseedor del token. Un solo coordinador en un gran sistema puede ocasionar un cuello de botella.

Existen muchas situaciones de la vida cotidiana en las cuales podemos extrapolar la función del Algoritmo de servidor centralizado y una de ellas es tan común cómo plantear una situación en la escuela primaria o secundaria en la cual podía haber un pase de salida para ir al sanitario, y este pase era concedido por un coordinador que era el profesor o prefecto que en el caso del algoritmo sería el proceso coordinador y cada uno de los alumnos un proceso el cual requiere el token para poder tener salida, si se perdía el token o pase o otro alumno en este caso proceso lo tenía el proceso coordinador tiene que enviar un permiso denegado.

Algoritmo en anillo (Token Ring)[editar]

Los requisitos de un algoritmo en anillo son:

[E1] (seguridad): Un proceso participante tiene un elegido donde este es el proceso con el identificador mayor que no se ha caído al final de ejecución.
[E2] (supervivencia): Todos los procesos participan y al final fijan el elegido o bien se han caído.

En este algoritmo la entrada a la sección crítica se basa en la posesión o no de un testigo (token), que se van pasando todos los nodos en forma circular. Cuando un nodo consigue el testigo, puede entrar a la sección crítica debiendo liberarlo y pasarlo cuando sale de ella hacia el siguiente nodo.

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 cola de prioridad compartida[editar]

Otro algoritmo que ayuda a crear la exclusión mutua es el de la cola de prioridad compartida. En este algoritmo, basado en los tiempos lógicos de Lamport, un nodo i cualquiera mantendrá de forma local una copia de parte de la cola de prioridad compartida para poder saber si tiene acceso a la sección crítica o no.

Cuando el nodo desee acceder a dicha sección crítica, deberá crear una petición (mensaje REQUEST) con una marca temporal y avisar a todos los demás nodos multidifundiendo un mensaje de petición, al que todos ellos responderán (mensaje REPLY). Para poder ejecutar su sección crítica deben darse dos situaciones: que la petición del nodo i sea la primera de su cola y que dicho nodo reciba respuesta del resto de nodos. Dados estos dos requisitos, i podrá acceder a la sección crítica. Al finalizar, deberá eliminar su petición de su cola y avisar a todos los demás nodos que ha finalizado (mensaje RELEASE), que a su vez también eliminarán la petición correspondiente.

Si el nodo i recibe una petición de otro nodo, la añadirá a su cola local. Si esta solicitud procede de un nodo por el que está esperando respuesta de una petición propia anterior esperará hasta obtener dicha respuesta. En cualquier otro caso, responderá con un mensaje REPLY.

Como principal ventaja está la "justicia" de este algoritmo, ya que se concederá acceso a la sección crítica según el tiempo en el que se creó la petición. En cuanto a las desventajas más importantes, están el número de mensajes producidos para poder entrar y salir de la sección crítica (3*(N-1)) y la tolerancia a fallos, ya que un fallo de cualquier nodo impide que el algoritmo pueda continuar.

Algoritmo de Ricart y Agrawala[editar]

El algoritmo de Ricart y Agrawala, al igual que el algoritmo de anillo basa su funcionamiento en tokens. Inicialmente el token es asignado a uno de los procesos y si otro proceso que no posee el token quiere acceder a la sección crítica, lo solicitará mediante una multidifusión de un mensaje al resto de procesos. Este mensaje deberá contener el identificador del proceso y un timestamp. Además, cada proceso tiene una variable mediante la cual indica su estado con respecto a la sección crítica, esta variable puede tomar tres valores:

LIBERADA, si se encuentra fuera de la sección crítica, en este caso el proceso responde a la petición de entrada a la sección crítica inmediatamente.
BUSCADA, si está fuera de la sección crítica y quiere acceder a ella, en este caso el proceso compara el tiempo de la petición que le llega y si es mayor que el suyo lo mete a una cola, si no responde inmediatamente.
TOMADA, si está dentro de la sección crítica, en este caso el proceso mete las peticiones entrantes directamente en la cola.

Cuando el proceso (Pj) que posee el token abandona la sección crítica, recorre su lista de peticiones ordenadas por tiempo y responde a cada una de ellas.

Algoritmo de Maekawa[editar]

El algoritmo de Maekawa pertenece a los basados en quorum y para entenderlo hay que pensar en la red o sistema distribuido como un subconjunto de nodos (Si), y que para que un nodo pueda acceder a la sección crítica este debe haber bloqueado anteriormente a los demás pertenecientes al mismo subconjunto. Cuando el nodo i trate de bloquear a todos los demás nodos si lo consigue podrá acceder a la sección crítica, pero si no tendrá que esperar a que todos los demás nodos estén libres para poder volver a intentarlo.

Para evitar el posible interbloqueo de los nodos debido a varias peticiones simultáneas de distintos nodos se utilizará una prioridad de dicha petición para dar el permiso a un nodo o a otro. Esta prioridad será una marca de tiempo o número de secuencia (timestamp), que cuanto más baja sea mayor prioridad le otorgará a la petición.

Recursos[editar]

Datos: Q56377736

Algoritmo de Servidor Centralizado, https://es.scribd.com/document/546337759/Algoritmo-de-Servidor-Centralizado