¿Cómo iterar sobre un contenedor de una manera segura para la ejecución de subprocesos?

Question

Tengo un contenedor (C++) en el que necesito operar de dos maneras, desde diferentes subprocesos: 1) Agregar y eliminar elementos, y 2) iterar a través de sus miembros. Claramente, elimine el elemento mientras la iteración está sucediendo = desastre. El código es como la siguiente:

class A 
{ 
public: 
    ... 
    void AddItem(const T& item, int index) { /*Put item into my_stuff at index*/ } 
    void RemoveItem(const T& item) { /*Take item out of m_stuff*/ } 
    const list<T>& MyStuff() { return my_stuff; } //*Hate* this, but see class C 
private: 
    Mutex mutex; //Goes in the *Item methods, but is largely worthless in MyStuff() 
    list<T> my_stuff; //Just as well a vector or deque 
}; 
extern A a; //defined in the .cpp file 

class B 
{ 
    ... 
    void SomeFunction() { ... a.RemoveItem(item); } 
}; 

class C 
{ 
    ... 
    void IterateOverStuff() 
    { 
     const list<T>& my_stuff(a.MyStuff()); 
     for (list<T>::const_iterator it=my_stuff.begin(); it!=my_stuff.end(); ++it) 
     { 
      ... 
     } 
    } 
}; 

Una vez más, B::SomeFunction() y C::IterateOverStuff() están recibiendo llamadas de forma asíncrona. ¿Qué es una estructura de datos que puedo usar para asegurar que durante la iteración, my_stuff esté 'protegido' para agregar o eliminar operaciones?

Answer 1

suena como reader/writer lock es necesario. Básicamente, la idea es que puede tener 1 o más lectores O un solo escritor. Nunca puede tener un bloqueo de lectura y escritura al mismo tiempo.

EDIT: Un ejemplo de uso que creo que se ajusta a su diseño implica hacer un pequeño cambio. Agregue una función "iterar" a la clase que posee la lista y haga que sea una plantilla para que pueda pasar una función/functor para definir qué hacer para cada nodo. Algo como esto (pseudo código rápido y sucio, pero usted consigue el punto ...):

class A { 
public: 
    ... 
    void AddItem(const T& item, int index) { 
     rwlock.lock_write(); 
     // add the item 
     rwlock.unlock_write(); 
    } 

    void RemoveItem(const T& item) { 
     rwlock.lock_write(); 
     // remove the item 
     rwlock.unlock_write(); 
    } 

    template <class P> 
    void iterate_list(P pred) { 
     rwlock.lock_read(); 
     std::for_each(my_stuff.begin(), my_stuff.end(), pred); 
     rwlock.unlock_read(); 
    } 

private: 
    rwlock_t rwlock; 
    list<T> my_stuff; //Just as well a vector or deque 
}; 


extern A a; //defined in the .cpp file 

class B { 
    ... 
    void SomeFunction() { ... a.RemoveItem(item); } 
}; 

class C { 
    ... 

    void read_node(const T &element) { ... } 

    void IterateOverStuff() { 
     a.iterate_list(boost::bind(&C::read_node, this)); 
    } 
}; 

Otra opción sería hacer el bloqueo de lectura/escritura de acceso público y tener la persona que llama responsables de la utilización correcta La cerradura. Pero eso es más propenso a errores.

Answer 2

Cuando devuelve la lista, devuelvala encerrada en una clase que bloquea/desbloquea el mutex en su constructor/destructor. Algo a lo largo de las líneas de

class LockedIterable { 
public: 
    LockedIterable(const list<T> &l, Mutex &mutex) : list_(l), mutex_(mutex) 
    {lock(mutex);} 
    LockedIterable(const LockedIterable &other) : list_(other.list_), mutex_(other.mutex_) { 
    // may be tricky - may be wrap mutex_/list_ in a separate structure and manage it via shared_ptr? 
    } 
    ~LockedIterable(){unlock(mutex);} 
    list<T>::iterator begin(){return list_.begin();} 
    list<T>::iterator end(){return list_.end();} 
private: 
    list<T> &list_; 
    Mutex &mutex_; 
}; 

class A { 
    ... 
    LockedIterable MyStuff() { return LockedIterable(my_stuff, mutex); } 
}; 

La parte difícil es escribir constructor de copia para que su exclusión mutua no tiene que ser recursivos. O simplemente use auto_ptr.

Ah, y el bloqueo lector/escritor es de hecho una mejor solución que mutex aquí.

Answer 3

En mi humilde opinión, es un error tener un mutex privado en una clase de estructura de datos y luego escribir los métodos de clase para que todo sea seguro, sin importar lo que haga el código que llama a los métodos. La complejidad que se requiere para hacer esto de manera completa y perfecta es demasiado exagerada.

La manera más simple es tener un mutex público (o global) que el código de llamada es responsable de bloquear cuando necesita acceder a los datos.

Here es el artículo de mi blog sobre este tema.