Stack C++ thread-safe

Question

Sono nuovo del C++ e sto scrivendo un'app multi-thread in cui diversi scrittori spingono gli oggetti su una pila e i lettori li tirano fuori dallo stack (o almeno spingono il puntatore a un oggetto) ..

Esistono strutture integrate in C++ che possono gestire questo senza aggiungere codice di blocco, ecc.? In caso contrario, per quanto riguarda le librerie Boost?

EDIT:

Hi. Grazie per le prime grandi risposte. Immagino che una ragione per cui ho pensato che questo potesse essere integrato era che stavo pensando esclusivamente nello spazio x86 e ho pensato che un PUSH/POP di puntatori dovrebbe essere un'azione atomica a livello di istruzione.

Non sono sicuro che la mia impressione iniziale sia vera o meno, ma immagino che questo non sia necessariamente vero per tutte le piattaforme. Sebbene se si esegua su x86, si ottengono PUSH e POP atomici nello stack e, in tal caso, questo lo rende essenzialmente privo di blocco?

Answer 1

Sì: Boost.Thread è ottimo, e dovrebbe soddisfare le tue esigenze molto bene. (In questi giorni, molte persone dicono che potresti quasi contare Boost come funzionalità built-in.)

Non esiste ancora una classe che potresti utilizzare immediatamente, ma una volta che hai a disposizione i primitivi di sincronizzazione , è abbastanza semplice implementare il proprio wrapper thread-safe, ad esempio, std::stack. Potrebbe essere simile a questa (non implementare tutti i metodi ...):

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; 
}  

---

Se siete nuovi a C++, si prega di conoscere RAII. Pertinente a questo caso, Boost.Thread ha le classi "scoped lock" per rendere difficile spararti a una gamba dimenticando di rilasciare un lucchetto.

Se vi trovate mai a scrivere codice come questo:

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

, allora si dovrebbe solo dire no, e andare Raii invece (sintassi non direttamente da Boost):

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

Il punto è che quando l'oggetto scoped_lock esce dall'ambito, il suo distruttore rilascia la risorsa, in questo caso il lucchetto. Ciò accadrà sempre, indipendentemente dal fatto che tu esca dall'oscillazione lanciando un'eccezione o eseguendo l'affermazione dispari return che il tuo collega ha aggiunto di nascosto nel mezzo della tua funzione, o semplicemente raggiungendo la fine della funzione.

Answer 2

L'attuale standard C++ non affronta il threading, quindi la risposta alla prima domanda è no. E in generale, è una cattiva idea creare un blocco nelle strutture dati di base, perché non hanno informazioni sufficienti per eseguirlo correttamente e/o in modo efficiente. Invece, il blocco dovrebbe essere eseguito nelle classi che usano le strutture dati - in altre parole, nelle proprie classi di applicazioni.

Answer 3

AFAIK, nessun supporto integrato in C++. Dovrai sincronizzare le operazioni di stack usando un semplice strumento di sincronizzazione. CriticalSection farebbe se i thread appartengono allo stesso proceass altrimenti andranno per Mutex.

Answer 4

Non esiste un meccanismo integrato per supportare questo in C++ né nelle librerie Boost (nota: alcune persone hanno scritto thread-safe stacks/etc. in the Boost style). Dovrai prendere in prestito del codice o cucinare nella tua sincronizzazione.

Nota che il tuo caso probabilmente richiede una protezione per più lettori (SWMRG) a scrittore singolo in cui più thread di writer possono accedere allo stack (ma solo uno in un determinato punto nel tempo) e in cui più lettori possono accedere al stack (molti in un dato momento). Richter ha lo reference implementation.

Answer 5

Se non si desidera utilizzare il blocco, è necessario utilizzare uno stack senza lock. Questo in realtà non è così difficile (la coda senza blocco è più difficile). È necessaria una primitiva di scambio di confronti specifica della piattaforma, come InterlockedCompareExchange su Windows, ma non è difficile da astrarre.

Vedi qui per un esempio in C#:

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

Answer 6

Se si esegue su Windows, SLIST implementa uno stack lockfree (con le strutture SLIST_HEADER & SLIST_ENTRY).

L'algoritmo viene implementato utilizzando stack di elenchi collegati singolarmente push/pop utilizzando funzioni interbloccate. L'unico elemento non ovvio è l'incremento del contatore per evitare problemi ABA.