400440304. Uso de jerarquías de bloqueo para evitar interbloqueos

En las dos primeras columnas sobre Concurrencia Efectiva —»Los Pilares de la Concurrencia» y «¿Cuánta escalabilidad tenemos o necesitamos?» — vimos los tres pilares de la concurrencia y los tipos de concurrencia que expresan:
– Pilar número 1: aislamiento mediante agentes asíncronos. Consiste en realizar trabajos de forma asíncrona para conseguir aislamiento y capacidad de respuesta mediante técnicas como la mensajería. Algunas técnicas del pilar número 1, como la canalización, permiten también una escalabilidad limitada, pero esta categoría persigue principalmente el aislamiento y la capacidad de respuesta.
– Pilar número 2: escalabilidad mediante colecciones concurrentes Consiste en volver a permitir el extra de poder enviar aplicaciones que se aceleran en máquinas con más núcleos, usando más núcleos para conseguir una respuesta más rápida explotando el paralelismo en los algoritmos y los datos.
– Pilar número 3: Consistencia mediante recursos compartidos de forma segura- Mientras hacemos todo lo anterior, necesitamos evitar carreras e interbloqueos cuando usamos objetos compartidos en memoria o cualquier otro recurso compartido.
Mis últimas columnas se centraban en el pilar número 3, y me refería a los niveles de bloqueo o jerarquías de bloqueo como una forma de controlar los interbloqueos. Una serie de lectores me han pedido que explique lo que son y cómo funcionan, así que voy a escribir una columna más sobre el pilar número 3 (de momento).

El problema: Anatomía de un interbloqueo o “deadlock”

Nuestro programa contiene un interbloqueo en potencia si:
– Una parte del mismo intenta adquirir uso exclusivo de dos recursos compartidos (como los mutexes) a y b a la vez adquiriendo primero a y luego b.
– Alguna otra parte del programa intenta hacer lo mismo adquiriendo b y luego a en el orden contrario.
– Los dos segmentos de código podrían en alguna ocasión ejecutarse de forma concurrente.

Por mera conveniencia, a partir de ahora voy a hablar sólo de bloqueos, pero las cuestiones y las técnicas son aplicable a cualquier recurso compartido que necesite ser usado exclusivamente por sólo un trozo de código a la vez. El siguiente código muestra el ejemplo más sencillo de un interbloqueo potencial:


// Thread 1: a then b // Thread 2: b then a

a.lock(); b.lock();

b.lock(); a.lock();

... ...

// unlock a and b // unlock a and b

// in either order // in either order

La única forma de eliminar este interbloqueo potencial es asegurarse de que todos los mutexes contenidos a la vez en algún momento se adquieren en un orden consistente. Pero ¿cómo podemos garantizarlo de forma que sea a la vez utilizable y correcto? Por ejemplo, podríamos intentar averiguar qué grupos de mutexes podrían ser contenidos a la vez en algún momento, y después intentar definir normas de ordenación en pares que cubren todas las posibles combinaciones.

Pero ese método en sí mismo tiende a pasar por alto de forma accidental combinaciones inesperadas de bloqueo; e incluso aunque lo hiciera perfectamente, el resultado seguiría siendo como mucho «DAG spaghetti»— un gráfico acíclico dirigido (DAG, por sus siglas en inglés) que nadie entendería en su conjunto. Y cada vez que quisiéramos añadir un nuevo mutex al sistema, tendríamos que encontrar un modo de encajarlo dentro del DAG sin crear ningún ciclo.

Podemos hacerlo mejor si explotamos directamente el conocimiento que ya tenemos sobre la estructura del programa par regularizar el caos y hacerlo comprensible.

Una solución: Jerarquías de bloqueo y Establecimiento de capas

La idea de una jerarquía de bloqueos es la de asignar un nivel numérico a cada mutex del sistema, y a continuación seguir dos sencillas reglas de manera consistente:
– Regla número 1: mientras mantenemos un bloqueo en un mutex a nivel N, sólo podemos adquirir nuevos bloqueos en mutexes a niveles más bajos .
– Regla número 2: Hay que adquirir los bloqueos múltiples al mismo nivel a la vez, lo que implica que necesitamos una operación de «bloqueo-múltiple» como lock( mut1, mut2, mut3, … ). Esta operación tiene internamente la “inteligencia” para garantizar que siempre toma los bloqueos solicitados en algún orden global consistente. (1) Obsérvese que sirve cualquier orden consistente; por ejemplo, una estrategia típica es adquirir mutexes al mismo nivel en un orden de dirección en aumento.

Si todo el programa sigue estas reglas, en ese caso no puede haber interbloqueo entre las operaciones de adquirir mutex porque ningún par de segmentos de código puede en ningún momento intentar adquirir dos mutexes a y b en orden opuesto:

O bien a o b están en niveles diferentes y por tanto el que está en el nivel superior será tomado primero; o bien están en el mismo nivel y han de ser solicitados a la vez, y el sistema los adquirirá de manera automática en el mismo orden.

