Interbloqueo y Sincronización en Sistemas Distribuidos: Condiciones y Soluciones

Interbloqueo en Sistemas Operativos

El interbloqueo ocurre cuando todos los procesos de un grupo se encuentran esperando un recurso que está retenido por otro proceso del mismo grupo.

Elementos que definen un Interbloqueo

Un conjunto de procesos ejecutándose en un sistema (computador).
Un conjunto de recursos que son utilizados por dichos procesos.

Interbloqueo de Tráfico

Ningún proceso del grupo puede avanzar (queda suspendido permanentemente).
Ningún otro proceso podrá obtener los recursos retenidos, puesto que no pueden ser liberados.

Los interbloqueos son un gran problema para los Sistemas Operativos, como UNIX, que no contemplan ningún tratamiento en absoluto.

Ejemplo de Bloqueo

El proceso “a” solicita la impresora, que se le concede.
El proceso “b” solicita la unidad de memoria, que se le concede.
El proceso “a” solicita la unidad de memoria, pero se deniega la solicitud hasta que “b” la libere.
El proceso “b” solicita la impresora y se produce el bloqueo (deadlock).

Condiciones de Coffman

Las siguientes cuatro condiciones son necesarias para que se produzca un interbloqueo:

Exclusión mutua: Al menos un recurso debe ser utilizado en exclusión mutua (modo no compartido).
Retener y esperar: Al menos un proceso retiene un recurso y, al solicitar otro recurso que está retenido por otro proceso, entra en estado de espera.
No expulsión: Un proceso mantiene retenido un recurso hasta que deja de utilizarlo y lo libera voluntariamente.
Espera circular: Debe existir un conjunto de procesos {P1, P2, …, Pn} donde P1 espera un recurso que retiene P2, P2 espera un recurso que retiene P3, y así sucesivamente. Si estas condiciones se cumplen simultáneamente, el sistema está en riesgo de sufrir un interbloqueo.

Tratamiento del Bloqueo

Ignorar el problema, asumiendo que dicha situación nunca se dará en el sistema.
Emplear algún algoritmo o protocolo que asegure que nunca se va a producir un interbloqueo. Esto se puede hacer de dos formas:
- Prevención: Consiste en conseguir que no puedan darse simultáneamente las cuatro condiciones de Coffman.
- Evitación: Se lleva la cuenta de los recursos disponibles, los recursos usados por los procesos y los que van a solicitar.
Usar un algoritmo que detecte un interbloqueo (detección) y aplicar una técnica que elimine dicha situación (recuperación).

Evitación del Bloqueo

Solamente se permiten peticiones de recursos que no lleven al sistema a un estado de interbloqueo.

Estado seguro: Si los procesos ya tienen concedidos los recursos, pueden ser completados en algún orden determinado.
Estado no seguro: No implica interbloqueo, pero alguna secuencia de solicitudes podría llevar al sistema a un interbloqueo.

Detección del Interbloqueo

Para detectar un interbloqueo, es necesario saber qué recursos están asignados y mantener información sobre las solicitudes. Existen dos tipos de algoritmos:

Primer tipo: Se basa en la detección de ciclos o nudos en el grafo de asignación de recursos.
Segundo tipo: Utiliza una matriz de asignados, un vector de disponibles y una matriz de solicitudes.

Recuperación del Bloqueo

Para recuperar un sistema interbloqueado, hay que identificar los procesos que producen el interbloqueo y después realizar una de las siguientes acciones:

Reiniciar un proceso (abandonar): Esto implica la pérdida del trabajo que el proceso había ejecutado. Si el interbloqueo persiste, se deben abandonar más procesos. Es importante abandonar procesos y comprobar el estado del sistema después de cada abandono.
Reiniciar todos los procesos: Devolver los procesos a un estado anterior donde no haya bloqueo. Para poder volver atrás, es necesario haber guardado el estado del sistema en memoria.
Expropiar o apropiar recursos: Expropiar recursos a procesos hasta que deje de existir el interbloqueo.

Relojes y Sincronización

Sincronización: Mecanismos que facilitan el trabajo coordinado.
La sincronización en sistemas distribuidos es más compleja que en sistemas centralizados debido al acceso a recursos compartidos y la ordenación de eventos. En sistemas distribuidos, cada nodo tiene un reloj.
Para tener un único reloj en sistemas distribuidos, es necesario sincronizar los relojes de los diferentes nodos para tener un reloj común.
Una forma de sincronizar en sistemas centralizados se deriva de emplear un reloj único.

Algoritmo de Cristian

Se da cuando un nodo con un reloj muy preciso, sincronizado con otros más precisos todavía, sirve como referencia. Los demás nodos tratan de sincronizarse con él. El servidor es el nodo con el reloj preciso y el cliente es el nodo que se desea sincronizar.

Problemas:

Los relojes no pueden retroceder.
El tránsito de mensajes por la red consume tiempo.

Pasos:

El cliente pide el valor del reloj al servidor en el instante T0 (según el reloj local del cliente).
El servidor recibe la petición y contesta con el valor de su reloj: Cs.
La respuesta llega al cliente en T1 (según el reloj local del cliente).
El cliente fija su reloj al valor de Cs + (T1 – T0) / 2.
Si se conoce el tiempo de procesamiento del servidor (Tp), se fija el valor del reloj a Cs + (T1 – T0 – Tp) / 2.

