5

Recently I had to implement a Semaphore using a Mutex and a Conditional Variable (this combination is also known as a Monitor) for an exercise at the university:

the Semaphore's decrement operation blocks until its counter is more than zero before decrementing,

and the increment operation increments the counter and then notifies one waiting thread.

However, I also learned that:

a Mutex is a binary semaphore with the extra restriction that only the thread decremented it can increment it later.

As these two definitions are clearly mutually recursive, I am wondering how Semaphores and Mutexes can be implemented (in pseudocode) directly, without using the other data type in their implementations.

  • 4
    I don't see how the definitions are "mutually recursive", it is just that Mutex is a particular case of Semaphore Semaphore - can notify any waiting thread Mutex - subset of Semaphore where the waiting thread is the same that called decrement operation You can find pseudocode implementations that match your requirement in Wikipedia... en.wikipedia.org/wiki/Semaphore_(programming) en.wikipedia.org/wiki/Dekker%27s_algorithm – Bruno Guardia Jan 16 '17 at 15:35
  • 3
    I agree with Bruno. A Mutex is just a special case of Semaphore. There's no mutual recursion going on here, conceptual or otherwise. – Robert Harvey Jan 16 '17 at 15:49
  • 3
    Synchronization methods are based on CPU primitives that are guaranteed to be atomic, like InterlockedCompareExchange and TestAndSet. The most fundamental operation is to read the present value of a variable while also setting it, then check if the read value allows you to proceed or if you have to undo the operation. All the rest are details... – user251748 Sep 25 '17 at 16:45
14

I think your question is more about what primitives are used to implement those, and the answer is - it depends. I will try to focus on modern implementations.

First, Linux uses futex syscall (Fast Userspace muTEX). Two most commonly used operations are FUTEX_WAIT:

This operation tests that the value at the futex word pointed to by the address uaddr still contains the expected value val, and if so, then sleeps waiting for a FUTEX_WAKE operation on the futex word.

and FUTEX_WAKE:

This operation wakes at most val of the waiters that are waiting (e.g., inside FUTEX_WAIT) on the futex word at the address uaddr.

It is very important that FUTEX_WAIT verifies value before sleeping, as this ensures thread does not miss wake-ups.

Using futex(2) it is possible to implement mutex that does not require any syscall if mutex is not contested, but is able to suspend calling thread otherwise. Example below:

struct mutex { int ftx; };

enum { UNLOCKED, LOCKED, CONTESTED };

void mutex_init(struct mutex *mtx)
{
    mtx->ftx = UNLOCKED;
}

void mutex_lock(struct mutex *mtx)
{
    if (atomic_cmpxchg(&mtx->ftx, UNLOCKED, LOCKED) == UNLOCKED)
        return;

    while (atomic_xchg(&mtx->ftx, CONTESTED) != UNLOCKED)
        futex_wait(&mtx->ftx, CONTESTED);
}

void mutex_unlock(struct mutex *mtx)
{
    if (atomic_xchg(&mtx->ftx, UNLOCKED) == CONTESTED)
        futex_wake(&mtx->ftx, 1);
}

Semaphore can be implemented like this:

struct sema { int ftx; int waiters; };

void sema_init(struct sema *sem)
{
    sem->ftx = 0;
    sem->waiters = 0;
}

bool sema_trywait(struct sema *sem)
{
    int val = atomic_load(&sem->ftx);

    do {
        if (val == 0)
            return false;
   } while ((val = atomic_cmpxchg(&sem->ftx, val, val - 1)) != val);

    return true;
}

void sema_wait(struct sema *sem)
{
    if (sema_trywait(sem))
        return;

    atomic_add(&sem->waiters, 1);

    do {
        futex_wait(&sem->ftx, 0);
    } while (!sema_trywait(sem));

    atomic_sub(&sem->waiters, 1);
}

