Futex

컴퓨터 과학에서 futex(fast userspace mutex, 빠른 사용자 공간 상호 배제, 퓨텍스)는 개발자가 기본적인 잠금을 구현하기 위해 사용되거나 세마포어, POSIX 뮤텍스, 조건 변수와 같은 상위 계층의 잠금 추상화를 위한 빌딩 블록으로서 쓰일 수 있는 리눅스 커널에서 제공하는 시스템 호출이다.

동작

futex의 기본 동작들은 WAIT, WAKE라는 두 개의 특정 동작에만 기반한다. 특정 버전의 리눅스 커널에만 의존하는 일부 futex 구현체들은 특정 목적을 위해 동작들이 몇 개 더 많은 경우도 있다.[1]

WAIT (addr, val): addr 주소에 저장된 값이 val인지 확인하며, 만일 그러할 경우 현재의 스레드를 sleep 상태로 둔다.

WAKE (addr, val): addr 주소에서 대기 중인 스레드의 수만큼 val을 깨운다.

About

퓨텍스 없이는 의미 없다 | GeekNews
- [원문] Without the futex, it's futile | H4X0R****
- crashoverride/mutex: Using futexes to build successively better mutexes! - Codeberg.org - 전체 코드 예제

Futex는 현대 병렬 프로그래밍에서 효율적인 동기화의 핵심 구성요소로, 기존 System V 기반 락보다 뛰어난 성능을 보임

퓨텍스는 락 획득과 대기/깨우기 기능을 분리하여, 불필요한 시스템 콜과 오버헤드를 줄이는 구조를 가짐

서론

Phil Eaton이 'The Art of Multiprocessor Programming, 2nd Edition' 북클럽을 시작함
이 책은 병렬 프로그래밍 분야에서 권위 있는 교재로 여겨지지만, 저자는 내용의 실용성 결여를 지적함
특히, 4학년 학부생과 대학원생을 대상으로 한다면서도 퓨텍스(futex)라는 핵심 동기화 기법을 다루지 않는다는 점을 비판함

퓨텍스란 무엇인가 – 왜 중요한가

퓨텍스(futex)는 “fast user space mutex”의 줄임말로, 실제로는 뮤텍스라기보다는 현대 락 구현을 위한 OS 지원 동기화 원시 구성요소임
과거에는 대부분의 락이 System V IPC의 세마포어 기반으로 구현돼 효율성과 확장성에 한계가 있었음
Linux에 2002년 퓨텍스가 도입되면서, 1000개 동시 작업 환경에서 System V 락 대비 20~120배 빠른 성능을 보임
Windows(2012년)와 macOS(2016년) 등 타 OS도 유사한 메커니즘을 도입함
오늘날에 널리 쓰이는 pthreads 등 시스템 라이브러리의 락은 퓨텍스를 사용함

퓨텍스의 동작 원리 및 차별점

기존 세마포어는 락과 대기를 결합했지만, 퓨텍스는 락 획득과 대기/깨우기를 분리함
이로 인해 불필요한 딜레이와 시스템 콜을 줄일 수 있으며, 락 해제 시 대기 스레드 없음이 확실하다면 커널에 진입하지 않아도 됨
퓨텍스의 대기(wait) 호출은 “특정 메모리 주소의 값이 원하는 상태일 때만 대기”하게 하며, 타임아웃도 지원함
퓨텍스 깨우기(wake) 호출은 특정 메모리 주소와 연결된 내부 대기 리스트에서 원하는 개수의 스레드를 깨움
메모리 주소의 실제 값 검증을 요구해, 이미 상태가 변한 경우 불필요한 대기를 방지함

퓨텍스의 실질적 활용 – 직접 구현

퓨텍스는 저수준 원시 기능이므로, 컴파일러 및 하드웨어의 메모리 연산 순서 이슈를 고려해 atomic 자료형을 사용함
Linux에선 syscall로 퓨텍스 시스템콜을 직접 호출해야 하며, MacOS에선 __ulock 인터페이스를 사용함(최근엔 더 쉬운 API 추가됨)
기본적으로 퓨텍스 대기는 성공시 0, 실패시 에러코드(타임아웃 등) 를 반환함
퓨텍스 기반 핵심 연산:
- h4x0r_futex_wait_timespec() : 기대값이 일치할 경우 대기, 타임아웃 적용 가능
- h4x0r_futex_wake() : 1개 혹은 모든 대기자 깨우기

