Sección crítica: algoritmos de Dekker y semáforos para la sincronización de procesos

El Problema de la Sección Crítica (SC)

Consideramos n procesos, cada uno con un segmento de código al que se denomina Sección Crítica (SC). En esta sección, cada proceso podría estar modificando variables comunes, actualizando tablas o escribiendo archivos. La característica fundamental de este sistema es que si un proceso se está ejecutando en su SC, ningún otro puede hacerlo; es decir, la ejecución de la SC es mutuamente exclusiva en el tiempo. El problema radica en el diseño de un protocolo que permita a los procesos cooperar de forma segura.

Cada proceso debe solicitar el ingreso a su SC, lo cual se implementa en la sección de entrada. Puede existir una sección de salida. El código restante se denomina sección no crítica. La solución debe satisfacer tres requisitos fundamentales:

• Exclusión Mutua: Solo un proceso puede estar ejecutándose en su Sección Crítica a la vez.
• Progreso: Solo los procesos que no estén en su sección no crítica pueden participar en la decisión de qué proceso entrará a la Sección Crítica a continuación.
• Espera Limitada: Debe existir un límite en el número de veces que un proceso puede ser superado por otros procesos que desean entrar a la Sección Crítica.

Sabemos que los procesos se ejecutan a una velocidad arbitraria (distinta de cero), pero no podemos hacer ninguna suposición acerca de dicha velocidad relativa.

Las soluciones pueden implementarse por hardware, utilizando instrucciones específicas de una clase de CPU, o bien ser independientes del hardware mediante algoritmos.

Algoritmo de Dekker

El Algoritmo de Dekker es una de las primeras soluciones correctas para el problema de la Sección Crítica para dos procesos, evitando la espera activa en ciertas condiciones. A continuación, se describen sus versiones:

Versiones del Algoritmo de Dekker

Versión 1:

Se comparte una variable global entera que representa el turno. Permite el acceso a la SC al proceso correspondiente, pero no satisface el requisito de Progreso.

Versión 2:

Incorpora la información del estado de cada proceso, sustituyendo la variable entera por un array de booleanos que indican si el proceso i-ésimo está listo para entrar en SC. A pesar de esto, no cumple el requisito de Progreso.

Versión 3:

Combina ideas de las versiones uno y dos. Se comparten dos variables: una entera (para el turno) y un array de booleanos (para indicar el deseo de acceder a la SC). Esta solución cumple los tres requisitos.

Versión 4: Generalización a n procesos (Algoritmo de la Panadería)

Esta versión es una generalización del algoritmo de Dekker para n procesos. Se utilizan dos arrays: uno de enteros (para los números de turno) y otro de booleanos (para indicar si un proceso está eligiendo un número).

Semáforos

Los semáforos son una herramienta de sincronización introducida por Dijkstra. Su idea consiste en sincronizar procesos mediante el envío y recepción de señales. Son una solución de alto nivel. Básicamente, son variables enteras inicializadas a un determinado valor inicial en función de las necesidades de sincronización. Solo puede accederse a ellos mediante dos operaciones atómicas: espera (wait), que se denota como P, y señal (signal), que se denota como V.

Operaciones Atómicas de los Semáforos

P(S) {
  while (S <= 0) { /* hacer nada (espera activa) */ }
  S = S - 1;
}

V(S) {
  S = S + 1;
}

Dado que estas funciones son atómicas, si un proceso está evaluando o modificando el valor de S, ningún otro puede hacerlo simultáneamente.

Los semáforos pueden usarse para resolver el Problema de la Sección Crítica para n procesos. Todos los procesos comparten un semáforo binario, comúnmente llamado mutex, que se inicializa con el valor 1. Este valor representa el número máximo de procesos que pueden utilizar el recurso de forma simultánea (en este caso, uno).

Implementación de Semáforos

Todas las soluciones vistas hasta ahora provocan espera activa (busy waiting), lo cual es un problema significativo en sistemas multiprogramados reales, ya que ocupa la CPU en ciclos de espera improductivos. Si se sabe que la espera durará poco tiempo, esta aproximación podría ser admisible.

Para evitar la espera activa, pueden modificarse las definiciones de P (wait) y V (signal) de modo que, en lugar de esperar activamente, un proceso se bloquee y se coloque en una cola asociada al semáforo. Cuando otro proceso ejecute V (signal), uno de los procesos en la cola será despertado y podrá continuar su ejecución.

Estructura y Operaciones de Semáforos con Bloqueo

typedef struct {
  int valor; // Valor del semáforo
  Lista L;   // Cola de procesos esperando
} Semaforo;

P(Semaforo S) {
  S.valor = S.valor - 1;
  if (S.valor < 0) {
    agregar_proceso_a_cola(S.L, proceso_actual);
    bloquear_proceso();
  }
}

V(Semaforo S) {
  S.valor = S.valor + 1;
  if (S.valor <= 0) {
    proceso_despertar = extraer_proceso_de_cola(S.L);
    despertar_proceso(proceso_despertar);
  }
}

Estas definiciones emplean llamadas al sistema operativo (SO). Además, esta implementación de semáforos permite valores negativos para S.valor, que representan el número de procesos bloqueados esperando por ese semáforo.