Las dos simples reglas nos proporcionan una forma conveniente y comprensible de expresar de forma conveniente un orden total en todo el bloqueado realizado en el sistema.
Pero ¿dónde encontramos los niveles? La respuesta es: Es probable que ya los tengamos. Los mutexes protegen datos, y los datos están ya en capas.

Los niveles de bloqueo deberían incentivar directamente y reflejar las distintas capas que ya hay en la estructura modular de nuestra aplicación. La figura 1 ilustra un ejemplo típico de capas (o “descomposición jerárquica” y “hacia un gráfico acíclico dirigido”, si preferimos la jerga especializada), una técnica de comprobada eficacia para controlar las dependencias en nuestro software.

La idea es agrupar el código en módulos y los módulos en capas, en las que el código que está en una capa dada sólo puede invocar código que esté en la misma o en capas inferiores, y debería evitar invocar hacia arriba en las capas superiores.

Figura 1

Muestra de descomposición de módulos/capas.

Si suena muy parecido a las Dos Reglas de jerarquías de bloqueo, no es mera coincidencia. Después de todo, tanto las capas como los mutexes están regidos por el mismo objetivo: Proteger y controlar el acceso a los datos encapsulados que son propiedad de cada trozo de código, y mantenerlo libre de corrupción manteniendo correctamente sus invariantes.

Como en la figura 1, los niveles que asignamos a los mutexes normalmente irán muy próximos a los niveles de la estructura estratificada del programa. Una consecuencia directa de la Norma número 1 es que los bloqueos mantenidos en mutexes a niveles más bajos tienen una duración más corta que los bloqueos mantenidos a niveles más altos; eso es justo lo que esperamos de las invocaciones al código en las capas más bajas de un sistema de software en capas.

El software no puede siempre estar perfectamente en capas, pero las excepciones deberían ser raras. Después de todo, si no podemos definir este tipo de capas, implica que hay un ciclo en alguna parte entre los módulos que incluye código en lo que debería ser un subsistema de menor nivel invocando en alguna parte a código de un nivel superior, como mediante una “callback» , y tenemos posibilidad de reentrar incluso en el código de hilado único.

Recordemos que la reentrada es una forma de concurrencia, de manera que el programa puede observar un estado corrupto incluso en el código de hilado único. Si hay código de nivel alto que en esos momentos está llevando al sistema de un estado válido a otro y temporalmente, por tanto, rompiendo alguna variante, e invoca a código de nivel más bajo, el problema está en que si esa invocación pudiera volver a invocar en última instancia a código de nivel superior podría ver la invariante rota.

El establecimiento de capas ayuda a solucionar este problema de concurrencia de hilado único por las mismas razones que ayuda a solucionar la versión más general de hilos múltiples.

Plataformas y jerarquías de bloqueo

Es curioso que las plataformas más importantes que suministran mutexes y bloqueos no hacen nada por ofrecer ningún tipo de soporte directo para las jerarquías de bloqueo. A todos nos enseñan que las jerarquías de bloqueo constituyen buenas prácticas, pero después nos dicen en general que hagamos las nuestras.

Los distribuidores de plataformas sin duda arreglarán en el futuro este pequeño “problema”, pero de momento aquí presento una receta útil de seguir cuando estamos haciendo nuestro propio envoltorio de mutex sensible a los niveles. Podemos adaptar este sencillo bosquejo a las necesidades específicas de nuestro proyecto (por ejemplo, para atenerse a detalles como si la operación lock es un método o una clase separada):
– Escribimos un envoltorio entorno a cada uno de nuestros tipos favoritos de mutex específicos de plataforma o de lenguaje, y dejamos que el constructor o constructores del envoltorio tome(n) un parámetro de número de nivel que guarda en un miembro myLevel. Usamos estos envoltorios en todas partes. (Donde sea práctico, podemos ahorrar tiempo haciendo que el envoltorio sea genérico —como plantilla C++, o un genérico de Java o de .NET— de forma que pueda ser instanciado a envolver tipos arbitrarios de mutex que tienen similares características de bloqueo/antibloqueo. Quizá sólo tengamos que hacerlo una vez.)
– Damos a la clase envoltorio (wrapper) una variable estática de hilo local denominada currentLevel, inicializada a un valor superior que cualquier nivel válido de bloqueo.
– En el método lock (o similar) del envoltorio, nos aseguramos de que currentLevel es mayor que myLevel, el nivel del mutex que estamos a punto de intentar adquirir. Recordemos que si el valor anterior de currentLevel está usando la variable de otro miembro, tendremos que fijar currentLevel = myLevel; y adquirir el bloqueo.
– En el método unlock (o similar) del envoltorio, restauramos el valor anterior de currentLevel.
– Según se necesite, envolvemos otros métodos necesarios que tengamos que poder usar como try_lock. Cualquiera de estos métodos que podrían intentar adquirir el bloqueo deberían hacer las mismas cosas que hace lock.
– Por último, escribimos un método de «bloqueo-múltiple» lock( m1, m2, … ) que toma un número variable de objetos que se puedan bloquear, comprueba que están todos al mismo nivel, y los encierra en su orden de dirección (o su orden GUID, o algún otro orden global consistente).

