futex — jak naprawdę działają muteksy w Linuksie

Dlaczego pthread_mutex_lock zwykle nie robi syscalla

Powszechna intuicja: założenie muteksa to wejście do kernela. pthread_mutex_lock() wygląda jak operacja systemowa, więc „pewnie robi syscall”. Tymczasem w niespornym przypadku — gdy lock jest wolny i nikt o niego nie konkuruje — pthread_mutex_lock() nie dotyka kernela ani razu. Cała operacja to atomowa instrukcja CPU w userspace, kosztująca kilkanaście nanosekund.

Sekretem jest futex (fast userspace mutex) — prymityw synchronizacji, na którym glibc buduje muteksy, zmienne warunkowe, semafory i bariery. Idea jest genialnie prosta: nie wołaj kernela, dopóki nie musisz. Dopóki nie ma kontencji, synchronizacja żyje w całości w userspace. Dopiero gdy wątek musi zasnąć czekając na lock, następuje syscall futex().

Ten artykuł rozkłada futex na fast path i slow path: atomowy CAS w userspace, mechanikę FUTEX_WAIT/FUTEX_WAKE, problem thundering herd, futeksy międzyprocesowe oraz — kluczowe dla decyzji produkcyjnych — kiedy narzut syscalla synchronizacji faktycznie się liczy.

Problem: dlaczego nie wystarczy zwykła zmienna

Najprostszy „lock” to flaga w pamięci: 0 = wolny, 1 = zajęty. Problem w tym, że sprawdzenie i ustawienie flagi to dwie osobne operacje, a między nimi inny wątek może wcisnąć się i też ustawić flagę — klasyczny race condition. Potrzebna jest operacja atomowa: sprawdź-i-ustaw w jednej, niepodzielnej instrukcji.

Procesory dostarczają to przez instrukcje typu compare-and-swap (CAS). Na x86-64 to lock cmpxchg — porównuje wartość w pamięci z oczekiwaną i, jeśli pasuje, atomowo podmienia ją na nową. Prefiks lock gwarantuje, że żaden inny rdzeń nie wejdzie w trakcie operacji.

#include <stdatomic.h>

/* Najprostszy spinlock — CAS w pętli, bez kernela */
typedef struct {
    atomic_int locked;   /* 0 = wolny, 1 = zajęty */
} spinlock_t;

void spin_lock(spinlock_t *lock) {
    int expected = 0;
    /* Próbuj atomowo zmienić 0 → 1. Jeśli się nie uda, kręć w pętli. */
    while (!atomic_compare_exchange_weak(&lock->locked, &expected, 1)) {
        expected = 0;        /* CAS nadpisuje expected — resetuj */
        __builtin_ia32_pause();  /* instrukcja PAUSE — hint dla CPU */
    }
}

void spin_unlock(spinlock_t *lock) {
    atomic_store(&lock->locked, 0);
}

Spinlock działa, ale ma fatalną wadę: wątek czekający na lock spala CPU w pętli. Dla locka trzymanego mikrosekundy to akceptowalne. Dla locka trzymanego milisekundy — katastrofa: rdzeń kręci się jałowo zamiast oddać czas innym wątkom. Tu wchodzi futex.

Fast path: futex nie dotyka kernela

Kluczowa obserwacja stojąca za futeksem: w niespornym przypadku spinlock jest idealny — jeden CAS i gotowe, zero syscalli. Problem pojawia się dopiero przy kontencji, gdy wątek musi czekać. Futex łączy oba światy: fast path w userspace dla przypadku bez kontencji, slow path z syscallem tylko gdy trzeba zasnąć.

#include <linux/futex.h>
#include <sys/syscall.h>
#include <unistd.h>
#include <stdatomic.h>

/* Wrapper na surowy syscall futex — glibc nie eksponuje go wprost */
static int futex(atomic_int *uaddr, int op, int val) {
    return syscall(SYS_futex, uaddr, op, val, NULL, NULL, 0);
}

/* Stany muteksa: 0 = wolny, 1 = zajęty, 2 = zajęty + są oczekujący */
#define UNLOCKED 0
#define LOCKED   1
#define CONTESTED 2

void futex_lock(atomic_int *m) {
    int c;
    /* FAST PATH: spróbuj atomowo 0 → 1. Brak kontencji = zero syscalli. */
    if ((c = 0, atomic_compare_exchange_strong(m, &c, LOCKED)))
        return;   /* lock zdobyty bez dotykania kernela */

    /* SLOW PATH: lock zajęty — oznacz jako CONTESTED i zaśnij */
    do {
        /* Jeśli już CONTESTED lub uda się oznaczyć — czekaj w kernelu */
        if (c == CONTESTED ||
            atomic_compare_exchange_strong(m, &c, CONTESTED) != UNLOCKED) {
            /* FUTEX_WAIT: zaśnij DOPÓKI *m == CONTESTED */
            futex(m, FUTEX_WAIT, CONTESTED);
        }
        c = 0;
    } while (!atomic_compare_exchange_strong(m, &c, CONTESTED));
}

