멀티프로세서 스케줄링: 복잡한 코어들의 효율적인 지휘법

현대 컴퓨팅 환경에서 멀티프로세서(Multiprocessor) 시스템은 일반 적이다. 노트북, 스마트폰조차 여러 개의 CPU 코어가 들어간 멀티코어 프로세서를 사용하고 있다. 하지만 CPU가 많아진다고 해서 시스템이 저절로 빨라지는 것은 아니다. 운영체제가 여러 코어에 작업을 어떻게 배분하느냐, 즉 **멀티프로세서 스케줄링(Multiprocessor Scheduling)**이 성능의 핵심을 결정한다.

1. 배경: 하드웨어의 이해 없이는 스케줄링도 없다

멀티프로세서 스케줄링을 이해하려면 먼저 하드웨어, 특히 **캐시(Cache)**를 알아야 한다.

캐시와 지역성 (Locality)

CPU는 메인 메모리에서 데이터를 가져오는 속도가 상대적으로 느리기 때문에, 자주 사용되는 데이터의 복사본을 캐시라는 작고 빠른 메모리에 저장한다. 캐시는 **지역성(Locality)**에 기반하여 작동한다. 캐시는 2가지로 나뉜다.

시간 지역성(Temporal Locality): 한 번 접근된 데이터는 곧 다시 접근될 가능성이 높다.
공간 지역성(Spatial Locality): 접근된 데이터의 주변 데이터도 곧 접근될 가능성이 높다.

캐시 일관성 (Cache Coherence)

문제는 CPU가 여러 개일 때 발생한다. 여러 CPU가 동일한 메모리 주소의 데이터를 각자의 캐시에 가지고 있을 때, 한 CPU가 이 데이터를 수정하면 다른 CPU가 가진 데이터는 ‘과거의 것’이 되어버려 일관성을 잃어버린다. 이를 해결하기 위해 하드웨어 차원에서 버스 스누핑(Bus Snooping) 등의 기법을 사용하여 데이터 변경을 감지하고, 다른 캐시의 데이터를 무효화(Invalidate)하거나 갱신하여 일관성을 유지한다.

2. 멀티프로세서 스케줄링의 난제

멀티프로세서 스케줄링을 구현할 때 크게 두 가지 문제를 마주친다.

동기화(Synchronization)와 확장성(Scalability): 여러 CPU가 스케줄링을 위해 공통된 자료구조(예: 준비 큐)에 접근하려면 락(Lock) 이 필수적이다. 하지만 코어 수가 늘어날수록 락을 얻기 위한 경쟁(Lock Contention/Overhead)이 심해져 성능 저하가 발생한다.
캐시 친화성(Cache Affinity): 프로세스가 특정 CPU에서 실행되면 그 CPU의 캐시에 프로세스의 데이터가 쌓입니다(Warm Cache). 만약 다음 타임 슬라이스에 다른 CPU에서 실행된다면(Migration), 캐시를 다시 채워야 하므로(Cold Cache) 성능 손실이 발생한다. 따라서 가능한 한 쓰던 CPU를 계속 쓰는 것이 유리하다.

3. 접근법 1: 단일 큐 스케줄링 (SQMS)

가장 단순한 접근 방식은 모든 작업을 하나의 전역 큐(Single Queue) 에 넣고, 노는 CPU가 작업을 하나씩 꺼내가는 것이다.

장점

단순함: 기존 단일 프로세서 스케줄러를 거의 그대로 사용할 수 있다.
자동 부하 분산(Load Balancing): 모든 CPU가 하나의 큐를 공유하므로, 특정 CPU만 놀고 있는 상황이 발생하지 않는다.

단점

확장성 저하: CPU가 늘어날수록 큐에 접근하기 위한 락 경쟁이 치열해져 성능이 급격히 떨어진다.
캐시 친화성 부족: 작업이 매번 이리저리 다른 CPU에서 실행될 수 있어 캐시 효과를 보기 어렵다. 이를 해결하기 위해 ‘가능하면 원래 CPU에서 실행’하도록 하는 메커니즘을 추가해야하므로 구현이 복잡해진다.