La razón para usar comprobaciones en los métodos lock es para que, en una compilación de depurado, obligamos a exponer los errores la primera vez que ejecutamos la ruta del código que viola las normas en la jerarquía del bloqueo. De esa forma, podemos esperar encontrar violaciones en el momento de la comprobación, y tener la confianza de que el programa está libre de interbloqueos basados en la cobertura de la ruta del código.

Permitir unos fallos tan deterministas en el momento de las comprobaciones es una gran mejora sobre la forma en que se manifiestan normalmente los errores de concurrencia, a saber, como fallos no deterministas en el tiempo de ejecución no pueden ser comprobados en profundidad usando sólo cobertura en la ruta del código.

Pero a menudo nuestra cobertura de la ruta del código durante el momento de la comprobación no es completo, bien porque sea imposible cubrir todas las posibles combinaciones de rutas de código o bien porque se nos pueden olvidar algunos casos; por eso es preferible también realizar pruebas en las compilaciones de liberación, registrando las violaciones en un registro o vertido de diagnósticos que podemos revisar más tarde si se presenta algún problema.

Unos comentarios sobre la componibilidad

Aunque las jerarquías de bloqueos dan respuesta a muchos de los problemas de los bloqueos, incluida la posibilidad de un interbloqueo, siguen compartiendo el mismo talón de Aquiles: Como los mismos bloqueos, las jerarquías de bloqueo no son componibles en general sin algo de disciplina y esfuerzo extras.
Después de todo, sólo porque usemos una disciplina de jerarquía de bloqueo correctamente dentro del código que controlamos, un módulo de otro autor distinto o un plug-in con el que nos vinculamos no necesariamente sabrá nada de nuestra jerarquía de bloqueos, a no ser que ,de alguna forma, les informemos de nuestras capas y de cómo deberían encajar en la jerarquía.

Por ejemplo, observemos de nuevo la arquitectura de la aplicación muestra de la figura 1 y consideremos lo siguiente: ¿Qué pasaría si la aplicación quiere permitir plugins que son invocados desde la capa 5000? En primer lugar, por supuesto, el programa y todos los plug-ins deberían hacer todos los esfuerzos posibles por evitar invocar código desconocido (en este caso, uno al otro) mientras contienen un bloqueo.

Pero, como se puede ver en «Avoid Calling Unknown Code While Inside a Critical Section«, edición americana de DDJ, diciembre 2007, podemos encontrarnos con problemas incluso si un plug-in no toma ningún bloqueo pero invoca de nuevo dentro del programa principal y crea una ruta de código que inesperadamente invoca código en un nivel más alto que toma un bloqueo de nivel más alto.

Así pues, los plug-ins deben ser sensibles a las capas de la aplicación y hay que decirles que tienen que operar al nivel (pongamos) 4999, y sólo pueden invocar API por debajo del nivel 4999.

Resumen

Hay que mantenerlo en el nivel: Hay que usar jerarquías de bloqueo para evitar interbloqueos (deadlocks, en inglés, que literalmente sería “bloqueo muerto”, aunque en castellano es normalmente “punto muerto” o “callejón sin salida”) en el código que controlamos.

Hay que asignar a cada recurso compartido un nivel que se corresponde con su capa arquitectónica dentro de la aplicación, mientras se mantiene un recurso a un nivel más alto, hay que adquirir sólo recursos a niveles inferiores, y adquirir múltiples recursos al mismo nivel todos a la vez.

Si nuestro programa va a invocar código externo, especialmente plug-ins, hay que documentar la API pública suficientemente para que los autores de plug-ins vean a qué nivel se espera que operen sus plug-ins, y así las invocaciones de API que pueden hacer y que no pueden hacer (las de por debajo de su nivel y las de por encima de su nivel, respectivamente).

El próximo mes, vamos a empezar a examinar cuestiones y técnicas para escribir aplicaciones de muchos núcleos y escalables. Manténganse al tanto.

Notas

(1) O si no obtiene el mismo efecto. Por ejemplo, es posible empezar simplemente a intentar adquirir los bloqueos en algún orden seleccionado aleatoriamente usando operaciones try_lock, y si no podemos adquirirlas todas, simplemente retrocedemos (desbloqueamos las ya adquiridas) e intentamos un orden distintos hasta que encontramos uno que funciona.

Sorprendentemente, esto puede resultar más eficiente que tomar los bloqueos en un orden global hard-coded , aunque cualquier estrategia de retroceso y volver a intentar tiene que tener cuidado de que no termine con tendencias a problemas de bloqueos paralelos o “livelock” (literalmente “bloqueos vivos”).

Pero podemos dejar todas estas cosas al encargado de la implementación; la clave es que el programador escribe simplemente lock( /* whatever */ ) y está protegido de los detalles de establecer la mejor forma de mantener consistente el orden.

DDJ