2009-04-26 25 views
14

Soy nuevo en C++ y estoy escribiendo una aplicación multiproceso por la cual diferentes escritores empujarán objetos a una pila y los lectores los sacarán de la pila (o al menos empujarán el puntero a un objeto) ..Thread-safe C++ stack

¿Hay estructuras integradas en C++ que puedan manejar esto sin agregar código de bloqueo, etc.? Si no, ¿qué pasa con las bibliotecas de Boost?

EDITAR:

Hola. Gracias por las excelentes respuestas iniciales. Supongo que una de las razones por las que pensé que esto podría ser incorporado fue que estaba pensando puramente en el espacio x86 y pensé que un PUSH/POP de punteros debería ser una acción atómica en el nivel de instrucción.

No estoy seguro de si mi corazonada inicial es verdadera o no, pero supongo que esto no sería necesariamente cierto en todas las plataformas. Aunque si se ejecuta en x86, ¿obtienes PUSHes y POPs atómicos en la pila y, de ser así, esto esencialmente lo hace sin bloqueos?

+0

Si está interesado en la atomicidad de las instrucciones x86 PUSH/POP, por favor haga una pregunta por separado: no tiene nada que ver con C++, que no usaría tales instrucciones para acceder a una estructura de datos de pila. –

+2

El comité está más ocupado escribiendo clases de predicación paralelas en DDJ en lugar de hacer abstracciones de modelo de memoria atómicas y mucho mejores para el compilador obligatorio en TR1 (probablemente ni siquiera en TR2). Para responder: realmente no empuja y pop y, por lo tanto, implícitamente modificar los registros a través de los hilos dice que actualmente se ejecuta en núcleos distintos, ¿o sí? :-) Buen golpe, pero no funcionaría. No puedes hacerlo sin cerrojo o al menos sin el martillo CAS. Para fanáticos de C++: Deben simplemente sentarse y definir y acordar los protocolos de coherencia existentes, + dejar algo de espacio para nuevos desarrollos. –

+0

Para los interesados, investigué las operaciones atómicas e Intel tiene soporte de DCAS a través de cmpxchg16b. Lamentablemente, AMD solo tiene cmpxchg8b. No me importa, ya que estoy escribiendo para las máquinas Intel :) – bugmenot77

Respuesta

21

Sip: Boost.Thread es genial, y debe ajustarse perfectamente a sus necesidades. (En estos días, muchas personas dicen que casi se puede contar con Boost como funcionalidad incorporada.)

Todavía no hay clases que pueda usar de fábrica, pero una vez que tenga las primitivas de sincronización disponibles , es bastante simple implementar su propia envoltura segura para subprocesos, por ejemplo, std::stack. Podría ser algo como esto (no implementar todos los métodos ...):

template <typename T> class MyThreadSafeStack { 
    public: 
    void push(const T& item) { 
     boost::mutex::scoped_lock lock(m_mutex); 
     m_stack.push(item); 
    } 
    void pop() { 
     boost::mutex::scoped_lock lock(m_mutex); 
     m_stack.pop(); 
    } 
    T top() const { // note that we shouldn't return a reference, 
        // because another thread might pop() this 
        // object in the meanwhile 
     boost::mutex::scoped_lock lock(m_mutex); 
     return m_stack.top(); 
    } 

    private: 
    mutable boost::mutex m_mutex; 
    std::stack<T> m_stack; 
}  

Si usted es nuevo en C++, por favor, aprender sobre RAII. Pertinente a este caso, Boost.Thread tiene las clases de "cerradura de alcance" para dificultar dispararse en la pierna al olvidarse de liberar un candado.

Si alguna vez se encuentra escribiendo código como este:

void doStuff() { 
    myLock.lock(); 
    if (!condition) { 
    reportError(); 
    myLock.unlock(); 
    return; 
    } 
    try { 
    doStuffThatMayThrow(); 
    } 
    catch (std::exception& e) { 
    myLock.unlock(); 
    throw e; 
    } 
    doMoreStuff(); 
    myLock.unlock(); 
} 

, a continuación, sólo debe decir que no, e ir RAII lugar (sintaxis no directamente de Boost):

