현대 OS의 스케줄링

이론적인 알고리즘을 넘어, 실제 운영체제가 어떻게 스케줄링을 구현하는지 살펴보겠습니다. 수천 개의 프로세스와 수십 개의 코어를 다루는 현대 OS의 스케줄러는, 교과서의 알고리즘을 그대로 구현한 것이 아니라 수십 년간의 실전 경험과 벤치마크를 통해 발전한 정교한 엔지니어링의 결과물입니다.

Linux CFS (Completely Fair Scheduler)

Linux 2.6.23(2007년)부터 기본 스케줄러로 사용되는 CFS(Completely Fair Scheduler)는 Ingo Molnár가 설계했습니다. 이름 그대로 완전히 공정한 스케줄링을 목표로 합니다. CFS의 철학은 이상적인 멀티태스킹 CPU를 소프트웨어로 근사하는 것입니다. 이상적인 CPU가 n개의 프로세스에게 각각 $\frac{1}{n}$의 속도로 동시에 실행해 준다면, 모든 프로세스가 정확히 같은 양의 CPU 시간을 받을 것입니다. CFS는 이 이상에 최대한 가깝게 동작합니다.

vruntime — 핵심 메커니즘

CFS의 핵심은 가상 실행 시간(vruntime)입니다. 각 프로세스가 CPU를 사용할 때마다 vruntime이 증가합니다. 스케줄러는 항상 vruntime이 가장 작은 프로세스(CPU를 가장 적게 사용한 프로세스)에게 CPU를 줍니다.

모든 프로세스의 우선순위가 같다면, 모든 프로세스의 vruntime이 같은 속도로 증가하여 완전히 공정합니다. 그런데 우선순위가 다르면? CFS는 vruntime의 증가 속도에 가중치를 적용합니다.

높은 우선순위(낮은 nice 값) 프로세스: vruntime이 천천히 증가 → 결과적으로 더 많은 CPU 시간을 받음

낮은 우선순위(높은 nice 값) 프로세스: vruntime이 빠르게 증가 → 결과적으로 더 적은 CPU 시간을 받음

구체적으로, nice 값이 1 차이 나면 CPU 시간 배분이 약 1.25배(약 25%) 차이납니다. nice 0인 프로세스가 10ms를 받으면, nice 1인 프로세스는 약 8ms를 받습니다. nice -20인 프로세스는 nice 19인 프로세스보다 약 88,000배 더 많은 CPU 시간을 받습니다.

레드-블랙 트리

CFS는 모든 실행 가능한 프로세스를 vruntime을 키로 하는 레드-블랙 트리(Red-Black Tree)에 저장합니다. 레드-블랙 트리는 자기 균형 이진 탐색 트리로, 삽입·삭제·검색 모두 $O(\log n)$입니다.

스케줄러가 다음에 실행할 프로세스를 선택할 때, 트리의 가장 왼쪽 노드(최소 vruntime)를 $O(1)$로 가져옵니다(캐시해 두므로). 프로세스가 CPU를 받아 실행되면 vruntime이 증가하고, 트리에서 오른쪽으로 이동합니다. 결국 다른 프로세스가 최소 vruntime을 가지게 되고, 그 프로세스가 다음에 실행됩니다.

CFS의 타임 슬라이스

CFS에는 고정된 타임 퀀텀이 없습니다. 대신 목표 지연 시간(target latency)이라는 개념을 사용합니다. 이것은 모든 실행 가능한 프로세스가 최소 한 번은 CPU를 사용하는 시간 간격입니다. 기본값은 6ms(프로세스 수가 적을 때)입니다.

목표 지연 시간을 프로세스 수로 나누면 각 프로세스의 타임 슬라이스가 됩니다. 프로세스가 3개면 각각 2ms, 6개면 각각 1ms입니다. 프로세스가 매우 많으면 타임 슬라이스가 너무 작아져 컨텍스트 스위칭 오버헤드가 커지므로, 최소 단위(min_granularity)가 설정됩니다(기본 0.75ms).

CFS 이후: EEVDF (Linux 6.6+)

Linux 6.6(2023년)부터, CFS가 EEVDF(Earliest Eligible Virtual Deadline First)로 교체되었습니다. CFS의 기본 철학은 유지하면서, 대기 시간이 긴 프로세스에게 더 빠르게 CPU를 줘서 지연 시간을 줄이는 개선입니다.

Windows 스케줄러

Windows는 우선순위 기반 선점형 스케줄링을 사용합니다. 0~31까지 32단계의 우선순위가 있으며, 항상 실행 가능한 가장 높은 우선순위의 스레드가 실행됩니다. 같은 우선순위 내에서는 라운드 로빈으로 동작합니다.

우선순위 구간:

Windows는 가변 우선순위 클래스(1~15)에서 프로세스의 행동에 따라 우선순위를 동적으로 조정합니다.

포그라운드 부스트: 사용자가 현재 사용 중인 창(포그라운드)의 프로세스에 더 큰 타임 퀀텀을 줍니다. 기본 타임 퀀텀의 3배까지 증가합니다. 사용자가 보고 있는 앱이 더 부드럽게 동작합니다.

I/O 완료 부스트: I/O 작업이 완료된 스레드의 우선순위를 일시적으로 높입니다. 키보드 I/O는 +6, 디스크 I/O는 +1 등 I/O 유형에 따라 다릅니다. I/O를 기다리던 대화형 프로세스가 빠르게 응답할 수 있게 합니다.

