No más bloqueos: Técnicas avanzadas para evitar y detectar interbloqueos en aplicaciones .NET

Noviembre de 2005

Joe Duffy

En este artículo se analizan los siguientes temas:
*Descripción de cómo se producen los interbloqueos
*Evitar los interbloqueos aplicando nivelación de bloqueo
*Detección e interrupción de interbloqueos
*Examen de un host de CLR personalizado para la detección de interbloqueos

En este artículo se utilizan las siguientes tecnologías: .NET Framework, C#, C++

Descarga de código disponible en: Deadlocks.exe (188 KB)

Resumen: El bloqueo de una aplicación es una de las situaciones más frustrantes que un usuario puede vivir. Los bloqueos son muy difíciles de encontrar antes de su envío y todavía más difíciles de depurar después de haber implementado una aplicación. A diferencia de un error, es posible que el bloqueo de una aplicación no produzca un volcado ni desencadene una lógica de error personalizado. Los usuarios suelen cerrar una aplicación congelada antes de capturar dicha información, lo que significa que no hay ningún seguimiento de la pila que ayude a encontrar el origen del problema.

En esta página

	Introducción
	Interbloqueos 101
	Otros ejemplos sutiles de interbloqueo
	Evitar los interbloqueos aplicando nivelación de bloqueo
	Detección e interrupción de interbloqueos
	Algoritmos
	Análisis mediante las API de alojamiento
	Construcción de gráfico y recorrido de la espera
	Host personalizado para interbloqueos en acción
	Conclusión
	Acerca del autor

Introducción

Los bloqueos pueden ser temporales o permanentes. Pueden deberse a una E/S lenta, a un algoritmo costoso a nivel de equipos o a un acceso a los recursos mutuamente excluyente, lo que en todos los casos produce una disminución de la capacidad de respuesta general de una aplicación. El código que bloquea la ejecución del subproceso de una interfaz gráfica de usuario puede impedir que una ventana procese la intervención entrante del usuario y los mensajes generados por el sistema, lo que provocará que la aplicación "No responda". Los programas que no tienen interfaz gráfica de usuario también pueden experimentar problemas con su capacidad de respuesta cuando utilizan recursos compartidos o cuando efectúan comunicación entre subprocesos, entre procesos o entre equipos. Es evidente que el peor tipo de bloqueo es aquél que nunca se recupera, es decir, un interbloqueo.

La ingeniería en aplicaciones simultáneas de gran tamaño que utilizan el conjunto de herramientas de memoria compartida de Windows® estándar para subprocesos y bloqueos desempeña un papel mucho más importante de lo que pudiera parecer a simple vista. No bloquear la memoria en movimiento puede llevar a condiciones de carrera que, en el mejor de los casos, originan errores y, en el peor, datos dañados. Existe un equilibrio entre el rendimiento secuencial, con corrección (granularidad general de los bloqueos), y la escalabilidad paralela (granularidad concreta de los bloqueos). Los distintos segmentos de código, que adquieren y liberan bloqueos a granularidades variables, tienden a interactuar unos con otros de manera imprevista. Si suponemos que el sistema no hace nada por mitigar los interbloqueos, en este caso, un sutil paso en falso puede estropear la compleja maquinaria de su programa.

Los modelos de programación con memoria compartida que existen actualmente exigen que el programador considere la posible intercalación de instrucciones durante toda la ejecución del programa. Si ocurre algo inesperado, puede ser extremadamente difícil reproducir los pasos que originaron el incidente. Los interbloqueos, a pesar de ser más obvios que las carreras (en el caso más simple, el programa sencillamente se detiene en seco), siguen siendo difíciles de ubicar y eliminar. Puede encontrar un pequeño número de ellos por accidente en los conjuntos de prueba funcional habituales, pero lo más probable es que muchos de ellos permanezcan aletargados en el producto de envío, esperando sorprender a un cliente desprevenido. Es más, cuando logre hallar la causa, es posible que ya esté en un gran aprieto.

Puede luchar contra los interbloqueos mediante una combinación de prácticas de bloqueo disciplinado y de agresivas pruebas de esfuerzo en distintas plataformas de hardware. La primera de estas disciplinas constituye el tema principal de este artículo. Pero antes, revisemos los aspectos básicos de los interbloqueos.

Principio de la página

Interbloqueos 101

Un interbloqueo se produce cuando un conjunto de usuarios simultáneos se esperan mutuamente para poder progresar antes de que cualquiera de ellos pueda progresar. Parece una paradoja. Y lo es. Para que se produzca un interbloqueo deben existir cuatro propiedades generales:

Exclusión mutua Cuando un subproceso posee ciertos recursos, otro no puede adquirirlos. Esto es lo que sucede con la mayoría de las secciones críticas, pero también se aplica a las interfaces gráficas de usuario en Windows. Cada ventana pertenece a un único subproceso, que es el único responsable de procesar los mensajes entrantes. Si no lo hace, se origina una pérdida de la capacidad de respuesta, en el mejor de los casos, y un interbloqueo, en casos extremos.

Un subproceso que posee un recurso puede originar una espera ilimitada Por ejemplo, cuando un subproceso ha entrado en una sección crítica, el código suele tener la libertad para tratar de adquirir otras secciones críticas mientras ésta es retenida. Normalmente, si la sección crítica objetivo ya es retenida por otro subproceso, se producirá un bloqueo.

No es posible quitar recursos a la fuerza a sus actuales propietarios En ciertas situaciones, es posible robar recursos si se observa contención, como en el caso de complejos sistemas de administración de bases de datos (DBMS). En general, éste no es el caso para las primitivas de bloqueo disponibles para el código administrado en la plataforma Windows.

Una condición de espera circular Se produce una espera circular si una cadena de dos o más subprocesos espera un recurso retenido por el siguiente miembro de la cadena. Observe que en el caso de bloqueos no reentrantes, un solo subproceso puede provocar un interbloqueo consigo mismo. La mayoría de los bloqueos son reentrantes, lo que elimina esta posibilidad.

