400410401. Desarrollo de Mutex en C++, de poco peso y que se pueden inicializar estáticamente

Mi problema original estaba relacionado con la implementación de instancias únicas (Singletons). Los problemas con las Singleton están relacionados con el orden y el tiempo de su inicialización y destrucción, además de con la seguridad de los hilos de dichas operaciones. A pesar de la multitud de técnicas desarrolladas para tratar sobre estas cuestiones, no parece que haya una solución universal – y mucho menos una sencilla.

La Singleton concreta en la que yo estaba trabajando tenía que ser colocada en una biblioteca de bajo nivel, que era utilizada por muchas aplicaciones y otras bibliotecas. Esta limitación descartaba el uso de una variable de ámbito de fichero en C++ como mecanismo para inicializar la Singleton porque no hay manera de garantizar que la inicialización de este tipo de objeto se hace correctamente antes de su primer uso. Para evitar la colaboración activa que resultaría de una inicialización explícita, concluí que la Singleton tenía que ser inicializada al acceder a ella por primera vez.

El patrón de Singleton de Meyers (Listado número 1) reúne este requisito. Cuando se emplea este patrón, la Singleton se inicializa la primera vez que se utiliza, y automáticamente se destruye al concluir el proceso. Unas palabras de aviso: Es necesario, a veces, no sólo garantizar que se destruye una Singleton con la conclusión del proceso, sino además establecer un orden relativo concreto; no era el caso con mi Singleton.

Esta implementación de una Singleton deja sin resolver la cuestión de la seguridad de los hilos. Si hay múltiples hilos que entran en la rutina de instancia simultáneamente, y si esta rutina no se ha ejecutado nunca antes, pueden producirse distintos problemas, dependiendo del compilador y de la plataforma.

Por ejemplo, el constructor de mi Singleton se puede ejecutar en múltiples ocasiones o en ninguna. Como alternativa, se puede ejecutar el constructor exactamente una vez, lo que está bien, pero una de las rutinas de instancia puede retornar antes de que se haya concluido la construcción – lo cual nos lleva a fallos impredecibles y de difícil depurado.

((Los problemas con las Singleton están relacionados con el orden y el tiempo de su inicialización y destrucción))

Como cabía esperar, podemos eliminar esta condición de raza mediante uno de entre varios mecanismos distintos de sincronización. El Listado número 2, por ejemplo, emplea un mutex. En el Listado número 2 no mostré cómo se inicializa la variable mutex. ¡El mutex en sí es una Singleton! Si este mutex tiene un constructor o destructor no trivial, tenemos el problema del huevo y la gallina.

UNIX: Soluciones pthread

La solución del problema de inicialización del mutex en plataformas UNIX no es difícil. La biblioteca pthread disponible en estas plataformas ofrece un mutex que es un tipo POD (Plain Old Data) que necesita sólo una inicialización estática (no en el momento de la ejecución), como en el Listado número 3. Además, la biblioteca pthread proporciona un mecanismo denominado “rutinas once” que pueden también utilizarse para resolver este problema de inicialización (Listado número 4).

Windows: Solución Spin-Lock

Por desgracia, la Singleton que yo estaba implementando tenía que soportar a Windows. Aquí es cuando surgió la principal complicación. Incluso las secciones críticas, que son el mecanismo de sincronización más sencillo disponible en Windows y aplicables a mi Singleton, no soportan la inicialización estática; se necesita hacer una invocación a InitializeCriticalSection En cuanto a las rutinas once, no hay soporte para ellas en la API de Win32.

Indudablemente, podría haber implementado un simple spin-lock (bloqueo de rotación) mediante la familia Interlocked de rutinas an la función Sleep como en el Listado número 5.

El Listado número 5 se puede optimizar más de dos maneras importantes: En primer lugar, podemos reemplazar la variable lock con una variable de control de tres estados (Listado número 6).
– Ningún hilo ha intentado todavía inicializar la Singleton. (Este es el estado inicial)- La Singleton está en proceso de ser inicializada. (Cualquier hilo, excepto el primer hilo que establece la variable de control a este valor, ha de esperar a que se complete la inicialización.)- La inicialización se ha completado.

La introducción de estos tres estados garantiza que, una vez se ha completado la inicialización, no se necesita ninguna rotación, incluso aunque haya múltiples hilos que entren en la rutina Singleton::instance de forma simultánea.

