Variables de condición, semáforos e interbloqueo

Un mutex responde a «¿Quién puede acceder a estos datos ahora?». No responde a «¿Ha terminado el trabajo?». Para esperar un evento, un hilo necesita un registro del evento y una forma de suspenderse hasta que ese registro cambie.

Por qué la espera activa es ineficiente

El bucle while (done == 0) ; consume tiempo de CPU al comprobar repetidamente un indicador. En una sola CPU, ese trabajo retrasa al hijo que debe establecer el indicador. En C, una lectura sin sincronización de una variable ordinaria mientras otro hilo escribe en ella también es una carrera de datos. El compilador no está obligado a volver a cargar el indicador en cada iteración.

Una variable de condición proporciona a los hilos una cola de espera. POSIX proporciona pthread_cond_t, inicializado con PTHREAD_COND_INITIALIZER o pthread_cond_init(). La cola es independiente del estado que se comprueba: done registra la finalización; la variable de condición proporciona un lugar donde suspenderse.

Mantén juntas la comprobación y la espera

pthread_cond_wait(&c, &m) requiere que el hilo que llama tenga adquirido el mutex m. Libera ese mutex e inicia la espera de forma atómica. Antes de retornar, vuelve a adquirir el mutex. Esto cierra el peligroso intervalo en el que otro hilo podría cambiar el estado y notificar antes de que el hilo en espera haya empezado realmente a esperar.

Aquí un padre espera a que termine un hijo. Los nombres lock, wait, signal y unlock abrevian las llamadas correspondientes de la biblioteca de hilos.

/* Parent */
lock(&m);
while (done == 0)
    wait(&c, &m);
unlock(&m);

/* Child */
lock(&m);
done = 1;
signal(&c);
unlock(&m);

Inicialmente done es 0. Si el padre se ejecuta primero, adquiere el cerrojo, comprueba que el trabajo no ha terminado y espera. La espera libera m, lo que permite al hijo adquirirlo, establecer done y notificar. Con el tiempo, el padre vuelve a adquirir m, comprueba de nuevo done y continúa.

Si el hijo se ejecuta primero, registra la finalización antes de que llegue el padre. Su notificación no despierta a nadie, pero el padre, al llegar después, ve done == 1 y omite la espera. El funcionamiento debe ser correcto en ambos órdenes.

Las notificaciones no almacenan eventos

pthread_cond_signal(&c) desbloquea al menos a un hilo en espera cuando los hay; POSIX permite que se despierte más de uno. Si no hay hilos en espera, no tiene efecto. pthread_cond_broadcast(&c) despierta a todos los hilos que esperan en ese momento. Ninguna de las dos llamadas guarda una notificación para futuros hilos.

Por tanto, omitir done estropea el patrón de espera a la terminación: un hijo puede notificar antes de que su padre espere, tras lo cual el padre se suspende sin que vaya a llegar otra notificación. Esto es un despertar perdido. Comprobar done fuera del mutex crea otra ventana de despertar perdido: el padre comprueba que es falso, el hijo lo establece como verdadero y notifica, y luego el padre empieza a esperar.

Protege la comprobación y cada cambio de estado con el mismo mutex. Mantenlo adquirido desde la comprobación hasta la llamada de espera. Una forma sencilla de notificar consiste en cambiar el estado y notificar mientras se sigue teniendo adquirido ese mutex. POSIX permite notificar sin tenerlo adquirido, pero el protocolo de estado compartido debe seguir evitando los despertares perdidos.

Retornar de la espera significa que el hilo puede volver a intentarlo. No significa que la condición que necesita siga siendo verdadera. Esta distinción importa cuando varios hilos compiten por los mismos datos.

Semánticas de Mesa y Hoare

POSIX, Java, las variables de condición de C++ y las condiciones de Python siguen el comportamiento de Mesa. Los monitores de Hoare introdujeron el modelo de entrega más fuerte; el enfoque de Mesa es la opción práctica habitual.

Supón que C1 espera a que un búfer de una posición deje de estar vacío. Un productor lo llena y notifica a C1. C1 está ahora listo, pero C2 puede adquirir primero el mutex y tomar el elemento. Cuando C1 finalmente vuelve a adquirir el mutex, el búfer está vacío de nuevo.

lock(&m);
while (count == 0)
    wait(&filled, &m);
v = get();
unlock(&m);

El while repite la comprobación después de cada retorno. Un if solo comprueba antes de la primera espera y permitiría que C1 llamara a get() sobre un búfer vacío. Incluso con un productor y un consumidor, usa while: POSIX también permite despertares espurios, en los que la espera retorna sin una notificación correspondiente.

¿Despertar a un hilo o a todos?

Una notificación a un hilo es adecuada cuando todos los hilos en espera necesitan la misma condición y cualquiera puede aprovechar el cambio. Una notificación a todos es útil cuando varios pueden continuar o cuando distintos hilos en espera necesitan cantidades diferentes y el hilo que notifica no puede seleccionar al adecuado.

Considera un asignador con 0 bytes libres. Ta necesita 100 bytes y Tb necesita 10. Otro hilo libera 50 bytes. Una notificación podría despertar a Ta, que aún no puede continuar, dejando a Tb suspendido aunque su solicitud puede atenderse. Notificar a todos despierta a ambos. Vuelven a adquirir el mutex de uno en uno; Tb puede asignar memoria, mientras Ta vuelve a esperar. Esta es una condición de cobertura: la notificación cubre a todos los hilos en espera que podrían continuar.

Notificar a todos puede causar despertares y cambios de contexto adicionales, y competencia por el mutex. Variables de condición separadas para distintos predicados pueden hacer que las notificaciones sean más selectivas. En un búfer, los productores y consumidores no deberían compartir una sola cola de notificación indiferenciada.

La relación con los monitores

Un monitor agrupa datos compartidos con operaciones que admiten un hilo a la vez y variables de condición para esperar. Los objetos de Java proporcionan un cerrojo y un conjunto de espera. Dentro de synchronized, un hilo puede llamar a wait(), notify() o notifyAll(); llamarlos sin ser propietario del monitor de ese objeto lanza IllegalMonitorStateException.

La espera solo libera el mutex asociado o el cerrojo del objeto Java. Si un hilo también tiene adquirido otro cerrojo, ese segundo cerrojo permanece adquirido. Un productor que lo necesite podría no poder hacer que la condición sea verdadera. Comprueba todos los cerrojos adquiridos al esperar, no solo el indicado en la llamada.