뮤텍스/스핀락/재귀락 구현의 실전 예

스핀락

가장 단순한 형태의 락, 오직 단일 비트(atomic_fetch_or) 로 동작
락을 가질 때까지 무한 루프(“스핀”)하지만, 높은 경합 상황에서는 CPU 낭비와 잘못된 해제, 재귀 호출 시 데드락 위험 등 구조적 문제가 있음

하이브리드 뮤텍스 (‘unsafe’ 뮤텍스)

보통은 스핀락으로 먼저 시도, 일정 횟수 실패시 퓨텍스로 전환하여 효율적 블로킹을 구현
대기자가 없으면 불필요한 시스템콜을 피할 수 있고, 대기자는 깨우기 시스템콜 최소화 가능
엄밀한 소유권 검증이나 재귀 처리는 미비해 “unsafe”라는 명칭을 사용

대기자 카운터 뮤텍스

한 비트는 락 상태, 나머지는 대기자 수 집계에 사용, 불필요한 깨우기 시스템콜 감소 목적
아직도 소유권 및 재귀 처리 없음

소유권 관리 포함 뮤텍스

pthread_t 값을 통해 락 소유자와 상태를 명확하게 추적하여 잘못된 unlock이나 재귀 사용시 문제 포착
락 획득, 해제, 대기자 관리 모두 엄격하게 atomic 연산으로 제어

재귀 락

스레드별 중첩 횟수(depth) 카운터를 추가하여 동일 스레드의 중첩 락 획득 가능
unlock 시 depth 감소, 0이 되면 실제 unlock 및 깨우기 진행
각 동작은 atomic 연산과 엄격한 소유권 검사로 구현

전체 코드 예제

#include <stdint.h>    // For uint32_t
#include <stdbool.h>   // For bool
#include <time.h>      // For struct timespec
#include <stdatomic.h> // For atomic_fetch_or, atomic_fetch_add, ...
#include <pthread.h>   // For pthread_self
#include <stdlib.h>    // For abort
#include <stdio.h>     // For printf
#include <errno.h>     // For ETIMEDOUT
#include <limits.h>

typedef _Atomic(uint32_t) h4x0r_futex_t;

#if defined(__linux__)
#if !defined(_GNU_SOURCE)
#define _GNU_SOURCE
#endif
#include <linux/futex.h>
#include <sys/syscall.h>
#include <unistd.h>

static inline int
h4x0r_futex_wait_timespec(h4x0r_futex_t  *futex,
                         uint32_t         expected,
                         struct timespec *timeout_ptr)
{
    int err = syscall(SYS_futex,
                      futex,
                      FUTEX_WAIT_PRIVATE,
                      expected,
                      timeout_ptr,
                      NULL,
                      0);
    if (err == -1) {
        return errno;
    }

    return 0;
}

static inline int
h4x0r_futex_wake(h4x0r_futex_t *futex, bool all)
{
    uint32_t n = all ? INT_MAX : 1;

    return syscall(SYS_futex,
                   futex,
                   FUTEX_WAKE_PRIVATE,
                   n,
                   NULL,
                   NULL,
                   0);
}
#elif defined(__APPLE__)

// These were never exposed in any headers.
extern int __ulock_wait2(uint32_t, void *, uint64_t, uint64_t, uint64_t);
extern int __ulock_wake(uint32_t, void *, uint64_t);

#define H4X0R_NSEC_PER_SEC 1000000000
#define H4X0R_LOCK_COMPARE_AND_WAIT          1
#define H4X0R_LOCK_WAKE_ALL                  0x00000100
#define H4X0R_LOCK_WAKE_THREAD               0x00000200

#define H4X0R_WAKE_ALL    (H4X0R_LOCK_COMPARE_AND_WAIT | H4X0R_LOCK_WAKE_ALL)
#define H4X0R_WAKE_THREAD (H4X0R_LOCK_COMPARE_AND_WAIT | H4X0R_LOCK_WAKE_THREAD)

