Such amazing semaphores

From a translator: Jeff Preshing is a Canadian software developer who has been with Ubisoft Montreal for the past 12 years. He had a hand in creating such well-known franchises as Rainbow Six, Child of Light and Assassin's Creed. In his blog, he often writes about interesting aspects of concurrent programming, especially in relation to Game Dev. Today I would like to submit to the public a translation of one of Jeff's articles.

The stream must wait. Wait until you can get exclusive access to the resource or until tasks for execution appear. One of the waiting mechanisms, in which the thread is not put to execution by the scheduler of the OS kernel, is implemented using a semaphore .

I used to think that semaphores are long out of date. In the 1960s, when very few wrote multithreaded programs, or any other programs, Edsger Dijkstra proposed the idea of ​​a new synchronization mechanism - a semaphore. I knew that with the help of semaphores you can keep track of the number of available resources or create a clumsy analogue of a mutex, but this, as I thought, their scope is limited.

My opinion changed when I realized that using only semaphores and atomic operations, you can create all the other synchronization primitives:

1. Lightweight Mutexes
2. Lightweight conditional variables
3. Lightweight read-write locks
4. Primitive for solving the problem of dining philosophers
5. Lightweight semaphore

All of these primitives are lightweight in the sense that some operations on them are performed completely in userspace, and they can (this is an optional condition) spin in the loop for a while before requesting a thread lock from the operating system (examples are available on GitHub .) my primitive library implements the Semaphore class , which is a wrapper over the system semaphores of Windows, MacOS, iOS, Linux and other POSIX-compatible OSs. You can easily add any of these primitives to your project.

Bouncer semaphore

Imagine a lot of threads awaiting execution, lined up, just like a queue in front of a trendy nightclub. A semaphore is a bouncer in front of the entrance. He allows you to go inside the club only when he is given instructions.



Each thread decides when to get into this queue. Dijkstra called this operation P , which probably was a reference to some funny-sounding Dutch term, but in modern semaphore implementations you are likely to find only the wait operation . In essence, when a thread calls the wait method , it becomes a queue.

Bouncer, i.e. semaphore, should be able to do only one operation. Dijkstra called this operation the V . To date, there is no agreement on how to name this operation. As a rule, you can come across post , release, or signal functions . I prefer signal. When this method is called, the semaphore “releases” one of the waiting threads from the queue. (It’s not necessary that it will be the same thread that called wait before others.)

And what happens if someone calls signal when there are no threads in the queue? No problem: when any of the threads calls wait , the semaphore will immediately skip that thread without blocking. Moreover, if signal is called 3 times in a row with an empty queue, the semaphore will allow the next three threads that caused wait to bypass the queue without waiting.



It goes without saying that the semaphore should count the number of signal calls when the queue is empty. Therefore, each semaphore is equipped with an internal counter, the value of which increases when the signal is called and decreases when the wait is called .

The beauty of this approach is that regardless of the order in which wait and signal are called , the result will always be the same: the semaphore will always skip the same number of threads for execution, and the same number of waiting ones will always remain in the queue.

1. Lightweight mutex

I already talked about how you can implement your own lightweight mutex in one of the previous articles . At that time, I did not know that this was only one example of the application of a common pattern, the main idea of ​​which is to delegate decision-making on blocking threads to some new entity - box office . Should the current thread wait in line? Should he pass the semaphore without waiting? Should we wake up some other thread?



Box office does not know anything about the number of threads waiting in the queue, just as it does not know the current value of the internal semaphore counter. Instead, he must somehow keep a history of his own states. If we are talking about implementing a lightweight mutex, then a single counter with atomic increment and decrement operations is enough to store history. I called this counter m_contention , because it stores information about how many threads at the same time wish to capture the mutex.