void futex_unlock(atomic_int *m) {
    /* Jeśli byli oczekujący (wartość 2), trzeba ich obudzić */
    if (atomic_fetch_sub(m, 1) != LOCKED) {
        atomic_store(m, UNLOCKED);
        /* FUTEX_WAKE: obudź JEDEN oczekujący wątek */
        futex(m, FUTEX_WAKE, 1);
    }
}

Sednem jest trójstanowość: wartość 2 (CONTESTED) koduje informację „są wątki śpiące w kernelu na tym locku”. To pozwala unlock uniknąć syscalla FUTEX_WAKE, gdy nikt nie czeka — jeśli wartość była 1, nie ma kogo budzić, więc syscall się pomija. Syscall pojawia się tylko wtedy, gdy faktycznie trzeba kogoś uśpić albo obudzić.

Mechanika FUTEX_WAIT i FUTEX_WAKE

Dwie operacje stanowią rdzeń interfejsu, a ich semantyka jest precyzyjnie zaprojektowana wokół jednego problemu: wyścigu między sprawdzeniem warunku a zaśnięciem.

Genialność FUTEX_WAIT polega na warunku *addr == val sprawdzanym atomowo w kernelu. Rozważ wyścig: wątek A widzi lock zajęty, postanawia zasnąć. Między tą decyzją a faktycznym zaśnięciem wątek B zwalnia lock i woła FUTEX_WAKE — ale A jeszcze nie śpi, więc budzenie trafia w próżnię. A zasypia na zawsze (lost wakeup).

Futex rozwiązuje to tak: FUTEX_WAIT przekazuje do kernela oczekiwaną wartość. Kernel atomowo sprawdza, czy *addr nadal ją ma — jeśli B zdążył ją zmienić, FUTEX_WAIT natychmiast wraca z EAGAIN zamiast zasnąć. Wątek nie zaśnie na nieaktualnym warunku. To jest właśnie sedno, którego naiwna implementacja „sprawdź flagę, potem śpij” nie ma.

Spinning vs sleeping — muteksy adaptacyjne

Czysty futex zasypia natychmiast przy kontencji. Ale uśpienie i obudzenie wątku to też koszt: context switch (~1–5 µs), wyrzucenie cache, scheduling. Jeśli lock jest trzymany krócej niż koszt uśpienia, taniej jest pokręcić się chwilę w pętli niż zasypiać. Stąd adaptacyjne muteksy (PTHREAD_MUTEX_ADAPTIVE_NP): najpierw spinują przez ograniczoną liczbę iteracji, a dopiero gdy to nie pomoże — wołają FUTEX_WAIT.

Decyzja spin-vs-sleep to ten sam typ inżynierskiego trade-offu co wybór modelu I/O — gdzie narzut syscalla determinuje, czy warto sięgać po bardziej złożony mechanizm. Tę samą logikę „mierz, gdzie syscall faktycznie boli” rozkłada artykuł o epoll vs io_uring.

Thundering herd — kogo obudzić

Załóżmy, że 100 wątków śpi na jednym locku, a ten właśnie się zwalnia. Naiwne FUTEX_WAKE(addr, INT_MAX) obudzi wszystkie 100 — które rzucą się na lock, ale zdobędzie go jeden, a pozostałe 99 natychmiast wróci do snu. To thundering herd: 99 zbędnych context switchy, 99 nieudanych prób CAS, kompletne marnotrawstwo.

Rozwiązanie to budzenie jednego wątku naraz (FUTEX_WAKE(addr, 1)) — dokładnie tak działa kod muteksa wyżej. Dla zmiennych warunkowych, gdzie czasem trzeba obudzić wszystkich (pthread_cond_broadcast), glibc używa optymalizacji FUTEX_REQUEUE: zamiast budzić 100 wątków na zmiennej warunkowej, przenosi 99 z nich bezpośrednio do kolejki oczekujących na mutex, budząc tylko jeden. Pozostałe są przekierowane bez wybudzania — eliminacja thundering herd u źródła.

Futeksy międzyprocesowe

