Interbloqueo: cuando un cerrojo deja de ser la solucion

Un cerrojo arreglo la carrera de la leccion anterior, asi que lo obvio es anadir otro. Aqui hay una transferencia entre dos cuentas, cada una con su propio cerrojo. Este es el fallo que ha tumbado mas sistemas en produccion que cualquier otro error suelto de concurrencia.

/* transfer.c */
void transfer(account *from, account *to, long cents) {
  mutex_lock(&from->lock);
  mutex_lock(&to->lock);
  from->balance -= cents;
  to->balance += cents;
  mutex_unlock(&to->lock);
  mutex_unlock(&from->lock);
}

transfer(&alice, &bob, 500);    /* thread 1 */
transfer(&bob, &alice, 700);    /* thread 2 */Cada cuenta tiene su propio cerrojo. Las dos llamadas de abajo se ejecutan a la vez en dos hilos distintos.

Mira quien posee que. El hilo 1 ha adquirido el cerrojo de alice y ahora quiere el de bob. El hilo 2 ha adquirido el de bob y ahora quiere el de alice. Ninguno lo soltara jamas, porque ninguno ha terminado. Los dos duermen para siempre. Para que esto ocurra tuvieron que cumplirse cuatro condiciones a la vez; las cuatro se nombraron en 1971 y siguen siendo la lista de comprobacion.

mutual exclusion      request()
hold and wait         hold(A); request(B)
no preemption         request(B); loop
circular wait         T1 -> B, T2 -> A

all four hold   ->   deadlock
break any one   ->   no deadlockLas cuatro condiciones de Coffman. Rompe cualquiera de ellas y el interbloqueo se vuelve imposible, sin importar como se usen los cerrojos.

La condicion mas barata de romper aqui es la espera circular, y el remedio es una linea: da a cada objeto bloqueable un orden global y adquiere siempre los cerrojos en ese orden. El truco clasico es comparar direcciones: el que esta mas abajo en memoria se toma primero. Asi dos hilos no pueden sostener cerrojos que el otro necesita, porque ambos van a por el mismo primero.

mutex_lock(&from->lock);   /* wrong: order depends on arguments */
mutex_lock(&to->lock);

mutex_lock(&lo->lock);     /* right: one global order, by address */
mutex_lock(&hi->lock);Ahora las dos llamadas toman primero la direccion menor, asi que una simplemente espera a la otra en lugar de pelearse con ella.

La otra condicion que se puede romper es sostener y esperar. Haz que cada adquisicion sea todo o nada: si el segundo cerrojo no esta libre ahora mismo, suelta el primero y empieza de nuevo. Nadie espera mientras sostiene algo, asi que no puede formarse un ciclo de poseedores. Esto solo funciona si el estado no queda a medio cambiar: la funcion debe hacerlo todo o nada. Es una restriccion real, y es exactamente por eso que el codigo bancario usa transacciones.

while (!mutex_trylock(&from->lock)) { /* backoff */ }
if (!mutex_trylock(&to->lock)) {
  mutex_unlock(&from->lock);
  return RETRY;                /* held nothing while waiting */
}

/* $ timeout 30 ./bank && echo ok || echo 'still stuck' */

El interbloqueo no es la unica forma de que el trabajo se detenga. Dos hilos tambien pueden seguir corriendo y seguir deshaciendo el trabajo del otro: cada uno detecta un conflicto, suelta su cerrojo con educacion y lo reintenta, y los dos reintentan en el mismo instante, para siempre. Eso es un livelock. La CPU esta al 100%, los registros estan llenos de actividad y ninguna transaccion llega a completarse. Es discutiblemente peor que un interbloqueo, porque un proceso interbloqueado esta a cero de CPU y aparece en un volcado de pilas, mientras que uno en livelock parece ocupado y sano. El remedio es introducir azar: retroceso exponencial con un componente aleatorio, para que los dos hilos dejen de reintentar al unisono.

deadlock    blocked,  cpu 0%
livelock    running,  cpu 100%
starvation  running,  cpu 100%

F1 holds B forever
F2 and F3 retry
F1 is frozenTres formas de que el trabajo se detenga, distinguidas solo por lo que hace el procesador y por quien esta atascado.

La inanicion es el tercer fallo y el que parece mas inofensivo. Nada es ciclico y nada esta bloqueado: el sistema en conjunto avanza, pero un hilo concreto nunca llega a su turno. La causa habitual es un cerrojo de lectores-escritores que siempre prefiere a los lectores que llegan: con un flujo constante de lectores, un escritor espera para siempre. Un hilo de prioridad minima en una maquina cargada es otro caso. La inanicion es un fallo de equidad, no estructural, y puede tardar dias en notarse porque las graficas de rendimiento se ven perfectas.

Y ahora la razon de que el consejo obvio este mal. Anadir un cerrojo no anade seguridad, anade un recurso, y cada recurso nuevo es una arista de espera nueva en el grafo. Dos cerrojos crean un ciclo posible; diez cerrojos crean 45 pares ordenados y cualquiera de ellos puede ser el orden equivocado en algun punto del codigo. Una funcion que toma tres cerrojos distintos y llama a codigo que toma otros dos ha hecho posible un interbloqueo en un sitio donde nadie pensara en buscar. Ademas los cerrojos no se componen: dos modulos independientes, cada uno correcto, pueden interbloquearse en el momento en que uno llama al otro mientras sostiene su propio cerrojo.

En la practica los cerrojos no son el unico recurso que puede interbloquearse. Un hilo que sostiene una conexion de base de datos mientras espera una conexion del mismo pool deja el pool sin recursos; dos servicios que esperan cada uno una llamada sincrona del otro son un interbloqueo distribuido que ningun volcado de pilas de un solo proceso puede mostrarte. En produccion esto se detecta con tiempos de espera e hilos vigilantes: si una transaccion no ha avanzado en N segundos, se vuelcan las pilas de todos los hilos y se busca el ciclo. En un proceso en marcha se ve directamente: las pilas de los hilos interbloqueados nombran el cerrojo que espera cada uno y el cerrojo que posee cada uno.