Потокобезопасный стек С++

Ответ 1

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

См. здесь пример на С#:

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

Ответ 6

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

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