La segunda optimización le permite al intervalo de espera ajustarse de forma dinámica mediante retroceso exponencial (Listado número 7; disponible online, véase www.ddj.com ). Si la inicialización de la Singleton (el constructor de nuestra clase Singleton) tarda relativamente mucho o si hay muchos hilos rotando, la elección de pequeños intervalos de espera puede crear bastantes costes extra.

((Si la inicialización de la Singleton es relativamente rápida, la elección de un intervalo de espera grande provoca un retraso innecesario. Aunque el ajuste dinámico del intervalo de espera no soluciona estos problemas totalmente))

Lo que es más, este problema se ve exacerbado en el momento en que los hilos que están rotando retrasan el progreso del hilo que está realizando la inicialización. En sistemas con una programación de hilos menos sofisticada (Windows 98, por ejemplo) esta deficiencia puede incluso hacer que se pare todo el sistema.

Por otro lado, si la inicialización de la Singleton es relativamente rápida, la elección de un intervalo de espera grande provoca un retraso innecesario. Aunque el ajuste dinámico del intervalo de espera no soluciona estos problemas totalmente, sí que reduce las posibilidades de que se produzcan.

Con estas sustanciales optimizaciones, el método del spin-lock, anuque poco elegante, es aceptable para muchas aplicaciones. No obstante, como yo buscaba una solución genérica con la intención de implementarla en una biblioteca de bajo nivel, utilizada por una amplia gama de aplicaciones y para una variedad de objetos Singleton, el método del spin-lock no me atraía.

Windows: Solución con Mutex denominados