Si Cs > Cc, se fija el valor del reloj del cliente a Cs.
Si Cs < Cc, se almacena LAG = Cc – Cs y se descartarán LAG ticks del reloj del cliente (se evita que retroceda el reloj, haciendo que el reloj vaya más lento).

Algoritmo de Berkeley

No se supone que exista un ordenador con reloj preciso.
Uno de los ordenadores actúa de servidor y los demás actúan de clientes.
El servidor pregunta el valor de los relojes a los clientes de forma periódica.
Dadas las respuestas, el servidor calcula la media y contesta a todos los clientes para que actualicen sus relojes.

Algoritmos Distribuidos

Algoritmos de media: Cada nodo envía a los demás su valor y cada nodo calcula la media de los valores recibidos y se ajusta.
Algoritmo NTP (Network Time Protocol): Logra precisión a escala mundial con un error entre 1 y 50 microsegundos.

Sincronización en Sistemas Distribuidos

El problema en un sistema distribuido es determinar el orden particular sobre cualquier conjunto de eventos. Existen dos grupos de mecanismos de sincronización: centralizados y distribuidos.

Algoritmos no Basados en Paso de Mensajes

Algoritmo de Lamport: Algoritmo propuesto para lograr la exclusión mutua en redes cuyos nodos se comunican solamente mediante mensajes y que no comparten memoria. Propuesto por Lamport en 1978.

Reloj Físico

Provee de un único bloque de tiempo para el sistema. Los procesos pueden usar la marca física del tiempo provista o leída de un reloj central para expresar algún orden en el conjunto de acciones que inician.

Ventajas: Simplicidad.

Inconvenientes:

El registro del tiempo depende de recibir correctamente la información.
El tiempo actual desplegado por el reloj físico.
El grado de exactitud depende de las constantes puestas en el sistema.

Sincronización de Relojes Físicos

Para conocer a qué hora del día ocurren los sucesos en los procesos de nuestro sistema distribuido Q, es necesario sincronizar los relojes de los procesos Ci con una fuente de tiempo externa autorizada. Esto es la sincronización externa.

Concurrencia

La concurrencia es la simultaneidad de hechos.

Un programa concurrente es aquel en el que ciertas unidades de ejecución internamente secuenciales (procesos o threads) se ejecutan paralela o simultáneamente. Incluye los siguientes aspectos:
- Comunicación entre procesos.
- Compartición y competencia por los recursos.
- Sincronización de la ejecución de varios procesos.
- Asignación del tiempo de procesador a los procesos.
Surgen en entornos con un solo procesador, con multiprocesadores y en procesos distribuidos.
Un programa concurrente está formado por una colección de procesos secuenciales autónomos que se ejecutan (aparentemente) en paralelo.
Tres formas de ejecutar procesos concurrentes:
- Los procesos multiplexan sus ejecuciones sobre un único procesador (multiprogramación).
- Los procesos multiplexan sus ejecuciones sobre un sistema multiprocesador de memoria compartida (multiproceso).
- Los procesos multiplexan sus ejecuciones en varios procesadores que no comparten memoria (procesamiento distribuido).
El término concurrencia indica paralelismo potencial.

Dificultades con la Concurrencia

Los problemas por la multiprogramación surgen porque no es posible predecir la velocidad relativa de los procesos:

El proceso depende de la actividad de otros procesos y de cómo el Sistema Operativo trata las interrupciones y las políticas de planificación.
Dificultades:
- Compartir recursos globales (variable global).
- Manejar la asignación de recursos.
- Detectar un error es difícil, dado que es difícil reproducir la situación.

Tipos de Procesos

Independientes: Su estado no es compartido, son deterministas y son reproducibles.
Cooperantes: Su estado es compartido, no son deterministas y son irreproducibles.

Interacción entre Procesos

Existen tres maneras en que los procesos interactúan:

Competencia por recursos escasos: Los procesos no conocen a los demás.
Cooperación por compartición: Los procesos conocen indirectamente a los demás.
Cooperación por comunicación: Los procesos conocen directamente a los otros.

Problemas Potenciales a Resolver

Exclusión mutua: Mecanismo empleado en el diseño de Sistemas Operativos para evitar problemas de competencia por recursos, basado en definir una zona o región crítica.
Interbloqueo (deadlock): Condiciones:
- P1 requiere R1 y R2.
- P2 requiere R1 y R2.
- Acciones:
  - P1 obtiene R1.
  - P2 obtiene R2.
  - P1 y P2 están bloqueados esperando cada uno al otro.
Inanición: Los procesos siempre están bloqueados y nunca acceden a los recursos que necesitan.

Sección Crítica

Es la parte del programa que accede a un recurso compartido. Solo un programa puede acceder a su sección crítica en un momento dado. No se puede confiar simplemente en el Sistema Operativo para hacer cumplir esta restricción.

Requerimientos:

Exclusión mutua: Sólo un proceso accede a la vez a su SC.
Un proceso suspendido en su SC no debe estorbar a otros.
No inanición, no interbloqueo: Si un proceso solicita acceso a su SC, no se debe demorar su atención.
Si ningún proceso está en su SC, no se puede evitar que otro proceso entre a su SC.
No suponer la velocidad relativa de los procesos.
Se permanece en la SC por un tiempo finito.