몇 달째, 리눅스 커널이 “다음에 어떤 태스크에 CPU를 넘길지” 결정하는 방식을 다룬 4부작 연재를 몇 주 간격으로 읽어왔다. 앞의 세 편은 만족스러운 이야기였다. 스케줄러는 측정할 수 없는 것(공정성)을 계산 가능하게 만들기 위해 허구의 시계를 발명하고, 깨질 수 없는 것(보장)을 실제로 구현하기 위해 거부권으로 뒷받침되는 진짜 계약을 발명한다. 하지만 마지막 편은 그 만족감의 일부를 무너뜨린다. 깔끔한 보장이 동시에 두 종류의 자원을 커버하라는 요구를 받는 순간 무슨 일이 벌어지는지를 보여주기 때문이다. 그 답은 내가 예상했던 것보다 훨씬 더 넓게 일반화된다.

비슷해 보이지만 다른 두 문제

현대의 CPU는 사실상 여러 개의 CPU다 — 코어, 소켓, 메모리 노드가 각기 다른 길이와 비용의 배선으로 연결되어 있다. 리눅스가 태스크를 “언제” 실행할지 결정할 때는 진짜 이론에 기댈 수 있다. EEVDF(Earliest Eligible Virtual Deadline First)는 2023년 10월 v6.6에서 기존의 Completely Fair Scheduler를 대체하며 일반 태스크의 기본 정책이 되었는데1, 공정성을 하나의 스칼라 값 — lag — 로 환원하고 그 값이 유계(bounded)임을 증명한다. 그 위에 있는 SCHED_DEADLINE은 공정성을 실제 계약으로 바꾼다. 태스크는 주기마다 얼마만큼의 실행 시간이 필요한지 선언하고, 입구의 admission control이 그 선언을 다른 모든 태스크의 선언과 합산해 총합이 CPU의 100%를 넘으면 거부한다. 승인된 태스크만이 “얼마나 늦어질 수 있는가(tardiness)”에 대한 수학적으로 유계인 보장을 받는다2.

하지만 “언제”는 스케줄러가 하는 일의 절반일 뿐이다. “어디서” — 머신의 어느 코어에서 태스크가 실제로 실행될지 — 도 결정해야 한다. 그리고 이 결정은, 알고 보면 같은 옷을 입은 전혀 다른 종류의 문제다.

이론이 없는 축

시간 축에는 약 300줄의 원리적인 수학이 주어졌다. 공간 축에 주어진 것은 그와 다른 것 — 휴리스틱의 누적이다. 리눅스는 물리적 머신을 “스케줄링 도메인”의 트리로 표현한다 — 하이퍼스레드 형제, 같은 다이 위의 코어, 소켓, NUMA 노드 — 그리고 주기적으로 그 트리를 훑으며 가장 혼잡한 그룹과 그 안에서 가장 혼잡한 큐를 찾아, 한가한 쪽으로 작업을 옮긴다. 시간 안에 한가한 코어를 찾으려면 그 자체로 별도의 지름길이 필요하고(전체 스캔이 가치가 있는지 미리 판단하는 사용률 사전 검사 등), 그 지름길들은 지금도 계속 패치되고 있다. 물리적 거리를 위한 vruntime 같은 것은 없다. “이 태스크를 이 코어에서 저 코어로 옮기는 비용이 얼마인가”를, lag가 “이 태스크가 자기 몫에 비해 얼마나 CPU를 받았는가”를 포착하는 것과 같은 방식으로 포착할 단 하나의 허구적 숫자를, 아직 아무도 발명하지 못했다.

이건 게으름의 문제가 아니다. 2016년의 실측 연구 “The Linux Scheduler: A Decade of Wasted Cores”는 이 휴리스틱 층이 실제로 재현 가능한 버그를 만들어낸다는 것을 보여줬다 — 실행 가능한 스레드가 다른 곳에서 기다리는 동안 코어가 몇 초씩 그냥 놀고 있는 것이다. 한 사례에서는 스케줄링 그룹을 구성하는 방식의 버그로 인해 같은 코어 집합이 겹치는 두 그룹에 등록되어, 시작 시점에 그곳에 배치된 태스크가 두 번 다시 밸런싱으로 빠져나가지 못했다. 이 논문은 동기화가 많은 과학 계산 워크로드에서 수 배의 속도 저하, 커널 빌드에서 두 자릿수 퍼센트의 지연 증가, 상용 데이터베이스에서 비슷한 수준의 처리량 저하를 보고했다 — 모두 배치의 문제이지 공정성 수학 자체의 결함이 아니다3. 실제 운영 환경에서 사람들이 의지하는 해결책은 더 똑똑한 스케줄러가 아니라 taskset이다. 태스크를 코어에 수동으로 고정시켜, 자동 결정 자체에서 발을 빼는 것이다.

계약이 깨지는 지점

여기가, 몇 주 전 내가 직접 썼던 내용에 대한 생각을 바꾼 부분이다. SCHED_DEADLINE의 admission control 보장 — 이전 글에서, “스스로를 구속하는 태스크는 단지 우선순위가 높다고 주장만 하는 태스크보다 더 신뢰받는다”는 성질 때문에 스케줄러 전체에서 가장 강한 약속이라고 불렀던 그것 — 은 알고 보니 시간 축을 따라서만 성립한다. 태스크를 특정 코어의 부분집합에 고정하는 순간(CPU affinity), 그 보장은 깨질 수 있다. 2021년 논문은 일반적인 affinity 마스크 아래에서는 SCHED_DEADLINE이 tardiness 보장을 확실히 유지하지 못하며, 이를 일반적으로 고치려면 비현실적일 정도의 내부 재작업이 필요하다고 밝혔다. 고칠 수 있는 것은 제한된 경우(semi-partitioned affinity)뿐이다4. 근본적인 이유는 코드의 실수가 아니다 — 하나의 공유 자원(총 CPU 시간)에 대해 태스크를 승인하는 것은 단순한 산술 검사지만, CPU 시간과 허용된 코어의 특정 부분집합을 동시에 승인하는 것은 빈 패킹(bin-packing) 문제가 되고, 빈 패킹은 일반적으로 NP-난해하기 때문이다. 시사적인 점은, 이 보장의 공백이 tardiness 보장이 처음 구현된 지 몇 년이 지난 뒤에도 스케줄러의 담당자 자신에 의해 미해결 문제로 계속 언급되었다는 것이다5.

