Using Threads With A Stack (C++)

Question

I try to create a stack with using Threads, my code:

Push function (m is mutex)

void Stack::Push(int num){  
    m.lock();
    sta[current++] = num;
    m.unlock();
}

Pop function:

int Stack::Pop(){
    if (current > 0){
        m.lock();
        int a = sta[--current];
        m.unlock();
        return a;
    }
    return sta[0];
}

The Main:

void threadsPrint(string s){
    m1.lock();
    cout << s << endl;
    m1.unlock();
}

void func(Stack & t){
    threadsPrint("T1 Push 1\n");
    t.Push(1);
    threadsPrint("T1 Push 2\n");
    t.Push(2);
    threadsPrint("T1 Push 3\n");
    t.Push(3);
    threadsPrint("T1 Push 4\n");
    t.Push(4);
    threadsPrint("T1 Push 5\n");
    t.Push(5);
    threadsPrint("T1 Push 6\n");
    t.Push(6);
}

void func2(Stack & t){
    threadsPrint("T2 Pop "+to_string(t.Pop())+"\n");
    threadsPrint("T2 Pop " + to_string(t.Pop()) + "\n");
    threadsPrint("T2 Pop " + to_string(t.Pop()) + "\n");
    threadsPrint("T2 Pop " + to_string(t.Pop()) + "\n");
    threadsPrint("T2 Pop " + to_string(t.Pop()) + "\n");
    threadsPrint("T2 Pop " + to_string(t.Pop()) + "\n");
}

int main(){
    Stack t;

    thread t1(func,ref(t));
    thread t2(func2,ref(t));
    t1.join();
    t2.join();
    return 0;
}

Output:

   T1 Push 1

   T2 Pop -842150451

   T1 Push 2

   T2 Pop 1

   T1 Push 3

   T2 Pop 2

   T1 Push 4

   T2 Pop 3

   T1 Push 5

   T2 Pop 4

   T1 Push 6

   T2 Pop 5

I know it's bad code, but I'm just trying to work with threads I still don't get proper result, what do I have to fix the code?

Answer 1

As per my observation the code is prone to race condition i.e. where the output of the program depends on the scheduling of its instructions.

looking at your code let's consider this scheduling scenario.

First thread 1 is scheduled and it enters func.

prints "T1 Push 1"

Context switch to T2 before it entered into push routine. Current remains 0 and nothing written over it.

prints "T2 Pop" and calls pop. Now doing --current will make you access stack[0] i.e. a garbage value. Zero if stack is global or some bad value otherwise.

Context switch back to t1 and continues at "T1 Push 2" and so on.

Hence the output which you're getting. It may give correct output a few times but if scheduling happens differently, it gives bad output.

So when your pop thread hits current 0 instead of returning stack[0] which may be garbage its wise to wait until something is pushed into stack.

I've written the code using wait and signal mechanism using pthreads.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <iostream>
#include <stack>

using namespace std;

pthread_mutex_t mutex;
pthread_cond_t condv;

pthread_mutexattr_t mattr;
pthread_condattr_t cattr;

int  FLAG= 0; //for wait and notify.

int current = 0;
int s[100] ; //stack


void push(int num)
{
    pthread_mutex_lock(&mutex);
    cout<<"push: curr "<<current<<endl;
    s[current++] = num;
    FLAG = 1; //Done pushing. Set flag.
    pthread_cond_signal(&condv); //notify other thread
    pthread_mutex_unlock(&mutex); // release mutex
}

int pop()
{
    int a = -1;
    pthread_mutex_lock(&mutex);
    while(FLAG == 0) {
        pthread_cond_wait(&condv,&mutex); //wait until the FLAG is unset.
    }
    if(current > 0)
    {
        cout<<"pop: curr "<<current<<endl;
        a = s[--current];
        if(current == 0) //If you're removing the last element of stack unset FLAG.
            FLAG = 0;
        pthread_mutex_unlock(&mutex);
        return a;
    }
    pthread_mutex_unlock(&mutex);
    return a;
}

void* t1(void *arg)
{
    cout<<"pushing 1\n";
    push(1);

    cout<<"pushing 10\n";
    push(10);

    cout<<"pushing 12\n";
    push(12);

    cout<<"pushing 4\n";
    push(4);

    cout<<"pushing 6\n";
    push(6);

    cout<<"pushing 7\n";
    push(7);
}

void* t2(void *arg)
{
    cout<<"Popped "<<pop()<<endl;
    cout<<"Popped "<<pop()<<endl;
    cout<<"Popped "<<pop()<<endl;
    cout<<"Popped "<<pop()<<endl;
    cout<<"Popped "<<pop()<<endl;
    cout<<"Popped "<<pop()<<endl;
}


int main()
{
    pthread_t thread1, thread2;

    pthread_mutexattr_init(&mattr);
    pthread_mutex_init(&mutex, &mattr); 

    pthread_condattr_init(&cattr);
    pthread_cond_init(&condv, &cattr);  

    pthread_create(&thread1, NULL, &t1, NULL);
    pthread_create(&thread2, NULL, &t2, NULL);


    pthread_mutexattr_destroy(&mattr);
    pthread_condattr_destroy(&cattr);


    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);

return 0;
}

Answer 2

One possible interleaving that would give the first few values you're seeing:

T1                                   T2
threadsPrint("T1 Push 1\n");
                                     threadsPrint("T2 Pop "+to_string(t.Pop())+"\n");
t.Push(1);

When T2 executes t.Pop() you'll get a garbage value, and T1 printed its output before it pushed, so the trace is wrong.

To fix the trace so it reflects the operations better, you need to move the trace output inside the lock (or add yet another lock).
To fix the "pop-bug", you need to wait until there's something on the stack before you pop anything.

Answer 3

if current > 0){
    m.lock();

You cannot check current outside the m.lock(). Is subject to race conditions.

int Stack::Pop(){
  m.lock();
  int a = current ? sta[--current] : sta[0];
  m.unlock();
  return a;
}

But your stack is still fundamentally unable to distinguish between popping the last item or popping on an empty stack. Personally I would prefer something like:

boolean Stack::Pop(int& val){
  boolean ret = false;
  m.lock();
  if (current) {
     val = sta[--current];
     ret = true;
  }
  m.unlock();
  return ret;
}

The problem of waiting for the stack to grow, when empty, is delegated to the caller. A fully fledged producer-consumer stack with wait and signaling is beyond the scope here.

Of course, lock()/unlock() should be RAII.

Answer 4

I think you may want to use a condition variable in addition to the mutex so that the Pop function will wait for something to be pushed if there is nothing on the stack.

In Push() you can call cv.notify_one(); and in Pop() you can call cv.wait(m, []{return current > 0;});

See an example here: http://en.cppreference.com/w/cpp/thread/condition_variable