Futex domyślnie działa w obrębie jednego procesu, ale jego prawdziwa moc ujawnia się między procesami. Ponieważ futex identyfikowany jest przez adres fizyczny strony pamięci (nie wirtualny), dwa procesy mapujące tę samą pamięć współdzieloną mogą synchronizować się na tym samym futeksie.

#include <sys/mman.h>

/* Mutex w pamięci współdzielonej — synchronizacja MIĘDZY procesami */
atomic_int *shared_mutex = mmap(
    NULL, sizeof(atomic_int),
    PROT_READ | PROT_WRITE,
    MAP_SHARED | MAP_ANONYMOUS,   /* współdzielone z procesami potomnymi */
    -1, 0
);

/* Po fork() oba procesy widzą TEN SAM futex — kernel mapuje
   adres wirtualny na ten sam adres fizyczny strony.
   futex_lock(shared_mutex) działa identycznie ponad granicą procesów. */

Dla futeksów w obrębie procesu glibc dodaje flagę FUTEX_PRIVATE_FLAG, która pozwala kernelowi pominąć kosztowne tłumaczenie na adres fizyczny i użyć szybszego, lokalnego hashowania — stąd futeksy prywatne są szybsze od współdzielonych. Mechanika pamięci współdzielonej stojąca za futeksem międzyprocesowym to ten sam MAP_SHARED, który rozkłada artykuł o mmap i memory-mapped I/O, a relacja proces-wątek — artykuł o wywołaniu fork().

Priority inheritance — futeksy PI

Klasyczny problem czasu rzeczywistego: inwersja priorytetów. Wątek niskopriorytetowy trzyma lock, którego potrzebuje wątek wysokopriorytetowy. Ten wysoki czeka — ale wątek średniopriorytetowy wywłaszcza niski, więc lock nie zostaje zwolniony, a wysoki priorytet czeka w nieskończoność, zablokowany pośrednio przez średni.

Kernel rozwiązuje to przez PI futexes (FUTEX_LOCK_PI): gdy wysokopriorytetowy wątek blokuje się na locku trzymanym przez niski, kernel tymczasowo podnosi priorytet posiadacza locka do poziomu czekającego. Niski wątek kończy sekcję krytyczną szybciej, zwalnia lock i wraca do swojego priorytetu. To kluczowy mechanizm dla systemów real-time i sterowników, gdzie deterministyczne czasy reakcji są wymogiem, nie luksusem.

Diagnostyka — narzędzia

Praktyczny sygnał: jeśli strace -c -f pokazuje setki tysięcy wywołań futex na sekundę, masz realną kontencję locków — wątki spędzają czas śpiąc i budząc się zamiast pracować. To moment na profilowanie przez perf lock i rewizję granularności lockowania. Sama obserwacja syscalli to ta sama technika, którą rozkłada artykuł o strace i czytaniu syscalli.

Kiedy to się liczy — decision matrix

Podsumowanie: futex jako warstwa, którą warto rozumieć

Futex to nie egzotyczny prymityw dla autorów bibliotek — to fundament, na którym stoi każdy pthread_mutex_lock, każda zmienna warunkowa i każdy semafor, którego używasz. Zrozumienie podziału na fast path (atomowy CAS w userspace, zero syscalli) i slow path (FUTEX_WAIT/FUTEX_WAKE tylko przy kontencji) zamienia „muteksy są wolne, bo robią syscall” w precyzyjny model: są wolne tylko wtedy, gdy faktycznie jest o co konkurować.

Kluczowe zrozumienia: niesporny lock to jeden CAS bez kernela; wartość CONTESTED koduje obecność oczekujących, pozwalając pominąć zbędne FUTEX_WAKE; atomowe sprawdzenie *addr == val eliminuje lost wakeup; FUTEX_REQUEUE zabija thundering herd; a PI futexy chronią systemy real-time przed inwersją priorytetów. Ta wiedza zamienia synchronizację z czarnej skrzynki w mierzalny, debugowalny i optymalizowalny aspekt systemu.

Gdy następnym razem ktoś powie „muteksy są drogie, bo wchodzą do kernela” — już wiesz, że w typowym przypadku nie wchodzą wcale. Koszt pojawia się dopiero przy realnej kontencji, a ta jest mierzalna jednym strace -c.

Powiązane artykuły

• epoll vs io_uring — kiedy event loop przestaje wystarczać — ten sam trade-off narzutu syscalla, w kontekście I/O
• mmap — kiedy memory-mapped I/O bije read() i write() — MAP_SHARED jako fundament futeksów międzyprocesowych
• fork() Linux — co naprawdę robi pod spodem — procesy, wątki i współdzielenie pamięci
• strace — czytanie syscalli, kiedy stack trace nie wystarcza — obserwacja wywołań futex w praktyce