void sema_post(struct sema *sem, int n)
{
    int val = atomic_load(&sem->ftx);

    while ((val = atomic_cmpxchg(&sem->ftx, val, val + n)) != val)
    { }

    // This accesses semaphore after unlocking. What if it was destroyed?
    // You can try to think about how this can be fixed.
    // I won't put correct implementation here due to higher complexity.
    if (atomic_load(&sem->waiters) != 0)
        futex_wake(&sem->ftx, n); // no point in waking more than 'n'
}

Condition variables are trickier. Complexity and performance of implementation depends on how much you want to stick to a "classic" interface, mainly whether you allow "notify" to be called outside of critical section or not.

State of condition variable might need to be protected by a separate mutex, so it is common for implementations to keep another mutex within a condition variable. If you allow "notify" to be only called from within critical section, additional mutex locking is not required, making implementation simpler and faster. Such combination of a mutex and a condition variable that only allows "notify" to be called from within critical section is usually called "monitor".

Languages like Java and C# both use monitors instead of mutexes and condition variables.

Another futex(2) trick is FUTEX_REQUEUE operation that can be used to move waiters from one futex to another and can be used to make condition varaible very effecient.

There is a good document "Futexes Are Tricky" about futexes written by Ulrich Drepper. It explains how futex(2) works and shows how it can be used to implemented common primitives. You can find it here.

Another decent article that shows usage of futex(2) is here, but this implementation is too "benchmark oriented".

As for other operating systems, today most provide equivalent of Linux'es futex(2):

  • WaitOnAddress, WakeOnAddress on Windows 8 and later.
  • _umtx_op(2) on OS X, FreeBSD (never used those, you can read more here).
  • I think OpenBSD partially implements futex(2) too.

Earlier versions of Windows (7, Vista, XP) are special. They provide alternative undocumented API called "Keyed Events". Just as futex(2), keyed events use table of wait queues hashed by address. There are two operations: "wait" and "release" (wake). This mechanism ensures that wake-ups are not missed by making "release" operation blocking e.g. calling threads is blocked until it actually wakes someone. Using such API requires having waiter counter in userspace. You can read more here.

If you want to see more Keyed Events in action, you should check Wine's sources and their implementation of RTL_SRWLOCK and RTL_CONDITION_VARIABLE.

Keyed events are well suited for condition variables, making implemenation is extremely simple. Condition variable is just a 4 byte counter of waiters.

Following code is simplified, you can check the original here.

void WINAPI RtlWakeConditionVariable( RTL_CONDITION_VARIABLE *variable )
{
    if (interlocked_dec_if_nonzero( (int *)&variable->Ptr ))
        NtReleaseKeyedEvent( keyed_event, &variable->Ptr, FALSE, NULL);
}

void WINAPI RtlWakeAllConditionVariable( RTL_CONDITION_VARIABLE *variable )
{
    int val = interlocked_xchg( (int *)&variable->Ptr, 0 );
    while (val-- > 0)
        NtReleaseKeyedEvent( keyed_event, &variable->Ptr, FALSE, NULL);
}