Los productores añaden elementos a un búfer de tamaño fijo; los consumidores los extraen. Un búfer acotado correcto impide sobrescribir un búfer lleno, extraer de uno vacío y modificar sus datos de control simultáneamente. La cola de solicitudes de un servidor web y la tubería entre grep error log.txt y wc -l siguen este patrón.

Sigue los índices circulares

Un búfer circular usa un arreglo y dos índices. fill_ptr indica la siguiente escritura; use_ptr indica la siguiente lectura. Ambos avanzan módulo MAX. Un count separado distingue el estado vacío del lleno, incluso cuando los dos índices son iguales.

void put(int v) {
    buffer[fill_ptr] = v;
    fill_ptr = (fill_ptr + 1) % MAX;
    count++;
}
int get(void) {
    int v = buffer[use_ptr];
    use_ptr = (use_ptr + 1) % MAX;
    count--;
    return v;
}

Comienza con capacidad 3 y ambos índices en 0. Al insertar 7, 8 y 9 se llenan las posiciones 0, 1 y 2. El índice de escritura vuelve a 0 y count llega a 3. La extracción devuelve 7 y hace avanzar el índice de lectura a 1. Al insertar 10 se reutiliza la posición 0. El arreglo es ahora [10, 8, 9], pero la extracción FIFO sigue el índice de lectura: primero sale 8, luego 9 y luego 10.

Dirige cada notificación al papel opuesto

Usa un mutex, empty para los productores que esperan espacio y fill para los consumidores que esperan un elemento. Inicializa ambas variables de condición y el mutex antes de iniciar los hilos.

/* Producer: repeat for each item v */
lock(&m);
while (count == MAX)
    wait(&empty, &m);
put(v);
signal(&fill);
unlock(&m);

/* Consumer */
lock(&m);
while (count == 0)
    wait(&fill, &m);
v = get();
signal(&empty);
unlock(&m);

La comprobación y la actualización del búfer permanecen en una misma sección crítica. De lo contrario, dos productores podrían ver una posición libre y sobrescribir el trabajo del otro. La espera libera m, de modo que el papel opuesto puede cambiar el búfer.

Por qué una sola cola puede detenerse

Con una variable de condición y notificaciones a un hilo, los productores y consumidores pueden despertar al papel equivocado. Con capacidad 1, C1 y C2 primero se suspenden porque está vacío. P inserta un elemento, despierta a C1 y luego espera porque el búfer está lleno. C1 extrae el elemento y notifica, pero la notificación puede despertar a C2 en vez de a P. C1 vuelve a esperar; C2 también encuentra el búfer vacío y espera. P sigue suspendido aunque hay espacio disponible. Dos colas dirigen cada notificación al papel que ahora puede continuar. Notificar a todos en una cola compartida puede evitar ese problema de selección, a costa de despertares adicionales.

Una capacidad mayor absorbe ráfagas y permite solapar el trabajo de producción y consumo fuera de la breve sección crítica del búfer. Las actualizaciones del propio búfer siguen realizándose en serie. Una capacidad de 1 obliga a alternar cada inserción y extracción.

Para cerrar de forma ordenada, espera primero a que todos los productores terminen de colocar sus elementos reales. Luego pon en cola un elemento reservado de fin de datos por cada consumidor, como -1 cuando los elementos reales no son negativos. Cada consumidor sale después de tomar uno. Enviar esos marcadores mientras los productores siguen activos puede dejar elementos reales sin ningún consumidor.

Un semáforo contiene un entero que se modifica mediante operaciones atómicas de espera y señalización. Dijkstra lo introdujo en la década de 1960 como P y V; POSIX denomina a las operaciones sem_wait() y sem_post(). Atómico significa que dos hilos no pueden realizar parcialmente la misma operación sobre el contador a la vez.

Las unidades disponibles determinan el valor inicial

sem_init(&s, 0, X) crea un semáforo sin nombre con valor X. El segundo argumento 0 selecciona la compartición entre hilos de un mismo proceso. Para compartirlo entre procesos, un argumento distinto de cero requiere que el semáforo esté en memoria compartida.

Un semáforo binario usado como cerrojo rodea una sección crítica con una espera y una señalización. Iniciarlo en 0 bloquea al primer hilo que intenta entrar. Iniciarlo en 2 permite la entrada de dos hilos y no proporciona exclusión mutua.

Dos modelos de recuento equivalentes

En la definición de Dijkstra, el valor permanece no negativo: la espera suspende el hilo hasta que puede decrementar sin bajar de cero, y la señalización añade una unidad. Linux sigue esta convención de valores no negativos.

Para los seguimientos manuales, usa el modelo de contador con signo: la espera decrementa y bloquea si el nuevo valor es negativo; la señalización incrementa y despierta a un hilo en espera cuando hay uno bloqueado. En este modelo, la magnitud de un valor negativo cuenta los hilos bloqueados. Es una convención para razonar, no un valor negativo que debas esperar de la API de semáforos de Linux.

Sigue un cerrojo inicializado en 1:

1. T0 espera: 1 pasa a 0, por lo que T0 entra.
2. T1 espera: 0 pasa a −1, por lo que T1 se bloquea.
3. T0 señaliza: −1 pasa a 0, lo que permite a T1 continuar.
4. T1 termina y señaliza: 0 pasa a 1.

El despertar transfiere el permiso existente a T1; no se necesita otra espera antes de que T1 entre en su sección crítica.

Una señalización se recuerda

Si no hay ningún hilo en espera, una señalización aumenta el recuento disponible. Una espera futura puede consumir ese permiso. Esto es útil cuando un hilo termina antes de que el hilo que lo espera haya empezado a esperar. Una notificación de variable de condición no tiene esa memoria.

Los semáforos no tienen propietario: un hilo puede esperar y otro puede señalizar. Un mutex pertenece al hilo que lo adquirió; liberar un mutex POSIX predeterminado desde otro hilo es un comportamiento indefinido. El semáforo sin propietario permite la señalización, pero también dificulta el diagnóstico de una señalización adicional.