기아 방지: Windows는 3~4초 이상 CPU를 받지 못한 스레드를 감지하면, 일시적으로 우선순위를 15로 높여줍니다. 2번의 타임 퀀텀 동안 실행하고 원래 우선순위로 복귀합니다.

멀티코어 스케줄링

현대 시스템은 4~128개의 코어를 가집니다. 멀티코어 환경에서 스케줄링은 어떤 프로세스를 실행할 것인가에 더해 어떤 코어에서 실행할 것인가라는 추가적인 결정을 해야 합니다.

프로세서 친화성 (Processor Affinity)

프로세스를 같은 코어에서 계속 실행하는 것이 유리합니다. 코어를 바꾸면 이전 코어의 L1/L2 캐시가 무효화되고, 새 코어에서 캐시를 다시 채워야 합니다(cold cache). 이것을 캐시 마이그레이션 비용이라 합니다.

소프트 친화성(Soft Affinity): OS가 가능하면 같은 코어를 사용하지만, 부하 불균형이 심하면 다른 코어로 이동합니다. Linux CFS의 기본 동작입니다.

하드 친화성(Hard Affinity): 프로세스를 특정 코어에 완전히 고정합니다. 캐시 성능이 매우 중요한 실시간 또는 고성능 애플리케이션에서 사용합니다.

# 프로세스를 CPU 0, 1에 고정
taskset -c 0,1 ./my_program

# 실행 중인 프로세스의 친화성 변경
taskset -cp 0-3 1234

# NUMA 환경에서 메모리 노드 지정
numactl --cpunodebind=0 --membind=0 ./memory_intensive_app

부하 분산 (Load Balancing)

모든 코어가 균등하게 일해야 시스템 처리량이 극대화됩니다. 한 코어에 프로세스가 몰려 있고 다른 코어가 놀고 있으면 비효율적입니다.

Linux CFS는 각 코어마다 독립적인 런 큐(Run Queue)를 유지합니다. 그리고 주기적으로(~4ms마다, 또는 코어가 유휴 상태가 될 때) 부하 분산(Load Balancing)을 수행합니다.

Push 마이그레이션: 과부하 코어에서 유휴 코어로 프로세스를 밀어냅니다.

Pull 마이그레이션: 유휴 코어가 바쁜 코어에서 프로세스를 가져옵니다.

부하 분산과 프로세서 친화성은 상충합니다. 부하를 분산하려면 프로세스를 다른 코어로 옮겨야 하는데, 그러면 캐시가 무효화됩니다. CFS는 스케줄링 도메인(Scheduling Domain) 개념으로 이 균형을 유지합니다. 같은 물리 코어(하이퍼스레딩)나 같은 소켓(L3 캐시 공유) 내에서 먼저 마이그레이션을 시도하고, 다른 소켓으로의 마이그레이션은 불균형이 클 때만 수행합니다.

NUMA 인식 스케줄링

NUMA(Non-Uniform Memory Access) 환경에서는 각 CPU 소켓이 자신의 로컬 메모리를 가집니다. 다른 소켓의 메모리에 접근하면 2~3배 느립니다. 스케줄러는 프로세스의 메모리가 어느 NUMA 노드에 있는지를 고려하여, 가능하면 같은 노드의 코어에서 실행합니다.

개발자가 알아야 할 스케줄링 지식

nice 값으로 우선순위 조절

Linux에서 nice 값(-20~+19)으로 프로세스의 상대적 우선순위를 설정합니다. 기본값은 0이며, 값이 낮을수록 높은 우선순위입니다. nice라는 이름은 다른 프로세스에게 양보(nice)하는 정도에서 유래합니다. nice 값이 높으면 다른 프로세스에게 더 nice하게 CPU를 양보합니다.

# 낮은 우선순위로 백그라운드 작업 실행
nice -n 10 ./background_task

# 높은 우선순위 (root 권한 필요)
sudo nice -n -5 ./important_task

# 실행 중인 프로세스 우선순위 변경
renice -n -5 -p 1234

# 전체 사용자의 프로세스 우선순위 변경
renice -n 10 -u username

cgroups로 자원 제한

nice보다 정밀한 제어가 필요하면 cgroups(Control Groups)를 사용합니다. Docker와 Kubernetes가 내부적으로 사용하는 메커니즘입니다.

# cgroup v2 기준
echo "50000 100000" > /sys/fs/cgroup/my_app/cpu.max
# 50000/100000 = 50%의 CPU 시간

스케줄링 문제 진단

프로세스가 느린 이유가 스케줄링 때문인지 확인하는 방법:

# 프로세스의 자발적/비자발적 컨텍스트 스위칭 수 확인
cat /proc/1234/status | grep ctxt

# perf로 스케줄링 이벤트 추적
perf sched record -p 1234 -- sleep 5
perf sched latency

# 실행 큐 길이 확인 (r 열)
vmstat 1

vmstat의 r 열이 CPU 코어 수보다 지속적으로 크면, CPU가 부족한 것입니다. 프로세스를 줄이거나 코어를 추가해야 합니다.

다음 장에서는 여러 스레드가 공유 자원에 동시에 접근할 때 발생하는 동기화 문제와 그 해결 방법을 다루겠습니다.