Estrategias de bloqueo de múltiples mutex y por qué las bibliotecas no usan la comparación de direcciones

Question

Existe una forma ampliamente conocida de bloquear bloqueos múltiples, que se basa en elegir el orden lineal fijo y los bloqueos que requieren de acuerdo con este orden.

Eso fue propuesto, por ejemplo, en la respuesta para "Acquire a lock on two mutexes and avoid deadlock". Especialmente, la solución basada en la comparación de direcciones parece ser bastante elegante y obvia.

Cuando traté de comprobar cómo se implementa realmente, he encontrado, para mi sorpresa, que esta solución no se usa ampliamente.

citar el Kernel Docs - Unreliable Guide To Locking:

libros de texto le dirá que si siempre se bloquea en el mismo orden, que nunca conseguir este tipo de estancamiento. La práctica le dirá que este enfoque no escala: cuando creo un nuevo bloqueo, no entiendo suficiente del kernel para averiguar en qué parte de la jerarquía de 5000 bloqueos se ajustará .

PThreads ello no le parece a tienen un mecanismo de este tipo construida en en absoluto.

Boost.Thread ocurrió solución completamente diferente, lock() para múltiples (2 a 5) mutex se basa en tratar y bloquear la mayor cantidad de exclusiones mutuas, ya que es posible por el momento.

Este es el fragmento del código fuente Boost.Thread (Boost 1.48.0, realce/hilo/locks.hpp: 1291):

template<typename MutexType1,typename MutexType2,typename MutexType3> 
void lock(MutexType1& m1,MutexType2& m2,MutexType3& m3) 
{  
    unsigned const lock_count=3; 
    unsigned lock_first=0; 
    for(;;) 
    {  
     switch(lock_first) 
     {  
     case 0: 
      lock_first=detail::lock_helper(m1,m2,m3); 
      if(!lock_first) 
       return; 
      break; 
     case 1: 
      lock_first=detail::lock_helper(m2,m3,m1); 
      if(!lock_first) 
       return; 
      lock_first=(lock_first+1)%lock_count; 
      break; 
     case 2: 
      lock_first=detail::lock_helper(m3,m1,m2); 
      if(!lock_first) 
       return; 
      lock_first=(lock_first+2)%lock_count; 
      break; 
     }  
    }  
}  

donde lock_helper rendimientos 0 sobre el éxito y el número de mutexes que no se bloquearon con éxito de lo contrario.

¿Por qué esta solución es mejor, que la comparación de direcciones o cualquier otro tipo de identificadores? No veo ningún problema con la comparación de punteros, que se puede evitar con este tipo de bloqueo "a ciegas".

¿Hay alguna otra idea sobre cómo resolver este problema a nivel de biblioteca?

Answer 1

A partir del texto de recompensas:

Ni siquiera estoy seguro de si puedo demostrar la corrección de la solución presentada Boost, que parece más complicado que el de orden lineal.

La solución de Boost no puede llegar a un punto muerto porque nunca espera mientras mantiene un bloqueo. Todos los bloqueos, pero los primeros se adquieren con try_lock. Si alguna llamada try_lock no puede adquirir su bloqueo, se liberan todos los bloqueos adquiridos previamente. Además, en la implementación de Boost, el nuevo intento comenzará desde que el bloqueo no pudo adquirir la hora anterior, y primero esperará hasta que esté disponible; es una decisión de diseño inteligente.

Como regla general, siempre es mejor evitar el bloqueo de llamadas mientras se mantiene un bloqueo. Por lo tanto, se prefiere la solución con try-lock, si es posible (en mi opinión). Como consecuencia particular, en el caso de un pedido de bloqueo, el sistema en su conjunto podría quedar atascado. Imagine que el último bloqueo (por ejemplo, el que tiene la dirección más grande) fue adquirido por un hilo que luego fue bloqueado. Ahora imagina que otro hilo necesita el último bloqueo y otro bloqueo, y debido al pedido, primero obtendrá el otro y esperará en el último bloqueo. Lo mismo puede suceder con todos los otros bloqueos, y todo el sistema no progresa hasta que se libera el último bloqueo. Por supuesto, es un caso extremo y bastante improbable, pero ilustra el problema inherente con el orden de bloqueo: cuanto mayor sea un número de bloqueo, mayor será el impacto indirecto que tendrá el bloqueo cuando se adquiera.

