퓨텍스 없이는 의미 없다

 (h4x0r.org)
4P by GN⁺ | ★ favorite | 댓글 1개
  • The Art of Multiprocessor Programming 교재가 퓨텍스(futex) 개념을 다루지 않아 아쉽다는 문제 제기
  • 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 연산과 엄격한 소유권 검사로 구현

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

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

결론

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

참고자료

  • 전체 코드 예제는 codeberg에서 확인 가능

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견

  • Windows에는 WaitForMultipleObjects라는 기능이 있는데, Linux도 5.16(2021년 말)에 Futex2로 이를 도입함음
    관련 링크
    최근 Futex2에 다양한 개선이 이루어져 왔음
    NUMA 지원도 드디어 추가됨음
    NUMA 관련 링크1
    NUMA 관련 링크2
    NUMA는 성능에 매우 중요한 요소임
    io_uring이 6.7(2024년)에서 futex에 적용되면서 postgresql aio 성능 향상에 도움을 주었음음
    관련 글
    6.7에서는 Small requeue와 single wait 기능도 추가됨음
    관련 링크

    • Windows는 WaitForMultipleObjects 기능을 새롭게 추가한 것이 아니라, 30년 넘게 처음부터 가지고 있었음음
      WaitForMultipleObjects는 UNIX에 비해 Windows NT의 장점이긴 했지만, IBM PL/I도 1965년에 이미 유사 기능이 있었음
      UNIX에서의 'wait' 함수는 IBM PL/I의 'wait'에서 단순화된 버전으로, Multics에서 물려받은 여러 기능들과 마찬가지로 원래 모델보다 약한 수준이었음
      MS의 WaitForSingleObject와 WaitForMultipleObjects도 효율적인 구현이 아니었기 때문에, 결국 Linux의 futex와 동등한 WaitOnAddress를 도입해야 했음
      Linux futex는 32비트 크기 제약과 단일 이벤트 만을 기다릴 수 있다는 한계가 있음
      원자적 비트 연산을 활용하면 여러 이벤트에 대한 대기를 구현할 수 있지만, 효율적이지 않아서 32비트 크기 문제가 커짐음
      'futex'에 WaitForMultipleObjects의 장점을 일부 결합하려는 시도는 반가운 일임
      이런 시도는 Windows를 따라하는 게 아니라, 사실 Microsoft보다 훨씬 오래된, 50년 넘게 잘 알려진 고전적인 기법을 재구현하는 것임

    • 아직도 futex_swap 기능이 없다는 점이 아쉬움
      관련 토론1
      관련 자료2

    • Futex는 WFMO(WaitForMultipleObjects)와 관계가 없고, 오히려 keyed events와 동등한 개념임
      Linux에서 WFMO에 해당하는 기능은 select/poll/epoll임

    • io_uring에서 futex 지원이 정말 좋은 기능임
      Ruby fibers와 작업할 때 mutex 및 queue 구현에 활용했음
      소스코드 참고

  • 책에서는 직접 동기화 구조물을 구현하기보다는 라이브러리/언어/시스템에서 제공하는 구조물을 사용하라고 밝히고 있음
    책의 주요 초점은 특정 플랫폼이 아니라 전반적인 concurrency 개념에 있음
    기사 작성자가 다소 과장된 대립 구도로 글을 쓴 점이 아쉬움
    이 글은 "TAoMP가 말하지 않는 것" 같은 협업적 시각에서 다뤘으면 더 좋았을 것임
    이 블로그가 새로 생겼고, Phil이 이 글을 올리고, Phil이 다른 글도 프로모션했다는 점은 눈에 띔

    • 내가 그 기사를 썼고, 책을 읽으며 실망해서 쓴 것임
      아카데미와 산업계 모두에서 실질적으로 쓸 만한 내용을 배우지 못하는 현실이 문제라고 느꼈음
      그러니까 "futex 알아보자!"식의 의도는 아니었음
      실제로 책에 실망해서 다른 글을 미루고 이 글을 먼저 쓴 것임
      Phil과는 예전에 같이 일해서 교류가 있지만, 지금까지 글을 쓰는 데 별 어려움 없이 독자를 찾았음

    • 예전에 sysv 스타일을 공룡에 비유하지도 않는다고 표현한 부분은 너무 심했다는 생각임
      겸손이 더 필요한 부분임

  • futex의 가장 멋진 점은 핸들리스(handle-less) 구조라는 것임
    syscall을 통한 할당/해제가 필요 없는 커널 기반 메모리 감시자로 매우 유용한 기본 동작을 제공함
    대기 중인 스레드가 없으면 모든 게 깔끔하게 정리되고, 경쟁이 없으면 커널은 mutex 자체를 인식하지 못함
    커널이 futex를 고성능으로 관리하는지에 대한 자세한 분석이 궁금함
    futex2에 대해 오늘 처음 알게 되었음
    관련 문서

    • 맞음, 또한 스레드가 락에서 블로킹될 때마다 커널의 malloc()을 호출하여 데이터를 할당하는 방식은 원하지 않음
      이를 방지하려고 많은 OS에서는 'queue object'를 스레드 생성 시마다 할당해 놓고, 해당 스레드가 경쟁 락을 만나면 이 오브젝트를 락에 할당하는 식임
      즉, 여러 스레드가 락에 연결된 linked list 형태로 queue object를 두고, 스레드가 깨어날 때마다 하나씩 가지고 나감
      스레드 종료 시 자신이 최초에 만들었던 오브젝트를 돌려받는 보장은 없고, 중간에 오브젝트가 섞임
      solaris에서 처음 이런 구조(turnstile)를 도입했고, BSD들도 이 방법을 채택함
      solaris internals 참고
      BSD pdf 자료

    • 초기 Unix 커널 내 대기 큐도 이런 방식이었음

  • 2002년 오리지널 futex 논문에서도 futex의 효율성이 명확하게 입증되었고, 1000개의 병렬 태스크 테스트에서 sysv 락 대비 20~120배 빠른 성능을 보였음
    하지만 실제로 기준점(baseline)이 sysv 락은 아님
    실질적으로 futex 없는 환경에서 락 구현 시 대부분 빠른 경로에서는 커널 진입이 없고, 느린 경로에서만 커널로 대기 전환하는데, futex의 개선점은 락 대기 상태를 나타내는 사용자 영역 자료구조의 크기가 작아졌다는 것이 유일함
    다른 대안으로는 thin locks(JVM에서 쓰는 방식), ParkingLot(완전 유저랜드 구현)은 OS의 futex 없이도 동작함

    • 내 경험상, 대부분이 실제로는 실무에서 제공되는 기본 primitive를 배우기 때문에, 내 언어의 표준 라이브러리가 무엇을 제공하냐에 집중하게 됨
      즉 sysv에서 futex로 옮겨온 흐름이 지배적이며, 최근에는 커스텀 방식도 있지만 대세는 futex임
      만약 유저랜드 직접 스케줄러를 만든다면 별도 구현도 가능하겠지만, 대부분은 파일 디스크립터에 기록하고 직접 큐를 관리하는 방식을 사용할 것 같음
      이런 처리 방식이 얼마나 이득이 있을지 의문이 들음

    • 실제로는 어느 현대 락이라도 결국 내부적으로 futex(지원된다면)를 쓰는 셈임
      Linux에서 futex가 가장 효율적인 대기 방식이기 때문에, 느린(down) 경로에서는 항상 futex 사용이 바람직함
      언어에서 thread.park() 같은 것도 결국 futex 위에서 동작할 확률이 높음

    • JVM에서 여전히 thin lock을 사용하는지 궁금함
      과거에 JVM이 futex를 호출한다는 레퍼런스를 찾았는데, 혹시 thin lock으로 마이그레이션 된 것인지 알고 싶은 마음임
      Stack Overflow 관련 토론

  • [recursive locks]의 실제 구현은 표준 간에도 일관성이 없고, 이게 어렵다는 이유로 아예 정의 자체를 하지 않은 경우가 많음
    이런 태도는 꽤 답답함
    "OS나 언어 구현자가 feature X를 제대로 구현 못 할 테니, 그냥 애플리케이션 개발자가 직접 처리하게 하자"는 식임
    결국 downstream 사용자는 벤더 변경 외에는 뾰족한 수가 없는 셈임

    • 표준에 과도한 제약을 주면 더 나은 구현 가능성을 닫아버릴 수 있음
      예로 들어, C++ 표준 해시테이블과 정규표현식은 제약이 많아 타사보다 훨씬 느림
      특정한 제약(예: 체이닝 방식만 사용하도록)이나 기능 보장을 하면 대안적 고성능 구현이 막힘
      recursive rwlock도 성능을 희생하거나 체크를 덜하는 구현이 가능하기 때문에, 다양한 방향성을 막을 필요는 없다고 생각함

    • 개인적으로 recursive lock은 애초에 쓰지 않는 게 좋기 때문에, 굳이 지원 스펙을 표준에 넣을 필요를 못 느끼겠음

    • worse is better 현상을 더 알고 싶다면 위키 참고
      별로 좋아하지 않지만, 어쩔 수 없는 현실임

  • linux에서 futex가 32bit int만 지원하는 한계가 궁금해져서 알아봤음
    64비트 지원 논의에서 Linus는 사용자 영역에서 64비트 atomic을 쓰고, 하위 32비트만 futex로 사용하면 된다고 언급함
    하지만 C/C++에서는 mixed-size atomic이 undefined behavior로 여겨지고, 실제로 glibc 세마포 구현도 그렇게 동작함
    64비트 정수에서 high 32는 waiter count, low 32는 세마포 값으로 사용하며, 하위 32비트에만 futex를 씀
    gcc에서 이게 정의된 동작인지, 아니면 프로세스 경계(커널 프로세스) 덕분에 상관없는 건지, 아니면 glibc조차 undefined behavior를 사용하는 건지 궁금함

  • Anthony Williams의 _C++ Concurrency in Action_도 추천하는데, futex나 동기화 primitive 직접 구현 방법은 다루지 않지만, 메모리 순서와 lock-free 구조에 필요한 SMR 등 실제에 가까운 내용을 다룸
    더 하드웨어 중심 시각이 필요하다면 Paul McKenney의 무료 저서 "Is Parallel Programming Hard, And, If So, What Can You Do About It?"도 추천
    이 책도 futex를 깊게 다루지는 않지만, Ulrich Drepper의 "Futexes Are Tricky"로 안내함
    TAOMPP는 고수준 concurrency 개념을 잘 다루는 용도로 적당하며, OS 수준 구현 디테일까지 담는 건 맞지 않음
    어쨌든 Peterson 혹은 bakery lock은 실사용엔 쓸모없지만, 증명만 익혀도 실전 동시성 알골리즘 이해에 큰 도움이 됨

    • bakery lock은 spin lock용으로는 좋은데, 캐시 친화적임
      reader/writer spin lock도 구현 가능하지만, 엄격한 FIFO됨
      user space에서 bakery lock spin wait에 futex를 연동할 수는 있지만, 매우 비효율적임
      futex는 이런 용도(스핀 대기)는 애초에 설계되지 않음
      lock-free 구조와 hazard pointer, RCU* 등도 여전히 tricky함
      wait-free hazard pointer도 실제로 만들 수 있음
      *RCU의 경우 copy-on-write는 직관적이지만, 업데이트가 잦으면 비용이 늘어남

  • Windows 8에서 futex 유사지가 도입된 것처럼, 원래 Win32 critical section은 커널 세마포 기반임
    그런데 Vista에서 도입된 SRW lock은 어떤 구조인지 궁금함

    • CRITICAL_SECTION과 SRWLock 모두 경쟁이 없으면 커널 진입이 없음
      SRWLock은 keyed event 기반이고, CRITICAL_SECTION은 실패 시에도 on-demand 커널 오브젝트를 만들어 호출하며, keyed event로 fallback 함

  • 2014년 linux futex 구현에서 Pinkie Pie가 발견한 취약점 중, requeue-once 룰은 futex_wait_requeue_pi에 전달된 futex에만 허용됨
    A에서 B로, 그 후 다시 B에서 C로 requeue는 불가능하지만, B에서 B로 재지정은 가능함
    이때 특정 조건을 통과하면 cleanup 함수가 호출되지 않는 버그가 있고, 포인터가 dangling 상태가 됨
    관련 사례 확인 가능
    관련 이슈

  • crashed thread에 의한 데이터 정합성을 걱정하지 않는 사람도 있지만, 프로세스 전체가 죽지 않는 이상 락 클린업 문제가 남음
    이를 위한 솔루션이 robust lock임
    held futex 리스트를 커널에 등록하고, sys_set_robust_list로 스레드 종료 시 해당 bit를 처리해 기다리는(waiter) 쪽을 깨워줌

    • robust lock 방식의 최대 단점은, 락이 보호하던 리소스 자체가 이미 inconsistent 상태일 가능성이 큼
      스레드가 왜 크래시 됐는지 확실히 알지 못하면, 데이터가 무결하지 않아서 복구가 불가함
      그래서 전체 앱을 함께 죽이는 게 더 실질적일 수도 있음
      robust lock을 사용한 cleanup/recovery 기능 자체는 멋지지만, 아마도 95%의 엔지니어는 robust data 구조까지 제대로 설계하지 않을 것 같음
      4%는 그럴 시간이 부족하고, 나머지 1%만 크게 보상받으면서 제대로 하는 경우일 것임

    • 여러 프로세스 간에 futex(크로스 프로세스 상태)를 사용할 때는, watchdog 프로세스가 각 프로세스별로 Unix domain socket(SOCK_STREAM 또는 SOCK_SEQPACKET)을 열어 crash를 감지하고 per-process 상태를 정리하는 식의 방식을 쓸 수 있음

    • 본인도 mutex 논의를 프로세스 경계까지만 한 이유가 깊은 논의로 끝이 없어질까 우려해서임

답변달기