What happens when two threads attempt a try_lock() on the SAME mutex at the EXACT same time?

Question

This is my second post. My first post was as an undergrad from an Intro to C class. I hope I do better this time.

I am developing a stochastic model for my research and I am looking for means of increasing computational efficiency in my algorithms. I have recently been introduced to multithreading by a colleague, and I have implemented it successfully into a few of my algorithms that did not require locks...

Now I am trying to modify/thread an algorithm that will require locks. In my literature/StackOverflow/google searches, I have learned quite a lot about the mutex class. However, the problem I am facing seems to be unique. For context, the closest thing I could find to an answer was here:

What happens when two threads ATTEMPT to lock the same resource at the exact same time?

It still didn't directly address the question I am about to ask.

I have been attempting to control memory access between threads using a dynamically allocated array of pointers to mutex objects. My code compiles without warnings/errors (compiled w/flags -pthread -std=c++11), and executes perfectly up until this threaded algorithm where a Segfault is thrown. Upon investigating with lldb I found that the exception being thrown is as follows:

lldb output screenshot

Upon further investigation, I found that the threads being referenced by the lldb output are all attempting a try_lock() on the EXACT SAME mutex object since the pointer array containing the address of that object was passed to each thread.

My question, which is similar to the previously mentioned post is:

What happens when a try_lock() is attempted by multiple threads (more than one) on the same mutex at the EXACT SAME time (same stroke of the processor clock)? Do newer implementations of the mutex class have workarounds for this seemingly catastrophic event (i.e. shard_mutex, timed_mutex, etc)?

This has recently been blowing my mind, so any insight would be greatly appreciated. Big shoutout to the S/O community for all the help, on this post and on all others that have been invaluable to my growth as a programmer.

LINK TO CODE:

https://github.com/tylerbalbright/StackOverflow_7_4.git

Error occurs in the RVEdata.cpp either at line 751 or 857.

FIXED BUT NOT SOLVED:

I was able to fix my code using a deque of mutex objects as opposed to creating a vector of pointers to dynamically created mutexes. The solution had been proposed by other users here:

How can I use something like std::vector<std::mutex>?

In my first (unsuccessful) trial, I was attempting to create an array of pointers to mutexes like this:

long int N = RuntimeVector.size(); //Varying size at runtime
std::mutex *MutexPtrs;
MutexPtrs = new std::mutex[N];

I would then pass the newly created array to a function as a pointer which would pass the pointer to the array to a new thread like this:

void SomeFunction(std::mutex *PosLocks[])
{
.
..
...

    SearchersPos.push_back(std::async(std::launch::async, &RVEdata::PositiveSearch, this, PosLocks));
}

Using this method, the code didn't fail on EVERY execution, but it failed like 90% of the time with EXC_BAD_ACCESS. What is interesting though, is that on EVERY failed execution the bad access was thrown when multiple threads were attempting to try_lock the same mutex. It NEVER failed with just 1 thread attempting a try_lock on a lone mutex. When I ran the same code on our HPC, the failures occurred like 95% of the time, but I couldn't find as much information in gdb as I could in lldb (I am less proficient in command line gdb).

PS - I am operating on macOS High Sierra 10.13.6, Apple LLVM version 10.0.0 (clang-1000.11.45.5).

Answer 1

When more than one thread does a try lock at the exact same time, one of them ends up with the lock and the others fail.

Your princess bug is in another castle caused by something else.

Answer 2

What happens when a try_lock() is attempted by multiple threads (more than one) on the same mutex at the EXACT SAME time (same stroke of the processor clock)? Do newer implementations of the mutex class have workarounds for this seemingly catastrophic event (i.e. shard_mutex, timed_mutex, etc)?

There is absolutely nothing catastrophic about it, this is what mutexes are for. You have not found a flaw in how mutexes work, select is not broken. You should read The First Rule of Programming by one of StackOverflow's founders.

In my first (unsuccessful) trial, I was attempting to create an array of pointers to mutexes like this:

The problem is that you're creating two arrays of mutexes:

std::mutex *PosLocks;
std::mutex *GndLocks;

PosLocks = new std::mutex[N];
GndLocks = new std::mutex[N];

But then you're passing the addresses of the arrays:

NetExists = FindNetwork(N, &PosLocks, &GndLocks);

which calls this function:

bool RVEdata::FindNetwork(long int N, std::mutex *PosLocks[], std::mutex *GndLocks[])

So now you have passed std::mutex** arguments to the function, which could be either a pointer to an array of mutexes or an array of pointers to mutexes.

And then you're accessing them as an array of mutex* instead of a pointer to mutex[]:

    if (PosLocks[i]->try_lock() == true)

PosLocks[i] indexes into an array to obtain a mutex* and then uses the -> operator to dereference a pointer. But that's backwards! You do not have an array of mutex*!

As I said in my comment above, you're simply accessing the array incorrectly. This means the program tries to lock a mutex object at some address where there is no mutex object, because you're reading an address which is somewhere in the middle of a mutex object, not at its start.

The line above should dereference the pointer first, to get to the mutex[], and then index into the array:

    if ((*PosLocks)[i].try_lock() == true)

Or even better would be to just stop passing a pointer to the array in the first place, i.e. declare the function as:

bool RVEdata::FindNetwork(long int N, std::mutex PosLocks[], std::mutex GndLocks[])

and call it as:

NetExists = FindNetwork(N, PosLocks, GndLocks);

Now you can just access the array directly:

    if (PosLocks[i].try_lock() == true)

Even better, stop using dynamically created arrays:

std::vector<std::mutex> PosLocks;
std::vector<std::mutex> GndLocks;
// ...
NetExists = FindNetwork(N, PosLocks, GndLocks);
// ...

bool RVEdata::FindNetwork(long int N, std::vector<std::mutex>& PosLocks, std::vector<std::mutex>& GndLocks)
{
    // ...
    if (PosLocks[i].try_lock() == true)

The problem would not have happened if you'd not been mixing arrays and pointers and dynamic allocation.