Thread: Am I doing the locking correctly?

My program here, tries to make a tread safe stack by using locks.

This was quite simple.. but I want to know if I'm making a conceptual mistake.
(Is using different mutex (s) for two data members which may not be accessed in the same function, a good idea?)

The test program spawns 6 threads pushing a number into the same stack, 500 times each.
And after joining them I check that the stack's size is 3000.
(Without the locking the number is about ~200 less !!..that gives me some confidence about the correctness of the code.)

Test code:

Code:

#include<thread>
#include<mutex>
#include<iostream>
#include<array>
#include<exception>
#include<functional>
#include<vector>
int main()
{
    mm::stack<int,10000> si;
    
    auto foo = [](mm::stack<int,10000>& si,int n){for(int i=0;i<500;i++)si.push(n);};
    //^ Pushes n 500 times into the stack si.
    
    std::vector<std::thread> threads;
    for(int i=0;i<6;i++)
        threads.push_back(std::thread(foo,std::ref(si),i));
    for(auto&x:threads)x.join();
    
    si.debug_print();
}

The stack:

Code:

namespace mm
{
    template<typename T, std::size_t MAX=10>
    class stack
    {
        typedef std::lock_guard<std::mutex> lgm;
    public:
        stack():head(-1){};
        bool empty()
        {
            lgm l(head_lock);
            return (head==-1);
        }
        T top()
        {
            if(empty())throw(std::runtime_error("Empty"));
            
            lgm d(data_lock),h(head_lock);
            return data[head];
        }
        std::size_t size()
        {
            lgm l(head_lock);
            return head+1;
        }
        void push(const T& t)
        {
            if(size()==MAX)throw(std::runtime_error("Overflow"));
            
            lgm d(data_lock),h(head_lock);
            data[++head]=t;
        }
        void pop()
        {
            if(empty())throw(std::runtime_error("Underflow"));
            lgm h(head_lock);
            --head;
        }
        void debug_print()
        {
            for(int i=0;i<=head;i++)
                std::cout<<data[i];
            std::cout<<"\nSize: "<<head+1;
        }
    private:
        std::array<T,MAX> data;
        int head;
        std::mutex data_lock;
        std::mutex head_lock;
        
    };
}

Not quite.

There is a general principle in multi-threaded design which says that no object (and entity that contains data) can protect itself from concurrent access.

To illustrate how that principle fails in your code, consider what happens if two threads are concurrently pushing a value to a stack that has size() equal to MAX-1. This sequence is feasible.

Code:

      thread A evaluates size(), detects the value is MAX-1, so does not throw an exception
      thread B evaluates size(), detects the value is MAX-1, so does not throw an exception.
      thread B adds a value to the stack.   The size is now MAX.
      thread A adds a value to the stack.  The size is now MAX+1.

From here on in, unless elements are popped, push() will continue growing the stack forever.

Although it might seem counter-intuitive, this sort of thing isn't fixed by just ensuring every member function grabs a mutex at the beginning, and releases it before returning. You need to have the thread function that is calling push() (or other operations) make use of an appropriate mutex. Having a mutex (or more than one mutex) managed by the same object that manages other data is insufficient.

I didn't think of that !

So, my foo function should be like this:

Code:

std::mutex m; //Is there a difference between this being a global and a static local?
void foo(mm::stack<int,10000>& si,int n)
{
    for(int i=0;i<500;i++)
    {
        m.lock();
        si.push(n);
        m.unlock();
    }
};

?
and I could use a normal stack ?


[For some reason, this is refusing to compile, despite having the same signature as the lambda......[edit]It was a typo..wrote 10000 instead of 3000 (which is my changed MAX).[/edit] ]

Originally Posted by manasij7479

So, my foo function should be like this:

Code:

std::mutex m; //Is there a difference between this being a global and a static local?
void foo(mm::stack<int,10000>& si,int n)
{
    for(int i=0;i<500;i++)
    {
        m.lock();
        si.push(n);
        m.unlock();
    }
};

?
and I could use a normal stack ?

Assuming all other functions that do anything to the stack use the same mutex, yes.

(Sorry, bit rushed, so haven't looked at the compile errors ... I'll leave that for someone else to take on)

Well, you could build a wrapper class around that stack that implements its own locking in its pop() und push() methods. That class could then be said to be "thread-safe".


P.S. Oh never mind, you did that in your original code ... there are just some holes in it.