즉, 단독으로 봤을 때 그토록 신뢰할 만하다고 내가 느꼈던 그 약속 — “이만큼만, 이 빈도로만 소비하겠다” — 은 “어디서(공간)”라는 두 번째 축이 “언제(시간)”에 함께 실리는 순간, 조용히 약속이기를 멈춘다. 선언의 내용은 아무것도 바뀌지 않았다. 바뀐 것은 그것이 동시에 몇 개의 독립적인 것을 보장하라고 요구받고 있는가다.

일반화할 수 있는 것

여기엔 명확히 말할 가치가 있는 주장이 있다고 생각한다. 커널에만 국한된 이야기로 보이지 않기 때문이다 — 보장의 강도는 그것이 커버하는, 독립적으로 변동하는 자원의 개수에 반비례한다. 응답 시간을 약속하는 업체는 검증 가능한 주장을 하고 있는 것이다. 응답 시간과 고정된 팀과 고정된 예산과 고정된 근무 시간을 약속하는 업체는, 어느 지점을 넘어서면 약속하는 그 순간에는 아무도 검증할 수 없는 내적 정합성을 주장하고 있는 셈이다 — 거짓말을 해서가 아니라, 검증해야 할 문제 자체가 조합적으로 어려워지기 때문이다. 이건 야심 찬 계약에 반대하는 주장이 아니다. “전부 약속합니다”와 “이 하나만 약속합니다”는, 둘 다 진심으로 한 말이라도 서로 다른 종류의 진술이라는 걸 알아채야 한다는 주장이다.

이보다 좁지만 인접한 관찰이 하나 더 있다. 시간 축을 다루기 쉽게 만드는 허구의 시계 — vruntime, lag — 가 작동하는 이유는, CPU 시간이 애초에 인위적이고 자의적인 단위이기 때문일 뿐이다. 그것을 “자연스럽게” 소비하는 방법 같은 건 처음부터 없었으니, 그것을 위한 회계 방식을 발명하는 데는 개념적으로 아무 비용도 들지 않는다. 코어 간의 물리적 거리는 그렇지 않다. 캐시 공유, 메모리 지연, 전력 도메인은 스케줄러가 배분을 시작하기도 전에 실리콘에 관한 사실로 이미 고정되어 있다. 이미 형태를 가진 자원에 시계를 발명해 덮어씌울 수는 없다 — 할 수 있는 것은, 내가 선택하지 않은 그 형태를 존중하는 휴리스틱을 쌓아 올리는 것뿐이다. 이 구분 — 자의적이기 때문에 배분 가능한 것과, 물리적임에도 불구하고 배분해야만 하는 것 — 이 커널 바깥에서 얼마나 멀리까지 통하는지는 아직 모르겠다. 하지만 토지, 전파 대역, 주의(attention)처럼 희소하면서도 절반은 자연적인 것을 사람들이 나누려는 곳이라면 어디든 얼굴을 내밀 것 같은 종류의 이야기라고 느낀다.

연재의 저자들은 지금 sched_ext를 주시하고 있다. 2024년 하반기에 커널에 병합된 메커니즘으로, 커스텀 스케줄러를 커널 본체에 컴파일해 넣는 대신 로드 가능한 BPF 프로그램으로 실행할 수 있게 해준다6. 이것이 공간 축 문제에 대한 진짜 답인지, 아니면 같은 미해결 휴리스틱을 좀 더 반복 개발하기 쉬운 곳으로 옮긴 것뿐인지는 아직 모르겠다. 이것이 지금 내가 계속 붙들고 있는 질문이다 — 더 유연한 실험의 장은 어려운 문제에 대한 진짜 진전인가, 아니면 그 문제를 미해결로 남겨두기에 더 편안한 자리일 뿐인가.

  1. Michael Larabel, “EEVDF Scheduler Merged For Linux 6.6,” Phoronix. 확인일: 2026-08-15. ↩

  2. “Deadline Task Scheduling,” The Linux Kernel documentation. 확인일: 2026-08-15. ↩

  3. Jean-Pierre Lozi, Baptiste Lepers, Justin Funston, Fabien Gaud, Vivien Quéma, Alexandra Fedorova, “The Linux Scheduler: a Decade of Wasted Cores,” EuroSys 2016. 확인일: 2026-08-15. ↩

  4. “On the Defectiveness of SCHED_DEADLINE w.r.t. Tardiness and Affinities, and a Partial Fix,” RTNS 2021. 확인일: 2026-08-15. ↩

  5. “GEDF Tardiness: Open Problems Involving Uniform Multiprocessors and Affinity Masks Resolved,” ECRTS 2019 (Peter Zijlstra의 ECRTS 2017 기조연설 미해결 문제 목록에 대한 언급 포함). 확인일: 2026-08-15. ↩

  6. “Sched_EXT With Linux 6.19 Improves Recovering For Misbehaving eBPF Schedulers,” Phoronix (sched_ext가 확장 가능한 스케줄러 클래스로 병합된 배경 정보). 확인일: 2026-08-15. ↩