io_uring을 쓰는 프로그램은 한 번에 여러 비동기 작업을 던져놓고 진행 상황을 추적한다. 그 말은 곧 커널 내부의 io_uring 서브시스템이 처리해야 할 작업(task) 목록을 항상 관리하고 있어야 한다는 뜻이다. 지금까지 io_uring은 이 목록을 커널의 범용 lockless 단일 연결 리스트(llist)로 관리해왔는데, 커널 7.2부터는 여기에 전용으로 새로 만든 lockless MPSC(Multi-Producer Single-Consumer) 큐가 대신 들어간다. 자료구조 하나 바꾼 것치고는 io_uring 코드가 단순해지고 성능도 눈에 띄게 좋아졌는데, 그 이유는 기존 llist가 이 용도에 근본적으로 안 맞았기 때문이다. 이 글에서는 llist 방식이 어떤 문제를 겪었는지, 새 MPSC 큐가 어떻게 이를 해결하는지, 그리고 완전한 lock-free는 아니라는 흥미로운 디테일까지 정리한다.
기존 llist 방식의 한계
커널의 llist는 다음과 같은 단순한 단일 연결 노드로 이루어진다.
struct llist_node {
struct llist_node *next;
};단일 연결이라 head 쪽에서만 접근이 실용적이고, 그 결과 여러 생산자가 넣고 하나의 소비자가 꺼내는 구조에서는 사실상 스택(LIFO)처럼 동작한다. 문제는 io_uring이 공정성을 위해 작업을 받은 순서(FIFO)대로 처리해야 한다는 점이다. 그래서 매 처리 라운드마다 리스트 전체를 순회하며 순서를 뒤집어야 했다. 여기에 큐가 너무 길어 한 번에 다 처리하지 못하는 경우까지 겹치면 문제가 더 커진다. 이미 뒤집어놓은 나머지 항목들을 원래 리스트에 그냥 다시 넣을 수 없어서, “뒤집었지만 아직 처리하지 않은 항목”을 위한 별도 리스트를 따로 유지해야 했다. 게다가 llist에 항목을 추가하는 것 자체도 단일 head 포인터를 두고 벌이는 CAS 재시도 루프라서, 경쟁이 심해지면 재시도와 그에 따른 캐시라인 바운싱이 성능을 깎아먹는다.
Lockless MPSC 큐의 구조
Jens Axboe가 올린 새 큐는 Dmitry Vyukov가 고안한 알고리즘을 기반으로 한다. 여전히 llist_node로 항목을 엮지만, 큐 자체는 다음과 같은 구조체로 표현한다.
struct mpscq {
struct llist_node *tail;
struct llist_node stub;
};“head”라는 이름이 없는 게 눈에 띄는데, 이 구조체는 생산자(producer) 관점만 담고 있어서 tail 포인터만 있으면 충분하기 때문이다. stub은 큐가 비어 있을 때만 리스트에 남아 있는 센티널(sentinel) 노드로, 초기화 시점에는 tail이 stub을 가리키고 stub.next는 NULL이다.
mpscq_push() — 생산자 쪽 동작
항목을 추가하는 함수는 이렇다.
static inline bool mpscq_push(struct mpscq *q, struct llist_node *node)
{
struct llist_node *prev;
node->next = NULL;
prev = xchg(&q->tail, node);
WRITE_ONCE(prev->next, node);
return prev == &q->stub;
}xchg()가 새 노드를 tail에 원자적으로 꽂고 이전 값을 돌려준다. 그 이전 값(빈 큐라면 stub)의 next를 새 노드로 연결하면 추가가 끝난다. 여기서 중요한 건 xchg()가 풀 배리어(full barrier)라는 점이다. node->next = NULL 대입이 tail 갱신보다 먼저 완료되고 나머지 시스템에 보인다는 걸 보장해주기 때문에, 컴파일러나 CPU가 두 대입 순서를 재배치해서 아직 초기화되지 않은 노드가 먼저 보이는 사고를 막아준다. 여러 CPU가 동시에 push를 호출해도 xchg()가 이들을 순서대로 직렬화해주므로, 락 없이도 tail이 일관된 상태를 유지한다. 두 CPU가 빈 큐에 거의 동시에 push(X), push(Y)를 호출하는 상황을 그림으로 보면 이해가 빠르다.
1) CPU1: prev = xchg(&tail, X) -> prev=stub, tail=X
2) CPU2: prev = xchg(&tail, Y) -> prev=X, tail=Y
(xchg가 원자적으로 직렬화하므로 순서는 위와 같이 정해진다)
이 시점 - 아직 WRITE_ONCE(prev->next, node)가 실행되기 전:
tail
|
v
[stub] [X] [Y]
next:NULL next:? next:NULL
(stub->X, X->Y 연결이 아직 안 됨)
3) CPU1이 WRITE_ONCE(stub.next, X) 실행
4) CPU2가 WRITE_ONCE(X.next, Y) 실행
최종 상태:
tail
|
v
[stub] --> [X] --> [Y] --next--> NULLmpscq_pop() — 소비자 쪽 동작
소비자는 mpscq 구조체와 별개로 자기만의 head 포인터를 따로 들고 있다. 이렇게 분리해두는 이유는 head와 tail을 서로 다른 캐시라인에 두어, 생산자와 소비자가 서로의 캐시라인을 밟지 않게 하기 위해서다.
struct llist_node *head = *headp, *next;
if (head == &q->stub) {
head = READ_ONCE(head->next);
if (!head)
return NULL;
q->stub.next = NULL;
*headp = head;
}
next = READ_ONCE(head->next);
if (next) {
*headp = next;
return head;
}
if (try_cmpxchg(&q->tail, &head, &q->stub)) {
*headp = &q->stub;
return head;
}
return NULL;세 경우로 나눠서 보면 이해하기 쉽다. head가 아직 stub을 가리키고 있다면(초기 상태 또는 방금 큐가 빈 상태에서 시작한 경우) stub.next를 확인해서 진짜 빈 큐인지, 새로 들어온 첫 항목이 있는지를 가른다. 다음 항목(next)이 있으면 그냥 head를 한 칸 옮기고 반환하면 끝이라 가장 흔한 경로이자 가장 빠른 경로다. next가 없다면 지금 꺼내려는 항목이 큐의 마지막 항목이라는 뜻인데, 이때는 tail을 다시 stub으로 되돌려야 큐가 빈 상태로 정리된다. 다만 이 순간에도 다른 생산자가 동시에 새 항목을 밀어 넣고 있을 수 있어서, try_cmpxchg()로 “내가 알고 있던 tail(=head)이 여전히 유효하면 stub으로 되돌리고, 아니라면 실패로 처리해 NULL을 반환”하는 식으로 안전하게 처리한다. 큐가 비었는지는 별도로 다음 함수로 확인한다. 일반적인 경우와 마지막 항목을 꺼내는 경우를 그림으로 비교하면 다음과 같다.
[일반적인 경우 - head 다음에 또 다른 항목이 있음]
head tail
| |
v v
[X] --> [Y] --next--> NULL
mpscq_pop() 호출 -> X 반환, head를 Y로 이동
head tail
| |
v v
[Y] --next--> NULL (X는 반환되어 큐에서 제외됨)
[마지막 항목을 꺼내는 경우 - try_cmpxchg로 tail을 stub으로 리셋]
head tail
| |
v v
[Y] --next--> NULL
try_cmpxchg(&tail, &Y, &stub) 성공 -> Y 반환, tail/head 모두 stub으로
head/tail
|
v
[stub] --next--> NULL (큐가 다시 빈 상태)static inline bool mpscq_empty(struct mpscq *q)
{
return READ_ONCE(q->tail) == &q->stub;
}진짜 lock-free는 아니다 — 유예 구간의 존재
이 알고리즘에는 잘 알려지지 않은 흥미로운 함정이 하나 있다. mpscq_push() 안에서 xchg(&q->tail, node)가 끝난 직후, 아직 WRITE_ONCE(prev->next, node)가 실행되기 전에 해당 생산자 스레드가 스케줄러에 의해 suspend되면 어떻게 될까. 이 구간에서 tail은 이미 새 노드를 가리키고 있지만, 그 노드는 아직 이전 노드의 next에 연결되지 않아 head 쪽에서는 도달할 방법이 없다. 이 상태에서 소비자가 mpscq_pop()을 호출하면 try_cmpxchg()가 실패해 NULL을 반환하는데, 동시에 mpscq_empty()는 false를 반환한다. 즉 “큐가 비어 있지는 않은데 지금 당장 꺼낼 건 없다”는 애매한 상태가 실제로 존재하고, 소비자는 이걸 “큐가 비었다”로 오해하지 말고 나중에 다시 시도해야 한다. 실제로 커널 소스의 io_uring/mpscq.h 상단 주석에도 이 구간이 “두 명령어 너비”라는 설명과 함께 명시되어 있다.
이건 학술적으로 엄밀한 의미의 lock-free 조건 — 임의의 스레드 하나가 멈춰도 나머지 시스템은 계속 진행할 수 있어야 한다는 조건 — 을 완전히 만족하지는 못한다는 뜻이다. 한 생산자가 하필 이 두 명령어 사이에서 오래 suspend되면, 그 뒤에 다른 생산자들이 아무리 항목을 추가해도 소비자 쪽에서는 전부 보이지 않는 상태로 쌓이게 된다. 다만 이런 지연이 발생해도 정확성 자체는 깨지지 않고(생산자가 재개되면 밀려 있던 항목이 한꺼번에 보인다), 하드 리얼타임처럼 지연 시간에 엄격한 보장이 필요하지 않은 I/O 워크로드에서는 실용적으로 문제가 되지 않는다는 게 커널 개발자들의 판단이다. 이 유예 구간을 그림으로 표현하면 다음과 같다.
[생산자가 xchg 직후, WRITE_ONCE(prev->next, node) 직전에 suspend됨]
tail
|
v
head [X]
| next: NULL
v
[stub] (stub.next는 아직 NULL - X로 연결 안 됨)
next: NULL
이 상태에서:
mpscq_pop() -> NULL 반환 (head 쪽에서 X에 도달 불가)
mpscq_empty() -> false 반환 (tail != stub 이므로)커널 7.2에서의 실제 효과
이 코드는 아직 io_uring/mpscq.h에만 있고, 커널 전역에서 쓸 수 있도록 lib/ 아래로 일반화되지는 않은 상태다. 커널 7.2부터 io_uring 내부 태스크 리스트 몇 곳에 이 구조가 적용됐고, 리스트를 뒤집는 과정과 “뒤집었지만 처리 안 된 항목”을 위한 별도 리스트가 통째로 사라지면서 코드가 단순해졌다. 성능 측면에서도 처리량은 늘고 커널 안에서 보내는 시간은 줄어드는, 자료구조 교체치고는 상당히 확실한 개선이 있었다고 보고됐다.
직접 확인해보기 — 유저스페이스로 포팅한 데모
커널 API인 xchg()/try_cmpxchg()/READ_ONCE()/WRITE_ONCE()를 C11 표준 원자 연산으로 그대로 옮기면 유저스페이스에서도 같은 알고리즘을 재현해볼 수 있다. 개념 검증용으로 컴파일·실행까지 확인한 코드다.
#include <stdatomic.h>
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define NUM_PRODUCERS 4
#define ITEMS_PER_PRODUCER 100000
typedef struct node {
_Atomic(struct node *) next;
int value;
} node_t;
typedef struct {
_Atomic(node_t *) tail;
node_t stub;
} mpscq_t;
static void mpscq_init(mpscq_t *q) {
atomic_store(&q->stub.next, NULL);
atomic_store(&q->tail, &q->stub);
}
static int mpscq_push(mpscq_t *q, node_t *node) {
atomic_store(&node->next, NULL);
node_t *prev = atomic_exchange(&q->tail, node);
atomic_store(&prev->next, node);
return prev == &q->stub;
}
static node_t *mpscq_pop(mpscq_t *q, node_t **headp) {
node_t *head = *headp;
node_t *next;
if (head == &q->stub) {
head = atomic_load(&head->next);
if (!head)
return NULL;
atomic_store(&q->stub.next, NULL);
*headp = head;
}
next = atomic_load(&head->next);
if (next) {
*headp = next;
return head;
}
node_t *expected = head;
if (atomic_compare_exchange_strong(&q->tail, &expected, &q->stub)) {
*headp = &q->stub;
return head;
}
return NULL;
}
static mpscq_t queue;
static _Atomic long total_pushed = 0;
void *producer(void *arg) {
long id = (long)arg;
for (int i = 0; i < ITEMS_PER_PRODUCER; i++) {
node_t *n = malloc(sizeof(*n));
n->value = (int)(id * ITEMS_PER_PRODUCER + i);
mpscq_push(&queue, n);
atomic_fetch_add(&total_pushed, 1);
}
return NULL;
}
int main(void) {
mpscq_init(&queue);
node_t *head = &queue.stub;
pthread_t producers[NUM_PRODUCERS];
for (long i = 0; i < NUM_PRODUCERS; i++)
pthread_create(&producers[i], NULL, producer, (void *)i);
long popped = 0;
long expected_total = (long)NUM_PRODUCERS * ITEMS_PER_PRODUCER;
while (popped < expected_total) {
node_t *n = mpscq_pop(&queue, &head);
if (n) {
popped++;
free(n);
}
}
for (int i = 0; i < NUM_PRODUCERS; i++)
pthread_join(producers[i], NULL);
printf("pushed=%ld popped=%ld\n", atomic_load(&total_pushed), popped);
return 0;
}생산자 스레드 4개가 각각 10만 개씩 항목을 밀어 넣고, 메인 스레드 하나가 소비자로서 계속 pop을 돌리며 꺼낸다. 컴파일하고 실행하면 다음과 같다.
gcc -O2 -pthread -Wall -Wextra -o mpscq_demo mpscq_demo.c
./mpscq_demopushed=400000 popped=400000여러 번 반복 실행해도 push된 개수와 pop된 개수가 항상 일치한다. 소비자가 바쁜 대기(busy-wait)로 mpscq_pop()을 계속 호출하는 구조라 앞서 설명한 “유예 구간”에 걸리더라도 조금 있다 재시도하면서 결국 모든 항목을 놓치지 않고 꺼내오는 걸 확인할 수 있다.
주의사항
- 이 큐는 이름 그대로 소비자가 하나일 때만 안전하다. 소비자를 여러 개 두려면
headp를 공유하는 부분부터 다시 설계해야 한다. mpscq_pop()이NULL을 반환했다고 큐가 비었다고 단정하면 안 된다.mpscq_empty()로 별도 확인하거나, 앞서 설명한 유예 구간을 감안해 짧게 재시도하는 로직이 필요하다.- 지연 시간에 엄격한 보장이 필요한 실시간성 워크로드에는 이 알고리즘의 특성(생산자 하나가 소비자 진행을 잠깐 막을 수 있음)이 맞지 않을 수 있다.
마무리
io_uring의 이번 변화는 범용 자료구조(llist)를 가져다 쓰다가, 실제 사용 패턴(다수 생산자·단일 소비자, FIFO 순서 필요)에 맞춘 전용 자료구조로 옮겨가면서 얻은 이득을 잘 보여준다. 락 없이 동작하면서도 재정렬이나 별도 보조 리스트 없이 FIFO를 그대로 유지한다는 점에서 실용적인 설계고, 동시에 “완전한 lock-free는 아니다”라는 이론과 실무 사이의 간극을 스스로 드러내고 문서화까지 해뒀다는 점도 눈여겨볼 만하다.