Un semáforo puede construirse con un mutex, una variable de condición y un entero no negativo. La espera adquiere el mutex, entra en un bucle mientras value <= 0, espera, decrementa y libera el mutex. La señalización adquiere el mutex, incrementa, notifica y libera el mutex. El mutex hace atómicas las operaciones del contador; el bucle gestiona los despertares que no dejan una unidad disponible. Los cerrojos con variables de condición y los semáforos pueden implementarse unos con otros, aunque implementar correctamente una variable de condición a partir de semáforos es más complejo.

El mismo par de espera y señalización puede representar un evento o una cantidad limitada de recursos. Decide qué significa un permiso antes de elegir el recuento inicial y dónde corresponde cada operación.

Haz que la finalización preceda al uso

Para que un padre espere a un hijo, inicializa finished en 0. El hijo señaliza después de terminar su trabajo. El padre espera antes de usar el resultado.

/* Child */
produce_result();
sem_post(&finished);

/* Parent */
sem_wait(&finished);
use_result();

Si el padre llega primero, el valor con signo cambia de 0 a −1 y se suspende. La señalización del hijo devuelve el valor a 0 y lo despierta. Si el hijo llega primero, su señalización cambia el valor de 0 a 1; la espera posterior lo cambia de 1 a 0 sin bloquearse. Un evento completado permite una espera satisfactoria.

Cuenta un conjunto de recursos

Un conjunto de cuatro conexiones a una base de datos usa un semáforo inicializado en 4. Cada cliente espera antes de tomar prestada una conexión y señaliza después de devolverla. Un quinto cliente simultáneo se suspende. El semáforo cuenta las admisiones; un mutex independiente sigue protegiendo la lista compartida que identifica qué conexión está libre. Dos hilos admitidos no deben retirar la misma entrada de la lista.

La limitación de la concurrencia aplica la misma idea a una fase costosa. Supón que 100 hilos necesitan cada uno 500 MB durante el procesamiento. Juntos podrían necesitar 50 000 MB. Una máquina con 8 GB tiene 8000 MB según las unidades decimales del SI. Admitir como máximo 12 trabajadores limita esta fase a 6000 MB y deja 2000 MB para otros usos.

sem_wait(&processing_slots);
run_memory_heavy_phase();
sem_post(&processing_slots);

Toda ruta posterior a una espera satisfactoria debe devolver su permiso, incluida una ruta de error. Olvidar una señalización reduce gradualmente la capacidad. Señalizar dos veces crea un permiso adicional y permite más usuarios simultáneos de los previstos.

Reunirse en un punto de encuentro

Un punto de encuentro requiere que lleguen dos hilos antes de que cualquiera continúe. Inicializa a_arrived y b_arrived en 0.

/* A */
sem_post(&a_arrived);
sem_wait(&b_arrived);

/* B */
sem_post(&b_arrived);
sem_wait(&a_arrived);

Si A llega primero, registra su llegada y se bloquea esperando a B. B registra su llegada y puede consumir el permiso guardado de A. A puede entonces consumir el permiso de B. Invertir ambas secuencias para esperar antes de señalizar deja a cada hilo suspendido antes de anunciar nada.

Estos dos semáforos implementan un encuentro. Reutilizar la sincronización en rondas repetidas requiere evitar que unas rondas consuman los anuncios de llegada de otras; un seguimiento satisfactorio no constituye un diseño de barrera reutilizable.

Un semáforo se adapta bien a un recuento o a un evento sencillo. Una variable de condición se adapta a un predicado más complejo, como esperar hasta que una cola contenga varios elementos de un tipo determinado. En ese caso, el mutex protege el estado a partir del cual se calcula la condición.

Un búfer con semáforos separa dos preguntas: «¿Hay un elemento o una posición disponible?» y «¿Quién puede actualizar el arreglo ahora?». Dos semáforos contadores responden a la primera pregunta y un mutex responde a la segunda.

Prepara tres controles distintos

Para una capacidad MAX, inicializa empty en MAX, full en 0 y el mutex como liberado. Aquí empty y full son semáforos, no variables de condición. Un permiso de empty reserva una posición; un permiso de full reserva un elemento.

/* Producer */
sem_wait(&empty);
lock(&mutex);
put(v);
unlock(&mutex);
sem_post(&full);

/* Consumer */
sem_wait(&full);
lock(&mutex);
v = get();
unlock(&mutex);
sem_post(&empty);

El productor adquiere espacio antes de acceder al búfer circular y luego publica el elemento terminado mediante una señalización de full. El consumidor adquiere un elemento, lo extrae con el mutex adquirido y devuelve el espacio mediante una señalización de empty. Una espera satisfactoria en un semáforo ya reserva el recurso, por lo que estas llamadas no necesitan un bucle de comprobación del predicado como el de una variable de condición.

Sigue una posición

Inicialmente empty vale 1 y full vale 0. Un consumidor espera en full, cuyo valor pasa a −1 en el modelo con signo, y se suspende. El productor espera en empty, cuyo valor pasa de 1 a 0. Adquiere el mutex, inserta, lo libera y señaliza full, cuyo valor pasa de −1 a 0 y permite continuar al consumidor.

La siguiente espera del productor en empty cambia el valor de 0 a −1 y lo bloquea. El consumidor toma el elemento con el mutex adquirido y señaliza empty, cuyo valor pasa de −1 a 0 y permite continuar al productor. Los recuentos de los semáforos realizan la transferencia; no se requiere un count separado para la sincronización.

Con un búfer más grande, varios productores pueden pasar el semáforo de espacio. Sin el mutex, ambos podrían leer el mismo fill_ptr y escribir en la misma posición. Una reserva no concede acceso exclusivo a los índices del arreglo.

Por qué adquirir primero el mutex puede causar un interbloqueo

Supón que el consumidor adquiere mutex antes de esperar en full. Con el búfer vacío se suspende mientras sigue teniendo adquirido el mutex. El productor necesita ese mutex para insertar el elemento cuya señalización permitiría continuar al consumidor. Ninguno puede terminar.

Una espera en un semáforo no libera ningún mutex. Una espera en una variable de condición libera deliberadamente su mutex asociado. Por tanto, el orden en este búfer importa: primero reserva, después adquiere el mutex, cambia el búfer, libera el mutex y luego señaliza el permiso opuesto.

La regla general es evitar bloquearse mientras se tiene adquirido un cerrojo que necesita la operación capaz de desbloquear al hilo. Esta regla explica por qué el algoritmo de lectores-escritores puede tener una disposición segura diferente: su escritor no necesita el cerrojo del contador de lectores para liberar su recurso.

