Потокобезопасный стек C ++ - PullRequest
14 голосов
/ 26 апреля 2009

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

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

EDIT:

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

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

Ответы [ 6 ]

21 голосов
/ 26 апреля 2009

Да: 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 имеет классы «блокировки прицела», которые затрудняют попадание в ногу, забывая снять блокировку.

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

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, которое ваш коллега украдкой добавил в середине вашей функции, или просто достигнув конца функции.

4 голосов
/ 26 апреля 2009

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

1 голос
/ 26 апреля 2009

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

Смотрите пример для C #:

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

1 голос
/ 26 апреля 2009

Нет встроенного механизма для поддержки этого ни в C ++, ни в библиотеках Boost (примечание: некоторые люди написали многопоточные стеки и т. Д. В стиле Boost ). Вам придется позаимствовать некоторый код или готовить в своей собственной синхронизации.

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

1 голос
/ 26 апреля 2009

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

0 голосов
/ 28 мая 2009

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

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

...