Your pop has a problem anyway. You first call empty, which does a lock, fetches the answer and then unlocks. Then you re-lock to decrement the head.
Between that unlock and the subsequent re-lock another thread may empty the stack.
You would need to place your lock 'h' before the empty() call, assuming that type of lock allows recursive locking.

'top' has the same problem.

And as noted, you can't actually use this class safely anyway because to remove the item at the top requires a call to top and pop, and to keep it locked over the duration of both calls requires that the locking be done externally. Well either that or you add the ability for the external code to call methods that lock and unlock on this class, again relying on the external code to get it right.

Originally Posted by manasij7479

Thanks....though I wonder where the term "thread safe data structure" comes from....if everything is up to the code using it.

The word "ignorance" often comes to mind as an explanation for that.

However, there are certain things like atomic types, which are managed by the operating system. Essentially, the OS provides an API (i.e. protective code) and manages things from there. User code makes requests to the OS. However, it is possible to assemble unsafe code using atomic operations. The issue is one of design.

That got me thinking... One way this kind of thing might be able to work is if you design the interface to allow passing in lamdas / std::functions. Then your methods can lock, perform some actions according to the lambdas passed in, and then unlock and exit. You still rely on certain things about those lambdas or functions such as not being written in a way that causes a deadlock.
Essentially the callers work is done inside the callee's code. I don't think this would work very well in practice. It would probably be annoying to use and somewhat limiting in what you can do. I'm not even going to try and come up with some sample code for it. It's probably some kind of anti-pattern.

Originally Posted by iMalc

You would need to place your lock 'h' before the empty() call, assuming that type of lock allows recursive locking.

As empty itself has a lock (locking the same mutex object)... won't that result in deadlocks ?
(That was my reasoning for not doing what you say .)

[Edit: This may be solved with passing/moving the mutex object and calling std::lock with the extra argument std::adopt_lock ...but I'm absolutely not sure about this.]

Originally Posted by manasij7479

As empty itself has a lock (locking the same mutex object)... won't that result in deadlocks ?

That depends on which type of mutex you use. Under C++-11, std::recursive_mutex can be locked multiple times by one thread (the effect is increasing a lock count, so it needs to be unlocked the same number of times). std::mutex cannot (necessarily) do that.

With other libraries (posix, win32, etc) there are generally options to either create different types of synchronisation primitives (mutexes, critical sections, etc) with relevant properties.

I thought a lot about thing some time ago when I had to implement thread safe applications.
Generally, when doing thread safety, there is, except for the simple lock whenever two threads use the same object, another thing you have to keep in mind: assumptions.
In a threaded environment, serial code execution--something that we rely on everyday--no longer holds. You can't rely on it.
Assume that every function is "thread safe," that is, it locks to ensure mutual exclusion in every member function. Consider:

Thread 1:

Code:

if (stack.empty())
	stack.push("Hello World!");

Thread 2:

Code:

stack.push("I like this world!");
stack.push("I hate this world!");
stack.pop();

Totally safe code, right (if members functions lock)?
That's what you'd think, but it isn't in a threaded environment.
"Hello World!" should be pushed if and only if the stack is empty. The if statement is okay, but as soon as it ends all bets are off. You can't guarantee that the stack will be empty when the push is made (thread 2 can execute push before thread 1 does a push). Were it a single threaded application, then it would hold true, but not in a multi-threaded app.
So when building multi-threaded applications, you must take into account how long you need your assumptions to be valid.

So the correct code should be:
Thread 1:

Code:

lock();
if (stack.empty())
	stack.push("Hello World!") // Make sure the the empty state still holds here!
unlock();

Thread 2:

Code:

lock();
stack.push("I like this world!"); // Just to make sure thread 1's lock works.
unlock();
lock();
stack.push("I hate this world!");
stack.pop(); // We must ensure that "I hate this world!" was the last thing pushed onto the stack.
unlock();

Originally Posted by iMalc

That got me thinking... One way this kind of thing might be able to work is if you design the interface to allow passing in lamdas / std::functions. Then your methods can lock, perform some actions according to the lambdas passed in, and then unlock and exit. You still rely on certain things about those lambdas or functions such as not being written in a way that causes a deadlock.
Essentially the callers work is done inside the callee's code. I don't think this would work very well in practice. It would probably be annoying to use and somewhat limiting in what you can do. I'm not even going to try and come up with some sample code for it. It's probably some kind of anti-pattern.

I actually made a container wrapper that you would actually have to lock before you can access its underlying object.
Of course, the lock function returned another object whose destructor would unlock. I kind of liked the solution.