El propio mutex puede ser un semáforo binario inicializado en 1. Su función sigue siendo la exclusión mutua; los otros dos semáforos cuentan recursos.

Las estructuras en las que predominan las lecturas pueden permitir varios lectores a la vez porque leer no cambia los datos. Un cerrojo de lectores-escritores admite a un grupo de lectores o a un escritor. Todo cambio en los datos protegidos requiere acceso de escritura.

Construye el grupo de lectores

Usa readers = 0, un semáforo lock inicializado en 1 para proteger ese contador y writelock inicializado en 1 para proteger el recurso compartido.

/* Acquire read access */
sem_wait(&lock);
readers++;
if (readers == 1)
    sem_wait(&writelock);
sem_post(&lock);

/* Release read access */
sem_wait(&lock);
readers--;
if (readers == 0)
    sem_post(&writelock);
sem_post(&lock);

Un escritor espera en writelock, cambia los datos y luego señaliza writelock. No adquiere el cerrojo del contador. El primer lector adquiere writelock para el grupo y el último lector lo devuelve. Un semáforo es adecuado para esa transferencia porque el hilo que lo señaliza no tiene que ser el que esperó originalmente.

Sigue la entrada de R1: aumenta readers a 1 y adquiere writelock. R2 aumenta el contador a 2 sin adquirir otro permiso. El escritor W se bloquea entonces en writelock. R1 sale y reduce el contador a 1. R2 sale, lo reduce a 0 y señaliza, lo que permite a W escribir en solitario.

El primer lector puede esperar a writelock mientras tiene adquirido lock. Esto no crea el interbloqueo del búfer acotado: el escritor actual no necesita el cerrojo del contador para terminar y señalizar writelock.

La equidad es una propiedad independiente

Este diseño da preferencia a los lectores. Mientras el contador de lectores siga siendo positivo, otro lector puede unirse al grupo antes que un escritor en espera. Un flujo continuo de lectores cuyas lecturas se solapan puede mantener al escritor esperando indefinidamente: inanición de los escritores.

El diseño básico proporciona seguridad, pero no establece un límite al tiempo de espera de un escritor. Una mayor tasa de procesamiento de lectores no equivale a una atención equitativa.

Usa el modo correcto

Un cerrojo de lectura no puede proteger una escritura frente a otros lectores. Actualizar incluso un contador de caché con acceso de lectura puede entrar en carrera con otro lector. Para convertir el acceso en este diseño básico, libera el acceso de lectura, adquiere el de escritura y vuelve a comprobar la condición. Esperar el acceso de escritura mientras el hilo sigue contado como lector puede hacer que se espere a sí mismo para siempre.

POSIX proporciona pthread_rwlock_t, pthread_rwlock_rdlock(), pthread_rwlock_wrlock() y pthread_rwlock_unlock(). Java ofrece ReentrantReadWriteLock; C++17 ofrece std::shared_mutex. Estos cerrojos requieren más trabajo de gestión que un mutex sencillo. Mide la carga de trabajo: las secciones cortas o las escrituras frecuentes pueden hacer que un mutex sencillo sea igual de rápido o más rápido.

Una violación de atomicidad ocurre cuando el código depende de que un grupo de accesos sea indivisible, pero otro hilo puede actuar entre ellos. Cada acceso individual puede parecer razonable mientras la operación conjunta falla.

Encuentra el intervalo después de la comprobación

Considera un búfer de registro compartido:

/* T1 */
if (log->buf != NULL)
    write_out(log->buf);

/* T2 */
log->buf = NULL;

T1 puede comprobar un puntero no nulo, pausarse y reanudar su ejecución después de que T2 lo establezca como nulo. Entonces T1 pasa un valor nulo a write_out(). La garantía buscada no era solo una comprobación válida; también era que el valor comprobado siguiera siendo utilizable durante la llamada.

Protege la comprobación y el uso juntos, y protege la asignación que compite con ellos con el mismo mutex:

/* T1 */
lock(&m);
if (log->buf != NULL)
    write_out(log->buf);
unlock(&m);

/* T2 */
lock(&m);
log->buf = NULL;
unlock(&m);

Ahora T2 se ejecuta antes o después de toda la operación de T1. Dar a cada hilo su propio cerrojo no ayuda: ambos podrían tener adquiridos sus cerrojos independientes simultáneamente. Proteger solo a T1 deja a T2 libre para entrar en el intervalo.

Una comprobación válida aún puede dar lugar a un saldo no válido

Comienza con un saldo de 50. Dos hilos pretenden retirar cada uno 30 solo si queda suficiente. Ambos pueden leer 50 y superar balance >= 30 antes de que cualquiera actúe. Si se aplican las retiradas, el saldo puede llegar a −10. Proteger juntas la comprobación y la resta permite que la primera retirada deje 20; el siguiente hilo ve 20 y rechaza la retirada.

Incluso las cargas y restas atómicas no convierten ese par en una sola transacción. Otro hilo puede actuar entre la comprobación atómica y el cambio atómico. Un cerrojo alrededor de toda la decisión y el cambio garantiza el límite necesario.

El mismo problema aparece en count++: la carga, la suma y el almacenamiento son etapas separadas. Dos hilos pueden cargar el mismo valor anterior y almacenar el mismo valor incrementado, perdiendo una actualización. Un cerrojo alrededor del incremento o una operación atómica de obtener y sumar realiza la actualización necesaria de forma segura.

Usa las pruebas sin generalizar en exceso

Lu y sus colegas examinaron 105 errores de concurrencia corregidos en MySQL, Apache, Mozilla y OpenOffice en un estudio de 2008. De ellos, 74 eran errores distintos del interbloqueo y 31 eran interbloqueos. Las violaciones de atomicidad y del orden de ejecución representaban el 97 % de la muestra de errores distintos del interbloqueo. Estos son resultados de la muestra estudiada, no un porcentaje garantizado para todas las bases de código.

Alrededor del 92 % de los errores estudiados podían provocarse controlando el orden de como máximo cuatro accesos a memoria. Por tanto, una pequeña tabla de intercalados puede revelar más que miles de ejecuciones normales satisfactorias. ThreadSanitizer ayuda a encontrar carreras de datos ejecutadas, pero un error lógico de atomicidad puede persistir incluso cuando cada acceso individual está sincronizado. Comprueba la propiedad invariante de toda la operación, como «una retirada satisfactoria nunca deja el saldo en descubierto».

