Implementing a thread-safe, generic stack in C++ on linux

Question

Hi All,

In a recent interview, I was asked to implement a thread safe generic (i.e.template based) stack in C++, on linux machine.
I quickly came up with the following (It may have compilation errors).
I got through. The interviewer probably liked something in this implementation. Maybe the design part :)
Here are a few problems that this implementation may have:-
1. Incorrect implementation to indicate overflow/underflow. There is no overflow handling since I'm using STL vector as the underlying data structure. Should there be any such handling? Also, underflow (in Pop()) yields false as return value. Should it be done by throwing of an exception?
2. Implementation of PopElem routine. Is the below implementation correct?
3. No real use of top element.
4. Better timing between start of writer and reader thread.

Please make any comments/suggestions/improvements.
Thanks.

//Implementing a thread safe generic stack.

#include<pthread.h>
#include<iostream>
#include<vector>

using namespace std;

template<typename T>
class MyStack
{
public:
//interface
bool Push(T elem);
bool Pop(T& elem);
bool IsEmpty();

//constructor
MyStack() {
pthread_mutex_init(&lock);
top = 0;
}

//destructor
~MyStack() {
pthread_mutex_destroy(&lock);
}

private:
pthread_mutex_t lock;
int top;
vector<T> stack;

bool MyStack::Push(T elem);
bool MyStack::PopElem(T& elem);
}; //end of MyStack

template<typename T>
bool MyStack<T>::Push(T elem)
{
    pthread_mutex_lock(&lock);
    PushElem(elem);
    pthread_mutex_unlock(&lock);
}

template<typename T>
bool MyStack<T>::Pop(T& elem)
{
    pthread_mutex_lock(&lock);
    PopElem(elem);
    pthread_mutex_unlock(&lock);
}

template<typename T>
bool MyStack<T>::PushElem(T elem)
{
    stack.push_back(elem);
     top = stack.size();
}

template<typename T>
bool MyStack<T>::PopElem(T& elem)
{
   if(this.IsEmpty())
   {
        return false;
   }

   elem = stack.back(); //tricky, returns a reference to the last element
   stack.pop_back(); // is elem valid after this ??
   top = stack.size();
   return true;
}      


template<typename T>
bool MyStack<T>::IsEmpty()
{
    return stack.empty();
}


class MyStackTest
{
public:
  void Initialize() {
  pthread_init(&readerT);
  pthread_init(&writerT);
  }

  void Run() {
 pthread_create(writerT,0,writer,0); 
 pthread_create(readerT,0,reader,0);
 pthread_join(&writerT);
 pthread_join(&readerT);
}

private:
pthread_t readerT;
pthread_t writerT;
MyStack<int> stack;

void reader(void);
void writer(void);
};

void MyStackTest::writer() {
  for(int i=0;i<20;i++) {
      stack.Push(i);
      cout<<"\n\t Pushed element: "<<i;
   } //end for
}

void MyStackTest::reader() {
   int elem;
   while(stack.Pop(elem))
   {
     cout<<"\n\t Popped: "<<elem;
   }
}

int main()
{
    MyStackTest Test;

    Test.Run();
}

Answer 1

Some issues:

• I would implement a Locker class to claim & free the mutex using RAII
• I would use std::stack
• I would make the user of std::stack use the Locker to implement the locking policy - having a stack that locks itself is bad design, as the stack can't know how it is to be used

Answer 2

I would add a condition variable so that "poppers" can wait without burning CPU time.

Answer 3

// tricky, returns a reference to the last element

The assignment copies the last element before it's popped off the vector, so that's fine.

As you say, "top" is pointless. You can grab the size of the vector any time you want it.

You should only ever call stack.empty() with the lock held, since there is no guarantee that it makes an atomic access. You could get an inconsistent answer if you call it while another thread is in the middle of updating the stack. So your public IsEmpty function should take the mutex, which means that you don't want to call it yourself from elsewhere.

But anyway, IsEmpty isn't very useful in parallel code. Just because it's false when you call it doesn't mean it will still be false one line later when you Pop. So either you should get rid of it from the public interface, or else you should expose the lock so that users can write their own atomic ops. In that case, I'd not have any underflow checking at all other than an assert in debug mode. But then, I've never believed in mollycoddling people who get as far as release mode without either reading the documentation or testing their code.