A la búsqueda de una solución mejor, decidí examinar cómo dos bibliotecas Open-Source —Boost.Threads (www.boost.org/doc/html/threads.html) y Pthreads-w32 ( http://sourceware.org/pthreads-win32/) trataban el problema. Aunque ninguna de las dos bibliotecas tiene que ver directamente con las Singleton, cada una de ellas tiene código que implementa el soporte a la rutina-once en Windows. Boost.Threads proporciona un conjunto portátil de primitivas relacionadas con MT que les viene muy bien a los programadores de C++.

Naturalmente, entre las plataformas soportadas por esta biblioteca se incluye la de Windows. Pthreads-w32, por otro lado, implementa una capa compatible con pthread, incluido pthread_once, sobre la API de Windows, lo que simplifica el portado de los programas MT de UNIX a Windows. Mi razonamiento era que, cualquiera que fuera la técnica que utilizara estas bibliotecas para implementar rutinas once en Windows, debería ser posible usar esa misma técnica para implementar mi Singleton.

La técnica que descubrí en Boost.Threads (libs/thread/src/once.cpp bajo el árbol de fuentes Boost ) dependía de una característica especial de Windows que permite que un nombre se asocie con un mutex. Si un hilo (no necesariamente dentro del mismo proceso) crea un mutex con un nombre que ya existe, en lugar de crear un nuevo mutex, el sistema retorna un control al ya existente.

El sistema se asegura además de que el mutex no se destruya siempre y cuando haya controles abiertos al mismo. Por último, el sistema garantiza que la creación de un mutex y el cierre de un control de mutex sean operaciones atómicas. El Listado número 8 (disponible online) muestra cómo un mutex con nombre puede ser usado para implementar nuestra Singleton.

El nombre del mutex está diseñado para que sea único. Si se considera que la cadena “Singleton::instance” no ofrece suficiente garantía frente a las colisiones, se puede utilizar una cadena aleatoria con el método favorito de uno (la cadena que realmente se usó en el código de Boost es “2AC1A572DB6944B0A65C38C4140AF2F4”). Conviene observar también que este código usa la optimización Double-Checked-Lock (www.cs.wustl.edu/~schmidt/PDF/DC-Locking.pdf). Para evitar los distintos problemas con las implementaciones “ingenuas” de esta optimización (www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf ), nos aseguramos de que todo acceso a la bandera se realiza mediante las rutinas que se bloquean entre sí de Windows, que incorporan todas las barreras de memoria necesarias. La invocación InterlockedExchangeAdd(&flag, 0) —una no-opción que incrementa la bandera en 0— es simplemente una forma de usar rutinas que se bloquean entre sí para leer la bandera. (Se puede lograr el mismo efecto de una forma más eficaz con algún ensamblador en línea.).

(Conviene observar también que este código usa la optimización Double-Checked-Lock ([www.cs.wustl.edu/~schmidt/PDF/DC-Locking.pdf) )]

Aunque una buena técnica extraída de la biblioteca Boost.Threads nos permite realizar mejoras en la anterior implementación, eliminando la imprevisibilidad inherente en la rotación, la solución sufre varias deficiencias. Para empezar, los mutex con nombre están pensados para ser usados en la sincronización a través de límites de procesos, en vez de entre hilos dentro del mismo proceso. La manipulación y creación de este tipo de mutex “dentro del proceso” es caro – sustancialmente mucho más que los que se usan para sincronizar hilos.

Lo que es más, con este pesado método, hay que crear al menos una vez un mutex con denominación, incluso cuando no hay ningún tipo de contención – incluso si la aplicación que usa esta Singleton es de un solo hilo. Por último, la generación de un nombre de mutex único desde un puntero es artificial y bastante poco elegante. Teniendo en cuenta los inconvenientes, esta solución, aunque aceptable con muchas aplicaciones, no satisfizo las necesidades de mi biblioteca de infraestructuras reutilizables de grandes prestaciones.

Desarrollo de la clase QLock

A continuación, examiné la biblioteca Pthread-w32. El código que descubrí en la implementación de pthread_once (pthread_once.c, CVS versión 1.16) de esa biblioteca usaba un método radicalmente distinto a cualquiera de las dos técnicas que acabamos de discutir: Si múltiples hilos entran en pthread_once de forma simultánea, el primer hilo que tiene que esperar (el segundo hilo general) crea un objeto de sincronización (un objeto de eventos Windows, en este caso). El último hilo en dejar la rutina destruye el objeto.

Un recuento de referencias atómicas registra el número de hilos que se han visto implicados. Todos los problemas de los dos métodos anteriores parecían haberse evitado. Por desgracia, un examen más atento del código descubrió una condición de raza. Después de unos cuantos intentos para arreglar el problema (véase el archivo de la lista de correos pthread-w32 si interesan los detalles; sources.redhat.com/ml/pthreads-win32/), se fue haciendo evidente que este enfoque general tiene errores de base y no se puede arreglar.

Aunque el recuento de las referencias empleado por la implementación pthread_once no funcionó, al tratar de arreglarlo me vinieron varias ideas. ¿Y qué pasaría si cada hilo que tenía que ser suspendido (esperando a que otro hilo completara la inicialización de una Singleton), creaba y luego destruía su propio objeto de sincronización? Por ejemplo, sabía cómo la implementación de los spin-locks de MCS, para reducir la contención, hace que cada hilo espere rotando sobre su propia bandera.

¿Podría usar yo una técnica similar, pero en lugar de rotar, hacer que cada hilo esperara en su propio semáforo u objeto de eventos? Resultó que no sólo era posible hacer que funcionara esta técnica, sino que además el código resultante era bastante sencillo. El Listado número 9 (disponible online) usa esta especializada técnica de espera para implementar mi Singleton.

((Una situación común, en la que parece que QLock es de gran utilidad, es cuando tenemos una gran colección de algún tipo de elementos a los que se accede desde múltiples hilos))

La idea central de este nuevo enfoque está encapsulada en la clase QLock. Cada instancia de esta clase representa un bloqueo contenido en el mutex que se pasaba como un argumento de constructor. El mutex mismo, que está representado por el tipo QLock::Mutex, es sencillamente un puntero, que se fija en cero cuando el mutex no está bloqueado.

Cuando el mutex está bloqueado, señala a la cola de la cola de hilos que están esperando en este mutex. Cada hilo de la cola está representado por la instancia de clase QLock QLock que creó el hilo para conseguir el bloqueo. En otras palabras, el mutex es un puntero a la instancia QLock creado por el último hilo que esperaba en la cola. Esta instancia QLock está vinculada a otra instancia QLock , que fue creada por el hilo anterior de la cola, y así sucesivamente. La instancia QLock a la cabeza de la cola corresponde al hilo que actualmente mantiene el bloqueo.

Un examen más detenido de QLock

La Tabla 1 es un listado de los miembros de datos de clase QLock, mientras que la Tabla 2 es un listado de los valores que pueden tener d_readyFlag y d_nextFlag. El constructor QLock::QLock intercambia atómicamente el puntero mutex para ello. Si el puntero mutex era 0 antes del intercambio, se obtiene el bloqueo y el constructor concluye. Si el puntero mutex no era cero, esta instancia de QLock tiene que ponerse a la cola y esperar a la bandera que esté lista.

El destructor QLock::~QLock, mediante una operación atómica de comparación e intercambio, comprueba si el puntero del mutex contiene el valor de este puntero. Si lo tiene, vuelve a colocar el puntero del mutex en cero, dando salida así al mutex. Si el mutex ya no contiene el valor de este puntero, se ha formado la cola, y el destructor tiene que pasar el bloqueo hasta la siguiente instancia en la cola. El destructor espera primero en d_nextFlag para asegurarse de que se ha fijado el puntero siguiente, y a continuación coloca d_readyFlag.

Los algoritmos utilizados en el constructor/destructor de QLock son básicamente los mismos que los utilizados para bloquear/desbloquear los spin-locks de MCS. Los métodos setFlag y waitOnFlag están en donde realizamos nuestra importante desviación de los bloqueos de MCS. En lugar de hacer rotar (como es lo normal con un spin-lock), la rutina waitOnFlag:
-# Crea un objeto de eventos.
-# Comprueba atómicamente la bandera que no se ha colocado e instala el control del objeto de eventos en la bandera.

Vamos ahora a comparar nuestra solución basada en QLock para el problema de Singleton con la dos soluciones anteriores (la basada en spin-lock y la basada en denominación de mutex ) Al igual que con la solución basada en denominación de mutex, evitamos el imprevisible comportamiento del spin-lock: En lugar de rotar, los hilos en espera son suspendidos por el núcleo, y continúan tan pronto como el mutex está disponible.

Además, evitamos los problemas de la denominación de mutex: Los objetos de eventos que se usan para la sincronización son de proceso local y no necesitan de nombres artificiales, y se crean sólo cuando hay que suspender los hilos por la contención. Cuando no hay contención (cuando sólo un hilo entra en el método Singleton::instance en el momento de la inicialización) no se crea ningún objeto de sincronización. El coste extra es sólo el de unas cuantas operaciones atómicas.

Observaciones

Tras usar los mecanismos de sincronización implementados por la clase QLock para solucionar el problema de la Singleton en Windows (y en términos más generales, el problema con la inicialización estática de mutex en Windows), descubrí que QLock tiene alguna otras propiedades importantes que lo hacen atractivo para otras aplicaciones (incluidas las de UNIX).

QLock::Mutex tiene una huella de memoria pequeña (un puntero), y un pequeño coste de inicialización (el de inicializar un puntero con 0). Además, cuando no hay contención, QLock es rápido. Si la espera no es necesaria, el bloqueo de un QLock sólo necesita una instrucción atómica y ninguna invocación al sistema. Si no hay hilos en espera, el desbloqueo es también una sola instrucción.

Lo que es más, cuando no hay contención, el coste de construir objetos de eventos (o semáforos en UNIX) puede ser eliminado virtualmente mediante un grupo libre de bloqueos de objetos de eventos asignados. Este grupo funciona especialmente bien porque el número de objetos de eventos que se requieren nunca excede el número de hilos en espera – un número inherentemente pequeño.

Una situación común, en la que parece que QLock es de gran utilidad, es cuando tenemos una gran colección de algún tipo de elementos a los que se accede desde múltiples hilos. Para incrementar la concurrencia, puede ser lógicamente posible y conveniente mantener un mutex por elemento de la colección (en vez de mantener un único mutex para toda la colección).

Ocurre con frecuencia, no obstante, que la huella de la memoria y el coste de la inicialización de un mutex estándar o una sección fundamental serían prohibitivos por el tamaño (a veces muy grande) de la colección. QLock, por su pequeño tamaño y su prácticamente inexistente coste de inicialización, puede ofrecer una solución viable para el bloqueo fino. DDJ

(Vladimir Kliatchko es arquitecto directivo y jefe de infraestructuras de la aplicación en Bloomberg LP. Se puede contactar con él en [vkliatchko@bloomberg.net. )]