Una violación del orden de ejecución significa que la operación A debe ocurrir antes que la operación B, pero el programa no proporciona una sincronización que lo garantice. La exclusión mutua por sí sola no puede decidir qué operación va primero.

Un hilo puede ejecutarse de inmediato

Supón que un creador almacena un registro de trabajador recién creado en un puntero compartido, mientras el trabajador empieza usando ese puntero:

/* Creator */
worker = thread_create(worker_main);

/* New worker */
use(worker->state);

El trabajador puede ejecutarse antes de que retorne thread_create() y antes de que termine la asignación. El orden del código fuente del creador no dice nada sobre cuándo obtiene tiempo de CPU el nuevo hilo. Una ejecución satisfactoria solo significa que el creador ganó esa carrera por casualidad.

Publica la disponibilidad después de la inicialización

Añade ready = 0, el mutex m y la variable de condición c. El creador mantiene adquirido el mutex mientras asigna el puntero y publica que está disponible:

/* Creator */
lock(&m);
worker = thread_create(worker_main);
ready = 1;
signal(&c);
unlock(&m);

/* Worker, before using worker */
lock(&m);
while (ready == 0)
    wait(&c, &m);
unlock(&m);
use(worker->state);

Si el trabajador llega primero al mutex, no puede superar la comprobación de disponibilidad hasta que el creador haya publicado el registro. Si llega más tarde, ready recuerda que terminó la inicialización. Mantén el registro válido mientras el trabajador lo usa y sincroniza cualquier cambio posterior.

Un semáforo inicializado en 0 ofrece una transferencia más breve: el creador señaliza después de asignar el puntero y el trabajador espera antes de usarlo. Para un resultado que solo existe después de que termina un hilo, esperar a que termine antes de leer su resultado establece el orden necesario. Del mismo modo, la liberación de un objeto debe esperar a que terminen quienes lo usan, por ejemplo mediante esperas a la terminación de los hilos o un contador de referencias correctamente sincronizado.

Por qué los cambios de tiempo no lo corrigen

Añadir sleep(1) o sched_yield() solo cambia la probabilidad de la planificación deseada. Un sistema más lento o cargado aún puede permitir que el consumidor continúe demasiado pronto. Un mutex alrededor de cada operación impide el solapamiento, pero sigue permitiendo que el uso adquiera el mutex antes de la inicialización.

En el estudio de Lu y sus colegas, alrededor de un tercio de los errores distintos del interbloqueo eran violaciones del orden de ejecución y alrededor del 73 % de los errores distintos del interbloqueo no se corrigieron simplemente añadiendo o cambiando cerrojos. Antes de elegir una primitiva, identifica la operación que debe terminar y la operación que debe esperar. Esa dependencia determina dónde corresponde la señalización, la notificación o la espera a la terminación.

Un conjunto de hilos está interbloqueado cuando cada uno espera algo que solo otro hilo del conjunto puede proporcionar. Ninguno puede continuar y realizar la acción que libera a los demás. El programa puede funcionar con muchas planificaciones antes de que un orden desfavorable revele el ciclo.

Construye el fallo de dos cerrojos

T1 adquiere L1 y luego solicita L2. T2 adquiere L2 y luego solicita L1. Si T1 adquiere L1 y después T2 adquiere L2, ambas segundas adquisiciones se bloquean. Cada hilo tiene exactamente el recurso que necesita el otro.

Esto puede ocultarse dentro de funciones ordinarias. Si transfer(a, b) adquiere el cerrojo de a y luego el de b, las llamadas simultáneas transfer(x, y) y transfer(y, x) pueden adquirir los cerrojos de las cuentas en órdenes opuestos. La encapsulación facilita una llamada, pero puede ocultar los cerrojos que adquiere.

Identifica las cuatro condiciones

Las cuatro condiciones son necesarias. Eliminar cualquiera de ellas en el diseño previene el interbloqueo de recursos. La presencia de cerrojos exclusivos y adquisiciones anidadas por sí sola no demuestra que una ejecución concreta haya llegado a un ciclo.

Interpreta un grafo de espera

Dibuja un nodo por hilo. Dibuja T → U cuando T espera un recurso que tiene U. Con recursos de una sola instancia, como los cerrojos exclusivos, un ciclo identifica un interbloqueo.

Si T1 tiene A y espera B, T2 tiene B y espera C, y T3 tiene C y espera A, el grafo es T1 → T2 → T3 → T1. Los tres están detenidos. Si T3 solicita en cambio un cerrojo libre D, puede terminar y liberar C, permitiendo que T2 y luego T1 continúen. Una cadena no es un ciclo.

Cuando los tipos de recurso tienen varias instancias intercambiables, un ciclo por sí solo no basta: puede quedar disponible otra instancia. Usa los recuentos de recursos y las solicitudes pendientes para evaluar ese caso.

Los filósofos comensales y fallos relacionados

Cinco filósofos comparten cinco tenedores dispuestos en círculo. Cada uno necesita los dos tenedores contiguos. Si todos toman primero su tenedor izquierdo, todos pueden esperar su tenedor derecho para siempre. Invertir el orden de adquisición de un filósofo rompe el ciclo. Limitar la admisión a cuatro filósofos también impide que los cinco retengan un tenedor; al menos un filósofo admitido puede obtener ambos tenedores.

La inanición significa que un hilo espera indefinidamente mientras otros avanzan. El bloqueo activo significa que los hilos se ejecutan y reaccionan, pero no consiguen avanzar repetidamente. Un conjunto interbloqueado está bloqueado. Un hilo puede incluso interbloquearse a sí mismo al adquirir un mutex normal, no recursivo, que ya tiene adquirido. Los semáforos y las variables de condición también pueden crear dependencias: un hilo en espera que tiene adquirido un cerrojo necesario para quien debe notificarlo puede cerrar un ciclo sin adquirir explícitamente un segundo cerrojo.

La prevención cambia el diseño para que no pueda surgir una condición necesaria del interbloqueo. El orden de adquisición de cerrojos suele ser el enfoque más claro porque ataca directamente la dependencia circular.

Asigna un orden a cada cerrojo

