Why unable to acquire a semaphore immediately when another thread releases it?

Question

Here is code:

#include <iostream>
#include <semaphore>
#include <thread>
#include <chrono>

std::binary_semaphore sema{ 1 };

int main()
{
    std::thread th([]
        {
            while (true)
            {
                sema.acquire();
                std::cout << "still hold\n";
                std::this_thread::sleep_for(std::chrono::milliseconds(50));
                sema.release();
            }
        });

    std::this_thread::sleep_for(std::chrono::seconds(1));

    std::cout << "try get\n";
    sema.acquire();
    std::cout << "semaphore get\n";

    std::this_thread::sleep_for(std::chrono::seconds(10000));
}

Main thread should be able to obtain this semaphore immediately, because the std::thread quickly releases and reacquires the semaphore, and the main thread should be able to obtain this semaphore at this time.

But in fact the main thread does not get this semaphore immediately, but after the std::thread th loops many times, maybe only a few times, or maybe dozens of times.

I use msvc(c++20).

So why can't the main thread get it immediately?

Answer 1

The C++ threading and concurrency model does not guarantee "fairness" or "starvation freedom" in threads waiting for locks. Depending on the implementation, releasing the semaphore will mark the main thread as "ready to run", but won't necessarily hand the semaphore to the main thread, and won't necessarily immediately start it executing. And since the very next thing the th thread does is reacquire the semaphore, there's just no time for the main thread to grab it. (The main thread is in fact woken many times, but upon waking it sees that the semaphore has already been taken, and goes back to sleep.) It is possible to implement semaphores in a way which does guarantee fairness but it's more complicated and lowers performance, particularly on multi-core systems.

If you want to guarantee fairness in something like this, condition variables are a better approach, since they involve the thread explicitly yielding to one or each thread waiting to grab a particular mutex.

Incidentally, this aspect of semaphore implementations (threads may wake up and immediately go back to sleep) can become a serious problem if there are many threads waiting for the semaphore, since all of them get woken when the semaphore is released but at most one of them will get to grab it. This is known as the thundering herd problem.