static inline int
h4x0r_futex_wait_timespec(h4x0r_futex_t   *futex,
                         uint32_t         expected,
                         struct timespec *timeout)
{
    uint64_t timeout_ns = 0;

    if (timeout) {
        timeout_ns = timeout->tv_nsec + timeout->tv_sec * H4X0R_NSEC_PER_SEC;
    }
    return __ulock_wait2(H4X0R_LOCK_COMPARE_AND_WAIT,
                         futex,
                         (uint64_t)expected,
                         timeout_ns,
                         0);
}

static inline int
h4x0r_futex_wake(h4x0r_futex_t *futex, bool all)
{
    return __ulock_wake(all ? H4X0R_WAKE_ALL : H4X0R_WAKE_THREAD,
                        futex,
                        0ULL);
}
#endif


#define H4X0R_SPIN_COUNT 16

typedef h4x0r_futex_t h4x0r_mutex_unsafe_t;

static inline void
h4x0r_mutex_unsafe_init(h4x0r_mutex_unsafe_t *lock)
{
    atomic_store(lock, 0);
}

static inline void
h4x0r_mutex_unsafe_acquire(h4x0r_mutex_unsafe_t *lock)
{
    for (uint32_t i = 0; i < H4X0R_SPIN_COUNT; i++) {
        if (!atomic_fetch_or(lock, 1)) {
            return;
        }
    }
    while (true) {
        h4x0r_futex_wait_timespec((h4x0r_futex_t *)lock, 1, NULL);
        if (!atomic_fetch_or(lock, 1)) {
            return;
        }
    }
}

static inline void
h4x0r_mutex_unsafe_release(h4x0r_mutex_unsafe_t *lock)
{
   atomic_store(lock, 0);
   h4x0r_futex_wake(lock, false);
}

// First one is OR'd in, the second is AND'd in.
#define H4X0R_MUTEX_LOCK_ON (1 << 31)
#define H4X0R_MUTEX_LOCK_OFF ~(H4X0R_MUTEX_LOCK_ON)

static inline bool
h4x0r_mutex_value_is_unlocked(uint32_t value)
{
    return !(value & H4X0R_MUTEX_LOCK_ON);
}

static inline bool
h4x0r_mutex_unsafe2_try_lock(h4x0r_mutex_unsafe_t *lock)
{
    uint32_t value = atomic_fetch_or(lock, H4X0R_MUTEX_LOCK_ON);
    return h4x0r_mutex_value_is_unlocked(value);
}

static inline uint32_t
h4x0r_mutex_unsafe2_add_waiter(h4x0r_mutex_unsafe_t *lock)
{
    return 1 + atomic_fetch_add(lock, 1);
}

static inline void
h4x0r_mutex_unsafe2_acquire(h4x0r_mutex_unsafe_t *lock)
{
    uint32_t expected;

    for (uint32_t i = 0; i < H4X0R_SPIN_COUNT; i++) {
        if (h4x0r_mutex_unsafe2_try_lock(lock)) {
            return;
        }
    }

    expected = h4x0r_mutex_unsafe2_add_waiter(lock);

    while (true) {
        if (h4x0r_mutex_value_is_unlocked(expected)
        && h4x0r_mutex_unsafe2_try_lock(lock)) {
            atomic_fetch_add(lock, -1);
            return;
        }

        h4x0r_futex_wait_timespec((h4x0r_futex_t *)lock, expected, NULL);
        expected = atomic_load(lock);
    }
}

static inline void
h4x0r_mutex_unsafe2_release(h4x0r_mutex_unsafe_t *lock)
{
   uint32_t waiters = atomic_fetch_and(lock, H4X0R_MUTEX_LOCK_OFF);

   if (waiters != H4X0R_MUTEX_LOCK_ON) {
       h4x0r_futex_wake(lock, false);
   }
}


typedef struct {
    h4x0r_futex_t      futex;
    _Atomic(pthread_t) owner;
    _Atomic(bool)      owned;
} h4x0r_mutex_t;

static inline void
h4x0r_mutex_init(h4x0r_mutex_t *mutex)
{
    *mutex = (h4x0r_mutex_t) {
    .futex = 0,
    .owned = false,
    };
}

