views:

1408

answers:

6

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?

+4  A: 

The current C++ standard doesn't address threading at all, so the answer to your first question is no. And in general, it is a bad idea to build locking into basic data structures, because they don't have sufficient information to perform it correctly and/or efficiently. Instead, the locking should be performed in the classes that use the data structures - in other words, in your own application classes.

anon
I have to sort-of disagree (though not downvote). I think it is perfectly okay to write a class ThreadSafeStack which wraps a private std::stack instance. Then in the beginning of each method (push, pop, ...) you enter a critical section, or similar. It is true that top() should no more return a reference but rather a copy. This causes loss in efficiency, but the added ease in writing the app classes is very often worth it, in my opinion. And in cases when not (e.g., huge objects being copied), then you just don't use the wrapper class.
Pukku
Yes, that is what I meant, but probably expressed badly - ThreadSafeStack is one of your application's classes. But a general purpose library should not (IMHO) supply such classes.
anon
Ah, ok. I was thinking of application classes as something that mainly contain business logic.
Pukku
A: 

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.

aJ
+5  A: 

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.

Pukku
Awesome answer. Thanks, this was very clear answer and very helpful!
bugmenot77
You are welcome; I'm glad if I was able to help!
Pukku
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.
ASk
@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.
Burly
A: 

There is no built-in mechanism to support this in C++ nor in the Boost libraries (note: some people have written thread-safe stacks/etc. in the Boost style). You'll have to borrow some code or cook in your own synchronization.

Note that your case probably calls for a single-writer multiple-reader guard (SWMRG) in which multiple writer threads can access the stack (but only one at a given point in time) and in which multiple readers can access the stack (many at a given point in time). Richter has the reference implementation.

James D
+1  A: 

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

Frederik Slijkerman
A: 

If you are running on Windows, SLIST implements a lockfree stack (with the structures SLIST_HEADER & SLIST_ENTRY).

The algorithm is implemented using fairly trivial push/pop singly linked list stack using interlocked functions. The only non-obvious item is the counter increment to avoid ABA issues.

Adisak
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.
bugmenot77