¿Utilidades para crear una jerarquía de bloqueo?

Question

De acuerdo con las respuestas encontradas en Threads and simple Dead lock cure y también Herb Sutter, la clave para evitar el interbloqueo es mediante el uso de jerarquías de bloqueo.

¿Hay alguna buena biblioteca en C++ que brinde soporte para esto? No puedo encontrar ninguno en Boost o Poco.

Idealmente, sería un sistema que permite definir la jerarquía en tiempo de compilación. Tal vez se vería así:

template<class LowerLevelMutex> 
class RankedMutex { ... }; 

class BottomMutex { ... }; 

typedef RankedMutex<BottomMutex> L1Mutex; 
typedef RankedMutex<L1Mutex> L2Mutex; 
typedef RankedMutex<L2Mutex> L3Mutex; 
// ... 

Answer 1

Sí, las jerarquías de bloqueo pueden prevenir bloqueos de manera efectiva; por supuesto, si realmente puede definir una jerarquía para su programa (especialmente, en presencia de complementos) es otro asunto completamente diferente.

Los bloques básicos son simples:

• Cada mutex debe tener un nivel (ya sea determinado en tiempo de compilación o en tiempo de ejecución)
• Cada hilo debe solamente siempre adquirir mutex en orden ascendente o nivel descendente (decidir una vez)

Espero que pueda hacer justicia a la idea, por favor considere la implementación de ejemplo debajo de un boceto; nunca ha sido compilado/probado.

un mutex básica:

template <typename Mutex, size_t Level> 
class HierarchicalMutex { 
public: 
    friend class LevelManager; 

    void lock() { 
     LevelManager::Lock(*this); 
    } 

    void unlock() { 
     LevelManager::Unlock(*this); 
    } 

private: 
    size_t previous; 
    Mutex mutex; 
}; // class HierarchicalMutex 

template <typename Mutex, size_t Level> 
size_t level(HierarchicalMutex<Mutex,Level> const&) { return Level; } 

papel La LevelManager 's es simplemente para asegurar que las transiciones de nivel suceden en el orden correcto.

class LevelManager { 
public: 
    // 
    // Single Mutex locking 
    // 
    template <typename M> 
    static void Lock(M& m) { 
     m.previous = LevelUp(level(m)); 
     m.mutex.lock(); 
    } 

    template <typename M> 
    static void Unlock(M& m) { 
     m.mutex.unlock(); 
     LevelDown(level(m), m.previous); 
    } 

    // 
    // Multiple Mutexes Group Locking 
    // 
    // Note: those should expose a "size_t level(M const&)" function, 
    //  and calls to lock/unlock should appropriately call 
    //  this manager to raise/lower the current level. 
    // 
    // Note: mutexes acquired as a group 
    //  should be released with the same group. 
    // 
    template <typename M> 
    static void Lock(std::array_ref<M*> mutexes) { // I wish this type existed 
     using std::begin; using std::end; 

     auto begin = begin(mutexes); 
     auto end = end(mutexes); 

     end = std::remove_if(begin, end, [](M const* m) { return m == 0; }); 

     if (begin == end) { return; } 

     Sort(begin, end); 

     size_t const previous = LevelUp(level(*std::prev(end))); 

     for (; begin != end; ++begin) { 
      begin->previous = previous; 
      begin->mutex.lock(); 
     } 
    } 

    template <typename M> 
    static void Unlock(std::array_ref<M*> mutexes) { 
     using std::begin; using std::end; 

     auto begin = begin(mutexes); 
     auto end = end(mutexes); 

     end = std::remove_if(begin, end, [](M const* m) { return m == 0; }); 

     if (begin == end) { return; } 

     Sort(begin, end); 

     std::reverse(begin, end); 

     for (auto it = begin; it != end; ++it) { it->mutex.unlock(); } 

     LevelDown(level(*begin), begin->previous); 
    } 

private: 
    static __thread size_t CurrentLevel = 0; 

    template <typename It> 
    static void Sort(It begin, It end) { 
     using Ref = typename std::iterator_traits<It>::const_reference; 

     auto const sorter = [](Ref left, Ref right) { 
      return std::tie(level(left), left) < std::tie(level(right), right); 
     }; 

     std::sort(begin, end, sorter); 
    } 

    static size_t LevelUp(size_t const to) { 
     if (CurrentLevel >= to) { throw LockHierarchyViolation(); } 
     CurrentLevel = to; 
    } 

    static void LevelDown(size_t const from, size_t const to) { 
     if (CurrentLevel != from) { throw LockHierarchyViolation(); } 
     CurrentLevel = to; 
    } 
}; // class LevelManager 

por diversión, he implementado la posibilidad de bloquear múltiples cerraduras del mismo nivel en un solo tiro.

Answer 2

Lo más importante que puede hacer en este tipo de casos es sólo asegúrese de que los bloqueos se aplican siempre jerárquicamente (que significa anidada). De esta forma, no podrá acceder al bloqueo de nivel 3 sin tener el bloqueo de nivel 2, al que no podrá acceder sin antes tener el bloqueo de nivel 1. Ni siquiera podrá llegar a 3 sin llegar primero a 1 y 2, por lo que debería evitar problemas mayores.

¿Puede ser más específico en algunos de los casos de interbloqueo que surgen? Tal vez podamos encontrar una solución para algunas de las cosas particularmente complicadas que pueden no ser tan fáciles de manipular como describí anteriormente.

Answer 3

No hay necesidad de una clase separada para administrar la jerarquía. Una buena solución puede encontrarse en C++ concurrencia en Acción, por Anthony Williams (ISBN 9781933988771):

#include <mutex> 
#include <stdexcept> 

class hierarchical_mutex 
{ 
    std::mutex internal_mutex; 
    unsigned long const hierarchy_value; 
    unsigned long previous_hierarchy_value; 
    static thread_local unsigned long this_thread_hierarchy_value; 

    void check_for_hierarchy_violation() 
    { 
     if(this_thread_hierarchy_value <= hierarchy_value) 
     { 
      throw std::logic_error("mutex hierarchy violated"); 
     } 
    } 
    void update_hierarchy_value() 
    { 
     previous_hierarchy_value=this_thread_hierarchy_value; 
     this_thread_hierarchy_value=hierarchy_value; 
    } 
public: 
    explicit hierarchical_mutex(unsigned long value): 
     hierarchy_value(value), 
     previous_hierarchy_value(0) 
    {} 
    void lock() 
    { 
     check_for_hierarchy_violation(); 
     internal_mutex.lock(); 
     update_hierarchy_value(); 
    } 
    void unlock() 
    { 
     this_thread_hierarchy_value=previous_hierarchy_value; 
     internal_mutex.unlock(); 
    } 
    bool try_lock() 
    { 
     check_for_hierarchy_violation(); 
     if(!internal_mutex.try_lock()) 
      return false; 
     update_hierarchy_value(); 
     return true; 
    } 
}; 
thread_local unsigned long 
    hierarchical_mutex::this_thread_hierarchy_value(ULONG_MAX);  

int main() 
{ 
    hierarchical_mutex m1(42); 
    hierarchical_mutex m2(2000); 

}