현대 OS의 스케줄링

이론적인 알고리즘을 넘어, 실제 운영체제가 어떻게 스케줄링을 구현하는지 살펴보겠습니다.

수천 개의 프로세스와 수십 개의 코어를 다루는 현대 OS의 스케줄러는, 교과서의 알고리즘을 그대로 구현한 것이 아니라 수십 년간의 실전 경험과 벤치마크를 통해 발전한 정교한 엔지니어링의 결과물입니다.

Linux CFS (Completely Fair Scheduler)

Linux 2.6.23(2007년)에 일반 작업용으로 도입된 CFS(Completely Fair Scheduler)는 Ingo Molnár가 설계했습니다.

이 절의 CFS 설명은 기존 선택 모델을 다룹니다. Linux 6.6 이후의 EEVDF 선택 방식은 뒤에서 구분합니다.

CFS의 철학은 이상적인 멀티태스킹 CPU를 소프트웨어로 근사하는 것입니다.

이상적인 CPU가 n개의 프로세스를 각각 $\frac{1}{n}$의 속도로 동시에 실행해 준다면, 모든 프로세스가 정확히 같은 양의 CPU 시간을 받을 것입니다.

CFS는 이 이상에 최대한 가깝게 동작합니다.

vruntime — 핵심 메커니즘

CFS의 핵심은 가상 실행 시간(vruntime)입니다.

각 프로세스가 CPU를 사용할 때마다 vruntime이 증가합니다.

CFS의 기본 선택 기준은 실행 가능한 공정 클래스 엔티티 중 가장 작은 vruntime입니다. 가중치를 적용한 값이므로 실제 CPU 사용 시간이 가장 짧다는 뜻과는 다를 수 있습니다.

같은 가중치라면 실행한 시간에 같은 비율로 vruntime이 증가하여 CPU 몫을 비슷하게 맞춥니다. 임의의 짧은 측정 구간에서 정확히 같은 시간을 준다는 보장은 아닙니다.

그런데 우선순위가 다르면?

CFS는 vruntime의 증가 속도에 가중치를 적용합니다.

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

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

같은 공정 스케줄링 그룹에서 계속 경쟁하는 작업을 단순화하면, 인접 nice 단계의 가중치 비율은 약 1.25배입니다. 실제 배분은 runnable 상태, cgroup, CPU 배치 등의 영향도 받습니다.

nice 0인 프로세스가 10ms를 받으면, nice 1인 프로세스는 약 8ms를 받습니다.

Linux 6.6 소스의 nice −20과 19 가중치는 각각 88761과 15로, 비율은 약 5,917배입니다. 88761이라는 가중치 자체를 CPU 시간의 배수로 읽으면 안 됩니다.

레드-블랙 트리

기존 CFS의 런 큐는 대기 중인 공정 스케줄링 엔티티를 vruntime 기준의 레드-블랙 트리(Red-Black Tree)로 관리합니다. 현재 실행 엔티티는 별도로 추적하므로 모든 시스템 태스크가 한 트리에 동시에 들어 있는 모델은 아닙니다.

레드-블랙 트리는 자기 균형 이진 탐색 트리로, 삽입·삭제·검색 모두 $O(\log n)$입니다.

스케줄러가 다음에 실행할 프로세스를 선택할 때, 트리의 가장 왼쪽 노드(최소 vruntime)를 $O(1)$로 가져옵니다(캐시해 두므로).

실행하며 vruntime을 갱신한 엔티티가 다시 큐에 들어가면 새 값에 맞는 위치에 배치됩니다.

결국 다른 프로세스가 최소 vruntime을 가지게 되고, 그 프로세스가 다음에 실행됩니다.

CFS의 타임 슬라이스

CFS에는 고정된 타임 퀀텀이 없습니다.

대신 목표 지연 시간(target latency)이라는 개념을 사용합니다.

이것은 모든 실행 가능한 프로세스가 최소 한 번은 CPU를 사용하는 시간 간격입니다.

버전·설정에 따라 값이 달라지므로 여기서는 목표 간격을 6ms로 놓은 단순 예를 사용합니다.

동일 가중치이며 최소 실행 단위에 걸리지 않는 예에서는 목표 간격을 작업 수로 나누어 몫을 설명할 수 있습니다.

프로세스가 3개면 각각 2ms, 6개면 각각 1ms입니다.

