Capitulo 7. Guía de programación de mutex. Control de concurrencia.

En este capitulo:

¿Momento para introducir un poco de estilo?

La mayoría de los ejemplos presentados en este tutorial eran bastante puntuales y preparados. Cuando diseñamos componentes reusables, o las bibliotecas para una gran aplicación multihilo, una concepción de “vuelo de águila” no es apropiada. El programador o diseñador de componentes necesitan construir clases que tengan seguridad para la programación multihilo en sí mismos, es decir, clases que asuman que podrían ser accedidas desde diferentes hilos y poseer los mecanismos internos necesarios para asegurarse de que los datos se mantengan consistentes. Para hacer esto, el diseñador de componentes necesita estar al tanto de algunos problemas que surgen cuando se usan mutex en aplicaciones cada vez más complicadas. Si esta tratando de escribir una clase que sea segura para funcionar con hilos por primera vez, no se deje desanimar por la aparente complejidad de algunas consideraciones de este capitulo. Con bastante frecuencia se pueden adoptar soluciones simplistas, que nos evitan muchas de las consideraciones mencionadas en este capitulo, a cambio de una menor eficiencia. Nótese que cada vez que se mencione “mutex” de aquí en más, lo mismo vale para las secciones críticas; omitiré mencionar las secciones críticas en cada caso para abreviar.

Deadlock en función del ordenamiento de mutex.

Si un programa posee más de un mutex, entonces será sorprendentemente sencillo provocar un Deadlock, con un código de sincronismo descuidado. La situación más común es cuando existen dependencias cíclicas por el orden en que los mutex son adquiridos. Esto es generalmente conocido en la literatura académica como el problema de la cena de los filósofos. Como vimos antes, el criterio de un Deadlock es que todos los hilos están esperando a otro para liberar el objeto de sincronización. El ejemplo más sencillo de esto es entre dos hilos, uno que quiere adquirir el mutex A antes de adquirir el mutex B y otro que quiere adquirir el mutex B antes de adquirir el mutex A.


Por supuesto, es completamente posible hacer caer un programa en un Deadlock de una manera más delicada con una cadena de dependencias, como la ilustrada más abajo con cuatro hilos y cuatro mutexes, A a D.


Obviamente, situaciones como esta no son aceptables en la mayoría de las aplicaciones. Hay muchas maneras de evitar este problema, y un montón de técnicas para aliviar problemas de dependencia de este tipo, haciendo mucho más sencillo evitar situaciones de Deadlock.

Evitando el Deadlock de un hilo, dejando que la espera de time-out.

Las funciones de Win32 para lidiar con mutex no requieren que un hilo espere por siempre para adquirir un objeto mutex. La función WaitForSingleObject le permite a uno especificar un tiempo que el hilo está preparado a esperar. Una vez que ha pasado este tiempo, el hilo será desbloqueado y la llamada devolverá un código de error indicando que a la espera se le acabó el tiempo (time-out). Cuando usamos mutex para forzar el acceso sobre una región crítica del código, uno no espera típicamente que el hilo tenga que esperar mucho tiempo, y un time-out establecido para suceder en pocos segundos debería ser apropiado. Si tu hilo usa este método, entonces deberá, por supuesto, poder manejar situaciones de error en forma adecuada, quizás volviéndolo a intentar o abandonándolo. Desde luego que los usuarios de las secciones críticas no tienen este lujo, ya que las funciones de espera de las funciones críticas esperan por siempre.

Evitando el Deadlock de un hilo imponiendo un orden en la adquisición de mutex.

Si bien es una buena idea ser capaz de manejar situaciones de error al adquirir un mutex, es una buena práctica asegurarse que las situaciones de Deadlock no sucedan en primer lugar. Como este tipo de Deadlock es provocado por dependencias cíclicas, puede ser eliminado al imponer un orden en la adquisición de mutexes. Este ordenamiento es muy sencillo. Digamos que tenemos un programa con mutexes M1, M2, M3, … Mn, donde uno o más de estos mutex pueden ser adquiridos por los hilos en el programa.

