PI futex는 얼마나 느린가 — 일반 futex와 처리량·우선순위 역전 실측

LWN은 “PING(PI next generation)”이라는 세 번째 futex 종류를 소개했다. 이 패치는 PI(priority-inheritance) futex의 처리량 손실을 줄이려고 나왔다. PI futex는 우선순위 역전(priority inversion)을 막는다. 대신 락을 대기 순서대로 넘기므로 일반 futex보다 느리다. 그런데 얼마나 느린지는 기사에 숫자가 없다.

이 글에서는 pthread 뮤텍스로 일반 futex와 PI futex를 직접 비교한다. 비교 항목은 futex 워드 값, 시스템 콜, 처리량, 우선순위 역전 시 대기 시간이다. 그다음 PING futex가 무엇을 바꾸는지 정리한다. 실험 환경은 Ubuntu 24.04, 커널 6.8.0-149-generic, glibc 2.39, 6 vCPU 가상 머신이다. futex 자체의 동작 원리는 리눅스 커널 futex로 유저스페이스 락 직접 구현하기에서 다뤘다.

일반 futex와 PI futex의 차이

항목일반 futexPI futex
pthread 설정기본값(PTHREAD_PRIO_NONE)PTHREAD_PRIO_INHERIT
futex 워드 값0(해제), 1(잠김), 2(대기자 있음)소유자 TID. 대기자가 있으면 FUTEX_WAITERS(0x80000000) 비트
대기·해제 연산FUTEX_WAIT / FUTEX_WAKEFUTEX_LOCK_PI / FUTEX_UNLOCK_PI
해제할 때대기자 하나를 깨운다. 깨어난 스레드는 다시 경쟁한다커널이 첫 대기자에게 소유권을 넘긴다
우선순위 역전막지 못한다커널이 소유자의 우선순위를 대기자 수준으로 올린다

futex 워드 값 비교

glibc의 pthread_mutex_t는 futex 워드를 __data.__lock에 둔다. 잠근 직후, 대기자가 생긴 뒤, 해제 후의 값을 찍는다.

#define _GNU_SOURCE
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/syscall.h>

static pthread_mutex_t m;

static void *waiter(void *arg)
{
	pthread_mutex_lock(&m);         /* 메인이 잡고 있으므로 대기 */
	pthread_mutex_unlock(&m);
	return NULL;
}

static void show(const char *name, int pi)
{
	pthread_mutexattr_t a;
	pthread_t t;

	pthread_mutexattr_init(&a);
	if (pi)
		pthread_mutexattr_setprotocol(&a, PTHREAD_PRIO_INHERIT);
	pthread_mutex_init(&m, &a);

	pthread_mutex_lock(&m);
	printf("%-6s tid=%ld  잠금 후      futex=0x%08x\n", name,
	       (long)syscall(SYS_gettid), (unsigned)m.__data.__lock);
	pthread_create(&t, NULL, waiter, NULL);
	usleep(100000);
	printf("%-6s              대기자 생김  futex=0x%08x\n", name,
	       (unsigned)m.__data.__lock);
	pthread_mutex_unlock(&m);
	pthread_join(t, NULL);
	printf("%-6s              해제 후      futex=0x%08x\n", name,
	       (unsigned)m.__data.__lock);
}

int main(void)
{
	show("normal", 0);
	show("pi", 1);
	return 0;
}
$ ./futex_word
normal tid=1658  잠금 후      futex=0x00000001
normal              대기자 생김  futex=0x00000002
normal              해제 후      futex=0x00000000
pi     tid=1658  잠금 후      futex=0x0000067a
pi                  대기자 생김  futex=0x8000067a
pi                  해제 후      futex=0x00000000

PI 뮤텍스의 0x67a는 10진수 1658로, 메인 스레드의 TID다. 커널은 이 값으로 소유자를 찾아 우선순위를 올린다.

strace로 본 시스템 콜

아래 처리량 측정 프로그램을 스레드 4개로 실행하고 futex 연산 종류를 센다.