[Edit: How to use RAII for locks

When people say to use RAII for a lock, they don't just mean to make sure the mutex is destroyed. They mean use it to make sure the mutex is unlocked. The point is that if you have code which looks like this:

lock();
doSomething();
unlock();

and doSomething() throws an exception, then you won't unlock the mutex. Ouch.

So, here's an example class, along with usage:

class LockSession;
class Lock {
    friend class LockSession;
    public:
    Lock()        { pthread_mutex_init(&lock); }
    ~Lock()       { pthread_mutex_destroy(&lock); }

    private:
    void lock()   { pthread_mutex_lock(&lock); }
    void unlock() { pthread_mutex_unlock(&lock); }

    private:
    Lock(const Lock &);
    const Lock &operator=(const Lock &);

    private:
    pthread_mutex_t lock;
};

class LockSession {
    LockSession(Lock &l): lock(l) { lock.lock(); }
    ~LockSession()                { lock.unlock(); }
    private:
    LockSession(const LockSession &);
    LockSession &operator=(const LockSession &);

    private:
    Lock &lock;
};

Then somewhere your code will have a Lock associated with the data you want to protect, and will use it something like the following:

void doSomethingWithLock() {
    LockSession session(lock);
    doSomething();
}

or

void doSeveralThings() {
    int result = bigSlowComputation();  // no lock
    {
        LockSession s(lock);
        result = doSomething(result); // lock is held
    }
    doSomethingElse(result);     // no lock
}

Now it doesn't matter whether doSomething() throws an exception or returns normally (well, in the second example doSomethingElse won't happen on exception, but I'm assuming that's something that doesn't need to be done in an error situation). Either way, session is destroyed, and its destructor releases the mutex. In particular, operations like "push" on a stack allocate memory, and therefore might throw, and therefore you need to cope with that.

RAII stands for Resource Acquisition Is Initialization. In the case of doSomethingWithLock(), the resource you want to acquire is that you want to hold the lock. So you write a class which allows you to do that by initializing an object (the LockSession). When the object is destroyed, the lock is relinquished. So you're treating "locking/unlocking the mutex" exactly the same way you treat "initing/deiniting the mutex", and you protect yourself against resource leaks the same way.

One slightly annoying fact is that this code is completely broken and buggy, and you have to be sure not to accidentally do it, even though it looks to the careless eye just like the correct code:

void doSomethingWithLock() {
    LockSession(lock);
    doSomething();
}

Here the first line creates a temporary object and immediately destroys it, releasing the lock again. doSomething() is not called with the lock held.

Boost has a class template scoped_lock, which does what LockSession does, and more.]

Answer 4

I would throw away top at first. When you don't need it it is just waste!

Small is beautiful

Also if you wanted to optimize the accesses to vector: Duplicate handling of management information (here: stacklength) is always error prone. Better hope, that vector is brilliantly fast (STL most of the time is) and so empty() also is.

Answer 5

This isn't idiomatic C++ and might not have any advantages but just for the novelty, have you considered implementing an immutable stack? That way, it would automatically be thread-safe.

Eric Lippert has done a C# implementation. Admittedly, the C++ code would be rather more involved.

Answer 6

One thing you didn't address is the issue of thread cancellation. The stl behaves badly when a thread is canceled during an operation on an stl container. You need to disable cancellation when you are operating on the vector. I found out the hard way about this. It is no fun when you have a deadlock and the threads are all in templated stl code and you are trying to debug exactly what happened. Use pthread_setcancelstate to change the cancellation state of the threads.

Answer 7

Neil, Onebyone:
An attempt on using RAII for mutex lock. Any comments?

template<typename T> 
class MyStack
{
public:
//interface
bool Push(T elem);
bool Pop(T& elem);
bool IsEmpty();

//constructor
MyStack() {
//top = 0;
}

//destructor
~MyStack() {

}

private:
    class Locker {   //RAII
    public:
     Locker() {
      pthread_mutex_init(&lock);
     }
     ~Locker() {
      pthread_mutex_destroy(&lock);
     }
     void Lock() {
      pthread_mutex_lock(&lock);
     }
     void UnLock() {
      pthread_mutex_unlock(&lock);
     }
    private:
     pthread_mutex_t lock;
    };
Locker MyLock;
//int top;
stack<T> mystack;

bool MyStack::Push(T elem);
bool MyStack::PushElem(T elem);
bool MyStack::Pop(T& elem);
bool MyStack::PopElem(T& elem);
}; //end of MyStack

template<typename T>
bool MyStack<T>::Push(T elem)
{
    MyLock.Lock();
    PushElem(elem);
    MyLock.UnLock();
}

template<typename T>
bool MyStack<T>::Pop(T& elem)
{
    MyLock.Lock();
    PopElem(elem);
    MyLock.UnLock();
}