Thread-safe C++ stack

Question

I'm new to C++ and am writing a multi-threaded app whereby different writers will be pushing objects onto a stack and readers pulling them off the stack (or at least pushing the pointer to an object)..

Are there any structures built-into C++ which can handle this without adding locking code etc.? If not, what about the Boost libraries?

EDIT:

Hi. Thanks for the initial great answers. I guess one reason I thought this could be built-in was that I was thinking purely in x86 space and thought that a PUSH/POP of pointers should be an atomic action at the instruction level.

I'm not sure if my initial hunch is true or not, but I guess this would not necessarily be true across all platforms. Though if running on x86, do you get atomic PUSHes and POPs to the stack and if so, does this essentially make it lock-free?

Solution 1

Yep: Boost.Thread is great, and should fit your needs very well. (These days, many people say that you could almost count Boost as built-in functionality.)

There is still no class that you could use out-of-the-box, but once you have the synchronization primitives at hand, it really is quite simple to implement your own thread-safe wrapper around, for example, std::stack. It could look something like this (not implementing every method...):

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

---

If you are new to C++, please learn about RAII. Relevant to this case, Boost.Thread has the "scoped lock" classes to make it difficult to shoot yourself in the leg by forgetting to release a lock.

If you ever find yourself writing code like this:

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

, then you should just say no, and go RAII instead (syntax not directly from Boost):

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

The point is that when the scoped_lock object goes out of scope, its destructor releases the resource -- in this case, the lock. This will always happen, no matter whether you exit the scope by throwing an exception, or by executing the odd return statement that your colleague sneakily added in the middle of your function, or simply by reaching the end of the function.

Solution 2

AFAIK, no built in support in C++. You will have to synchronize the stack operations using a simple synchronization tool. CriticalSection would do if threads belong to same proceass otherwise go for Mutex.

Solution 3

If you don't want to use locking, you need to use a lock-free stack. This is actually not that hard (lock-free queue is more difficult). You do need a platform-specific compare-exchange primitive, such as InterlockedCompareExchange on Windows, but this isn't hard to abstract.

See here for an example in C#:

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

Solution 4

The C++ 11 standard, introduced a memory model as well as standard tools for thread-safe programming.

The excellent example by Reuanen can be rewritten with those tools, that are quite similar in use as in the boost example.

You need these headers:

#include <mutex> // defines mutexes and locks
#include <stack>

Then your can create your thread-safe stack:

template <typename T> class MyThreadSafeStack {
  public:
    void push(const T& item) {
      std::lock_guard<std::mutex> lock(m_mutex);
      m_stack.push(item);
    }
    void pop() {
      std::lock_guard<std::mutex> 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
      std::lock_guard<std::mutex> lock(m_mutex);
      return m_stack.top();
    }

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

Naturally, you can also use non-locking constructions with atomic operation, however, this is more complex. I can add an example when people are interested.

View more solutions

Comments

[Jake Roberts]

Awesome answer. Thanks, this was very clear answer and very helpful!

[ASk]

You should note that std containers are not thread-safe even when locked down by a mutex. The reason is that their modification invalidates existing iterators.

[Jake Roberts]

Thanks. I hope this is useful for others. I was running on Linux and used the scoped lock solution above. In the end, I put the locking code in the code rather than the structure.

[Asim Ihsan]

@ASk - If you are iterating over a shared STL container (or any shared container for that matter) then you should probably be locking then as well. For example, if you are going to iteratively perform read-only actions on the contents of a container, you could obtain a read lock so that no one can invalid your iterator with a write during that operation. Additionally, you'll need to obtain a write lock to make changes to that structure to be forced to wait until current reads (outstanding iterators) complete.

[maciekm]

@Pukku Can I use entercriticalsection in pop and push method in your example above, instead boost::mutex::scoped_lock lock(m_mutex)?

[Reunanen]

@maciekm: Sure you can, but the problem is that then you need to be certain that you always call LeaveCriticalSection as well – even if an exception is thrown. So in this respect, it's not any better than calling myLock.lock() and myLock.unlock() in the example. As I wrote: please learn about RAII.

[David]

How will client use this class. Let say the stack is empty and the client called stk.pop(). What will this function return? Shouldn't it be block (using condition variable). Even if you prove stk.empty() there is no safe way to use in client without explicity locking if(stk.empt()) stk.pop();

[Reunanen]

@David Yes, you are absolutely correct. This was meant as an example (of wrapping standard containers inside thread-safe classes), rather than a fully functional implementation that is ready for production use.

[LimingFang]

I should say that your implementation is not thread-safe, even though the single member function is safe, but when user combined some of them, it's not safe anymore. For example, User calls stack.top() then stack.pop(). If there are two threads, one possible execution will result in two of the top() return the same value and another one is dropped.

[Reunanen]

@LimingFang: Yes, the application programmer needs to know how to use this – what can be done, and what cannot. In actual production code, I might have written an atomic get_top_and_pop_it method instead, or something like that. But different applications need different things, which is why I think it's pretty smart that the STL doesn't even try to include this functionality.

[LimingFang]

@Reunanen Yep. Also, <<C++ concurrency in action>> notes many advice and it's really nice. For example, like what you've said, combine the two methods, and provides users with some options.

[Spencer]

Just so we're all clear: This is a pre-C++11 answer from 12 years ago, and a whole bunch of multithreading stuff has been added to the base language in the years since.

[Emmef]

Better late than never: I added an example that rewrites this excellent answer to C++11 or newer here.