strace -f -qq -e trace=futex ./futex_bench normal 4 2>&1 | grep -o "FUTEX_[A-Z_]*" | sort | uniq -c
strace -f -qq -e trace=futex ./futex_bench pi 4 2>&1 | grep -o "FUTEX_[A-Z_]*" | sort | uniq -c
      1 FUTEX_BITSET_MATCH_ANY
      1 FUTEX_CLOCK_REALTIME
      1 FUTEX_WAIT_BITSET
   4682 FUTEX_WAIT_PRIVATE
   7235 FUTEX_WAKE_PRIVATE
      3 FUTEX_BITSET_MATCH_ANY
      3 FUTEX_CLOCK_REALTIME
   4134 FUTEX_LOCK_PI_PRIVATE
   4134 FUTEX_UNLOCK_PI_PRIVATE
      3 FUTEX_WAIT_BITSET

PI 뮤텍스는 FUTEX_LOCK_PI와 FUTEX_UNLOCK_PI가 정확히 같은 횟수다. 대기했던 잠금마다 커널이 직접 소유권을 넘기기 때문이다.

처리량과 락 넘김 비율

스레드 N개가 3초 동안 잠금과 해제를 반복한다. handoff는 직전 소유자와 다른 스레드가 락을 잡은 비율이다.

#define _GNU_SOURCE
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <sys/resource.h>

#define MAXT 64
static pthread_mutex_t lock;
static volatile int stop;
static unsigned long counts[MAXT];
static long last_owner = -1;
static unsigned long handoffs;    /* 직전 소유자와 다른 스레드가 락을 잡은 횟수 */

static void spin(int n) { for (volatile int i = 0; i < n; i++); }

static void *worker(void *arg)
{
	long id = (long)arg;
	while (!stop) {
		pthread_mutex_lock(&lock);
		if (last_owner != id)
			handoffs++;
		last_owner = id;
		spin(200);              /* 임계 구역 */
		pthread_mutex_unlock(&lock);
		counts[id]++;
		spin(200);              /* 임계 구역 밖 작업 */
	}
	return NULL;
}

int main(int argc, char **argv)
{
	int pi = argc > 1 && !strcmp(argv[1], "pi");
	int nthr = argc > 2 ? atoi(argv[2]) : 4;
	pthread_mutexattr_t a;
	pthread_t t[MAXT];
	struct rusage ru;

	pthread_mutexattr_init(&a);
	if (pi)
		pthread_mutexattr_setprotocol(&a, PTHREAD_PRIO_INHERIT);
	pthread_mutex_init(&lock, &a);

	for (long i = 0; i < nthr; i++)
		pthread_create(&t[i], NULL, worker, (void *)i);
	sleep(3);
	stop = 1;
	for (int i = 0; i < nthr; i++)
		pthread_join(t[i], NULL);

	unsigned long sum = 0, mn = ~0UL, mx = 0;
	for (int i = 0; i < nthr; i++) {
		sum += counts[i];
		if (counts[i] < mn) mn = counts[i];
		if (counts[i] > mx) mx = counts[i];
	}
	getrusage(RUSAGE_SELF, &ru);
	printf("%-6s threads=%d  ops/s=%9lu  handoff=%5.1f%%  min/max=%.2f  vol_csw=%ld\n",
	       pi ? "pi" : "normal", nthr, sum / 3, 100.0 * handoffs / sum,
	       (double)mn / mx, ru.ru_nvcsw);
	return 0;
}
gcc -O2 -Wall -pthread -o futex_bench futex_bench.c
for n in 2 4 6; do ./futex_bench normal $n; ./futex_bench pi $n; done
normal threads=2  ops/s=  3649191  handoff= 59.4%  min/max=0.99  vol_csw=21098
pi     threads=2  ops/s=   114193  handoff= 92.7%  min/max=1.00  vol_csw=43407
normal threads=4  ops/s=  3818099  handoff= 28.7%  min/max=0.99  vol_csw=131070
pi     threads=4  ops/s=    11757  handoff= 99.3%  min/max=0.97  vol_csw=35030
normal threads=6  ops/s=  1744911  handoff= 11.5%  min/max=0.84  vol_csw=12324
pi     threads=6  ops/s=    11315  handoff= 99.1%  min/max=0.95  vol_csw=33598