Asigna claves únicas a los cerrojos y adquiere siempre las claves menores antes que las mayores. Para las transferencias entre cuentas, ordena los identificadores de las cuentas antes de adquirir sus cerrojos. Así, tanto transfer(x, y) como transfer(y, x) adquieren primero el cerrojo de la misma cuenta. Si los identificadores designan la misma cuenta, adquiere su cerrojo una sola vez.

Un ciclo requeriría que las claves siguieran aumentando alrededor del círculo y volvieran a la clave inicial, lo cual es imposible. Todas las rutas de adquisición deben seguir la regla. Una sola función auxiliar que invierta el orden restablece el riesgo. lockdep de Linux registra las dependencias observadas entre cerrojos e informa de órdenes potencialmente inseguros.

Adquiere todo o no adquieras nada

Una forma estricta de eliminar la retención y espera es conceder a un hilo su conjunto completo de recursos en un solo paso, o no conceder nada. Así nunca retiene un conjunto parcial mientras espera el resto. Esto requiere conocer de antemano los recursos necesarios y puede reducir la concurrencia.

Un protocolo relacionado serializa las secuencias de adquisición con un cerrojo global de prevención:

lock(&prevention);
lock(&L1);
lock(&L2);
unlock(&prevention);
/* use L1 and L2, then release them */

Todos los hilos deben terminar de adquirir su conjunto completo bajo ese cerrojo global, y la liberación de recursos no debe requerir adquirirlo. Un hilo aún puede tener L1 mientras espera L2, por lo que esto no elimina literalmente la retención y espera. Impide que otros hilos comiencen una adquisición parcial que compita con ella. Ningún hilo que tenga recursos puede estar a mitad de una segunda secuencia de adquisición que compita con la primera. Los costes son adquirir los cerrojos antes y serializar la adquisición.

Renuncia y reintenta

pthread_mutex_trylock() retorna inmediatamente con EBUSY cuando un cerrojo no está disponible. Un hilo puede adquirir L1, intentar adquirir L2 y liberar L1 si el intento falla. También debe deshacer otras adquisiciones parciales antes de reintentar.

Dos hilos pueden colisionar repetidamente, esperar antes de reintentar y volver a intentarlo juntos. Eso es bloqueo activo: ambos se ejecutan, pero ninguno termina. La espera aleatoria antes del reintento reduce las colisiones repetidas; no convierte el bucle de reintento en una garantía de equidad.

Sustituye un cerrojo por una operación atómica

Comparar e intercambiar (CAS) cambia una ubicación solo si aún coincide con un valor esperado. Conceptualmente, un bucle de reintento de suma atómica lee el valor anterior, intenta sustituirlo por ese valor más el incremento y reintenta si otro hilo lo cambió primero. Las implementaciones reales en C usan tipos y operaciones atómicas tanto para la lectura como para la actualización.

Eliminar la adquisición de un cerrojo elimina el interbloqueo por cerrojos de esa operación. Un algoritmo sin cerrojos garantiza el progreso del sistema en su conjunto, pero un hilo puede seguir fallando en sus reintentos. Las estructuras generales sin cerrojos también necesitan un diseño cuidadoso del tiempo de vida de la memoria.

La evitación comprueba si una solicitud propuesta deja una forma de que todos los hilos terminen. Permite los patrones habituales de uso de recursos, pero retrasa las solicitudes que eliminan los órdenes seguros de finalización restantes.

Un estado seguro garantiza que existe un orden posible

Una secuencia segura ordena los hilos de modo que cada uno pueda obtener su demanda máxima restante a partir de los recursos actualmente libres más los que liberan los hilos anteriores. Un estado inseguro carece de ese orden garantizado. No tiene por qué estar ya interbloqueado: los hilos podrían solicitar menos de su máximo o liberar recursos antes.

La planificación también puede evitar solapamientos peligrosos garantizando que dos tareas que entran en conflicto no accedan a sus fases de uso de recursos al mismo tiempo. No basta con colocar ambas en una CPU, porque aún pueden ser expropiadas e intercalarse mientras retienen recursos. La garantía necesaria es que las fases que entran en conflicto no se solapen.

Prepara las tablas del banquero

Para cada tipo de recurso, registra Available. Para cada hilo, registra Max, Allocation y Need = Max - Allocation. Compara los vectores componente por componente, nunca por la suma de sus componentes.

Usa los totales de recursos (7, 5, 6):

Las asignaciones suman (4, 3, 4), lo que deja Available = (3, 2, 2).

Sigue la comprobación de seguridad

Establece Work como Available. Elige un hilo que no haya terminado y cuyo Need quepa en Work, simula que termina y añade su Allocation de nuevo a Work.

1. T1 cabe en (3, 2, 2). Devolver (2, 0, 1) da Work (5, 2, 3).
2. T0 cabe. Devolver (1, 1, 0) da (6, 3, 3).
3. T2 cabe. Devolver (1, 1, 2) da (7, 4, 5).
4. T3 cabe. Devolver (0, 1, 1) da (7, 5, 6).

Todos los hilos terminan en esta simulación, por lo que el estado es seguro. Work aumenta en Allocation, no en Max: los recursos adicionales concedidos temporalmente para terminar también se devuelven, lo que da una ganancia neta igual a lo que el hilo tenía originalmente.

Simula la concesión y vuelve a comprobar

Una solicitud debe caber tanto en Need del hilo como en Available. Después réstala de Available, súmala a Allocation, réstala de Need y ejecuta la comprobación de seguridad sobre ese estado provisional.

Desde la tabla original, si T2 solicita (1, 0, 1), Available queda en (2, 2, 1). T1 aún puede ir primero, seguido de T0, T2 y T3, por lo que es seguro.

En cambio, si T3 solicita (2, 1, 1), Available queda en (1, 1, 1). El Need restante de T3 es (2, 0, 1). Ningún hilo cabe: T0 necesita 4 de A, T1 necesita 2 de B, T2 necesita 2 de C y T3 necesita 2 de A. Retrasa esta solicitud pese a los recursos actualmente libres.

Cada solicitud posterior necesita la misma comprobación. La evitación necesita demandas máximas declaradas y un modelo de recursos conocido, lo que la hace más adecuada para sistemas especializados y predecibles que para cargas de trabajo de aplicaciones generales.

Un sistema puede permitir que se forme un interbloqueo, detectarlo y recuperarse. Esto acepta la pérdida ocasional de trabajo a cambio de menos restricciones sobre las solicitudes ordinarias de recursos. La detección solo es útil cuando existe una acción de recuperación viable.

