Exclusión Mutua Distribuida Flashcards
Qué es la exclusión mutua?
La exclusión mutua es una característica deseable de las secciones críticas, donde se busca que solamente una entidad pueda acceder a la sección crítica a la vez. Normalmente, se asegura la exclusión mutua por medio de mutexs y conditional variables.
Qué problemas puede traer la exclusión mutua en sistemas distribuidos con respecto a una sola computadora?
La exclusión mutua en un sistema de una sola computadora se asegura utilizando mutexs y conditional variables, o incluso instrumentos como semáforos o monitores.
Estas herramientas no pueden implementarse en sistemas distribuidos. En ellos, es necesario utilizar algoritmos diseñados para asegurar la exclusión mutua en las SC.
Los problemas que se deben atacar cuando se busca garantizar la exclusión mutua en sistemas distribuidos son:
- sincronización: la mayoría de los algoritmos requieren de verificaciones de timestamps, por lo que se necesita asegurar que los timestamps están sincronizados. Se suele hacer con el algoritmo de Lamport.
- nodos caídos: se debe tener en cuenta que los nodos pueden dejar de funcionar, y el sistema debe adaptarse a esta situación.
- performance: comunicar sistemas distribuidos es más costoso a nivel tiempo que comunicar entidades que viven en la misma memoria.
Explicar el algoritmo centralizado para garantizar exclusión mutua.
El algoritmo centralizado requiere la existencia de un coordinador. Cuando un proceso A quiere acceder a la SC, le pide permiso al coordinador. Hay dos opciones:
- Nadie está en la SC: el coordinador le devuelve OK al instante, lockeando la SC para A
- Ya hay un proceso B en la SC: el coordinador espera a que B termine de ejecutar la SC, y recién entonces le devuelve OK a A, lockeando la SC para A
Explicar el algoritmo distribuido para garantizar exclusión mutua.
En este algoritmo, el proceso A, que quiere acceder a la SC, le envía mensaje a todos los procesos del sistema, pidiéndoles permiso para ejecutar la SC. El proceso que recibe el pedido tiene tres opciones:
- Si no está en la SC y no quiere entrar –> devuelve OK automáticamente
- Si ya está en la SC –> continúa ejecutando la SC y cuando termina, devuelve OK
- Si no está en la SC, pero quiere entrar –> compara el timestamp propio con el que llegó en el pedido del proceso A. Si el pedido del proceso A es anterior al del proceso actual, el proceso B le cede a A el derecho, devolviendo OK. Si el pedido del proceso A en más nuevo que el del proceso actual, el proceso actual arranca su propio pedido para acceder a la SC.
Cuando A recibe el OK de todos los procesos, recién entonces puede acceder a la SC.
Explicar el algoritmo token ring para garantizar exclusión mutua.
En este algoritmo, los nodos deben estar organizados en forma lógica de anillo, como una lista simplemente enlazada circular. Al levantar el sistema inicialmente, se genera un mensaje de tipo token, que circulará por el anillo durante toda la vida del sistema. El único proceso que puede acceder a la SC es el que posee el token en ese instante. Por lo tanto, eventualmente el proceso A recibirá el token de su anterior, y en ese momento revisará si necesita acceder a la SC. Si no lo necesita, envía el token a su siguiente directamente. Si lo necesita, primero ejecuta la SC en su totalidad, y luego envía el token a su siguiente.