El inconveniente de la solución basada en el intento de bloqueo es que puede causar livelock, y en casos extremos todo el sistema también podría atascarse durante al menos algún tiempo. Por lo tanto, es importante contar con un esquema de retroceso que haga que las pausas entre intentos de bloqueo sean más prolongadas con el tiempo, y quizás aleatorias.

Answer 2

A veces, el bloqueo A debe adquirirse antes que el bloqueo B. El bloqueo B puede tener una dirección más baja o más alta, por lo que no puede usar la comparación de direcciones en este caso.

Ejemplo: Cuando tiene una estructura de datos en árbol, y los subprocesos intentan leer y actualizar nodos, puede proteger el árbol utilizando un bloqueo de lector y escritor por nodo. Esto solo funciona si sus subprocesos siempre adquieren bloqueos de raíz a raíz de raíz a partida. La dirección de los bloqueos no importa en este caso.

Solo puede usar la comparación de direcciones si no importa en absoluto qué bloqueo se adquiere primero. Si este es el caso, la comparación de direcciones es una buena solución. Pero si este no es el caso, no puedes hacerlo.

Supongo que el kernel de Linux requiere que ciertos subsistemas se bloqueen antes que otros. Esto no se puede hacer usando la comparación de direcciones.

Answer 3

Un escenario en el que la comparación de direcciones fallará si usa el patrón de proxy. Puede delegar los bloqueos en el mismo objeto y las direcciones serán diferentes.

consideremos el siguiente ejemplo

template<typename MutexType> 
class MutexHelper 
{ 
    MutexHelper(MutexType &m) : _m(m) {} 
    void lock() 
    { 
    std::cout <<"locking "; 
    m.lock(); 
    } 

    void unlock() 
    { 
    std::cout <<"unlocking "; 
    m.unlock(); 
    } 

    MutexType &_m; 
}; 

si la función

template<typename MutexType1,typename MutexType2,typename MutexType3> 
void lock(MutexType1& m1,MutexType2& m2,MutexType3& m3); 

en realidad utilizar la dirección de comparar el código siguiente ca producir un estancamiento

Mutex m1; 
Mutex m1; 

Thread1

MutexHelper hm1(m1); 
MutexHelper hm2(m2); 

lock(hm1, hm2); 

thread2:

MutexHelper hm2(m2); 
MutexHelper hm1(m1); 
lock(hm1, hm2); 

EDIT:

este es un hilo interesante que compartir algo de luz sobre la aplicación de bloqueo de impulso :: thread-best-practice-to-lock-multiple-mutexes

Dirección comparar no funciona para inter- procesar mutexes compartidos (objetos de sincronización nombrados).

Answer 4

La "comparación de direcciones" y enfoques similares, aunque utiliza muy a menudo, son casos especiales.Se trabaja muy bien si usted tiene

1. un mecanismo libre de bloqueo para conseguir
2. dos (o más) "elementos" de la mismo tipo o nivel de jerarquía
3. cualquier esquema de ordenamiento estable entre esos elementos

Por ejemplo: tiene un mecanismo para obtener dos "cuentas" de una lista. Supongamos que el acceso a la lista está libre de bloqueos. Ahora tiene punteros a ambos elementos y desea bloquearlos. Como son "hermanos", debes elegir cuál bloquear primero. Aquí el enfoque que usa direcciones (o cualquier otro esquema estable de pedidos como "ID de cuenta") está bien.

Pero el texto de Linux enlazado habla de "jerarquías de bloqueo". Esto significa bloquear no entre "hermanos" (del mismo tipo) sino entre "padre" y "hijos" que pueden ser de diferentes tipos. Esto también puede ocurrir en estructuras de árbol reales en otros escenarios. ejemplo artificioso: Para cargar un programa que debe

1. bloquear el i-nodo del archivo,
2. bloquear la tabla de procesos
3. bloquear la memoria de destino

Estos tres bloqueos no "hermanos" no son en una jerarquía clara. Los bloqueos tampoco se toman directamente uno después del otro - cada subsistema tomará las cerraduras a voluntad. Si considera todos los casos de uso donde interactúan esos tres (y más) subsistemas, no se puede pensar en un orden claro y estable.

La biblioteca de Boost está en la misma situación: se esfuerza por proporcionar soluciones genéricas. Por lo tanto, no pueden asumir los puntos desde arriba y deben recurrir a una estrategia más complicada.