Encuentra ciclos bloqueados

Para recursos de una sola instancia, mantén un grafo de espera y busca un ciclo, por ejemplo mediante una búsqueda en profundidad. Supón que las aristas son T1 → T2, T2 → T3, T3 → T1 y T4 → T2. T1, T2 y T3 forman el ciclo. T4 está bloqueado detrás de él; la propia ejecución de T4 no puede liberar un recurso que rompa ese ciclo.

Con varias instancias, un ciclo no basta. Usa Available, Allocation y la solicitud pendiente actual Request de cada hilo. Inicializa Work con Available. Busca repetidamente una solicitud que quepa, simula la finalización y añade a Work la Allocation de ese hilo. A diferencia de la evitación, esta comprobación usa lo que los hilos esperan ahora, no su posible demanda máxima futura.

El detector estándar de recursos aparta inicialmente a los hilos que no retienen recursos: no pueden aportar recursos retenidos a un ciclo de recursos. Entre los hilos que retienen recursos, los que quedan sin terminar en la comprobación están interbloqueados según el modelo. Otros hilos aún pueden ser incapaces de avanzar porque dependen de ese conjunto. Distinguir el ciclo de sus dependientes bloqueados ayuda a elegir una víctima de recuperación eficaz.

Recupérate sin corromper el estado compartido

Un sistema puede terminar uno o más procesos, recuperar recursos revirtiendo el estado a un punto de control o reiniciar. Elige las víctimas según el coste de recuperación, la prioridad, el trabajo ya realizado y los recursos retenidos. Después de eliminar una víctima, vuelve a comprobar: varios ciclos independientes pueden requerir más de una acción de recuperación.

Terminar un hilo arbitrario no basta si deja un mutex adquirido o una estructura compartida modificada a medias. La recuperación debe liberar o reconstruir los recursos y restaurar un estado válido. Los sistemas de transacciones pueden abortar una transacción interbloqueada porque la reversión forma parte de su diseño. Una aplicación ordinaria suele necesitar en su lugar un reinicio controlado del proceso.

Interpreta los tiempos de espera agotados con cuidado

pthread_mutex_timedlock() puede devolver ETIMEDOUT al alcanzar un plazo. Un temporizador de vigilancia puede reiniciar un dispositivo que deja de informar de su progreso. Ambos detectan una espera excesiva; una espera larga también puede deberse a una entrada/salida lenta o a la planificación. Un tiempo de espera agotado es una señal para investigar o recuperarse, no un diagnóstico inequívoco de un ciclo.

Linux y Windows generalmente no encuentran ni reparan ciclos entre los propios cerrojos de una aplicación. El programa debe implementar la estrategia elegida. Si la recuperación selecciona repetidamente el mismo trabajo como víctima, ese trabajo puede sufrir inanición aunque se resuelva cada interbloqueo individual.

Un bucle de eventos espera eventos y despacha manejadores breves en un solo hilo. El programa elige explícitamente qué evento disponible gestionar a continuación. Node.js y nginx usan diseños basados en eventos para atender muchas conexiones sin asignar un hilo dedicado a cada una.

while (1) {
    events = get_events();
    /* handle each ready event, then return to the loop */
}

Los manejadores síncronos del mismo bucle se ejecutan de uno en uno. Las instrucciones ordinarias de un manejador no son interrumpidas por otro manejador de ese bucle. El bucle sigue dependiendo de que los manejadores retornen con rapidez.

Construye y examina los conjuntos de select

select() acepta conjuntos de descriptores que se deben vigilar para lectura, escritura y condiciones excepcionales, además de un tiempo de espera. Su argumento nfds es uno más que el descriptor vigilado más alto. Por tanto, vigilar los descriptores 3, 5 y 9 necesita nfds = 10, no 3.

FD_ZERO(&readset);
FD_SET(3, &readset);
FD_SET(5, &readset);
FD_SET(9, &readset);
int n = select(10, &readset, NULL, NULL, NULL);
/* If n > 0, test each watched descriptor with FD_ISSET. */

Un tiempo de espera nulo espera hasta que algo esté disponible; un tiempo de espera cero comprueba y retorna inmediatamente. select() sobrescribe los conjuntos con los descriptores disponibles, por lo que debes reconstruirlos antes de cada llamada. Su retorno positivo cuenta los bits establecidos entre los conjuntos devueltos; un descriptor disponible en dos conjuntos cuenta dos veces. Cero significa que se agotó el tiempo de espera; −1 significa error.

La disponibilidad no es una transferencia de datos. El programa aún llama a read() o recv(). El fin de la entrada puede aparecer como disponibilidad para lectura; una lectura que devuelve 0 significa que el otro extremo ha cerrado su lado de envío. Gestiona ese resultado en vez de volver a despachar repetidamente la misma entrada terminada.

Mantén los manejadores breves y no bloqueantes

Configura los sockets con O_NONBLOCK. Cuando una operación no puede continuar, devuelve −1 con errno establecido en EAGAIN o EWOULDBLOCK, lo que permite al manejador retornar al bucle. La disponibilidad puede cambiar antes de la operación, por lo que el modo no bloqueante también protege frente a una espera inesperada después de un aviso de disponibilidad.

Una lectura bloqueante dentro de un manejador retrasa todos los eventos en cola. Con 100 solicitudes en cola y una lectura bloqueante de disco de 10 ms por manejador, la última solicitud espera unos 990 ms antes de que comience su propia lectura; el lote tarda unos 1000 ms. El hilo pasó la mayor parte de ese tiempo esperando mientras el trabajo disponible permanecía en cola.

Elige una interfaz de disponibilidad

select() y poll() examinan el conjunto vigilado proporcionado en cada llamada, por lo que su trabajo aumenta con su tamaño. Linux ofrece epoll; FreeBSD y macOS ofrecen kqueue. Vigilar solo unos pocos descriptores no hace que un valor de descriptor alto sea válido para un fd_set de tamaño fijo.

La disponibilidad de la red indica a un bucle cuándo puede intentar una operación de entrada/salida. Los archivos regulares de disco son diferentes: select() y poll() los indican como disponibles incluso cuando acceder a sus datos aún requiere esperar al almacenamiento. Para seguir atendiendo otros eventos, envía el trabajo de forma asíncrona y gestiona su resultado más tarde.

