When is a mutex prefarable to a condition variable?

Question

I discovered a mutex starvation problem and the propose answer is to use condition variables instead

int main ()
{
    std::mutex m;
    std::condition_variable cv;
    std::thread t ([&] ()
    {
        while (true)
        {
            std::unique_lock<std::mutex> lk(m);
            std::cerr << "#";
            std::cerr.flush ();
            cv.notify_one();
            cv.wait(lk);
        }
    });

    while (true)
    {
        std::unique_lock<std::mutex> lk(m);
        std::cerr << ".";
        std::cerr.flush ();
        cv.notify_one();
        cv.wait(lk);
    }
}

Since the starvation problem on my platform made even the simple demo situation practically unusable, is there any reason I would not want a condition variable instead of a mutex?

As in, if the guarantees on mutex fairness are nonexistant and I can expect my ordinary Ubuntu platform to pathologically starve one mutex under normal circumstances, it would seem like using a mutex is never the sensible option in real world conditions.

When, if ever, would it be better to use a mutex instead of a condition variable?

Answer 1

You should almost always use a mutex. It should be your default means of synchronization. It's light and efficient. There are two cases where you should use a condition variable:

1. The very rare case where the mutex will be locked most of the time. Typically, most work done by threads doesn't impact shared data so most threads do most of their work holding no mutexes. In the rare case where a lock would be held most of the time, a mutex is not a good fit. Your example falls into this case.

2. The less rare case is where you need one thread to wait for another thread to finish something. For example, say you have a cache that holds some data. A thread might acquire a lock on the cache and see if some data is in the cache. If so, it'll use the cached copy. If not, it'll work out the data itself and then put it in the cache. But what if a new thread looks for the data in the cache while another thread is working it out? That thread needs to just wait for the other thread to put the data in the cache. A mutex is a bad fit for making one thread wait for another.

For the typical case where you have some shared data that needs to be briefly accesses by more than one thread, a mutex is the best fit. In the vast majority of cases, the mutex will be unowned when a thread tries to acquire it, so whether it provides fairness or not won't matter at all.

Waiting should be rare. If one thread spends most of its time waiting for another thread, it usually shouldn't be its own thread. In your example, you have two threads where neither can make any progress unless the other is stopped and either can make infinite progress while the other is stopped. That almost never happens in any realistic situation and usually indicates a serious design problem.

If you are worried about fairness, you are doing something wrong. Your code should only do work that you want done. If your code is doing the wrong work, then you didn't code it to do the work you most wanted done. Fix that. Generally speaking, it's the implementation's job to make your code make as much forward progress as possible and it's your job to make your code make the right forward progress.

Here's a quick and dirty implementation of a fair lock that checks if another thread is already waiting for the lock and gives it a chance to acquire the lock:

#include <mutex>
#include <thread>
#include <condition_variable>
#include <iostream>

class fair_lock
{
    private:

    std::mutex m;
    std::condition_variable cv;
    int locked = 0;
    int waiter_count = 0;

    public:

    void lock()
    {
        std::unique_lock<std::mutex> lk(m);

        ++waiter_count;

        // if someone was already waiting, give them a turn
        if (waiter_count > 1)
            cv.wait(lk);

        // wait for lock to be unlocked
        while (locked != 0)
            cv.wait(lk);

        --waiter_count;
        locked = 1;
    }

    void unlock()
    {
        std::unique_lock<std::mutex> lk(m);
        locked = 0;
        cv.notify_all();
    }
};

int main ()
{
    fair_lock m;

    std::thread t ([&] ()
    {
        while (true)
        {
            std::unique_lock<fair_lock> lk(m);
            std::cerr << "#";
            std::cerr.flush ();
        }
    });

    while (true)
    {
        std::unique_lock<fair_lock> lk(m);
        std::cerr << ".";
        std::cerr.flush ();
    }
}

..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.

Notice the two dots at the beginning? One thread was able to run twice before the other thread got started. This "fair" lock allows one thread to continue to make forward progress if no other thread is waiting.

This implementation only holds the mutex while the fair lock is being acquired or released, so contention on the mutex is minimal. The condition variable is used to allow one thread to wait for another to make forward progress. The code itself ensures that the desired thread makes forward progress (by blocking the thread we don't want to make forward progress), properly allowing the implementation to focus on allowing the code to make as much forward progress as possible.