작업이 많아질 때는 최소 실행 단위를 고려하여 문맥 전환이 지나치게 잦아지는 것을 막습니다. 예전 CFS의 튜닝 값과 현재 커널의 base_slice_ns 등을 같은 고정 기본값으로 취급하지 않습니다.

CFS 이후: EEVDF (Linux 6.6+)

Linux 6.6부터 공정 스케줄러의 선택 방식이 EEVDF(Earliest Eligible Virtual Deadline First)로 전환되기 시작했습니다. CPU 몫을 추적하는 기반을 유지하면서, 받을 몫이 남은 eligible 작업 중 가상 데드라인이 가장 이른 작업을 선택합니다.

다음은 같은 가중치의 세 작업과 평균 가상 실행 시간 V=20을 놓은 설명용 상태입니다. lag = V − vruntime으로 단순화하고 서로 다른 실행 요청 길이에 따른 가상 데드라인(VD)을 비교합니다. 수치는 실제 커널 실행 기록이나 현실의 마감 시각이 아닙니다.

A의 vruntime=18, VD=30이고 B는 19, 25, C는 23, 24입니다. 기존 CFS의 기본 선택에서는 최소 vruntime인 A가 앞섭니다. EEVDF 예에서는 먼저 lag를 계산하여 A=+2, B=+1, C=−3을 얻고, eligible인 A·B만 남긴 다음 VD 30과 25를 비교하여 B를 고릅니다. C의 VD=24만 보고 가장 급한 후보라고 고르면 먼저 수행해야 하는 자격 판단을 빠뜨립니다. 커널의 CFS 설계 문서와 EEVDF 설명의 기준을 단순화한 예입니다.

독립 확인: 같은 가중치·V=20을 유지하면서 A의 vruntime/VD가 18/30, B가 19/25, C가 20/24라면 EEVDF의 자격 판단과 최종 선택은 어떻게 바뀔까요?

Windows 스케줄러

Windows는 우선순위 기반 선점형 스케줄링을 사용합니다.

0~31까지 32단계의 우선순위가 있으며, 항상 실행 가능한 가장 높은 우선순위의 스레드가 실행됩니다.

같은 우선순위 내에서는 라운드 로빈으로 동작합니다.

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

포그라운드·입력 우대: 현재 창과 입력을 처리하는 작업의 반응성을 높이도록 우선순위 등을 조정합니다.

구체적인 퀀텀 배수는 Windows 버전과 시스템 설정에 따라 달라집니다.

사용자가 보고 있는 앱이 더 부드럽게 동작합니다.

I/O 완료 부스트: I/O 작업이 완료된 스레드의 우선순위를 일시적으로 높입니다.

부스트는 I/O나 입력 등 대기 해제 이유에 따라 달라지며, 모든 버전에 동일한 증가 수치를 적용할 수는 없습니다.

I/O를 기다리던 대화형 프로세스가 빠르게 응답할 수 있게 합니다.

동적 조정: Windows는 반응성과 기아 완화를 위해 가변 우선순위를 조정합니다. 부스트된 우선순위는 실행 후 기본 우선순위로 내려오며, 16~31의 실시간 기본 우선순위에는 이 부스트를 적용하지 않습니다. 내부 시간 기준을 모든 버전의 API 보장으로 취급하지 않습니다.

멀티코어 스케줄링

시스템마다 코어 수와 캐시·메모리 구조가 다릅니다.

멀티코어 환경에서 스케줄링은 어떤 프로세스를 실행할 것인가에 더해 어떤 코어에서 실행할 것인가라는 추가적인 결정을 해야 합니다.

프로세서 친화성 (Processor Affinity)

프로세스를 같은 코어에서 계속 실행하는 것이 유리합니다.

코어를 바꾸면 새 코어에 필요한 데이터가 없어 캐시를 다시 채우는 비용이 생길 수 있습니다. 이동 자체가 이전 코어의 L1/L2를 전부 무효화하는 것은 아닙니다.

이것을 캐시 마이그레이션 비용이라 합니다.

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

Linux CFS의 기본 동작입니다.

하드 친화성(Hard Affinity): 태스크가 실행될 수 있는 CPU 집합을 제한합니다. 여러 CPU를 지정하면 그 집합 안에서 이동할 수 있습니다.