Envía, espera en otra parte y recoge

La entrada/salida asíncrona POSIX almacena una solicitud en struct aiocb. Los campos importantes son aio_fildes para el descriptor de archivo, aio_offset para la posición en el archivo, aio_buf para el destino y aio_nbytes para la longitud solicitada.

/* cb describes a read request */
aio_read(&cb);
/* Return to other work. Later: */
int status = aio_error(&cb);
/* EINPROGRESS: still running; 0: succeeded; otherwise an error. */
/* After completion, aio_return(&cb) collects its result. */

aio_read() pone la solicitud en cola y retorna. La finalización es un evento separado. Cuando aio_error() indica que ha terminado, aio_return() proporciona el resultado, como los bytes leídos tras una lectura satisfactoria. Una solicitud puede fallar y una lectura satisfactoria puede devolver menos bytes de los solicitados. El registro de la solicitud y su búfer deben permanecer válidos mientras la operación esté pendiente.

Examinar repetidamente cada solicitud en un bucle continuo desperdicia tiempo de CPU. aio_sigevent puede configurar una señal o una función de retorno de finalización. io_uring de Linux usa colas de envío y finalización; los puertos de finalización de entrada/salida de Windows proporcionan despacho basado en la finalización. Estas interfaces permiten al programa actuar sobre el trabajo terminado sin volver a comprobar constantemente cada solicitud pendiente.

Conserva el estado durante el intervalo

Un hilo bloqueado mantiene las variables locales de su función en su pila. Un manejador de eventos que envía una operación de entrada/salida y retorna debe guardar lo que necesita el manejador posterior. Este trabajo de gestión explícito es la gestión manual de la pila; el estado guardado es una continuación.

Supón que un servidor lee el descriptor de archivo 12 para un cliente en el socket 7. Al enviar la solicitud guarda un registro que asocia esa solicitud de lectura con el socket 7 y el estado de su respuesta. Cuando llega la finalización, el bucle encuentra el registro, comprueba el resultado de la lectura y continúa enviando la respuesta al cliente correcto. Los registros separados evitan que varias solicitudes pendientes confundan sus destinos.

La continuación debe estar ligada a la operación concreta, no solo a un identificador que podría reutilizarse después. Mantén válida la referencia al cliente hasta que se gestione la finalización y elimina el registro cuando termine la tarea. Esos detalles del tiempo de vida sustituyen las suposiciones que una función bloqueante de ejecución secuencial podría mantener en su pila.

Una sintaxis legible puede ocultar una suspensión

Las funciones de retorno, las promesas y async/await automatizan gran parte de este guardado de estado. En JavaScript, const data = await readFile(path); suspende esa función mientras su operación de entrada/salida está pendiente. Puede ejecutarse otro trabajo del bucle y la función se reanuda más tarde con su estado local restaurado.

Asíncrono significa que quien llama puede continuar antes de que termine la operación. No significa que sus manejadores se ejecuten en varios núcleos de CPU a la vez. Tampoco hace que el código que consume mucha CPU después de un await ceda automáticamente: ese código sigue ocupando el hilo que lo ejecuta hasta que retorna o vuelve a suspenderse.

Un bucle de eventos es adecuado para muchas conexiones inactivas la mayor parte del tiempo con pequeñas ráfagas de trabajo. Un diseño basado en hilos mantiene juntos el flujo de control de una tarea y su pila. La mejor elección depende del tiempo de espera, el trabajo de CPU, la memoria y cómo evolucionará el código.

Compara el trabajo que implica cada diseño

Un servidor de chat con 50 000 conexiones mayormente inactivas puede beneficiarse de usar registros de eventos en vez de una pila de hilo dedicada por conexión. Un procesador de imágenes que realiza cálculos intensos por solicitud necesita suficientes trabajadores para usar los núcleos disponibles; un solo bucle ocupado no puede ejecutar esos cálculos en paralelo.

Las esperas ocultas siguen importando

Un manejador puede detenerse sin una llamada evidente a una API bloqueante. Acceder a una página que se ha paginado al disco puede provocar una lectura de disco. Durante ese fallo de página, el hilo del bucle espera. mlock() puede mantener residentes las páginas necesarias cuando el sistema permite la cantidad solicitada de memoria fijada. Eliminar las llamadas bloqueantes explícitas no elimina todas las causas de retraso.

Los cambios de código pueden introducir otra espera oculta. Si una función auxiliar que antes respondía de inmediato empieza a obtener datos, quien la llama desde código basado en eventos debe dividir su trabajo en torno a una continuación o derivar la llamada. La pila de un hilo bloqueante ya almacena dónde reanudar y el estado local que necesita.

Combina las ventajas

Un diseño híbrido mantiene la gestión de la disponibilidad de red en el bucle de eventos y envía las tareas bloqueantes o que consumen mucha CPU a un grupo de trabajadores. Las finalizaciones vuelven al bucle para gestionar la respuesta. Node.js usa el grupo de hilos de libuv para las operaciones del sistema de archivos, por lo que una interfaz asíncrona puede implementarse mediante hilos en segundo plano.

Para usar varios núcleos, un servidor puede ejecutar un bucle de eventos por núcleo en hilos o procesos separados. Si esos bucles comparten datos modificables, necesitan los cerrojos habituales u otro protocolo de sincronización. La ventaja de no necesitar cerrojos se aplica a los manejadores síncronos de un solo bucle, no a todas las partes de un servidor basado en eventos.

Una tarea puede intercalarse a través de await

Supón que queda una unidad en existencias. Un manejador comprueba la disponibilidad, espera el pago y luego descuenta la unidad. Mientras está suspendido, otro manejador puede comprobar las mismas existencias y también iniciar el pago. Ambas comprobaciones pueden tener éxito antes de cualquiera de los descuentos. No hay dos manejadores síncronos ejecutándose simultáneamente, pero la operación completa de comprobación y actualización no es atómica.

Reserva la unidad mediante un cambio de estado sincronizado antes de ceder la ejecución, con una vía para liberar la reserva si falla el pago, o vuelve a comprobar bajo un protocolo que impida una segunda venta. Mantener un mutex adquirido durante una espera larga puede crear otros problemas de progreso, por lo que debes diseñar explícitamente la transición de estado y su recuperación. El código basado en eventos sigue necesitando razonar sobre qué hechos siguen siendo verdaderos tras cada suspensión.