3

In my program I have a single mutex and two threads. One of these threads acquires the lock very often. The other thread tries to acquire but has to wait forever.

Could it be that the lock is acquired so quick after releasing it that the other thread does not get a chance? Does a mutex always give everyone a chance? If not, what would be a good solution?(some kind of FIFO lock?)

I am using std::mutex and std::lock_guard

Question expansion seccpur pointed out that an std::condition_variable would be a solution to this problem. How does this scale with three threads? Does std::condition_variable assure every thread gets a turn? Assuming you use notify_one().

Aart Stuurman
  • 3,188
  • 4
  • 26
  • 44
  • 1
    Conditional variable should work perfectly in your case – seccpur Oct 05 '16 at 15:30
  • Are you using std::mutex and std::lock_guard? std::condition_variable? It would be nice to see some code. – davepmiller Oct 05 '16 at 15:31
  • I'm using std::mutex and std::lock_guard. – Aart Stuurman Oct 05 '16 at 15:32
  • @seccpur How would condition_variable scale with three threads? Could it be that two threads together starve out a third thread? – Aart Stuurman Oct 05 '16 at 15:51
  • @AartStuurman: Use notify_all to broadcast to multiple threads – seccpur Oct 05 '16 at 15:55
  • @seccpur notify_all confuses me. notify_one allows one thread to continue, giving it lock ownership. What happens then with notify_all? As far as I understand only one unique_lock can be locked at the same time? – Aart Stuurman Oct 05 '16 at 16:18
  • @AartStuurman: conditional varaible combine with or without std::atomic can filter a particular thread out of the three waiting threads. – seccpur Oct 05 '16 at 16:20
  • That is what I thought of. But would that have the same result as just calling notify_one? – Aart Stuurman Oct 05 '16 at 16:22
  • @AartStuurman Say three threads are all waiting for a particular computational result to be available. Once the result is available, all three threads need to stop waiting for it to be available, right? – David Schwartz Oct 05 '16 at 17:00
  • @David Schwartz In general that is what I would expect of notify_all, yes. But as I understand, the provided unique_lock is locked after passing through the conditional wait. Which of the threads is responsible for unlocking? That is what confuses me. – Aart Stuurman Oct 06 '16 at 06:59
  • @AartStuurman The thread that holds the mutex is responsible for unlocking it. – David Schwartz Oct 06 '16 at 07:00

3 Answers3

4

An std::mutex does not guarantee giving everyone an equal chance. So it is possible that one thread starves another. The first thing you can try is to insert std::this_thread::yield() and see if it helps. If this does not help, then your code must have logic errors. Post some portion of the code and we can help you diagnose further.

Donghui Zhang
  • 1,133
  • 6
  • 8
3

Using seccpur's hints I came up with the following solution to prevent starving out a single thread.

#include <condition_variable>
#include <mutex>
#include <atomic>

class NoStarveLock
{
    std::condition_variable condition;
    std::atomic_flag flag = ATOMIC_FLAG_INIT;
    std::mutex conditionLock;
public:
    void lock()
    {
        std::unique_lock<std::mutex> lck(conditionLock);
        while (flag.test_and_set()) // multiple threads can wake up at the same time, so use a set+test
        {
            condition.wait(lck); // wait for a wakeup
        }
    }

    void unlock()
    {
        std::unique_lock<std::mutex> lck(conditionLock);
        flag.clear();
        condition.notify_all();
    }
};
Aart Stuurman
  • 3,188
  • 4
  • 26
  • 44
  • nice solution, but it seems it can have some scalability issues because if few threads are releasing from wait on the same time you don't have guaranteed which one would set the flag first and a thread can be staved by other threads I recommended you to take a look at the solution offered in this answer (fix Olaf's suggestion) https://stackoverflow.com/a/14792685/4834897 – Or Hirshfeld May 07 '20 at 07:32
  • This is still potentially unfair. Suppose thread A owns the flag, and B and C are waiting. A's notify_all wakes up both threads, and B wins the race and gets the flag. When B finishes, it wakes up A and C, and A wins the race. A and B keep winning the race and C gets starved out. If you want FIFO, you need to keep track of who has been waiting the longest and make sure they get the flag next. Even with only two threads A and B, this is potentially unfair: A can release the flag and notify_all to wake up B, but before B can claim the flag, A immediately does a lock() and claims it again. – Raymond Chen Oct 27 '21 at 10:11
0

An example using std::mutex, std::lock_guard, std::unique_lock(reader) and std::condition_variable. _mutexLockCondition, _mutexObject, and _dataContainer are shared between ReaderClass and WriterClass.

Tried to be a bit vague on the actual data container, so getDataContainer() and addDataToContainer() are up to you.

std::shared_ptr< Data > ReaderClass::read()
{
    std::unique_lock< std::mutex > lock( _mutexObject );

    // handle spurious wakeup from waitForMessageNotification
    while( _dataContainer.empty() )
    {
        if( waitForMessageNotification( lock ) )
        {
            // timeout occurred, return nullptr to prevent blocking
            return nullptr;
        }
    }

    return getDataFromContainer();
}

bool ReaderClass::waitForNotification( unique_lock< mutex > & lock )
{
    //_mutexLockCondition is a std::condition_variable
    return _mutexLockCondition.wait_for( lock, std::chrono::milliseconds( 100 ) )
                                            == std::cv_status::timeout;
}


void WriterClass::write( std::shared_ptr< Data > dataPtr )
{
    std::lock_guard< mutex > lock( _mutexObject );

    addDataToContainer( dataPtr );

    _mutexLockCondition.notify_one();
}
davepmiller
  • 2,620
  • 3
  • 33
  • 61