Sincronización en sistemas operativos: Dekker, Peterson, semáforos y monitores

Resumen

El documento repasa los mecanismos clásicos para garantizar la exclusión mutua entre procesos concurrentes: los intentos fallidos de solución, el algoritmo de Dekker, el algoritmo de Peterson, los semáforos y los monitores. Se explican sus ventajas, sus inconvenientes y los problemas que aparecen al combinar semáforos con regiones críticas.

Puntos clave

La tercera tentativa (espera infinita) puede provocar un bloqueo mutuo entre los dos procesos.
La cuarta tentativa (aplazamiento indefinido) garantiza la exclusión mutua y evita el bloqueo mutuo, pero puede producir aplazamiento indefinido.
El algoritmo de Dekker combina las banderas de intención de entrar con una variable turno, asegura la exclusión mutua y está libre de interbloqueos.
El algoritmo de Peterson simplifica el de Dekker manteniendo las mismas garantías.
Los semáforos fueron propuestos por Dijkstra en 1965 para resolver la exclusión mutua evitando la espera activa, con las operaciones wait(s) y signal(s).
Los inconvenientes de los semáforos son la inicialización crítica, la facilidad para confundir wait y signal y la complejidad de los programas resultantes.
Un wait sobre un semáforo con contador 0 dentro de una región crítica bloquea dicha región.
Los monitores son un mecanismo de sincronización de nivel superior, donde solo un proceso puede estar activo a la vez dentro del módulo.

Ponte a prueba

Mecanismos de Sincronización en Sistemas Operativos

Tercera tentativa: espera infinita

Se puede producir un bloqueo mutuo, donde los dos procesos entran en un ciclo infinito. Esto se debe a que cada uno de los procesos se puede bloquear en su verificación.

Cuarta tentativa: aplazamiento indefinido

Se introduce un tratamiento de cortesía. Cuando un proceso ve que otro quiere utilizar el recurso, le cede el turno cortésmente. La exclusión mutua está garantizada y no ocurre bloqueo mutuo, pero puede ocurrir un aplazamiento indefinido debido al retraso [delay(random)].

Algoritmo de Dekker

Utiliza, además de las banderas de intención de entrar, una variable turno que resuelve en caso de conflicto. Es una combinación de los programas PrimerIntento y CuartoIntento anteriormente descritos. Esta solución asegura la exclusión mutua y está libre de interbloqueos. Este algoritmo sirve para conseguir la exclusión mutua entre dos procesos. El algoritmo utilizado para N procesos tan sólo tiene un interés teórico ya que consume demasiado tiempo para conseguir la exclusión mutua.

Algoritmo de Peterson

Simplifica el algoritmo de Dekker. El protocolo de entrada es más elegante con las mismas garantías de exclusión mutua, imposibilidad de bloqueo mutuo y de aplazamiento indefinido.

Semáforos

El uso de semáforos fue propuesto en 1965 por Dijkstra, con el objetivo de resolver el problema de la exclusión mutua, evitando la espera activa. Los semáforos son herramientas a nivel software donde es el SO el que interactúa con el hardware y no el usuario.

Esta solución es aplicable a n procesos. wait(s) Bloquea al proceso si el resultado no es positivo y decrementa. signal(s) Incrementa y despierta a un proceso suspendido (si lo hay).

Ventajas

Mecanismo seguro de acceso a un recurso compartido mediante el encapsulamiento de las operaciones sobre la variable que controla el semáforo.
Consiguen sincronización de procesos concurrentes evitando la espera activa.
El programa principal debe inicializar el semáforo (según su uso).

Inconvenientes

La inicialización es crítica.
Confundir un wait con un signal u omitir alguno de ellos.
Resultan programas muy grandes y complejos, difíciles de depurar.

Región crítica

En cualquier caso existen razones para no implementar RC con semáforos, por ejemplo, el compilador no conoce qué variables protege un semáforo, con lo que no ayudaría si se está utilizando una variable compartida fuera de su RC (esto tendría que controlarlo también el programador). También hay que tener sumo cuidado cuando se combinan los semáforos y las RC. Si un proceso que está dentro de una RC realiza una operación wait() sobre un semáforo cuyo contador vale 0, este proceso se parará dentro de la RC, bloqueándola en consecuencia.

Monitores

Son mecanismos de sincronización de nivel más alto que los semáforos. Los procedimientos van encapsulados dentro de un módulo que tiene la propiedad especial de que sólo un proceso puede estar activo cada vez para ejecutar un procedimiento del monitor. La única acción que debe realizar el programador del proceso que usa un recurso es invocar una entrada del monitor.

Preguntas frecuentes

¿Qué es el algoritmo de Dekker?

Es un algoritmo de exclusión mutua entre dos procesos que usa banderas de intención de entrar y una variable turno para resolver los conflictos. Garantiza la exclusión mutua y está libre de interbloqueos.

¿En qué se diferencia el algoritmo de Peterson del de Dekker?

El algoritmo de Peterson simplifica el de Dekker. Su protocolo de entrada es más elegante y ofrece las mismas garantías de exclusión mutua, ausencia de bloqueo mutuo y ausencia de aplazamiento indefinido.

¿Para qué se usan los semáforos?

Se usan para sincronizar procesos concurrentes y resolver la exclusión mutua evitando la espera activa. Se manipulan mediante las operaciones wait(s) y signal(s).

¿Qué es un monitor en sistemas operativos?

Es un mecanismo de sincronización de nivel más alto que los semáforos, en el que los procedimientos están encapsulados en un módulo y solo un proceso puede estar activo cada vez dentro de él.