Thread-safe C++ stack

Question

Я новичок в C++ и пишу многопоточное приложение, в котором разные авторы будут толкать объекты в стек, а читатели вытаскивают их из стека (или, по крайней мере, нажимают указатель на объект) ..

Существуют ли какие-либо структуры, встроенные в C++, которые могут обрабатывать это без добавления кода блокировки и т. Д.? Если нет, как насчет библиотек Boost?

EDIT:

Hi. Спасибо за начальные большие ответы. Я предполагаю, что одна из причин, по которой я думал, что это может быть встроено, состояла в том, что я думал чисто в пространстве x86 и думал, что PUSH/POP указателей должен быть атомарным действием на уровне инструкций.

Я не уверен, что моя первоначальная догадка верна или нет, но я думаю, это не обязательно было бы верно для всех платформ. Хотя, если вы работаете на x86, вы получаете атомарные PUSHes и POP в стек, и если да, то делает ли это по существу сделать его заблокированным?

Answer 1

Да, Boost.Thread Отлично, и он должен соответствовать вашим потребностям очень хорошо. (В наши дни многие говорят, что вы можете почти подсчитать Boost как встроенную функциональность.)

До сих пор нет класса, который можно было бы использовать из коробки, но как только у вас есть примитивы синхронизации , на самом деле довольно просто реализовать собственную потокобезопасную оболочку, например, std::stack. Это может выглядеть примерно так (не реализует каждый метод ...):

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

---

Если вы новичок в C++, пожалуйста, узнать о RAII. В этом случае Boost.Thread имеет классы «scoped lock», которые затрудняют съемку в ноге, забыв выпустить блокировку.

Если вы когда-нибудь сами писать код, как это:

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

, то вы должны просто сказать нет, и идти RAII вместо (синтаксис не напрямую от Boost):

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

точки заключается в том, что когда объект scoped_lock выходит за пределы области видимости, его деструктор освобождает ресурс - в этом случае - блокировку. Это всегда произойдет, независимо от того, выходите ли вы из области действия, бросая исключение или выполняя нечетное утверждение return, которое ваш коллега скрытно добавил в середине вашей функции или просто дошел до конца функции.

Answer 2

Нынешний стандарт C++ не касается нитей на всех, поэтому ответ на ваш первый вопрос - нет. И вообще, это плохая идея построить блокировку в базовых структурах данных, потому что у них недостаточно информации для правильной и/или эффективной работы. Вместо этого блокировка должна выполняться в классах, которые используют структуры данных - другими словами, в ваших собственных классах приложений.

Answer 3

AFAIK, нет встроенной поддержки в C++. Вам придется синхронизировать операции стека с помощью простого инструмента синхронизации. CriticalSection будет делать, если потоки принадлежат к одному прокси-файлу, в противном случае для Mutex.

Answer 4

Нет встроенного механизма для поддержки этого на C++ и в библиотеках Boost (примечание: некоторые люди написали thread-safe stacks/etc. in the Boost style). Вам придется заимствовать код или готовить в вашей собственной синхронизации.

Обратите внимание, что ваш случай, возможно, требует защиты от нескольких считывателей с одним писателем (SWMRG), в котором несколько потоков записи могут обращаться к стеку (но только одному в данный момент времени) и в котором несколько читателей могут получить доступ к стек (многие в данный момент времени). У Рихтера есть reference implementation.

Answer 5

Если вы не хотите использовать блокировку, вам необходимо использовать стоп-блокировку. На самом деле это не так сложно (заблокированная очередь сложнее). Вам нужен примитив для обмена данными с платформой, такой как InterlockedCompareExchange в Windows, но это не сложно абстрагироваться.

Смотрите здесь для примера в C#:

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

Answer 6

Если вы работаете в Windows, SLIST реализует стек lockfree (со структурами SLIST_HEADER & SLIST_ENTRY).

Алгоритм реализован с использованием довольно тривиального точечного перетаскиваемого стека списков push/pop с использованием блокированных функций. Единственный неочевидный элемент - это приращение счетчика, чтобы избежать проблем с ABA.