4. 접근법 2: 멀티 큐 스케줄링 (MQMS)

확장성 문제를 해결하기 위해, CPU마다 **자신만의 큐(Multi Queue)**를 가지는 방식이 제시되었다.

특징

새로운 작업이 들어오면 특정 정책(랜덤, 적은 작업 수 등)에 따라 하나의 큐에 배정된다.
그 이후로는 기본적으로 그 큐(CPU)에서만 실행된다.

장점

뛰어난 확장성: 각 CPU는 자기 큐만 쳐다보면 되므로 락 경쟁이나 동기화 오버헤드가 거의 없다.
강력한 캐시 친화성: 작업이 계속 같은 CPU에 머무르므로 캐시 효율이 극대화된다.

치명적 단점: 워크로드 불균형 (Load Imbalance)

각 큐가 독립적이다 보니 문제가 생긴다. CPU 0은 일이 너무 많아 허덕이는데, CPU 1은 할 일이 없어 노는 상황이 발생할 수 있다. 즉 CPU 유휴 상태로 인한 성능저하가 발생한다.

5. 불균형의 해결책: 작업 훔치기 (Work Stealing)

MQMS의 불균형 문제를 해결하려면 결국 작업을 이동(Migration)시켜야 한다. 이때 사용되는 대표적인 기법이 작업 훔치기(Work Stealing) 이다.

동작: 할 일이 없는(소스) 큐가 바쁜 다른(타겟) 큐를 훔쳐본다. 타겟 큐가 자신보다 훨씬 바쁘다면 작업을 훔친다.
딜레마: 너무 자주 훔쳐보면 오버헤드가 커져서 성능을 갉아먹고, 너무 가끔 훔쳐보면 불균형이 해결되지 않는다. 적절한 간격을 찾는 것이 핵심!

6. 실제 세상의 스케줄러: 리눅스(Linux)의 진화

리눅스는 위 이론들을 실제 커널에 적용하며 치열하게 발전해왔다.

O(1) Scheduler (과거)

리눅스 초기에는 O(1) 스케줄러를 사용했다. 이름처럼 작업 선택에 걸리는 시간이 상수 시간인 것이 특징이었으며, 우선순위 기반의 멀티 큐 구조를 가진다. 인터랙티브한 프로세스에 보너스를 주는 복잡한 휴리스틱이 있는데, 관리를 어렵게 만든다.

CFS (Completely Fair Scheduler) - 현재의 표준

현재 리눅스의 기본 스케줄러인 CFS는 이름 그대로 ‘공정함’을 최우선으로 합니다.

가상 런타임 (vruntime): 프로세스마다 가상 실행 시간을 기록하여, 가장 적게 실행된 놈을 먼저 실행시켜준다. (Red-Black Tree 사용)
스케줄링 도메인 (Scheduling Domains): 멀티코어 최적화의 핵심으로 CFS는 단순히 CPU 0, 1로 나누는 것을 넘어, 하드웨어 토폴로지(Core, Socket, NUMA Node 등)를 계층적으로 묶어 도메인으로 관리한다.
- 같은 코어 내의 하이퍼쓰레드끼리는 자주 부하 분산을 해도 비용이 싸다.
- 하지만 NUMA 노드를 건너뛰는 작업 이동은 메모리 접근 비용이 매우 비싸므로, 정말 심각한 불균형일 때만 이동.
- 하드웨어 구조를 반영한 계층적 밸런싱을 통해 오버헤드를 최소화하고 성능을 최적화한다.

BFS (Brain Fuck Scheduler) / MuQSS

다시 단일 큐(SQMS)로 회귀하려는 시도이다. 코어 수가 아주 많지 않은(예: 8코어 이하) 데스크탑 환경에서는 복잡한 밸런싱 로직보다는 단순한 단일 큐가 반응성에는 더 유리할 수 있다는 철학이다. 이를 통해 락 오버헤드를 감수하더라도 낮은 레이턴시를 유지할 수 있다.

