[Concurrency] Mutex와 futex

#동시성

futex는 Mutex의 대표적인 구현 패턴이다.
기존의 느리고 비효율적인 Mutex 구현을 대체하기 위해 나왔다.

현재 사용되는 대부분의 Mutex 구현체는 전부 futex 기반으로 만들어져있다.

이건 Rust의 표준 Mutex

기존의 Mutex 구현

futex가 나오기 전의 Mutex 구현은 효율적이라고 말하기 어려웠다.

스레드간 통신을 IPC 기반으로 프로세스 간 통신을 날리기도 했고, lock/unlock을 할때마다 syscall을 무지성으로 날려댔다. 아니면 spinlock처럼 대기 중에 CPU 리소스를 과도하게 갉아먹기도 했다.

그래서 과거에는 Mutex를 쓰면 스레드가 늘어날수록 극심하게 성능 저하가 발생했었다. 요즘 구현과 비교하면 수십배, 혹은 수백배까지도 느렸다.

그래서 futex가 무엇인가?

futex는 상기한 비효율성을 개선하기 위해 나왔다.

단, 유의할 점은 이게 os syscall로만 완결되는 기능은 아니란 것이다.
OS 수준에서도 futex 함수를 제공하긴 하는데, 라이브러리 수준에서도 함께 맞춰서 처리를 해줘야 한다.

커널스페이스와 유저스페이스를 적절히 오가면서 커널 호출을 줄이는 하이브리드 방법론이기 때문이다.

물론 대부분의 성숙한 언어들은 기본 Mutex 자체가 거기에 맞춰서 구현을 해뒀다. 내가 확인한 바로 Java, Rust, Go는 표준 Mutex가 확실하게 futex 구현을 사용한다.

계층 분리: user + kernel
아무튼 futex를 대표하는 핵심 원리는 lock과 wait/wake 구조를 분리하는 것이다.
lock을 유저스페이스에서 관리하고, wait/wake를 OS 커널 수준에서 관리한다.
user 수준 lock을 선제적으로 사용하다가, 어쩔 수 없을 때만 os 수준 wait/wake를 사용하는 식으로 구성된다.

1. user 수준 lock
futex의 라이브러리 수준 구현에서는 대부분 내부적으로 추가 플래그를 두고 compare and swap 같은 atomic operation을 돌려서 비교적 가벼운 유저스페이스 Lock을 구현한다.
이를 통해 lock/unlock을 할때 경쟁중인 스레드가 없다면 커널 호출 없이 유저스페이스 Lock만으로 완료할 수 있도록 처리한다. 당연히 커널 호출이 없으니 경쟁이 적은 경우에는 훨씬 빨라진다.
하지만 경쟁이 심하다면 이 방법은 스핀락처럼 리소스를 과다하게 소모한다. 이런 경우에는 결국 2번의 접근법이 필요하다.

2. 커널 수준 wait/wake - 대기열 기반의 스레드 절전
futex에서 중요한 점 중 하나가 "대기 스레드"에 대한 리소스 절약이다. 당연히 lock을 얻지 못해서 대기 중인 스레드의 경우에는, 굳이 리소스를 낭비하게 할 필요가 없다.
이 경우에는 스레드 자체를 "대기열"에 넣어두고, 다른 스레드에서 unlock을 하는 시점에 일어나서(wake) 활성화가 되게 하면 되는 것이다. 이게 futex syscall이 지원하는 영역이다.
이건 경쟁이 적은 경우에는 비효율적이고, 경쟁이 심해서 lock을 쉽게 얻을 수 없는 경우에만 효율적이다. 그래서 일반적으로 user 수준 Lock에서 심한 경쟁이 탐지된 경우에만 사용되곤 한다.

다음은 Rust 표준 뮤텍스의 lock 구현례다.

atomic op으로 먼저 잠겨있는지 최대 2번까지 체크하고, 그래도 충돌이 발생했다면 "futex_wait"으로 커널 호출을 하는 것이다.

그래서 futex는 단독으로 기깔나게 최적화를 잘 한 방법론이라고 할 것은 아니다. 경쟁이 심한 경우와 경쟁이 심하지 않은 경우를 종합해서 유연하게 처리하는 2단계 방법론인 셈이다.

futex의 역사

2002년쯤에 리눅스 커널에 futex라는 이름으로 처음 들어갔다. 이때부터 리눅스에서는 사용이 가능해졌다.

Windows에서는 WaitOnAddress라는 이름으로 2012년부터 지원됐다.
MacOS는 2016년부터 지원한다.

사실 의미적으로 가장 적확한 이름은 futex가 아니라 windows가 작명한 WaitOnAddress다.
futex syscall 자체가 단독으로 하는 역할은 대기열 관리하고 깨워주는게 전부이기 때문이다...

참조
https://h4x0r.org/futex/
https://stackoverflow.com/questions/45764378/how-are-threads-processes-parked-and-woken-in-linux-prior-to-futex
http://www.wowotech.net/kernel_synchronization/futex.html