¿Suena un poco abstracto? Tomemos un ejemplo concreto bastante sencillo. En esta parte del capitulo, me referiré a objetos de “bloqueo” y “desbloqueo”. Esta terminología parece apropiada cuando un mutex está asociado con un dato, y el acceso atómico a ese dato es necesario. Uno debería notar que esto efectivamente significa que cada hilo obtiene el mutex antes de acceder a un objeto, y abandona el mutex después de haber accedido: la operación es idéntica a las discutidas anteriormente, el único cambio está en la terminología, que para esta coyuntura, es más apropiada para un modelo orientado a objetos. En esencia, Objeto.Lock puede ser considerado completamente equivalente a EnterCriticalSection(Objecto.CriticalSection) o quizás WaitForSingleObject(Objeto.Mutex, INFINITE).


Tenemos una lista con estructuras de datos que es accedida por varios hilos. Enganchados a la lista hay algunos objetos, cada uno de los cuales tiene su propio mutex. De momento, asumiremos que la estructura de la lista es estática, no cambia, y puede ser leída libremente por los hilos sin ningún tipo de bloqueo. Los hilos que operan en esta estructura de datos quieren hacer alguna de estas cosas:

Un simple pseudo-código para estas funciones, ignorando los tipos, manejos de excepciones y otros aspectos que no son centrales, puede verse como algo así.

Imaginémonos por un momento que a un hilo se le pide comparar los ítems X e Y de la lista. Si el hilo siempre bloquea X y luego Y, entonces podría ocurrir un Deadlock si a un hilo se le pide comparar ítems 1 y 2, y a otro hilo se le pide comparar ítems 2 y 1. Una solución sencilla sería bloquear primero el ítem cuyo número sea el menor, u ordenar los índices de entrada, realizar los bloqueos y ajustar los resultados de la comparación apropiadamente. Sin embargo, una situación más interesante es cuando un objeto contiene detalles de otro objeto con el que es necesario hacer la comparación. En esta situación, el hilo puede bloquear el primer objeto, obtener el índice del segundo objeto en la lista, darse cuenta que el índice de este es menor en la lista, bloquearlo y proceder luego con la comparación. Todo muy fácil. El problema ocurre cuando el segundo objeto tiene mayor índice en la lista que el primero. No podemos bloquearlo inmediatamente, porque de hacerlo, estaríamos permitiendo que se produzca un Deadlock. Lo que debemos hacer es desbloquear el primer objeto, bloquear el segundo y luego volver a bloquear el primero. Esto nos asegura que el Deadlock no ocurrirá. Aquí hay un ejemplo de comparación indirecta, representativo de esta discusión.

Fuera de la cacerola y ¡en el fuego!

Si bien esto evita las situaciones de Deadlock, crea un problema peliagudo. En la demora entre desbloqueo y vuelta a bloquear del primer objeto, no podemos estar seguros que otro hilo no ha modificado el primero objeto antes de que hayamos vuelto. Esto se da porque nosotros realizamos una operación compuesta: la operación en sí no es más atómica. Solucione a este problema son discutidas más abajo, en la página.

Evitando el Deadlock al “modo vago” y dejando que Win32 lo haga por ti.

Concientes de la gimnasia mental que estos problemas pueden presentar, los adorables diseñadores de Sistemas Operativos en Microsoft, nos han provisto de una manera de solucionar el problema mediante otra función de sincronización de Win32: WaitForMultipleObjects(Ex). Esta función le permite al programador esperar para adquirir muchos objetos de sincronización (incluyendo mutex) de una vez. En particular, esto le permite a un hilo esperar hasta que uno o todo un grupo de objetos estén libres (en el caso de mutex, el equivalente seria “sin propietario”), y luego adquirir la propiedad de los objetos señalados. Esto tiene la gran ventaja de que si dos hilos esperan por los mutex A y B, no importa que orden especificaron en el grupo de objetos para esperar, o ningún objeto es adquirido o todos son adquiridos atómicamente, de modo que es imposible un caso de deadlock de esta manera.