void RtlSleepConditionVariableSRW(
    RTL_CONDITION_VARIABLE *variable, RTL_SRWLOCK *lock)
{
    interlocked_xchg_add( (int *)&variable->Ptr, 1 );
    RtlReleaseSRWLockExclusive( lock );
    NtWaitForKeyedEvent( keyed_event, &variable->Ptr, FALSE, timeout 
    RtlAcquireSRWLockExclusive( lock );
}

Another way is to emulate futex-like functionality from userspace. WebKit's ParkingLot is an example of this. You can read more here. Mechanism is basically the same as with futex(2), but since it is implemented in userspace is allows execution of custom user code from inside the queue lock. This makes it possible to store less information in synchronization object and be overall smarter with thread scheduling. Unfortunately, performance in contested case will most likely be slower, as it will use futex(2) underneath anyway to block the calling thread, so there is an additional layer of code and locking that needs to be executed.

WebKit implementation lacks FUTEX_REQUEUE equivalent, although it is possible to add this if needed.

  • This is a wonderful and in-depth answer. Thank you! For anyone who is wondering: Turns out that futex stands for fast userspace mutex. – Qqwy Dec 18 '17 at 4:45
  • Yes. Very nicely described. About 20 years ago I created a counting semaphore using mutex and condition variable. When I ported to Windows NT I had to find similar system calls and objects, as you explained here. – user251748 Mar 23 '18 at 0:07
  • I'm afraid the above mutex implementation is not sound. Lets see what will happen if we have 3 threads. Suppose the mutex is locked by the first (UNLOCKED->LOCKED), then comes the second, sets it to contested and sleeps (LOCKED->CONTESTED). Then comes the third and sleeps too (the mutex remains CONTESTED). Then the first leaves the mutex and wakes one sleeper (CONTESTED->UNLOCKED). The second thread then locks the mutex, does its work, unlocks and leaves. At this point the third thread remains sleeping forever while the mutex is in UNLOCKED state. – l_belev Oct 30 '18 at 14:37
  • @I_belev The second thread will lock mutex by changing its state to CONTESTED, so it will awake the next thread on unlocking. There will be a redundant wake-up after the last thread leaves the mutex, but it is not a problem. – StaceyGirl Oct 31 '18 at 14:23
2

Here is another futex-based mutex implementation, that avoids the spurious futex_wake:

typedef struct {
    // the number of threads that want to use the mutex at the moment.
    // if any, exactly one of them has the mutex and the rest are blocked
    volatile int num_users;
    // the last owner sets this to 1 when there are waiters when he leaves the mutex;
    // whichever of the waiters manages to change it from 1 to 0, is unblocked
    volatile int wake_signal;
} mutex_t;

void mutex_lock(mutex_t *m)
{
    int spin;

    // buys-wait for a while, hoping the mutex will be released soon.
    // (this should be disabled in single-processor situations)
    for (spin = 1000; spin && m->num_users; spin--) PAUSE();

    // increment the users count (to include us now)
    if (ATOMIC_ADD_AND_FETCH(&m->num_users, 1) == 1)
        // if we changed it from 0 to 1, the mutex is ours
        return;

    // block until signaled
    while (!ATOMIC_SWAP(&m->wake_signal, 0))
        futex(&m->wake_signal, FUTEX_WAIT, 0);
}

void mutex_unlock(mutex_t *m)
{
    // decrement the users count
    if (ATOMIC_ADD_AND_FETCH(&m->num_users, -1) == 0)
        // if we changed from 1 to 0, we were the only user of the mutex so don't signal
        return;

    // signal one waiter
    m->wake_signal = 1;
    futex(&m->wake_signal, FUTEX_WAKE, 1);
}

The above mutex can easily be changed to use many other system primitives. Here is an example with unix pipes:

typedef struct {
    volatile int num_users;
    int pipe[2]; // create with the unix pipe() function
} mutex_t;

void mutex_lock(mutex_t *m)
{
    int spin, buf;
    for (spin = 1000; spin && m->num_users; spin--) PAUSE();

    if (ATOMIC_ADD_AND_FETCH(&m->num_users, 1) == 1)
        return;

    read(m->pipe[0], &buf, 4);
}

void mutex_unlock(mutex_t *m)
{
    int buf;

    if (ATOMIC_ADD_AND_FETCH(&m->num_users, -1) == 0)
        return;

    write(m->pipe[1], &buf, 1);
}

And another example with win32 events:

typedef struct {
    volatile int num_users;
    HANDLE event; // a win32 auto-reset event
} mutex_t;

void mutex_lock(mutex_t *m)
{
    int spin;
    for (spin = 1000; spin && m->num_users; spin--) PAUSE();

    if (ATOMIC_ADD_AND_FETCH(&m->num_users, 1) == 1)
        return;

    WaitForSingleObject(m->event, INFINITE);
}

void mutex_unlock(mutex_t *m)
{
    if (ATOMIC_ADD_AND_FETCH(&m->num_users, -1) == 0)
        return;

    SetEvent(m->event);
}

protected by gnat Nov 1 '18 at 14:17

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.