static inline bool
h4x0r_mutex_try_lock(h4x0r_mutex_t *lock)
{

    uint32_t value = atomic_fetch_or(&lock->futex, H4X0R_MUTEX_LOCK_ON);
    pthread_t self;

    if (!h4x0r_mutex_value_is_unlocked(value)) {
    return false;
    }
    // If what we read when we wrote says "unlocked", then we
    // successfully acquired the lock.
    self = pthread_self();

    if (atomic_load(&lock->owned)) {
    if (pthread_equal(self, atomic_load(&lock->owner))) {
        fprintf(stderr, "Mutex was used recursively.\n");
    }
    else {
        fprintf(stderr, "Acquired a lock owner didn't properly yield.\n");
    }
    abort();
    }

    // We have the lock, so we make it known.
    atomic_store(&lock->owned, true);
    atomic_store(&lock->owner, self);

    return true;
}

static inline uint32_t
h4x0r_mutex_add_waiter(h4x0r_mutex_t *lock)
{
    return 1 + atomic_fetch_add(&lock->futex, 1);
}

static inline bool
h4x0r_mutex_acquire(h4x0r_mutex_t *lock, struct timespec *timeout)
{
    uint32_t  expected;

    for (uint32_t i = 0; i < H4X0R_SPIN_COUNT; i++) {
        if (h4x0r_mutex_try_lock(lock)) {
            return true;
        }
    }

    expected = h4x0r_mutex_add_waiter(lock);

    while (true) {
        if (h4x0r_mutex_value_is_unlocked(expected)
        && h4x0r_mutex_try_lock(lock)) {
            atomic_fetch_add(&lock->futex, -1);
            return true;
        }

        int err = h4x0r_futex_wait_timespec((h4x0r_futex_t *)&lock->futex,
                        expected,
                        timeout);

    if (err == ETIMEDOUT) {
        return false;
    }
        expected = atomic_load(&lock->futex);
    }
}

static inline void
h4x0r_mutex_release(h4x0r_mutex_t *lock)
{
    if (!atomic_load(&lock->owned)
        || !pthread_equal(pthread_self(), atomic_load(&lock->owner))) {
    fprintf(stderr, "Thread unlocked a mutex it doesn't own.\n");
    abort();
    }

    atomic_store(&lock->owned, true);
    uint32_t waiters = atomic_fetch_and(&lock->futex, H4X0R_MUTEX_LOCK_OFF);

    if (waiters != H4X0R_MUTEX_LOCK_ON) {
    h4x0r_futex_wake(&lock->futex, false);
    }
}

typedef struct {
    h4x0r_futex_t      futex;
    _Atomic(uint32_t)  depth;
    _Atomic(pthread_t) owner;
    _Atomic(bool)      owned;
} h4x0r_mutex_recursive_t;


static inline void
h4x0r_mutex_recursive_init(h4x0r_mutex_recursive_t *mutex)
{
    *mutex = (h4x0r_mutex_recursive_t) {
    .futex = 0,
    .depth = 0,
    .owned = false,
    };
}

static inline bool
h4x0r_mutex_recursive_check_ownership(h4x0r_mutex_recursive_t *lock,
                      pthread_t                self)
{
    if (!atomic_load(&lock->owned)) {
    return false;
    }
    if (pthread_equal(self, atomic_load(&lock->owner))) {
    atomic_fetch_add(&lock->depth, 1);
    return true;
    }

    return false;
}

// Called from our internal try-lock call, once it knows we definitely
// just acquired ownership.
static inline void
h4x0r_mutex_recursive_new_ownership(h4x0r_mutex_recursive_t *lock,
                    pthread_t                self)
{
    if (atomic_load(&lock->owned)) {
    fprintf(stderr, "Acquired a lock owner didn't properly yield.\n");
    abort();
    }
    atomic_store(&lock->owned, true);
    atomic_store(&lock->owner, self);
    atomic_store(&lock->depth, 1);
}