여담: 제작자인 Con Kolivas는 당시 기존 Linux 프로세스 스케줄러의 복잡성에 대한 불만을 표현하기 위해 이 이름을 선택했음.(CFS 휴리스틱 알고리즘에 불만이 많았는걸로 사료됨ㅋㅋ)

7. 최신 Linux 스케줄러

리눅스 커널 6.6 부터 EEVDF(Earliest Eligible Virtual Deadline First) 가 CFS를 밀어내고 표준 스케줄러로 자리잡았다.

EEVDF: “누가 더 급한가?”의 수학적 계산

CFS가 모든 프로세스에게 CPU를 ‘공평하게’ 나눠주는 데 집중했다면, EEVDF는 지연 시간(Latency) 최소화에 집중한다.

자격(Eligible): 프로세스가 원래 받아야 할 CPU 시간보다 적게 썼는지를 먼저 체크한다. 빚을 덜 진(적게 쓴) 놈에게만 CPU를 받을 ‘자격’을 준다.
마감일(Deadline): 자격이 있는 프로세스들 중, 요청한 작업량(Time slice)을 기준으로 가장 빨리 끝내야 하는 놈(Virtual Deadline이 가장 빠른 놈)을 먼저 선택한다.
결과: 이를 통해 오디오 편집이나 게임처럼 응답 속도가 중요한 작업들이 CFS 시절보다 훨씬 더 빠르게 CPU를 점유할 수 있게 된다.

sched_ext: 스케줄러도 ‘플러그인’처럼 갈아 끼우는 시대

리눅스 커널 6.12부터는 운영체제 역사상 가장 파격적인 변화 중 하나인 sched_ext (SCX) 가 도입되었다.

BPF의 마법: 커널 코드를 수정하거나 재빌드하지 않고도, 사용자 공간에서 BPF를 이용해 자신만의 스케줄링 로직을 동적으로 로드할 수 있다.
맞춤형 전략: 게임 성능에 올인한 BORE 스케줄러나, Rust 언어로 안전하게 작성된 scx_rustland 등을 상황에 맞춰 실시간으로 교체하며 사용할 수 있다.

실제 적용 사례: 단순히 연구용이 아니라, 이미 글로벌 테크 기업들은 이 기술로 눈에 보이는 성능 향상을 만들어내고 있습니다.
- Meta (서버 최적화), Valve Steam Deck (게이밍) (https://news.hada.io/topic?id=25293) (https://byteiota.com/meta-uses-steam-deck-linux-scheduler-on-servers-bpf-win/)
- CachyOS (데스크톱 최적화): 성능 특화 배포판인 CachyOS는 사용자가 버튼 하나로 게임 성능에 올인한 BORE나 Rust로 작성된 scx_rustland 스케줄러를 즉시 교체하며 쓸 수 있는 환경을 제공한다. (https://news.ycombinator.com/item?id=41056942)(https://wiki.cachyos.org/configuration/sched-ext/)

마치며: 정답은 없다, 트레이드오프만 있을 뿐

멀티프로세서 스케줄링은 복잡성, 효율성, 공정성, 확장성 사이의 선택이다.

SQMS는 구현이 쉽고 밸런싱이 좋지만 확장성이 떨어진다.
MQMS는 확장성과 캐시 효율이 좋지만 워크로드 밸런싱이 어렵다.
EEVDF와 sched_ext는 현대 하드웨어의 복잡성과 사용자의 다양한 요구사항을 해결하기 위해 ‘유연성’과 ‘정밀함’을 선택함.

리눅스 CFS에서 EEVDF로의 전환은 운영체제가 하드웨어의 발전 속도에 맞춰 얼마나 치열하게 진화하고 있는지를 보여주고 있다. 우리가 멀티코어 기기로 끊김 없이 멀티태스킹을 즐길 수 있는 것은, 보이지 않는 곳에서 마감일을 계산하고 코어를 배분하는 이 영리한 스케줄러들 덕분일 것이다.

참고: 이 글은 Operating Systems: Three Easy Pieces의 10장 Multiprocessor Scheduling (Advanced) 내용을 기반으로 재구성했습니다.

[OSTEP] 멀티프로세서 스케줄링