class LightweightMutex
{
private:
    std::atomic m_contention;         // The "box office"
    Semaphore m_semaphore;                 // The "bouncer"

When a thread wants to acquire the mutex, it refers to the box office, which in turn increases the value of m_contention .

public:
    void lock()
    {
        if (m_contention.fetch_add(1, std::memory_order_acquire) > 0)  // Visit the box office
        {
            m_semaphore.wait();     // Enter the wait queue
        }
    }

If the counter value is zero, then the mutex is in an unmarked state. In this case, the current thread automatically becomes the owner of the mutex, bypasses the semaphore without waiting and continues to work in the code section protected by the mutex.

If the mutex is already captured by another thread, then the counter value will be greater than zero and the current thread must wait its turn to enter the critical section.



When the thread releases the mutex, box office decreases the value of the internal counter by one:

    void unlock()
    {
        if (m_contention.fetch_sub(1, std::memory_order_release) > 1)  // Visit the box office
        {
            m_semaphore.signal();   // Release a waiting thread from the queue
        }
    }

If the counter value before decrement was less than 1, then there are no waiting threads in the queue and the m_contention value simply remains equal to 0.

If the counter value was more than 1, then another thread or several threads tried to capture the mutex, and, therefore, wait for their turn to enter critical section. In this case, we call signal so that the semaphore wakes up one of the threads and allows it to capture the mutex.



Each call to box office is an atomic operation. Thus, even if several threads call lock and unlock in parallel, they will always access the box office sequentially. Moreover, the behavior of the mutex is completely determined by the internal state of the box office. After accessing box office, threads can call semaphore methods in any order, and this in no way violates the consistency of execution. (In the worst case, threads will compete for a place in the semaphore queue.)

This primitive can be called “lightweight”, since it allows a thread to capture a mutex without accessing the semaphore, i.e. without making a system call. I posted a mutex code on GitHub called NonRecursiveBenaphore, there is also a recursive version of the lightweight mutex. However, there are no prerequisites for using these primitives in practice, since most well-known mutex implementations are lightweight anyway . However, this code serves as a necessary illustration of the approach that is used for all other primitives described in this article.

2. Lightweight conditional variable

Note transl.: in the original, the author named this primitive Auto-Reset Event Object, however, search engines on this request provide links to the C # class AutoResetEvent, whose behavior can be compared with std :: condition_variable with a few assumptions.

At CppCon 2014, I noted for myself that conditional variables are widely used when creating game engines, most often to notify one thread of another (possibly in standby mode) that there is some work for it ( note: as such work the task of unpacking graphic resources and loading them into the GL context ).



In other words, no matter how many times the signal method is called , the internal counter of the conditional variable should not become greater than 1. In practice, this means that you can queue tasks for execution by calling the signal method each time . This approach works even if a data structure other than a queue is used to assign tasks to execution .

Some operating systems provide system tools for organizing conditional variables or their analogues. However, if you add several thousand tasks at a time to the queue, calls to the signal method can greatly affect the performance of the entire application.

Fortunately, the box office pattern can significantly reduce the overhead associated with calling a methodsignal . Logic can be implemented inside the box office entity using atomic operations so that the semaphore is accessed only when it is necessary to make the thread wait for its turn.



I implemented this primitive and named it AutoResetEvent . This time, box office uses a different way of accounting for the number of threads waiting in a queue. If m_status is negative , its absolute value shows the number of threads waiting on the semaphore:

class AutoResetEvent
{
private:
    // m_status == 1: Event object is signaled.
    // m_status == 0: Event object is reset and no threads are waiting.
    // m_status == -N: Event object is reset and N threads are waiting.
    std::atomic m_status;
    Semaphore m_sema;

In the method of signal we atomically increment the variable m_status , until its value reaches 1:

public:
    void signal()
    {
        int oldStatus = m_status.load(std::memory_order_relaxed);
        for (;;)    // Increment m_status atomically via CAS loop.
        {
            assert(oldStatus <= 1);
            int newStatus = oldStatus < 1 ? oldStatus + 1 : 1;
            if (m_status.compare_exchange_weak(oldStatus, newStatus, 
                                                                           std::memory_order_release, 
                                                                           std::memory_order_relaxed))
                break;
            // The compare-exchange failed, likely because another thread changed m_status.
            // oldStatus has been updated. Retry the CAS loop.
        }
        if (oldStatus < 0)
            m_sema.signal();    // Release one waiting thread.
    }

3. Lightweight read-write lock

Using the same box office pattern, we can implement a primitive for read-write locks.

This primitive does not block threads in the absence of writers. In addition, it is starvation-free for both writers and readers, and, like other primitives, can temporarily lock a spin lock before blocking the execution of the current thread. To implement this primitive, two semaphores are required: one for expecting readers, the other for writers.

4. The problem of dining philosophers

Using the box office pattern, you can solve the problem of dining philosophers, in a rather unusual way that I have never seen before. I don’t really believe that the proposed solution will be useful to anyone, so I won’t go into the implementation details. I have included a description of this primitive just to demonstrate the universality of semaphores.

So, we assign each philosopher (stream) our own semaphore. Box office monitors which of the philosophers are currently eating, which of the philosophers asked to start a meal and the sequence of these requests. This information is enough for the box office to guide all philosophers through semaphores attached to them in an optimal way.



I suggested as many as two implementations. One of them is DiningPhilosophers , which implements a box office using a mutex. Second - LockReducedDiningPhilosophers , in which each access to box office implemented as a lock-free algorithm.

5. Lightweight semaphore

Yes, that's right: with the help of the box office pattern and the semaphore, we can implement ... another semaphore.

Why do we have to do this? Because then we get LightweightSemaphore . Such a semaphore has a very cheap signal operation when there are no waiting threads in the queue. In addition, it does not depend on the implementation of the semaphore provided by the OS. When calling signal , box office increases the value of its own internal counter, without resorting to the underlying semaphore.



In addition, you can make the thread wait for a while in the loop, and only then block it. This trick allows you to reduce the overhead associated with a system call if the wait time is less than some predetermined value.

In GitHub repositories, all primitives are based on LightweightSemaphore . This class is implemented on the basis of Semaphore , which in turn is implemented on the basis of semaphores provided by a particular OS.



I ran several tests to compare the speed of the presented primitives when using LightweightSemaphore and Semaphore on my Windows PC. The corresponding results are shown in the table:

	Lightweight semaphore	Semaphore
testBenaphore	375 ms	5503 ms
testRecursiveBenaphore	393 ms	404 ms
testAutoResetEvent	593 ms	4665 ms
testRWLock	598 ms	7126 ms
testDiningPhilosophers	309 ms	580 ms

As you can see, the operating time sometimes differs by an order of magnitude. I must say, I am aware that not every environment will have the same or similar results. In the current implementation, the thread waits for 10,000 iterations of the loop before locking on the semaphore. I quickly considered the possibility of using an adaptive algorithm, but the best way seemed to me unobvious. So I'm open to suggestions.

Comparing semaphores and condition variables

Semaphores turned out to be much more useful primitives than I expected. Why, then, are they missing in the C ++ 11 STL? For the same reason that they were absent in Boost: preference was given to mutexes and conditional variables. From the point of view of library developers, the use of traditional semaphores too often leads to errors .

If you think about it, the box office pattern is just an optimization of ordinary conditional variables for the case when all operations on conditional variables are performed at the end of the critical section. Consider the AutoResetEvent class. I implemented the AutoResetEventCondVar class with the same behavior, but using std: condition_variable. All operations on the conditional variable are performed at the end of the critical section.

void AutoResetEventCondVar::signal()
{
    // Increment m_status atomically via critical section.
    std::unique_lock lock(m_mutex);
    int oldStatus = m_status;
    if (oldStatus == 1)
        return;     // Event object is already signaled.
    m_status++;
    if (oldStatus < 0)
        m_condition.notify_one();   // Release one waiting thread.
}

We can optimize this method in two iterations:

1. We take out each conditional variable from the critical section and transform it into a semaphore. The independence of the signal - wait sequence of operations on the semaphore makes this optimization possible. After this step, our implementation of the method is already similar to the implementation of the box office pattern.
2. Now we can make the lock-free method, replacing all operations with CAS, thereby dramatically increasing the scalability of the system.

After these two simple optimizations, we get an AutoResetEvent.



On my Windows PC, simply replacing AutoResetEventCondVar with AutoResetEvent increases the speed of the algorithm by 10 times.

From a translator: I haven’t translated anything for a long time, so I will be grateful for corrections and clarifications.