c++ - Múltiples estrategias de bloqueo mutex y por qué las bibliotecas no usan la comparación de direcciones

multithreading boost-thread

Question

Existe una forma ampliamente conocida de bloquear múltiples bloqueos, que se basa en la elección del ordenamiento lineal fijo y en la adquisición de bloqueos de acuerdo con este ordenamiento.

Eso se propuso, por ejemplo, en la respuesta para "Adquirir un bloqueo en dos mutexes y evitar el interbloqueo" . Especialmente, la solución basada en la comparación de direcciones parece ser bastante elegante y obvia .

Cuando intenté verificar cómo se implementa, descubrí, para mi sorpresa, que esta solución no se usa mucho.

Para citar los Kernel Docs - Guía no confiable para el bloqueo :

Los libros de texto le dirán que si siempre bloquea en el mismo orden, nunca obtendrá este tipo de punto muerto. La práctica le dirá que este enfoque no se amplía: cuando creo un nuevo bloqueo, no entiendo lo suficiente del núcleo para averiguar dónde encajará en la jerarquía de 5000 bloqueos.

PThreads no parece tener tal mecanismo incorporado en absoluto.

Boost.Thread presentó una solución completamente diferente, lock() para múltiples mutexes (2 a 5) se basa en probar y bloquear tantos mutexes como sea posible en este momento.

Este es el fragmento del código fuente de Boost.Thread (Boost 1.48.0, boost / thread / 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 devuelve 0 en caso de éxito y número de lock_helper que no se bloquearon correctamente de lo contrario.

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

¿Hay otras ideas sobre cómo resolver este problema a nivel de biblioteca?

Answer 1

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 de árbol e hilos que intentan leer y actualizar nodos, puede proteger el árbol mediante un bloqueo de lector-escritor por nodo. Esto solo funciona si sus subprocesos siempre adquieren bloqueos de arriba a abajo de root-to-leave. La dirección de las cerraduras no importa en este caso.

Solo puede usar la comparación de direcciones si no importa en absoluto qué bloqueo se obtenga 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 estén bloqueados antes que otros. Esto no se puede hacer utilizando la comparación de direcciones.

Answer 2

Del texto de la recompensa:

Ni siquiera estoy seguro de poder probar la corrección de la solución Boost presentada, que parece más complicada que la de orden lineal.

La solución Boost no puede interrumpirse porque nunca espera mientras ya está bloqueado. Todos los bloqueos, pero los primeros se adquieren con try_lock. Si alguna llamada try_lock no logra obtener 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 se adquirió 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 bloquear llamadas mientras se mantiene un bloqueo. Por lo tanto, la solución con try-lock, si es posible, se prefiere (en mi opinión). Como consecuencia particular, en el caso de un pedido de bloqueo, el sistema en su totalidad podría atascarse. 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 imagine que otro hilo necesita el último bloqueo y otro bloqueo, y debido al pedido, primero obtendrá el otro y esperará el último bloqueo. Lo mismo puede ocurrir con todos los demás bloqueos, y todo el sistema no avanza hasta que se libera el último bloqueo. Por supuesto, es un caso extremo y bastante improbable, pero ilustra el problema inherente con el ordenamiento de los bloqueos: cuanto más alto es el número de un bloqueo, mayor es el impacto indirecto que tiene el bloqueo cuando se adquiere.

El inconveniente de la solución basada en try-lock es que puede causar un bloqueo vital, y en casos extremos, todo el sistema también puede atascarse durante al menos algún tiempo. Por lo tanto, es importante tener algún esquema de retroceso que haga que las pausas entre los intentos de bloqueo sean más largas con el tiempo y quizás sean aleatorias.

Answer 3

La "comparación de direcciones" y enfoques similares, aunque se utilizan con bastante frecuencia, son casos especiales. Funcionan bien si tienes

1. un mecanismo de bloqueo libre para obtener
2. dos (o más) "elementos" del mismo tipo o nivel de jerarquía
3. cualquier esquema de orden estable entre esos artículos

Por ejemplo: tiene un mecanismo para obtener dos "cuentas" de una lista. Supongamos que el acceso a la lista está libre de bloqueo. Ahora tienes punteros a ambos elementos y quieres bloquearlos. Como son "hermanos", tienes que elegir cuál bloquear primero. Aquí el enfoque que utiliza direcciones (o cualquier otro esquema de orden estable como "id de cuenta") es correcto.

Pero el texto de Linux vinculado habla de "jerarquías de bloqueo". Esto significa bloquear no entre "hermanos" (del mismo tipo) sino entre "padres" e "hijos", que pueden ser de diferentes tipos. Esto puede suceder en estructuras de árbol reales y en otros escenarios. Ejemplo elaborado: para cargar un programa debes

1. bloquear el archivo inode,
2. bloquear la tabla de proceso
3. bloquear la memoria de destino

Estos tres bloqueos no son "hermanos" que no están en una jerarquía clara. Los bloqueos tampoco se toman directamente uno tras otro, cada subsistema tomará los bloqueos a voluntad. Si considera todos los casos de uso en los que interactúan los tres (y más) subsistemas que ve, no hay un orden claro y estable en el que pueda pensar.

La biblioteca Boost se encuentra 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.

Answer 4

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

Considera 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 funcion

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

en realidad utilizará la dirección compara el siguiente código ca produce un interbloqueo

Mutex m1;
Mutex m1;

hilo 1

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

lock(hm1, hm2);

thread2:

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

EDITAR:

este es un subproceso interesante que comparte algo de luz sobre boost :: bloqueo de implementación thread-best-practice-to-lock-multiple-mutexes

La comparación de direcciones no funciona para las exclusiones compartidas entre procesos (objetos de sincronización con nombre).