두 번 실행한 결과를 표로 정리한다. 처리량은 두 번의 범위다.

스레드일반 ops/sPI ops/s일반 handoffPI handoff
2365만~406만11만~29만59~65%91~93%
4334만~382만1.2만~1.3만27~29%99%
6167만~174만1.1만~1.6만12%99~100%

스레드가 4개 이상이면 PI 뮤텍스의 처리량은 일반 뮤텍스의 1/100 아래로 떨어진다. 일반 뮤텍스에서는 락을 놓은 스레드가 곧바로 다시 잡는다(handoff 12%). 이 스레드는 이미 실행 중이고 캐시도 따뜻하다. PI 뮤텍스에서는 거의 매번 잠든 스레드에게 락이 넘어간다. 그 스레드가 깨어나 CPU에 오를 때까지 락은 아무도 쓰지 않는다.

우선순위 역전 실측

PI가 필요한 상황을 재현한다. 세 SCHED_FIFO 스레드를 CPU 0 하나에 묶는다. low(10)가 락을 잡고 50 ms 일한다. high(30)는 그 락을 기다린다. mid(20)는 락과 무관하게 300 ms 동안 CPU를 쓴다.

#define _GNU_SOURCE
#include <pthread.h>
#include <sched.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

static pthread_mutex_t m;

static double now_ms(clockid_t c)
{
	struct timespec ts;
	clock_gettime(c, &ts);
	return ts.tv_sec * 1e3 + ts.tv_nsec / 1e6;
}

/* 스레드 CPU 시간 기준으로 ms만큼 일한다. 선점된 시간은 세지 않는다 */
static void burn(double ms)
{
	double end = now_ms(CLOCK_THREAD_CPUTIME_ID) + ms;
	while (now_ms(CLOCK_THREAD_CPUTIME_ID) < end)
		;
}

static void *low(void *a)  { pthread_mutex_lock(&m); burn(50); pthread_mutex_unlock(&m); return NULL; }
static void *mid(void *a)  { burn(300); return NULL; }
static void *high(void *a)
{
	double t0 = now_ms(CLOCK_MONOTONIC);
	pthread_mutex_lock(&m);
	printf("  high: 락 대기 %.1f ms\n", now_ms(CLOCK_MONOTONIC) - t0);
	pthread_mutex_unlock(&m);
	return NULL;
}

static pthread_t start(void *(*fn)(void *), int prio)
{
	pthread_attr_t a;
	struct sched_param sp = { .sched_priority = prio };
	pthread_t t;

	pthread_attr_init(&a);
	pthread_attr_setinheritsched(&a, PTHREAD_EXPLICIT_SCHED);
	pthread_attr_setschedpolicy(&a, SCHED_FIFO);
	pthread_attr_setschedparam(&a, &sp);
	pthread_create(&t, &a, fn, NULL);
	return t;
}

int main(int argc, char **argv)
{
	int pi = argc > 1 && !strcmp(argv[1], "pi");
	struct sched_param sp = { .sched_priority = 50 };
	pthread_mutexattr_t a;
	cpu_set_t cpu;
	pthread_t l, mi, h;

	CPU_ZERO(&cpu);
	CPU_SET(0, &cpu);
	sched_setaffinity(0, sizeof(cpu), &cpu);   /* 모두 CPU 0 하나에서 경쟁 */
	sched_setscheduler(0, SCHED_FIFO, &sp);

	pthread_mutexattr_init(&a);
	if (pi)
		pthread_mutexattr_setprotocol(&a, PTHREAD_PRIO_INHERIT);
	pthread_mutex_init(&m, &a);

	printf("%s:\n", pi ? "PTHREAD_PRIO_INHERIT" : "PTHREAD_PRIO_NONE");
	l = start(low, 10);  usleep(10000);   /* low가 락을 잡는다 */
	h = start(high, 30); usleep(5000);    /* high가 락에서 막힌다 */
	mi = start(mid, 20);                  /* mid가 CPU를 차지한다 */
	pthread_join(h, NULL);
	pthread_join(mi, NULL);
	pthread_join(l, NULL);
	return 0;
}
gcc -O2 -Wall -pthread -o prio_inv prio_inv.c
sudo ./prio_inv none
sudo ./prio_inv pi
PTHREAD_PRIO_NONE:
  high: 락 대기 334.4 ms