void doStuff() { 
    scoped_lock lock; 
    if (!condition) { 
    reportError(); 
    return; 
    } 
    doStuffThatMayThrow(); 
    doMoreStuff(); 
} 

El punto es que cuando el objeto scoped_lock sale del alcance, su destructor libera el recurso, en este caso, el bloqueo. Esto siempre ocurrirá, sin importar si sale del alcance lanzando una excepción o ejecutando la extraña declaración return que su colega agregó furtivamente en el medio de su función, o simplemente al llegar al final de la función.

+0

Awesome answer. Gracias, esta fue una respuesta muy clara y muy útil. – bugmenot77

+0

De nada; ¡Me alegra que pudiera ayudar! – Reunanen

+2

Debe tener en cuenta que los contenedores estándar no son seguros para hilos, incluso cuando están bloqueados por un mutex. La razón es que su modificación invalida iteradores existentes. – ASk

4

El estándar actual de C++ no aborda el enhebrado en absoluto, por lo que la respuesta a su primera pregunta es no. Y, en general, es una mala idea crear un bloqueo en las estructuras de datos básicas, ya que no tienen suficiente información para realizarlo correctamente y/o de manera eficiente. En cambio, el bloqueo debe realizarse en las clases que usan las estructuras de datos, en otras palabras, en sus propias clases de aplicaciones.

+1

Tengo que ordenar-de estar en desacuerdo (aunque no downvote). Creo que está perfectamente bien escribir una clase ThreadSafeStack que envuelva una instancia privada de std :: stack. Luego, al comienzo de cada método (push, pop, ...) ingresa una sección crítica, o similar. Es cierto que top() no debería devolver una referencia sino una copia. Esto causa pérdida de eficiencia, pero la mayor facilidad para escribir las clases de aplicaciones a menudo vale la pena, en mi opinión. Y en los casos en que no (por ejemplo, se copian objetos enormes), simplemente no utiliza la clase contenedora. – Reunanen

+0

Sí, eso es lo que quise decir, pero probablemente expresado mal: ThreadSafeStack es una de las clases de su aplicación. Pero una biblioteca de propósito general no debe (IMHO) proporcionar tales clases. –

+1

Ah, está bien. Estaba pensando en las clases de aplicaciones como algo que principalmente contiene lógica de negocios. – Reunanen

1

AFAIK, sin soporte integrado en C++. Tendrá que sincronizar las operaciones de pila con una herramienta de sincronización simple. CriticalSection funcionaría si los hilos pertenecen al mismo procedimiento; de lo contrario, elija Mutex.

1

No hay un mecanismo incorporado para admitir esto en C++ ni en las bibliotecas de Boost (nota: algunas personas han escrito thread-safe stacks/etc. in the Boost style). Tendrás que pedir prestado un código o cocinar en tu propia sincronización.

Tenga en cuenta que su caso probablemente requiera un guardián múltiple de lector único (SWMRG) en el que múltiples subprocesos de escritorios pueden acceder a la pila (pero solo uno en un momento determinado) y en el que varios lectores pueden acceder al pila (muchos en un punto dado en el tiempo). Richter tiene el reference implementation.

1

Si no desea utilizar el bloqueo, debe utilizar una pila sin bloqueo. Esto realmente no es tan difícil (la cola libre de bloqueos es más difícil). Necesita una primitiva de comparación de comparación específica de plataforma, como InterlockedCompareExchange en Windows, pero esto no es difícil de abstraer.

Vea aquí un ejemplo en C#:

http://www.boyet.com/Articles/LockFreeRedux.html

0

Si está ejecutando en Windows, SLIST implementa una pila lockfree (con las estructuras SLIST_HEADER & SLIST_ENTRY).

El algoritmo se implementa utilizando una lista de enlaces individuales push/pop bastante trivial utilizando funciones interconectadas. El único elemento no obvio es el incremento del contador para evitar problemas de ABA.

+0

Gracias. Espero que esto sea útil para otros. Me estaba ejecutando en Linux y usé la solución de bloqueo de ámbito anterior. Al final, puse el código de bloqueo en el código en lugar de la estructura. – bugmenot77