Este enfoque también tiene algunas desventajas. La primera desventaja es que como todos los objetos de sincronización deben estar libres antes de que alguno de ellos sea adquirido, es posible que un hilo que espere por un gran número de objetos, no adquiera la propiedad por un largo período de tiempo si otros hilos están adquiriendo los mismos objetos de sincronización de a uno. Por ejemplo, en el diagrama de abajo, el hilo más a la izquierda espera por los mutexes A, B y C, mientras que otros tres hilos adquieren cada mutex en forma individual. En el peor de los casos, el hilo esperando por muchos objetos puede que nunca adquiera la propiedad.

La segunda desventaja es que aún es posible caer en trampas de Deadlock, esta vez no con un solo mutex, ¡sino con un grupo de varios mutexes!

La tercera desventaja que tiene este enfoque, en común con método de “time-out” para evitar el Deadlock, es que no es posible usar esta función si se están usando secciones críticas, la función EnterCriticalSection no le permite especificar una cantidad de tiempo de espera, ni tampoco devuelve un código de error.

Atomicidad en la composición de operaciones – optimismo versus pesimismo en el control de concurrencia.

Cuando pensamos en el ordenamiento de mutex anterior, nos encontramos en una situación donde necesitamos desbloquear para luego volver a bloquear un objeto de modo de respetar el ordenamiento de mutex. Esto significa que varias operaciones han ocurrido en un objeto y el bloqueo de ese objeto ha sido liberado entre medio de dichas operaciones.

Control de concurrencia optimista.

Una manera de lidiar con el problema es asumir que este tipo de interferencia de hilos es poco probable que ocurra, y simplemente verificar el problema y devolver un error si esto es así. Esto es comúnmente un modo válido de lidiar con el problema en situaciones complejas donde la “sobrecarga” de estructuras de datos por varios hilos no es demasiado elevada. En el caso presentado antes, podemos verificar trivialmente esto, guardando una copia local de los datos y verificando que aún son válidos cuando volvemos a bloquear ambos objetos en el orden requerido. Aquí esta la rutina modificada.

Con estructuras de datos más complicadas, uno puede recurrir algunas veces a ID’s únicos globales o marcado de versiones en piezas de código. Como nota personal, recuerdo haber trabajado con un grupo de otros estudiantes en un proyecto de fin de año de la universidad, donde este enfoque funcionó muy bien: un número secuencial era incrementado cuando una pieza de datos era modificada (en este caso los datos consistían en anotaciones en un diario multiusuario). Los datos eran bloqueados mientras se leía, luego se mostraban al usuario y si el usuario editaba los datos, el número era comparado con el obtenido por el usuario en la última lectura, y la actualización era abandonada si los números no coincidían.

Control de concurrencia pesimista.

Podemos tomar un enfoque bastante diferente del problema, considerando que la lista tiende a ser modificada y, por esto, requiere su propio bloqueo. Todas las operaciones que lean o escriban en la lista, incluyendo búsquedas, deberán bloquear primero la lista. Esto provee una solución alternativa al problema de bloquear limpiamente a varios objetos en la lista. Revisemos las operaciones que deseamos realizar nuevamente, con el ojo puesto en este diseño alternativo del bloqueo.

Un hilo puede querer leer y modificar los contenidos de un objeto de la lista, pero sin modificar el objeto existente ni su posición en la lista. Esta operación toma mucho tiempo, y no queremos obstaculizar a otros hilos que quieran operar con otros objetos, de modo que el hilo que modifique el objeto debe realizar las siguientes operaciones:

Esto es fantástico ya que, aún si el hilo realiza operaciones de lectura o escritura en el objeto que tomen mucho tiempo, no tendrá la lista bloqueada por ese tiempo y, por ende, no demorará a otros hilos que quieran modificar otros objetos.

Un hilo puede eliminar un objeto llevando a cabo el siguiente algoritmo:

Nótese que es posible desbloquear la lista antes de eliminar finalmente el objeto, ya que eliminamos el objeto de la lista, y así sabemos que ninguna otra operación está en progreso en el objeto o la lista (al tener a ambos bloqueados).

Aquí viene la parte interesante. Un hilo puede comparar dos objetos llevando a cabo un algoritmo más simple que el mencionado en la sección anterior:

Como verán, en la operación de comparación, no he hecho ninguna restricción en el orden en que son realizados los bloqueos en los objetos. ¿Podrá esto provocar un Deadlock? El algoritmo presentado no necesita el criterio para evitar los Deadlocks presentados al comienzo del capitulo, porque los Deadlock no ocurrirán nunca. Y no ocurrirán nunca porque cuando un hilo bloquea un objeto mutex, él ya tiene posesión del mutex de la  lista, y con esta posesión, puede bloquear varios objetos si no libera el mutex de la lista. El bloqueo compuesto en varios objetos resulta atómico. Como resultado de esto, podemos modificar el criterio de Deadlock de arriba:

Evitando agujeros en el esquema de bloqueo.

No es ninguna novedad a estas alturas, que el ejemplo de arriba es típico de un código de bloqueo que es muy sensible al ordenamiento. Más allá de esto, todo esto debe indicarnos que cuando ideamos esquemas de bloqueo que no son triviales, debemos tener mucho cuidado en el orden en que suceden las cosas.

Si estás seguro que tu programa funcionará en Windows NT (o 2K, XP, 2003), entonces el API de Windows provee en efecto una solución al problema de operaciones compuestas cuando se desbloquean y vuelven a bloquear objetos. La llamada del API SignalObjectAndWait te permite marcar atómicamente (o liberar) un objeto de sincronización, y esperar por otro. Conservando estas dos operaciones atómicas, se puede transferir un estado de bloqueo de un objeto a otro, mientras que se asegura que ningún otro hilo modifica el estado del objeto durante la transferencia. Esto significa que el control de concurrencia optimista no es necesario en estas situaciones.

¿Ya esta confundido? ¡Puede tirar la toalla!

Si pudo permanecer leyendo hasta este punto, lo felicito, ha adquirido un conocimiento básico del los problemas que le dan a los programadores multihilo bastante dolores de cabeza. Es útil destacar que los esquemas complicados en estructuras internas de datos son habitualmente necesarios para sistemas con alta performance. Pequeñas aplicaciones de escritorio pueden funcionar habitualmente con enfoques no tan complicados. Hay varias maneras de “tirar la toalla”.

Bloquear todos los datos compartidos es habitualmente útil, si uno está dispuesto a sacrificar eficiencia. La mayoría de los usuarios prefieren un programa que funciona un poco lento que uno que falla en intervalos impredecibles, por errores en el esquema de bloqueo. Si uno tiene una gran cantidad de datos que necesitan ser persistentes de alguna manera, poner todos los datos en la BDE es otro enfoque. Todos los (medianamente decentes) motores de bases de datos son seguros para trabajar con múltiples hilos, lo que significa que puedes acceder a tus datos sin ningún problema desde hilos separados. Si usas un motor de bases de datos, entonces deberás estudiar algo sobre administración de transacciones, por ejemplo, las semánticas reservation, y el uso de premature, commit y rollback, pero recuerda que esto es sólo el enfoque basado en transacciones para solucionar problemas de concurrencia, y sencillamente la otra cara de la misma moneda; la mayor parte de la programación difícil (incluido los dolores de cabeza) lo han hecho por ti. El uso de la BDE con hilos de ejecución será tratado luego.


Contenido - Anterior - Siguiente