// Called when definitely holding the lock.
// Returns true if we are nested, and false if we aren't (proper unlock).
static inline bool
h4x0r_mutex_recursive_nesting_check(h4x0r_mutex_recursive_t *lock)
{

    if (!pthread_equal(pthread_self(), atomic_load(&lock->owner))) {
    fprintf(stderr, "Thread is trying to unlock a lock it doesn't own.\n");
    abort();
    }

    if (atomic_fetch_add(&lock->depth, -1) > 1) {
    return true;
    }
    atomic_store(&lock->owned, false);
    return false;
}

static inline bool
h4x0r_mutex_recursive_internal_try_lock(h4x0r_mutex_recursive_t *lock, pthread_t self)
{
    uint32_t value = atomic_fetch_or(&lock->futex, H4X0R_MUTEX_LOCK_ON);
    bool result    =  h4x0r_mutex_value_is_unlocked(value);

    if (result) {
    h4x0r_mutex_recursive_new_ownership(lock, self);
    }

    return result;
}

static inline uint32_t
h4x0r_mutex_recursive_add_waiter(h4x0r_mutex_recursive_t *lock)
{
    return 1 + atomic_fetch_add(&lock->futex, 1);
}

static inline bool
h4x0r_mutex_recursive_acquire(h4x0r_mutex_recursive_t *lock,
                  struct timespec         *timeout)
{
    uint32_t  expected;
    pthread_t self = pthread_self();

    if (h4x0r_mutex_recursive_check_ownership(lock, self)) {
    // We already owned the lock, and incremented the nesting count.
    return true;
    }

    for (uint32_t i = 0; i < H4X0R_SPIN_COUNT; i++) {
        if (h4x0r_mutex_recursive_internal_try_lock(lock, self)) {
        // internal_try_lock will set up ownership.
            return true;
        }
    }

    expected = h4x0r_mutex_recursive_add_waiter(lock);

    while (true) {
        if (h4x0r_mutex_value_is_unlocked(expected)
        && h4x0r_mutex_recursive_internal_try_lock(lock, self)) {
            atomic_fetch_add(&lock->futex, -1);
            return true;
        }

        int err = h4x0r_futex_wait_timespec((h4x0r_futex_t *)&lock->futex,
                        expected,
                        timeout);
    if (err == ETIMEDOUT) {
        return false;
    }
        expected = atomic_load(&lock->futex);
    }
}

static inline bool
h4x0r_mutex_recursive_try_lock(h4x0r_mutex_recursive_t *lock)
{
    pthread_t self = pthread_self();

    if (h4x0r_mutex_recursive_check_ownership(lock, self)) {
    // We already owned the lock, and incremented the nesting count.
    return true;
    }
    return h4x0r_mutex_recursive_internal_try_lock(lock, self);
}

static inline void
h4x0r_mutex_recursive_release(h4x0r_mutex_recursive_t *lock)
{
    if (h4x0r_mutex_recursive_nesting_check(lock)) {
    // We were nested, and the decrement happened, so we're done.
    return;
    }

    uint32_t waiters = atomic_fetch_and(&lock->futex, H4X0R_MUTEX_LOCK_OFF);

    if (waiters != H4X0R_MUTEX_LOCK_ON) {
    h4x0r_futex_wake(&lock->futex, false);
    }
}

남은 과제 및 실제 엔지니어링 현실

락 소유 스레드가 비정상 종료/죽는 경우, 락 관리를 위한 별도 관리 리스트, 종료 콜백 등 추가 관리 필요
프로세스 간 공유 뮤텍스를 쓸 때도 상태 변화 관리에 추가적 고려 필요
POSIX RW락은 재귀 중첩 동작이 정의되어 있지 않고 구현마다 상이해, 실제로는 안전성 확보가 어려움
저자는 책이 실전에서 정말 중요한 동시성 이슈(퓨텍스, 재귀 락, 비동기 런타임 등) 를 교과과정에 포함하지 않는 점을 비판함

결론

'The Art of Multiprocessor Programming'은 역사 또는 이론적 관점에 치우쳐 중요한 현대적 병렬 프로그래밍 실무 지식을 제대로 담지 못함
실질적으로 시스템에서 동작하는 퓨텍스 등 핵심 동기화 구성요소를 제대로 다루지 않으면 후학들에게 실질적 해악 초래 가능성
저자는 최신 개념 반영 및 실용적 내용 보완의 필요성을 강조함

Favorite site

Futex - Wikipedia