mutex

How does a muxex work?

Summary

A mutex works by wrapping around an atomic int. This atomic int provides memory barrier for reads/writes between multiple threads.

Description

Given a mutex

  • The first thread grabs the mutex. No kernel syscall is required since the thread doesn’t need to sleep. Simply increment the atomic int from 0 to 1.
  • When the second thread tries to grab the mutex, it sees that the atomic_int isn’t 0. It calls futex.wait(&atomic_int, 1) (If the value stored at the address addr is 1, puts the current thread to sleep.)
  • When the first thread is done with the mutex, it decrements the atomic_int from 1 to 0. The kernel notices that the atomic_int changed from 1 and wakes up the second thread, who can now obtain the ’lock'.
  • This design results in the thundering herd problem, that when the first thread is done with the mutex, multiple threads will be woken up, yet only one thread can make progress. This is where WAKE_OP comes in handy:
WAKE_OP(addr1, addr2, num1, num2, op, op_arg, cmp, cmp_arg);
Will read addr2, perform op with op_arg on it, and store the result back to addr2. Then it will wake num1 threads waiting on addr1, and, if the previously read value from addr2 matches cmp_arg using comparison cmp, will wake num2 threads waiting on addr2. This very flexible and generic wake mechanism is useful for implementing many synchronization primitives.

From GPT

typedef struct {
    atomic_int value;  // 0 = unlocked, 1 = locked
} mutex_t;

// Wrapper for syscall
int futex(int *addr, int op, int val, const struct timespec *timeout, int *addr2, int val3) {
    return syscall(SYS_futex, addr, op, val, timeout, addr2, val3);
}

void mutex_init(mutex_t *m) {
    atomic_init(&m->value, 0);
}

// Lock function (same as before)
void mutex_lock(mutex_t *m) {
    int expected = 0;

    if (atomic_compare_exchange_strong(&m->value, &expected, 1)) {
        return;
    }

    while (1) {
        expected = 0;

        if (atomic_load(&m->value) != 0 ||
            !atomic_compare_exchange_strong(&m->value, &expected, 1)) {
            futex(&m->value, FUTEX_WAIT, 1, NULL, NULL, 0);
        } else {
            return;
        }
    }
}

// Unlock using FUTEX_WAKE_OP
void mutex_unlock(mutex_t *m) {
    futex(&m->value,
          FUTEX_WAKE_OP,
          1,                      // Wake 1 thread
          NULL,
          &m->value,              // addr2
          FUTEX_OP_CLEAR |        // Atomic: *addr2 = 0
          (FUTEX_OP_CMP_EQ << 28) | 1); // If *addr2 == 1 before clear
}

Consequences

Because CAS can be done in userspace, obtaining a mutex without contention is pretty fast (~20ns) whereas if there is contention, a slow syscall will need to be used to efficiently sleep and wake the thread.

Other reads