Cualquier programador que haya trabajado con algoritmos pesimistas debería saber cómo se produce un interbloqueo. Un algoritmo pesimista detecta una contención cuando se trata de adquirir un recurso compartido y, generalmente, su respuesta será esperar hasta que éste pase a estar disponible (por ejemplo, el bloqueo). Compare esta situación con los algoritmos optimistas, que tratan de progresar con el riesgo de que la contención sea detectada en forma posterior, como cuando una transacción trata de obtener una confirmación. Por lo general, es más fácil programar y razonar en función del pesimismo. Éste es considerablemente más común en la plataforma en comparación con las técnicas optimistas, tomando, por lo general, la forma de un monitor (un bloqueo de C# o un bloqueo de SyncLock de Visual Basic®), una exclusión mutua o una CRITICAL_SECTION de Win32®.

Los algoritmos libres de bloqueo o con base interbloqueada que pueden detectar y responder a la contención son relativamente comunes para el software de nivel de sistemas; estos algoritmos suelen evitar por completo la entrada en una sección crítica en la ruta de acceso rápida y eligen lidiar con el bloqueo activo, no con el interbloqueo. Sin embargo, un bloqueo activo constituye también un desafío para un código paralelo y es provocado por contención concreta. El resultado detiene los progresos de manera muy similar a un interbloqueo. Para ilustrar los efectos del bloqueo activo, imagine a dos personas que tratan de pasar por una entrada: ambas se mueven de un lado al otro tratando de ocupar el camino de la otra, pero lo hacen de tal forma que ninguna de las dos avanza.

Para ilustrar aún más la forma en que podría producirse un interbloqueo, considere la siguiente secuencia de acontecimientos:

En este punto, ambos subprocesos se bloquean y ya no se reactivan. El código C# en la figura 1 ilustra esta situación.

La figura 2 detalla los seis posibles resultados si t1 y t2 entran en una condición de carrera entre ellos. En todos los casos se produce un interbloqueo, salvo en dos: 1 y 4. Aunque resulta tentador, no se puede concluir que se producirá un interbloqueo 2 de cada 3 veces (dado que 4 de los 6 resultados llevaron a un interbloqueo), porque las pequeñas ventanas de tiempo necesarias para producir los casos 2, 3, 5 ó 6 estadísticamente no se producirán con la misma frecuencia que los casos 1 y 4.

Independientemente de las estadísticas, si escribe un código como éste es evidente que el programa pende de un hilo. Tarde o temprano, el subprograma tenderá a acertar uno de estos cuatro casos de interbloqueos; quizás debido a un nuevo hardware que el cliente ha comprado y que nunca se utilizó para probar el software, o a un cambio de contexto entre dos instrucciones específicas que se originan a partir de un subproceso de alta prioridad que pasa a ser ejecutable, lo que detiene el programa en seco.

El ejemplo recién mostrado es fácil de identificar y razonablemente fácil de corregir: simplemente vuelva a escribir t1 y t2 de tal modo que adquieran y liberen los bloqueos en un orden coherente. Es decir, escriba el código de tal forma que tanto t1 como t2 adquieran A y luego B, o viceversa, lo que elimina este abrazo mortal. Pero considere un caso más sutil de protocolo de bloqueo propenso a interbloqueo:

void Transfer(Account a, Account b, decimal amount) {
  lock (a) {
    lock (b) {
      if (a.Balance < amount)
        throw new InsufficientFundsException();
      a.Balance -= amount;
      b.Balance += amount;
    }
  }
}

Por ejemplo, si alguien tratara de transferir $500 desde la cuenta nº 1234 hacia la cuenta nº 5678 al mismo tiempo que alguien más estuviese tratando de transferir $1.000 desde la cuenta nº 5678 hacia la cuenta nº 1234, es muy probable que se produjese un interbloqueo. Un uso de alias de referencia como éste, donde varios subprocesos hacen referencia al mismo objeto mediante distintas variables, puede causar dolores de cabeza y es una práctica extraordinariamente común. Del mismo modo, las llamadas a métodos virtuales implementados en código de usuario pueden llevarlo a una pila de llamadas que adquiere ciertos bloqueos de manera dinámica y en un orden impredecible, lo que hace que un subproceso retenga simultáneamente combinaciones de bloqueos imprevistas y se origine un riesgo real de interbloqueo.

Principio de la página

Otros ejemplos sutiles de interbloqueo

El riesgo de un interbloqueo no se limita a secciones críticas mutuamente excluyentes. Existen formas aún más sutiles en las que podría producirse un interbloqueo real en el programa. Los interbloqueos parciales (donde una aplicación pareciera estar interbloqueada, pero en realidad sólo se ha estancado al realizar una operación de alta latencia o contenciosa) también son problemáticos. Por ejemplo, los algoritmos que requieren muchos cálculos y que se ejecutan mediante el subproceso de la interfaz gráfica de usuario pueden llevar a una pérdida total de la capacidad de respuesta. En este caso, hubiera sido una mejor opción programar el trabajo con ThreadPool (de preferencia, con el nuevo componente BackgroundWorker de .NET Framework 2.0).

Es importante entender las características de rendimiento de cada método al que el programa llama, pero en la práctica esto es muy difícil. Una operación que invoca a otra cuyas características de rendimiento presentan gran variedad puede llevar a una latencia, bloqueo y nivel de intensidad de CPU impredecibles. La situación empeora si, cuando esto sucede, el autor de la llamada retiene un bloqueo exclusivo sobre un recurso, lo que serializa el acceso a los recursos compartidos mientras se lleva a cabo alguna operación arbitrariamente costosa. Partes de la aplicación podrían tener un rendimiento excelente en escenarios comunes, pero esto podría cambiar drásticamente si surgiera alguna condición ambiental. La E/S de la red es un muy buen ejemplo: tiene en promedio una latencia moderada a alta, pero se deteriora considerablemente cuando una conexión de red se satura o deja de estar disponible. Si ha incrustado lotes de E/S de red en la aplicación, ojalá haya probado cuidadosamente la forma en que el software funciona (o no funciona) cuando desconecta el cable de red del equipo.

Cuando el código se ejecuta en un subproceso con apartamento de un único subproceso (STA), se produce el equivalente a un bloqueo exclusivo. Al interior de un STA, solamente un subproceso puede actualizar una ventana de interfaz gráfica de usuario o ejecutar de una sola vez un código dentro de un componente COM de subprocesos de tipo apartamento. Dichos subprocesos poseen una cola de mensajes en la cual el sistema y otras partes de la aplicación colocan la información que se va a procesar. Las interfaces gráficas de usuario utilizan esta cola para obtener información, tales como solicitudes de volver a dibujar, la entrada de un dispositivo que se va a procesar y solicitudes de cierre de ventana. Los servidores proxy COM utilizan la cola de mensajes para realizar la transición de las llamadas a métodos entre apartamentos en el apartamento con el cual un componente tiene afinidad. Todo código que se ejecute en un STA es responsable de proporcionar la cola de mensajes (buscar y procesar nuevos mensajes con el bucle de mensajes), de lo contrario la cola se obstruye, provocando la pérdida de la capacidad de respuesta. En términos de Win32, esto significa usar MsgWaitForSingleObject, MsgWaitForMultipleObjects (y sus homólogos Ex) o las API CoWaitForMultipleHandles. Una espera sin suministro como WaitForSingleObject o WaitForMultipleObjects (y sus homólogos Ex) no proporcionará los mensajes entrantes.

En otras palabras, el "bloqueo" del STA sólo se puede liberar proporcionando la cola de mensajes. Las aplicaciones que efectúan operaciones cuyas características de rendimiento varían enormemente según el subproceso de la interfaz gráfica de usuario sin suministro de mensajes (como aquéllas indicadas anteriormente) pueden experimentar un interbloqueo con gran facilidad. En el caso de los programas bien escritos hay dos opciones: programar el trabajo de larga ejecución para que se realice en otro lugar o proporcionar los mensajes cada vez que éstos se bloqueen a fin de evitar este problema. Por suerte, CLR efectúa el suministro cada vez que se bloquea un código administrado (mediante una llamada a un recurso contencioso como Monitor.Enter, WaitHandle.WaitOne, FileStream.EndRead, Thread.Join, etc.), lo que ayuda a mitigar este problema. Sin embargo, muchos códigos (incluso parte de .NET Framework) terminan el bloqueo en un código no administrado, en cuyo caso el autor del código de bloqueo puede o no haber agregado una espera de suministro.

A continuación se presenta un clásico ejemplo de un interbloqueo inducido por un STA. Un subproceso que se ejecuta en un STA genera gran cantidad de instancias del componente COM de subprocesos de tipo apartamento y, en forma implícita, sus correspondientes Contenedores que se pueden llamar en tiempo de ejecución (RCW). Desde luego, CLR debe finalizar los RCW cuando éstos se vuelvan inaccesibles o cuando se pierdan. Pero el subproceso del finalizador de CLR siempre se une al Apartamento multiproceso (MTA) del proceso, lo que significa que debe utilizar un servidor proxy para el STA a fin de solicitar la Liberación de los RCW. Si el STA no realiza suministro de mensajes para recibir el intento del finalizador por invocar el método Finalize mediante un RCW determinado (debido quizás a que ha elegido aplicar un bloqueo a través de una espera sin suministro), el subproceso del finalizador se estancará. Se bloquea hasta que el STA se desbloquee y suministre mensajes. Si el STA no vuelve a suministrar mensajes, el subproceso del finalizador nunca efectuará ningún progreso y con el tiempo se producirá una acumulación lenta y silenciosa de todos los recursos finalizables. A su vez, esto puede llevar a un posterior error de memoria insuficiente o a una iteración del proceso en ASP .NET. Obviamente, ambos resultados son insatisfactorios.

Marcos de alto nivel como Windows Forms, Windows Presentation Foundation y COM ocultan gran parte de la complejidad de los STA, pero de todas maneras pueden presentar errores de manera impredecible, incluido el interbloqueo. Los contextos de sincronización COM presentan desafíos similares, pero sutilmente distintos. Además, muchos de estos errores sólo se producirán en una pequeña fracción de las ejecuciones de prueba y con frecuencia sólo bajo mucha presión.

Por desgracia, distintos tipos de interbloqueos requieren distintas técnicas de combate. El resto de este artículo se concentrará exclusivamente en los interbloqueos de sección crítica. CLR 2.0 incluye herramientas útiles para capturar y depurar los problemas de transición de STA. Se creó un nuevo Ayudante para la depuración administrada (MDA), ContextSwitchDeadlock, con el fin de supervisar los interbloqueos inducidos por las transiciones entre apartamentos. Si la transición demora más de 60 segundos en finalizar, el CLR supone que el STA de recepción está interbloqueado y activa el MDA. Para obtener más información sobre cómo habilitar este MDA, consulte la documentación de MSDN®.

Existen dos estrategias generales útiles para abordar los interbloqueos basados en sección crítica.

Evitar los interbloqueos Elimina completamente una de las cuatro condiciones antes mencionadas. Por ejemplo, se puede permitir que múltiples recursos compartan un mismo recurso (lo cual no suele ser posible debido a la seguridad del subproceso), evitar totalmente los bloqueos cuando se retienen los bloqueos o eliminar las esperas circulares. Esto requiere cierta disciplina estructurada, la cual, por desgracia, puede agregar una notable sobrecarga a la creación del software simultáneo.

Detectar y mitigar los interbloqueos La mayoría de los sistemas de bases de datos utilizan esta técnica para las transacciones de usuarios. Detectar un interbloqueo es sencillo, pero responder a él es más difícil. En términos generales, los sistemas de detección de interbloqueos seleccionan a una víctima e interrumpen el interbloqueo obligándola a anular y liberar sus bloqueos. Dichas técnicas en códigos arbitrarios administrados podrían llevar a la inestabilidad, de modo que estas técnicas se deben emplear con sumo cuidado.

Muchos desarrolladores son conscientes de la posibilidad de que se produzcan interbloqueos a nivel teórico, pero pocos saben cómo combatirlos en forma seria. Demos un vistazo a algunas soluciones que pertenecen a estas dos categorías.

Principio de la página

Evitar los interbloqueos aplicando nivelación de bloqueo

Un enfoque común para combatir los interbloqueos en sistemas de software de grandes dimensiones es una técnica llamada nivelación de bloqueo (conocida también cómo jerarquía de bloqueo u ordenación de bloqueo). Esta estrategia factoriza todos los bloqueos a niveles numéricos, lo que permite que componentes en capas específicas de la arquitectura del sistema adquieran los bloqueos sólo en los niveles inferiores. Por ejemplo, en la muestra original, podría asignar el bloqueo A a un nivel 10 y el bloqueo B a un nivel 5. Entonces, es legal que un componente adquiera A y luego B, ya que el nivel de B es inferior al de A, pero la acción inversa está totalmente prohibida. Esto elimina la posibilidad de un interbloqueo. Una disciplina de ingeniería ampliamente aceptada es la factorización correcta de las dependencias de la arquitectura del software.

Desde luego, la idea fundamental de nivelar el bloqueo presenta algunas variantes. He implementado una de estas variantes en C#, disponible en la descarga de código para este artículo. Una instancia de LeveledLock corresponde a una única instancia de bloqueo compartido, muy similar a un objeto en el cual se efectúan los métodos Enter y Exit a través de la clase System.Threading.Monitor. Al momento de la instancia, se asigna un bloqueo a un nivel basado en int:

LeveledLock lockA = new LeveledLock (10);
LeveledLock lockB = new LeveledLock (5);

Un programa normalmente declararía todos sus bloqueos en una ubicación central, por ejemplo, a través de campos estáticos a los que el resto del programa tiene acceso.

Las implementaciones de los métodos Enter y Exit exigen un objeto de supervisión privada subyacente. Además, el tipo hace un seguimiento de la adquisición de bloqueo más reciente mediante el Almacenamiento local de subproceso (TLS), de modo que éste pueda garantizar que no habrá bloqueos que infrinjan la jerarquía de bloqueo. Por lo tanto, se puede eliminar totalmente la posibilidad de que alguien adquiera accidentalmente B y luego A (en el orden incorrecto), lo que elimina las probabilidades de espera circular y, por consiguiente, cualquier posibilidad de un interbloqueo:

// Thread 1
void t1() {
  using (lockA.Enter()) {
    using (lockB.Enter()) {
      /* ... *
} } }

// Thread 2
void t2() {
  using (lockB.Enter()) {
    using (lockA.Enter()) {
      /* ... */
} } }

Tratar de ejecutar t2 generará una LockLevelException que se origina en la llamada a lockA.Enter, lo que indica que se infringió la jerarquía de bloqueo. Es evidente que debe utilizar pruebas agresivas para encontrar y corregir todas las infracciones de la jerarquía de bloqueo antes de enviar el código. Una excepción no controlada sigue siendo una experiencia insatisfactoria para los usuarios.

Observe que el método Enter devuelve un objeto IDisposable, lo que le permite utilizar una instrucción using de C# (muy similar a un bloqueo); la que implícitamente llama al método Exit cuando se abandona el ámbito. Existe un par de otras opciones cuando se crea una instancia de nuevo bloqueo, que están disponibles mediante parámetros de constructor: el parámetro reentrante indica si es posible volver a adquirir el mismo bloqueo cuando ya está retenido y es verdadero en forma predeterminada; el parámetro de nombre es opcional y le permite otorgar un nombre al bloqueo para depurarlo mejor.

De manera predeterminada, no se pueden adquirir bloqueos entre niveles; en otras palabras, si retiene el bloqueo A en un nivel 10 y trata de adquirir el bloqueo C en un nivel 10, su intento producirá un error. Permitir esto infringiría directamente la jerarquía de bloqueo, porque dos subprocesos podrían tratar de adquirir bloqueos en el orden contrario (A y luego C, en contraposición de C y luego A). Puede anular esta directiva especificando "verdadero" para una sobrecarga del método Enter que asuma el parámetro permitIntraLevel. Sin embargo, una vez hecho esto, vuelve a surgir la posibilidad de que se produzca un interbloqueo. Revise cuidadosamente el código para garantizar que esta infracción explícita de la jerarquía de bloqueo no origine un interbloqueo. No obstante, sin importar cuánto trabaje aquí, esto nunca será tan infalible como un estricto protocolo de nivelación de bloqueo. Utilice esta característica con suma precaución.

Aunque la nivelación de bloqueo funcione, esto no significa ausencia de desafíos. La composición dinámica de los componentes del software puede llevar a errores de tiempo de ejecución inesperados. Si un componente de nivel bajo retiene un bloqueo y efectúa una llamada de método virtual a un objeto suministrado por el usuario y el objeto de ese usuario trata de adquirir un bloqueo de nivel superior, se generará una excepción por infracción a la jerarquía de bloqueo. No se producirá un interbloqueo, pero sí un error de tiempo de ejecución. Éste es uno de los motivos que hacen que realizar llamadas a métodos virtuales mientras se retiene un bloqueo generalmente se considere una mala práctica. Aunque esto sigue siendo mejor que correr el riesgo de un interbloqueo, constituye la razón primaria por la cual las bases de datos no emplean esta técnica: deben habilitar una composición enteramente dinámica de transacciones de usuario.

En la práctica, muchos sistemas de software terminan con montones de bloqueos en el mismo nivel y se encontrarán varias llamadas que utilizan permitIntraLevel. Esto ocurre rara vez, no porque los desarrolladores hayan sido muy inteligentes o cuidadosos, sino más bien porque la nivelación de bloqueo es una práctica difícil y relativamente onerosa de seguir. Resulta más fácil aceptar conscientemente el riesgo de un interbloqueo o fingir que no existe (suponer que lo más probable es que éste no aparezca en las pruebas ni siquiera en su entorno natural), que pasar horas refactorizando correctamente las dependencias del código para efectuar un trabajo único de adquisición de bloqueo. No obstante, es posible utilizar el bloqueo disciplinado, por ejemplo, minimizar el tiempo de retención de un código, invocar solamente el código sobre el cual se tiene control estático y hacer copias defensivas de los datos cuando sea necesario, para simplificar nuestras vidas dentro de los confines de una jerarquía de bloqueo.

Muchos sistemas de nivelación de bloqueo son desactivados en versiones no depuradas para evitar la pérdida de rendimiento relacionada con el mantenimiento e inspección de los niveles de bloqueo en tiempo de ejecución. Pero esto significa que se debe probar la aplicación para descubrir todas las infracciones al protocolo de bloqueo. La composición dinámica hace que esto sea increíblemente difícil. Si desactiva la nivelación de bloqueo durante el envío, un caso omitido puede originar un interbloqueo real. Un sistema de nivelación de bloqueo ideal detectaría y evitaría la infracción a la jerarquía en forma estática a través de un compilador o de compatibilidad con análisis estático. Existe una investigación disponible que utiliza esas técnicas, pero, por desgracia, no existen productos convencionales que se puedan utilizar para aplicaciones administradas. En lugar de evitar el interbloqueo, a veces se puede utilizar una segunda técnica llamada detección de interbloqueo.

Principio de la página

Detección e interrupción de interbloqueos

Las técnicas analizadas hasta este momento son útiles para evitar totalmente los interbloqueos. Pero muchos códigos ya escritos podrían no prestarse para adoptar la nivelación de bloqueo de manera sistemática. Por lo general, cuando se produce un interbloqueo, éste se manifiesta como un bloqueo que puede o no hacer que se capture o informe de datos erróneos. Pero idealmente, si el sistema no pudiera evitarlos en su totalidad, detectaría un interbloqueo si éste ocurriera y lo informaría en forma oportuna, para que se pudiera corregir el error. Esto incluso es posible sin adoptar la nivelación de bloqueo en las aplicaciones.

Aunque todas las bases de datos modernas utilizan detección de interbloqueo, emplear las mismas técnicas en aplicaciones administradas arbitrariamente es más complicado en la práctica. Cuando existen transacciones de bases de datos en competencia que tratan de adquirir bloqueos en una forma que pudiera llevar a un interbloqueo, el DBMS puede eliminar aquélla con menos tiempo y recursos invertidos hasta ahora, habilitando al resto de las transacciones involucradas para que continúen como si nada hubiese pasado. El DBMS deshará automáticamente las operaciones de la víctima del interbloqueo. Entonces la aplicación que invoca la llamada de la base de datos puede responder, ya sea, recuperando la transacción, o bien, dando al usuario la opción de volver a intentar, cancelar o modificar su acción. Por ejemplo, en el caso de un sistema de emisión de boletos, un interbloqueo podría significar que un boleto reservado fuese entregado a otro cliente para mantener su progreso, en cuyo caso el usuario podría tener que reiniciar la transacción de reserva del boleto.

Sin embargo, es probable que una aplicación administrada más sencilla (que no se haya escrito para la lidiar con los errores de interbloqueo originados por adquisiciones de bloqueo) no esté preparada para responder de manera inteligente a una excepción generada por un intento de adquisición de bloqueo. Detener el proceso es prácticamente lo único que se puede hacer.

El código administrado que se aloja en SQL Server™ 2005 cuenta con una función de detección de interbloqueo similar a la que describiré a continuación. Dado que todo código administrado está contenido implícitamente en una transacción, esto funciona muy bien junto con la detección normal de interbloqueo basada en datos de SQL Server.

Se puede escribir un código administrado sofisticado para advertir sobre interbloqueos y para tratar de retirar uno por uno los bloqueos que se han acumulado. Por ejemplo, si un código retiene los bloqueos A y B, y recibe un error de interbloqueo cuando trata de adquirir C, éste puede deshacer los cambios introducidos desde la adquisición de B, liberar B, renunciar a la ejecución (de modo que otros subprocesos puedan progresar), volver a adquirir B, realizar los cambios deshechos previamente y luego intentar la adquisición de C. Si esto vuelve a producir un error debido al interbloqueo, puede deshacer todo hasta la adquisición de A y volver a intentarlo.

La interfaz de alojamiento de CLR permite agregar lógica personalizada para la adquisición y liberación de monitores. He utilizado esta capacidad para construir un nuevo host de muestra para efectuar la detección y migración de interbloqueos (que se incluye en la descarga de código). Ahora revisaremos este host y demostraremos cómo podría funcionar la detección de interbloqueos en la práctica.

Principio de la página

Algoritmos

Existen dos técnicas ampliamente aceptadas para la detección de interbloqueos: detección basada en tiempo de espera y detección basada en gráfico.

Con la detección basada en tiempo de espera, a la adquisición de un bloqueo o recurso se le asigna un tiempo de espera que es mucho mayor al esperado en caso de que no exista interbloqueo. Si se excede ese tiempo de espera, significa que hay un error con el autor de la llamada. En ocasiones, el error causa una excepción, mientras que en otras, la función sólo devuelve un valor falso (como Monitor.TryEnter), lo que permite que el programa del usuario haga algo al respecto. El espacio de nombres System.Transactions utiliza este modelo para TransactionScopes, anulando de manera predeterminada cualquier transacción que se ejecute durante 60 segundos o más.

La principal desventaja de este enfoque es que, por lo general, un interbloqueo permanecerá sin ser detectado por más tiempo del que debiera o que transacciones legales pero largas serán eliminadas puesto que parecen estar interbloqueadas. Además, las funciones que dejan que el programador decida cómo responder son propensas a errores; el desarrollador de una aplicación deficiente rara vez conoce la respuesta correcta y podría simplemente tratar de volver a adquirir el bloqueo (sin considerar que eso podría llevar a un bucle infinito inducido por un interbloqueo).

Con la detección basada en gráfico, si se tiene una lista de usuarios que esperan activamente y una lista de los recursos que posee cada usuario, puede elaborar un gráfico que refleje quién espera a quién. Si hace esto y detecta un ciclo en el gráfico, se ha producido un interbloqueo (a menos que alguien en el ciclo tenga planeado un tiempo de espera y podría interrumpir el interbloqueo a voluntad). Ésta es una estrategia infalible, pero puede ser costosa en términos de impacto de tiempo de ejecución en las adquisiciones de bloqueo.

En muchos casos, una combinación de técnicas puede llevar a los mejores resultados. Si se produce un tiempo de espera, puede realizar una detección basada en gráfico. En general, esto evita una costosa detección, en que la adquisición se produce antes de que se supere el tiempo de espera. Esto es lo que implementé.

Antes de profundizar en la implementación del host personalizado, revisemos el algoritmo para la construcción de un gráfico de espera y la detección de interbloqueos. La figura 3 describe este proceso.

La directiva que usaré para la interrupción del interbloqueo (por ejemplo, si el Paso 5 encuentra un interbloqueo) es eliminar la tarea incorrecta cuya adquisición habría provocado el interbloqueo. Ésta es la estrategia más simple y la menos costosa, pero no es tan inteligente como la mayoría de los DBMS, que tratan de optimizar el rendimiento general del sistema eliminando la transacción en el gráfico con el menor esfuerzo posible. Dado que medir el trabajo es más difícil para los programas administrados en forma arbitraria que para los sistemas de transacción, he elegido la estrategia más simple. (Una estrategia alternativa e interesante sería cambiar el host para usar una técnica alternativa, por ejemplo, usar marcas de hora de adquisición de bloqueo para simular el trabajo, lo que detiene al usuario que adquirió su primer bloqueo en forma más reciente).

Veamos cómo podría funcionar esto. Imagine tres subprocesos (1, 2 y 3) y tres bloqueos (A, B y C) que participan en alguna forma de coordinación de memoria compartida. El subproceso 1 retiene el bloqueo A y tiene bloqueada la adquisición del bloqueo B; el subproceso 2 retiene el bloqueo B y tiene bloqueada la adquisición del bloqueo C; el subproceso 3 retiene el bloqueo C. Entonces, si el subproceso 3 trata de adquirir el bloqueo A, el algoritmo se activa y elabora un gráfico de espera tal como el que aparece en la figura 4. Luego detectaré un ciclo y responderé deteniendo el subproceso 3. Esto libera el bloqueo C, lo que permite que el subproceso 2 se desbloquee, adquiera C, ejecute y libere B. Esto desbloquea el subproceso 1, el cual entonces puede adquirir B y ejecutar hasta finalizar. El subproceso 3 probablemente no esté muy feliz, pero los subprocesos 1 y 2 sí lo estarán (suponiendo que el programa sobrevivió a la excepción).

Figura 4. Ejemplo del gráfico de espera

Naturalmente, este análisis se ha simplificado para ayudar a ilustrar los elementos centrales del algoritmo. No obstante, ahora analizaremos cómo ampliar realmente el CLR para efectuar esta lógica. Esto requerirá algunas tangentes relacionadas con el aprovechamiento de la potencia de las API de alojamiento del CLR.

Principio de la página

Análisis mediante las API de alojamiento

Las API de alojamiento CLR ofrecen formas de incluir los objetos de administrador del usuario para controlar la carga de ensamblado, la administración de memoria, la agrupación de subprocesos y el inicio y cierre, entre otras cosas. En este ejemplo, he utilizado las extensiones de administración de tarea y sincronización. El nuevo host es un ejecutable simple escrito en Visual C++®, deadhost.exe. Cuando se ejecuta, se le transfiere la ruta de acceso del ejecutable administrado para que se ejecute con la detección de interbloqueo activada, junto con todos los argumentos para ese ejecutable. Entonces, éste inicia el proceso de CLR a través de un conjunto de API expuestas desde mscoree.dll, carga el programa objetivo y lo ejecuta. Además, se informa de inmediato de los interbloqueos que se producen.

Por motivos de espacio, he omitido muchos aspectos fundamentales. Para obtener una descripción completa de las capacidades de alojamiento de los CLR, recomiendo conseguir una copia del libro de Steven Pratschner, Customizing the Microsoft .NET Framework Common Language Runtime (Microsoft Press^®, 2005).

Los dos controles de host implementados son DHTaskManager, para la interfaz IHostTaskManager, y DHSyncManager, para la interfaz IHostSyncManager. Las instancias de estos tipos son devueltas al CLR a petición, donde señalan que el CLR efectuará la devolución de llamadas en mi código para ciertos eventos. Desde luego, también he implementado todas las interfaces relacionadas: IHostCrst, IHostAutoEvent, IHostManualEvent, IHostSemaphore e IHostTask. Estas interfaces son más bien de gran tamaño, pero la mayoría de las funciones son traducciones simples a homólogos de Win32. Aquellas funciones que no estén se pueden ignorar con seguridad (afinidad de subprocesos, regiones críticas, anulaciones por retraso) y sólo algunas requieren lógica especializada para la detección de interbloqueos. Analizaré sólo la última.

El CLR implementa la funcionalidad básica de Monitor.Enter y Exit. Para adquisiciones de bloqueos no contenciosos (para monitores sin propietarios), el CLR simplemente hace una rápida comparación e intercambio (InterlockedCompareExchange) en una estructura de datos internos. Si este intento arroja un error, significa que se detectó una contención y que se utilizó un evento de restablecimiento automático de Windows. Este evento sirve entonces para esperar la disponibilidad del bloqueo. Cada vez que alguien libera el bloqueo, ellos definen el evento, el cual afecta a la liberación de un subproceso de espera en el monitor. Éste se creará sin ningún esfuerzo la primera vez que un monitor específico exhiba una contención. Las API de alojamiento permiten controlar la creación del evento y de todas las llamadas para quedar en espera o para definirla. Las API de alojamiento también admiten bloqueos para lector-escritor (System.Threading.ReaderWriterLock), pero por motivos de espacio, omitiré su análisis en este artículo.

A continuación se indica precisamente lo que el host debe hacer: cada vez que el código administrado trate de adquirir un monitor que ya es retenido por alguien más, el CLR debe llamar a IHostSyncManager::CreateMonitorEvent. Esta acción devuelve un objeto cuyo tipo implementa una interfaz simple, similar al controlador de espera del evento (IHostAutoEvent, con los métodos Wait y Set), en el cual puedo colocar lógica de detección personalizada para que se inicie cada vez que alguien bloquee o libere un monitor. Tratar de adquirir un monitor bloqueado da como resultado una llamada al método Wait, mientras que la liberación de un monitor llama al método Set.

Cada vez que se llama al método Wait en un evento devuelto por CreateMonitorEvent, insertaré un registro de espera en una lista de todo el proceso para indicar que el subproceso tiene relación con el bloqueo sobre la adquisición de un monitor. Esto servirá para la posterior detección del interbloqueo.

Luego realizo esperas cronometradas, que se inician a los 100 ms y que retroceden exponencialmente, ejecutando cada vez el algoritmo de detección de interbloqueos. El uso de un tiempo de espera optimiza en primer lugar la situación común en que los bloqueos son retenidos por cortos períodos, lo que evita el costoso proceso de la construcción de gráfico y recorrido de espera. Si alguna vez se descubre un interbloqueo, devuelvo HOST_E_DEADLOCK (0x80131020) al CLR, el cual responde generando una nueva COMException con el mensaje "El subproceso actual ha sido elegido como sujeto del bloqueo interno". Ésta es una nueva funcionalidad de CLR 2.0 que facilita la detección e interrupción de interbloqueos en SQL Server 2005. Ejecuto el programa administrado en su propio subproceso, de modo que cualquiera de las excepciones puede estar totalmente no controlada, lo que activa el depurador asociado (si lo hubiera) en el primer paso, detiene el proceso y luego otorga al usuario final una segunda oportunidad para asociar un depurador. Si adquiero correctamente el monitor, sólo debo quitar el registro de espera y devolver la ejecución al programa administrado.

El algoritmo de detección fue escrito para imponer la menor sobrecarga posible (la mayor parte de ésta es libre de bloqueo), pero sigue habiendo cierta sincronización necesaria mientras se tiene acceso a las estructuras de datos compartidos, como la administración de los registros de espera. La ruta de acceso rápida se produce cuando el programa no tiene que ejecutar esta lógica en absoluto. La mejor situación se presenta cuando el CLR puede adquirir el monitor sin tener que crear un evento y llamar al método Wait, cuando el monitor no está contenido, dado que ambas operaciones requieren costosas transiciones en modo kérnel.

Vale la pena mencionar brevemente algo más. La estructura interna de datos por subproceso KTHREAD de Windows contiene una lista de objetos de distribuidores cuando un subproceso determinado se encuentra actualmente en espera. Los datos se almacenan en una estructura de datos _KWAIT_BLOCK, cuya definición se encuentra en Ntddk.h. En Windows XP, el programa Comprobador de controlador lo utiliza para detectar interbloqueos en los controladores de dispositivos. También podría utilizar estos datos en lugar de insertar registros de espera y esto funcionaría tanto para códigos administrados como no administrados. Sin embargo, hacer esto requiere de cierta manipulación desordenada de la memoria con estructuras de datos internos y una estrategia alternativa para obtener la información del actual propietario. Para este ejemplo, era mucho más simple mantener una lista personalizada de los registros de espera completamente en modo de usuario. Sin embargo, debido a esto, ignoro explícitamente los interbloqueos que surgen de bloqueos internos de CLR, bloqueos no administrados y de Windows, y el bloqueo del cargador del sistema operativo.

Principio de la página

Construcción de gráfico y recorrido de la espera

Cuando el CLR enlaza nuestro host para cualquier acción relacionada con un monitor, lo aborda en términos de cookies (del tipo SIZE_T), las que representan identificadores únicos para cada monitor. He creado un tipo llamado DHContext que suele ser responsable de la implementación de toda la funcionalidad relacionada con la detección de interbloqueos. Una instancia del host comparte el contexto de todo un proceso a través de todos los subprocesos administrados. Un contexto posee una lista de registros de espera, la cual asocia las tareas con las cookies del monitor en las que ellas están esperando:

map<IHostTask*, SIZE_T> *m_pLockWaits

El contexto también ofrece un conjunto de métodos para invocar la detección de los interbloqueos. TryEnter inserta un registro de espera y comprueba si hay interbloqueos, lo que devuelve un puntero hacia un objeto DHDetails, si se encontró uno, o NULL, en caso contrario; y EndEnter efectúa cierto mantenimiento después de la adquisición de un monitor, tal como quitar el registro de espera. Esta arquitectura se muestra en la figura 5.

Figura 5. Arquitectura del host

Cuando el host necesita un evento para un monitor, construyo y suministro uno desde la función DHSyncManager::CreateMonitorEvent. Devuelvo un objeto del tipo DHAutoEvent, una implementación personalizada de la interfaz IHostAutoEvent que hace que la función de destino llame al contexto a través del campo m_pContext de tipo DHContext. El método Wait (consulte la figura 6) es el más interesante, que ejecuta los primeros cuatro pasos indicados en la figura 3.

DHContext::HostWait realiza una espera basada en los indicadores especificados por CLR en el argumento de la opción del método Wait. Éste omite totalmente la detección de interbloqueos si se suministró WAIT_NOTINDEADLOCK y emplea un estilo de suministro y/o espera factible de poner en alerta según sea necesario si se especificó WAIT_MSGPUMP y/o WAIT_ALERTABLE.

Observe que gran parte de este código está dedicado a administrar el tiempo de espera de retroceso exponencial. La parte más interesante es la llamada a TryEnter. Después de insertar el registro de espera, éste delega al método interno DHContext::DetectDeadlock para que realice la lógica de detección real. Si TryEnter devuelve un valor que no es nulo, se ha encontrado un interbloqueo. Se puede responder llamando a la función personalizada PrintDetails para imprimir la información del interbloqueo para la secuencia de error estándar (una solución más sólida escribiría esto en el registro de sucesos de Windows), y luego devolver HOST_E_DEADLOCK para que el CLR pueda reaccionar tal como se analizó anteriormente (generando una COMException).

El algoritmo de detección de interbloqueo detallado anteriormente en este artículo se implementó dentro de la función DetectDeadlock mostrada en el código de la figura 7.

Este código utiliza el método IHostTaskManager::GetCurrentTask para obtener el elemento IHostTask, ICLRSyncManager::GetMonitorOwner, actualmente en ejecución, para recuperar el objeto propietario IHostTask de una cookie de monitor determinada, y la lista m_pLockWaits del contexto para saber en qué tarea espera la adquisición cada monitor. Con esta información a mano, puede implementar completamente la lógica analizada anteriormente. Cualquier ejecución de código a través de este host identificará e interrumpirá correctamente los interbloqueos. Eso es todo: un host de CLR para detección de interbloqueos totalmente funcional.

Desde luego, he omitido más de 1000 líneas de código, de modo que si escribir un host de CLR personalizado le pareció sencillo, olvídelo. No obstante, resulta impresionante la cantidad de posibilidades que pueden surgir de las interfaces de alojamiento del CLR (aparte de los interbloqueos), y va desde la adición de errores hasta pruebas de solidez de la confiabilidad frente a las bastas descargas de AppDomain. Obviamente, implementar host personalizados para los usuarios finales es difícil, pero un host fácilmente puede realizar la detección de interbloqueos, por ejemplo, en sus conjuntos de prueba.

Principio de la página

Host personalizado para interbloqueos en acción

He desarrollado algunas pruebas simples mientras escribía deadhost.exe, que están disponibles en el directorio \tests\ en la descarga de código. Por ejemplo, el programa test1.cs que aparece en la figura 8 se interbloqueará casi un 100% de las veces.

Cuando se ejecuta en el host con la siguiente línea de comando, recibirá una excepción no controlada:

deadhost.exe tests\test1.exe

Si se introduce en el depurador (si ya está asociado o si elige asociarlo en respuesta al error), estará justo en la línea cuya ejecución habría provocado el interbloqueo, donde puede inspeccionar todos los subprocesos involucrados y los bloqueos retenidos, lo que representa una buena forma de comenzar a depurar el problema. Si queda totalmente sin control, verá un mensaje similar a la figura 9 que se imprimió para salida estándar.

El mensaje impreso para la consola no sirve mucho para comprender y depurar el error en profundidad. Le entrega los identificadores de subproceso sin formato que está esperando y las cookies de monitor en las que ellos están esperando. Con más tiempo y esfuerzo, se podría ampliar el host para reunir más datos durante las adquisiciones y liberaciones de bloqueo, e imprimir, por ejemplo, los detalles acerca del objeto utilizado para el bloqueo y la ubicación del código fuente de las adquisiciones. Sin embargo, si dispone sólo de la información que aparece en la figura 8, fácilmente podrá ver que en el subproceso 600 trató de adquirir 18a27c; 5b4 era propietario de 18a27c y estaba esperando el bloqueo 18a24c; pero 18a24c era propiedad de 600, lo que creó el ciclo del interbloqueo. También podrá ver el seguimiento de la pila para la víctima del malvado interbloqueo. La mejor parte es la facilidad con que puede entrar en el depurador y solucionar el problema justo en ese momento.

Principio de la página

Conclusión

En este artículo traté de analizar cierta información básica sobre los interbloqueos y de presentar una visión general de las estrategias para evitarlos y abordarlos. Por lo general, mientras más concreta sea la granularidad de los bloqueos, más de ellos se pueden retener de una sola vez; y mientras más tiempo los retenga, mayor será el riesgo de sufrir un interbloqueo. Un mayor paralelismo en el servidor y equipos de escritorio sólo agravará y expondrá este riesgo, puesto que las instrucciones se van intercalando en formas nuevas e interesantes.

Evitar los interbloqueos se considera ampliamente como la mejor práctica en el caso de los software simultáneos de cuidadoso diseño, mientras que la detección de interbloqueos puede servir para sistemas complejos, integrados en forma dinámica, en especial aquéllos que cuentan con equipamiento para lidiar con errores de bloqueo (tales como sistemas con transacciones y software albergado o con complementos). Es mejor hacer algo para asegurarse de que los interbloqueos no contaminen sus aplicaciones que no hacer nada. Espero que este artículo le ayude a escribir un código libre de interbloqueos y más fácil de mantener, a mejorar la capacidad de respuesta de sus programas y, por último, le ahorre bastante tiempo cuando deba depurar errores basados en la simultaneidad.

Principio de la página

Acerca del autor

Joe Duffy es administrador de programas técnicos del equipo Microsoft Common Language Runtime (CLR), donde trabaja en modelos de programación de simultaneidad para códigos administrados. Joe publica regularmente en www.bluebytesoftware.com/blog y ha escrito un libro que pronto será publicado, Professional .NET Framework 2.0 (Wrox, 2006).

Principio de la página