캐시 성능이 매우 중요한 실시간 또는 고성능 애플리케이션에서 사용합니다.

# 프로세스를 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)

부하를 여러 코어에 나누면 처리량이 좋아질 수 있지만, CPU 성능 차이·공유 캐시·전력 비용 때문에 균등 분배가 항상 최선은 아닙니다.

한 코어에 프로세스가 몰려 있고 다른 코어가 놀고 있으면 비효율적입니다.

Linux CFS는 각 코어마다 독립적인 런 큐(Run Queue)를 유지합니다.

스케줄링 도메인의 주기적 검사나 CPU가 유휴 상태가 되는 계기 등에 부하 분산(Load Balancing)을 수행합니다. 간격은 고정 4ms가 아닙니다.

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

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

부하 분산과 프로세서 친화성은 상충합니다.

부하를 분산하려면 프로세스를 다른 코어로 옮겨야 하는데, 그러면 새 코어의 캐시 적중률이 낮아질 수 있습니다.

CFS는 스케줄링 도메인(Scheduling Domain) 개념으로 이 균형을 유지합니다.

같은 물리 코어(하이퍼스레딩)나 같은 소켓(L3 캐시 공유) 내에서 먼저 마이그레이션을 시도하고, 다른 소켓으로의 마이그레이션은 불균형이 클 때만 수행합니다.

NUMA 인식 스케줄링

NUMA(Non-Uniform Memory Access) 환경에서는 CPU와 메모리의 위치에 따라 접근 비용이 달라집니다. 소켓별 로컬 메모리는 대표적인 구성이며 소켓과 NUMA 노드가 항상 일대일인 것은 아닙니다.

원격 노드 메모리 접근에는 추가 비용이 생길 수 있으며, 배수는 하드웨어와 접근 패턴에 따라 달라집니다.

스케줄러는 프로세스의 메모리가 어느 NUMA 노드에 있는지를 고려하여, 가능하면 같은 노드의 코어에서 실행합니다.

현대 스케줄러의 성능 문제는 CPU 시간만 보지 않고 캐시, 런 큐, 메모리 위치까지 함께 판단해야 합니다.

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

nice 값으로 우선순위 조절

Linux에서 nice 값(-20~+19)으로 프로세스의 상대적 우선순위를 설정합니다.

기본값은 0이며, 값이 낮을수록 높은 우선순위입니다.

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

위 명령의 PID·CPU 번호·사용자는 예시입니다. taskset -cp는 지정 태스크의 허용 집합을 바꾸며, 기존 멀티스레드 프로세스의 모든 스레드에 자동으로 적용된다고 가정하지 않습니다. CPU 가용성·cpuset·권한과 배치 전후 측정이 필요합니다.

cgroups로 자원 제한

nice보다 정밀한 제어가 필요하면 cgroups(Control Groups)를 사용합니다.

Docker와 Kubernetes가 내부적으로 사용하는 메커니즘입니다.

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

50000 100000은 그룹 전체가 100ms마다 합계 50ms의 CPU 시간을 쓰는 상한으로, 논리 CPU 하나의 50%에 해당합니다. 전체 머신의 50%나 성능·응답 시간 보장은 아닙니다. cgroup 생성, CPU 컨트롤러 활성화, 작업 배치와 쓰기 권한은 별도로 준비해야 합니다.

cgroup v2의 cpu.max 설명은 기간별 그룹 CPU 사용 상한을 규정합니다. 이 예의 CPU 컨트롤러가 활성화되어 있고 두 사용 가능한 CPU에서 해당 그룹에 속한 일반 공정 스케줄링 클래스의 두 작업만 계속 실행하며 버스트·추가 제한·비용을 무시한다고 가정하면, 합계 50ms의 예산을 약 25ms의 벽시계 시간에 사용할 수 있습니다. 이는 두 작업 각각에 50ms를 준다는 뜻이 아니며, 나머지 기간의 스로틀링과 실제 배분은 실행 상태와 설정의 영향을 받습니다.

독립 확인: 같은 조건에서 cpu.max가 30000 100000이고 두 작업이 각각 다른 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 사용률·친화성·할당량·스케줄링 지연을 함께 확인해야 하며, 이 값만으로 코어 증설이라는 결론을 내릴 수는 없습니다. 이 절은 진단 명령의 사용 예이며 실제 측정 결과를 제시하지 않습니다.

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