PTHREAD_PRIO_INHERIT:
  high: 락 대기 35.3 ms
PTHREAD_PRIO_NONE:
  high: 락 대기 338.4 ms
PTHREAD_PRIO_INHERIT:
  high: 락 대기 39.1 ms
프로토콜high의 대기 시간이유
PTHREAD_PRIO_NONE334~338 msmid(20)가 low(10)를 선점한다. high는 mid가 끝날 때까지 기다린다
PTHREAD_PRIO_INHERIT35~39 ms커널이 low를 30으로 올린다. mid가 low를 선점하지 못한다

PI가 없으면 high는 자기와 상관없는 mid의 300 ms를 그대로 기다린다. 이 시간이 처리량을 내주고 PI를 쓰는 이유다.

PING futex가 바꾸는 것

술레이만 수랄(Suleiman Souhlal)의 PING futex는 위 두 결과를 함께 얻으려 한다. 패치는 아직 메일링 리스트 단계라 직접 실행하지 못했다. 아래는 LWN 기사와 패치 설명 기준이다.

변경동작위 실험과의 관계
잠금 가로채기(lock stealing)대기자가 깨어나는 동안 락은 “비었지만 대기자 있음” 상태다. 실행 중인 다른 스레드가 이 락을 가져갈 수 있다handoff 99%를 일반 futex 수준으로 낮추려는 장치
기아 방지한 번 가로채인 뒤의 해제에서는 첫 대기자에게 직접 넘긴다대기자가 무한히 밀리지 않는다
커널 스핀잠들기 전에 커널에서 잠깐 스핀한다. 소유자가 같은 CPU에 있으면 스핀하지 않는다가로채기 성공률을 높인다
proxy execution우선순위 대신 대기 스레드의 실행 환경 전체를 소유자에게 빌려준다. 해제 시 그 대기 스레드를 깨운다우선순위 역전 실험의 PI 결과를 유지한다. 모든 스케줄링 클래스에서 같게 동작한다

페터르 제일스트라(Peter Zijlstra)는 잠금 변경에 반대하고 대안을 제안했다. 그는 다른 futex 개선 계획이 있어 이 작업이 이르다고 본다. 기존 PI futex를 proxy execution으로 바꾸려는 작업도 따로 있다. 머지까지는 시간이 걸릴 것이다.

주의사항

  • 경쟁이 심한 락에 PTHREAD_PRIO_INHERIT를 기본으로 켜지 말 것. 위 실험에서 스레드 4개부터 처리량이 1/100 아래로 떨어졌다. 실시간 스레드가 그 락을 기다리는 경우에만 쓴다.
  • SCHED_OTHER 스레드만 쓰는 프로그램에서 PI 효과를 기대하지 말 것. 우선순위 상속은 RT 우선순위에서 의미가 있다. LPC 발표에서는 SCHED_NORMAL 작업에서 PI futex가 오히려 역전을 키우는 경우도 소개됐다.
  • __data.__lock을 프로그램 로직에 쓰지 말 것. glibc 내부 필드다. 위 코드는 관찰용이다.
  • 숫자를 다른 환경에 그대로 옮기지 말 것. 측정은 6 vCPU 가상 머신에서 했다. 임계 구역 길이와 코어 수에 따라 비율이 바뀐다.
  • SCHED_FIFO 실험은 root로, 전용 호스트에서 할 것. 바쁜 루프가 CPU 0을 독점한다. 기본 sched_rt_runtime_us(950000)가 남겨 두는 5%만 다른 작업에 돌아간다.

마무리

PI futex는 우선순위 역전을 300 ms에서 40 ms 아래로 줄였다. 하지만 경쟁 상황의 처리량은 1/100 아래로 떨어졌다. 차이는 락을 누구에게 넘기느냐에서 나온다. PING futex는 가로채기로 처리량을 되찾고 proxy execution으로 역전을 막으려 한다. 머지된다면 위 벤치마크로 다시 비교할 수 있다.

참고

답글 남기기