[OS 2편] CPU 스케줄링과 big.LITTLE 구조

유정빈·2026년 5월 31일

CPU 스케줄링의 본질은 간단합니다.

제한된 자원인 CPU 코어를 여러 프로세스에 어떻게 효율적이고 공평하게 나누어 줄 것인지에 대한 문제입니다.

이번 글에서는 스케줄링의 기본 개념부터 big.LITTLE 구조를 정리한 내용을 공유합니다.

0. CPU 스케줄링의 핵심

운영체제는 한 번에 여러 작업을 동시에 실행하는 것처럼 보이게 하기 위해 CPU 코어를 아주 짧은 시간 단위로 쪼개어 프로세스들에게 나누어 줍니다.

어떤 기준으로 이 자원을 배분할 것인지가 스케줄러의 핵심 설계 과제입니다.

대표적인 전통 스케줄링 알고리즘들의 특징과 한계점은 다음과 같습니다.

FCFS (First-Come, First-Served)

가장 단순하게 먼저 도착한 순서대로 CPU를 할당하는 방식입니다.

하지만 아래 다이어그램의 FCFS 예시처럼, 실행 시간이 100ms인 무거운 작업 A가 먼저 도달하고 5ms밖에 걸리지 않는 가벼운 작업 B, C가 뒤이어 도착할 경우 심각한 비효율이 발생합니다.

B와 C는 단 5ms 동안 실행되기 위해 A가 끝날 때까지 100ms 이상을 대기해야 합니다.
이를 호위 효과(Convoy Effect)라고 부릅니다.

이 경우 평균 대기 시간(Average Waiting Time)은 다음과 같이 계산됩니다.

$\text{평균 대기 시간} = \frac{0\text{ms} (A) + 100\text{ms} (B) + 105\text{ms} (C)}{3} \approx 68.3\text{ms}$

단 5ms짜리 작업을 처리하기 위해 시스템 전체가 상당한 대기 지연을 겪는 구조적인 문제를 안고 있습니다.

SJF (Shortest Job First)

FCFS의 호위 효과를 해결하기 위해, 대기열 중 실행 시간이 가장 짧은 작업을 우선 선출하는 방식입니다.

다이어그램의 SJF 예시를 보면, 스케줄러는 가장 짧은 B(5ms)와 C(5ms)를 먼저 실행하고, 가장 긴 A(100ms)를 맨 마지막에 배치합니다.

이 경우 평균 대기 시간은 획기적으로 낮아집니다.

$\text{평균 대기 시간} = \frac{0\text{ms} (B) + 5\text{ms} (C) + 10\text{ms} (A)}{3} = 5\text{ms}$

SJF는 평균 대기 시간을 최소화하는 수학적 최적 모델(Optimal)입니다. 그러나 실제 시스템에 적용하기에는 두 가지 주요 구조적 한계가 있습니다.

실행 시간 예측 불가능:
실제 운영체제 환경에서는 새로운 프로세스가 실행될 때 이 프로세스가 완료될 때까지 몇 ms 동안 작동할지 미리 알 방법이 없습니다.
기아 상태(Starvation):
가벼운 짧은 작업이 계속해서 끊임없이 들어오면, 무겁고 긴 작업 A는 대기열 맨 뒤로 밀려나 영원히 CPU를 할당받지 못하게 됩니다.

Round Robin (RR)

SJF의 예측 불가능성과 기아 상태 문제를 극복하기 위해 도입된 시분할(Time-Sharing) 스케줄링 방식입니다.

프로세스를 끝까지 실행하는 대신, 시간 할당량(Time Slice)이라는 작은 시간 단위로 쪼개어 프로세스를 번갈아 가며 실행합니다.

다이어그램의 RR 예시(시간 할당량 = 20ms)를 보면 다음과 같이 실행됩니다.

먼저 A가 20ms 동안 실행된 뒤 타임 아웃으로 대기열 뒤로 밀려납니다.
이어서 B가 실행되어 5ms 만에 작업을 완수하고 바로 종료됩니다.
다음으로 C가 실행되어 5ms 만에 종료됩니다.
마지막으로 남은 A의 80ms 분량이 끝까지 처리됩니다.

이 방식 덕분에 가벼운 B와 C는 각각 25ms, 30ms 만에 작업을 마칠 수 있어 기아 상태가 방지되고 응답 속도(Response Time)가 대폭 개선됩니다.

하지만 모든 작업을 시분할로 끊어 실행하면 프로세스가 완료되는 시점이 뒤로 밀려 평균 반환 시간(Average Turnaround Time) 관점에서는 FCFS나 SJF보다 오히려 불리해지는 단점이 있습니다.

예를 들어, 동일하게 10ms가 걸리는 작업 3개가 동시에 시작될 때, SJF는 10ms, 20ms, 30ms에 차례로 완료되어 평균 반환 시간이 20ms인 반면, 1ms 타임 슬라이스의 RR은 모두 28~30ms 시점에 완료되어 평균 반환 시간이 거의 30ms에 수렴합니다.

즉, 응답성(Response)을 위해 반환 성능(Turnaround)을 희생하는 명확한 트레이드오프가 존재합니다.

다만 시간 할당량 크기 설정에 대한 트레이드오프가 존재합니다. 할당량이 너무 크면 FCFS와 다름없어지고, 너무 작으면 잦은 문맥 교환(Context Switch) 오버헤드로 인해 시스템이 마비됩니다.

MLFQ (Multi-Level Feedback Queue)

SJF처럼 "작업 시간을 미리 알 수 없으면서도 짧은 작업의 응답 속도를 극대화하고", RR처럼 "공평하게 자원을 분배하겠다"는 목적을 달성하기 위해 고안된 현대 지능형 스케줄러입니다.

MLFQ는 우선순위가 다른 여러 개의 대기 큐(Q1, Q2, Q3)를 두고 아래와 같은 피드백 규칙으로 동작합니다.

규칙 1: 새로운 태스크는 무조건 가장 높은 우선순위 큐(Q1)에 먼저 진입합니다.
규칙 2: 각 큐는 고유한 시간 할당량을 가집니다. (높은 큐일수록 타임 슬라이스가 짧음)
규칙 3: 프로세스가 자신에게 할당된 시간 슬라이스를 모두 소진할 때까지 CPU를 양도하지 않으면(CPU 집중형 작업 A), 한 단계 낮은 우선순위 큐로 강등(Demoted)됩니다.
규칙 4: 프로세스가 시간 슬라이스가 끝나기 전에 I/O 요청 등으로 CPU를 스스로 내려놓으면(대화형 작업 B, C), 우선순위를 유지하며 고우선순위 큐(Q1)에 잔류합니다.

다이어그램의 MLFQ 구조처럼, 잠시 들어와 CPU를 양도하는 인터랙티브 작업 B, C는 Q1에 남아 최상의 반응 속도를 얻고, 무한 연산을 돌리는 작업 A는 Q1에서 Q2를 거쳐 결국 최하위 큐인 Q3(FCFS 방식)까지 강등당해 구동됩니다. 스케줄러가 과거의 이력을 바탕으로 프로세스의 성격을 피드백 받아 학습하는 방식입니다.

그러나 이 기본 규칙들만 적용하면 두 가지 주요 문제가 발생할 수 있습니다.

기아 상태(Starvation):
새로운 짧은 대화형 태스크가 계속해서 큐에 유입되면, 하위 큐로 한 번 강등된 무거운 연산 태스크 A는 영원히 CPU를 할당받지 못하는 기아가 생깁니다.
스케줄러 무력화(Gaming the scheduler):
어떤 프로세스가 의도적으로 시간 할당량의 99%만 채워 동작한 후 끝나기 직전에 I/O 요청을 일으켜 스스로 CPU를 내려놓으면, 스케줄러는 이를 대화형 태스크로 취급하여 최상위 큐(Q1)에 계속 잔류시킵니다. 이 꼼수를 이용해 특정 프로세스가 시스템 자원을 독점할 수 있게 됩니다.

이러한 한계를 방지하기 위해 현대적인 MLFQ는 다음 보완 규칙을 추가로 적용합니다.

규칙 5 (Priority Boost): 기아 상태를 예방하기 위해, 일정 시간 주기 $S$ 가 흐르면 시스템 내 모든 프로세스를 가장 높은 우선순위 큐(Q1)로 일제히 승격(Aging)시킵니다.
규칙 6 (Time Accounting): 악용을 차단하기 위해, 프로세스가 CPU를 양도할 때 누적 실행 시간을 기록해 둡니다. 실행을 여러 번 쪼개서 수행하더라도 해당 큐 등급에 할당된 총 시간 슬라이스를 모두 채워 소진하면 예외 없이 하위 큐로 강등시킵니다.

1. CFS (Completely Fair Scheduler)

한줄 요약: 누적 실행 시간(vruntime)이 가장 적은 태스크를 먼저 실행하여 모든 프로세스에 CPU 자원을 완전히 공평하게 배분하는 스케줄러입니다.

리눅스 커널은 2.6.23 버전부터 기존의 O(1) 스케줄러를 대체하는 CFS (Completely Fair Scheduler)를 도입했습니다.

기존 스케줄러는 사용자와 실시간으로 상호작용하는 대화형 프로세스를 판별하기 위해 복잡한 예측 연산(휴리스틱)을 사용했으나, 간혹 예측에 실패하면 사운드가 튀거나 화면이 버벅거리는 단점이 있었습니다.

CFS는 이러한 예측 대신 "모든 프로세스에 완전히 공평하게 가상의 CPU 자원을 나누어 주겠다"는 직관적인 개념을 도입했습니다. 이를 실현하기 위해 설계한 기준 지표가 바로 가상 실행 시간(vruntime, Virtual Runtime)입니다.

가상 실행 시간(vruntime)은 프로세스가 실제로 CPU를 사용한 물리적 시간에 가중치를 부여하여 계산된 논리적 지표입니다.

우선순위가 높은 프로세스일수록 가상 시간의 증가 속도가 느리게 설정되어, 결과적으로 스케줄러가 '가장 적게 실행된(vruntime이 가장 낮은) 프로세스'를 다음 실행 기회로 지속 선택하게 만드는 누적 기록계 역할을 합니다.

우선순위와 가중치(Weight)의 관계

리눅스는 프로세스의 우선순위(nice 값)에 따라 CPU 자원을 차등 배분하기 위해 수학적 중요도인 가중치(Weight) 개념을 사용합니다. 기준이 되는 nice 0에는 1024라는 기본 가중치가 부여되며, 우선순위가 높을수록 가중치 값이 커지고, 낮을수록 작아집니다. (예: nice 10은 가중치가 110으로 감쇄합니다.)

리눅스 커널은 nice 값이 1단계 변할 때마다 가중치가 약 1.25배씩 조절되도록 설계하여 우선순위 간의 비례 배분을 완성했습니다.

vruntime의 계산 방식

프로세스가 실제로 CPU를 사용했을 때, 가상 실행 시간(vruntime)은 다음과 같은 비례 공식으로 계산되어 누적됩니다.

새 가상 시간 = 기존 가상 시간 + (실제 실행 시간 × (기본 가중치 ÷ 나의 가중치))

가상 시간 계산 예시 (실제 실행 시간이 10ms일 때)

우선순위가 높은 Task A (nice 0, 가중치 1024):
새 가상 시간 = 기존 + 10ms × (1024 ÷ 1024) = 기존 + 10ms (실제 실행 시간과 동일하게 가상 시간 증가)

우선순위가 낮은 Task B (nice 10, 가중치 110):
새 가상 시간 = 기존 + 10ms × (1024 ÷ 110) = 기존 + 93ms (가상 시간이 실제 실행 시간보다 약 9.3배 빠르게 누적)

결과: 가상 시간이 빠르게 누적된 Task B는 스케줄러에 의해 "자원을 이미 충분히 할당받은 상태"로 분류되어 다음 실행 순서에서 뒤로 밀려납니다.

CFS의 핵심 난제 : 새로 깨어난 태스크의 가상 시간 보정

여기서 한 가지 예외 상황이 발생합니다.

만약 어떤 프로세스가 파일 다운로드를 걸어놓고 1시간 동안 아무런 일도 하지 않고 잠들어(Sleep) 있었다면, 이 프로세스의 vruntime은 1시간 전 수준에서 멈춰있을 것입니다.

그동안 CPU에서 작동하던 다른 태스크들의 vruntime은 계속 증가해 큰 값을 가지고 있습니다. 이 상태에서 잠들었던 프로세스가 깨어나면, 스케줄러가 보기에 가상 시간이 너무 작으므로 독점 실행 권한을 부여하게 됩니다. 결과적으로 다른 모든 태스크를 기아 상태로 몰아넣은 채 본인의 가상 시간이 다른 태스크들을 따라잡을 때까지 CPU를 혼자서만 계속 차지할 위험이 있습니다.

CFS는 이를 방지하기 위해 vruntime 보정(Normalization) 기법을 사용합니다. 잠들었다가 깨어난 태스크나 새로 생성된 태스크의 vruntime은 다음 공식을 통해 대기열 내 최소 가상 시간 근처로 강제 동기화됩니다.

새 가상 시간 = max(기존 가상 시간, 현재 대기열의 최소 가상 시간 - 약간의 혜택 시간)

여기서 약간의 혜택 시간은 깨어난 태스크가 오랫동안 대기한 대가로 약간의 반응성 이득(우선 실행 기회)을 얻을 수 있도록 보정해 주는 최소한의 지연시간 상수입니다.

이 보정 메커니즘 덕분에 CFS는 특정 태스크가 시스템 전체의 실행권을 독점하는 우회 시도를 원천 차단하고 공평성을 유지합니다.

물리적 타임 슬라이스의 동적 결정

CFS는 기존 Round Robin처럼 모든 태스크에 동일하게 고정된 타임 슬라이스를 주지 않으며, 현재 실행 대기열에 있는 태스크들의 우선순위 가중치 비율에 따라 매번 물리적인 타임 슬라이스 크기를 동적으로 결정합니다.

이때 스케줄러의 동작 기준이 되는 두 가지 핵심 sysctl 파라미터는 다음과 같습니다.

목표 주기 (sysctl_sched_latency):
대기열의 모든 태스크가 적어도 한 번씩은 CPU를 얻어야 하는 총 목표 시간입니다. (예: 기본 24ms)
최소 실행 단위 (sysctl_sched_min_granularity):
태스크가 한 번 선출되었을 때 보장받는 최소한의 실행 시간입니다. (예: 기본 3ms) 잦은 문맥 교환으로 인한 과도한 오버헤드를 막는 방어선 역할을 합니다.

각 태스크가 나누어 가지는 물리적인 실행 시간(타임 슬라이스)은 다음과 같은 비율 공식으로 계산됩니다.

나의 실행 시간(Time Slice) = 전체 목표 주기 × (나의 가중치 ÷ 대기열 모든 가중치의 합)

타임 슬라이스 계산 예시 (목표 주기 24ms에 Task A, B가 대기 중일 때)

대기열 가중치 합 = 1024(Task A, nice 0) + 110(Task B, nice 10) = 1134

Task A의 실행 시간: 24ms × (1024 ÷ 1134) ≈ 21.6ms (가중치 비율에 따라 대부분의 목표 주기 점유)

Task B의 실행 시간: 24ms × (110 ÷ 1134) ≈ 2.4ms (가중치 비율에 따라 최소한의 실행 시간만 점유)

만약 동시에 실행되려는 태스크 수가 급격히 늘어나 계산된 실행 시간이 최소 실행 단위(3ms)보다 작아지게 되면, 스케줄러는 시스템 붕괴를 막기 위해 타임 슬라이스를 최소 실행 단위 값으로 하한 고정합니다. 이 경우 전체 스케줄링 주기(목표 주기)는 태스크 수에 비례하여 자동으로 늘어나게 됩니다.

예를 들어, 동일 가중치를 가진 태스크가 10개로 증가하면 원래 비례 배분상으로는 2.4ms가 계산되어야 하지만, 하한선인 3ms씩 강제 할당되어 총 주기가 30ms로 자동 연장되며 실행 안정성을 유지합니다.

Red-Black Tree 자료구조 활용

CFS는 대기 중인 프로세스들을 효율적으로 관리하기 위해 자가 균형 이진 탐색 트리인 Red-Black Tree 구조를 사용합니다. 각 노드의 키(Key)값으로 프로세스의 vruntime을 설정하여 정렬 상태를 유지합니다.

CFS 트리의 구조적 선출 예시는 위 다이어그램에 나타나 있습니다.

vruntime이 각각 5ms(A), 10ms(C), 12ms(D), 15ms(E), 20ms(H)인 5개의 태스크가 대기 중일 때, 루트 노드인 E(15ms)를 기준으로 작으면 왼쪽 자식 노드로, 크면 오른쪽 자식 노드로 정교하게 정렬됩니다.

이 중 가장 왼쪽에 위치하는 최소 vruntime 태스크인 A(5ms)가 rb_leftmost 포인터에 의해 상시 캐싱되며, 스케줄러는 트리 탐색 연산( $O(\log N)$ )을 건너뛰고 이 포인터를 참조해 즉각적인 $O(1)$ 성능으로 Task A를 다음 구동 주자로 선택합니다.

Group Scheduling과 CFS Bandwidth Control (cgroups)

현대 멀티테넌트 서버나 컨테이너(Docker, Kubernetes) 환경에서는 개별 스레드 단위를 넘어서 특정 프로세스 그룹 또는 컨테이너 단위의 공평성이 대단히 중요합니다.

예를 들어, 한 사용자가 100개의 스레드를 돌리고 다른 사용자가 1개의 스레드를 돌린다면, 스레드 수준의 단순 CFS 공평성을 적용할 경우 100개 스레드를 돌린 사용자가 CPU 자원의 99%를 차지하게 되는 모순이 발생합니다.

이를 위해 CFS는 Group Scheduling 기능을 지원합니다.

개별 태스크가 아닌 cgroup 단위의 논리 노드를 스케줄링 트리에 삽입하여 그룹 간의 가중치를 먼저 나누고, 그 하위에서 각 태스크들이 다시 내부적으로 시간 배분을 받는 계층형 스케줄링을 수행합니다.

이와 연계하여 리눅스 컨테이너의 하드 리밋을 거는 CFS Bandwidth Control은 다음 두 설정을 통해 컨테이너의 CPU 상한선을 정밀하게 제한합니다.

cpu.shares: 경쟁 시점에 그룹이 보장받을 수 있는 최소한의 상대적 CPU 비율을 설정합니다.
cpu.cfs_period_us 및 cpu.cfs_quota_us: 정의된 주기(Period) 동안 해당 그룹 내 전체 스레드가 사용할 수 있는 누적 CPU 시간 한도(Quota)를 지정합니다. 이 쿼터를 모두 소진(Throttled)하면, 다음 주기가 도래할 때까지 스케줄러는 해당 그룹에 속한 모든 프로세스의 실행 권한을 동결하여 물리 코어 점유율을 엄격하게 제한합니다.

2. EEVDF 스케줄러: 공평함을 넘어 응답 속도까지 보장 (Linux 6.6+)

한줄 요약: 공평한 자원 배분(Lag)을 유지하면서, 각 태스크가 요청한 타임 슬라이스 크기에 따라 가상 마감일(Deadline)을 계산하여 응답성(레이턴시)을 극대화한 스케줄러입니다.

CFS는 처리량(Throughput) 관점에서는 가중치 비율대로 자원을 배분하여 훌륭하게 작동했습니다. 하지만 작업의 반응성(Latency)을 보장하는 측면에서는 구조적인 결함이 있었습니다.

예를 들어, 100ms마다 한 번씩 깨어나 1ms 동안 사운드 카드를 건드려 음악을 재생하는 스레드가 있다고 가정해 봅시다. 이 스레드는 실제 CPU 점유 시간은 매우 적어 vruntime이 항상 작지만, 깨어나는 그 순간 지연 없이 즉시 실행되지 않으면 음악이 뚝뚝 끊기게 됩니다.

CFS에서는 이 스레드가 깨어나도 현재 CPU를 쓰고 있는 무거운 백그라운드 연산 스레드의 시간 할당량(Time Slice)이 소모될 때까지 강제로 대기해야 하거나, 이를 방지하기 위해 커널 내부의 복잡한 레이턴시 튜닝 옵션들을 불안정하게 조정해야만 했습니다.

이러한 한계를 개선하기 위해 리눅스 커널 6.6 버전부터 CFS의 태스크 선택 로직은 EEVDF (Earliest Eligible Virtual Deadline First) 방식으로 전환되었습니다.

EEVDF는 기존 CFS의 공평성(Fairness) 모델과 런큐 구조를 유지하면서도, 태스크의 응답 지연 시간(Latency)을 보다 효과적으로 고려할 수 있도록 설계된 차세대 스케줄링 정책입니다.

EEVDF는 프로세스가 "공평하게 배분받아야 할 자격이 있는가"와 "얼마나 빨리 실행되어야 하는가"를 수학적으로 분리하여 스케줄링을 수행합니다.

전자는 시스템 평균 작동 시간 대비 덜 실행되어 자원 요구 자격을 얻는 지연 편차(Lag)로 제어하며, 후자는 요구하는 타임 슬라이스 크기에 비례하여 실행 기한을 결정하는 가상 데드라인(Virtual Deadline)을 기준으로 선입선출합니다.

1. Lag (지연 편차)

각 태스크가 공평하게 받아야 할 가상 시간의 몫(시스템 평균 가상 시간)과 자신이 실제로 사용한 가상 시간의 격차입니다.

지연 편차(Lag) = 시스템 평균 가상 시간 - 나의 가상 시간

여기서 시스템 평균 가상 시간은 실행 대기열에 참가한 모든 활성 프로세스들의 가상 시간(vruntime) 평균값으로, 전체 시스템의 평균적인 진척 속도를 나타냅니다.

지연 편차가 0 이상(Lag ≥ 0)인 경우:
시스템 평균보다 실행 시간이 적어 누적 자원 분배율이 낮으므로, 즉시 CPU를 할당받을 자격이 주어집니다. (적격 상태, Eligible)
지연 편차가 0 미만(Lag < 0)인 경우:
이미 평균보다 과하게 실행되어 자원을 초과 사용했으므로, 우선 실행 후보군에서 배제됩니다. (비적격 상태, Ineligible)

지연 편차 판정 예시 (시스템 평균 가상 시간이 100ms일 때)

Task A (가상 시간 80ms): 지연 편차(Lag) = 100 - 80 = +20ms (양수)
-> 시스템 평균보다 덜 실행되었으므로 실행 자격을 얻어 즉시 대기열 전방에 배치됩니다. (적격 상태)

Task B (가상 시간 120ms): 지연 편차(Lag) = 100 - 120 = -20ms (음수)
-> 시스템 평균보다 이미 자원을 많이 소모했으므로 우선순위에서 밀려납니다. (비적격 상태)

2. Virtual Deadline (가상 마감일)

실행 자격을 획득한 적격 상태(Lag ≥ 0) 태스크들 중, 실제로 누구를 가장 먼저 코어에 올릴지 결정하는 최종 선출 기준입니다.

가상 마감일(Deadline) = 나의 가상 시간 + 이번에 요구한 실행 시간(slice)

여기서 요구한 실행 시간(slice)은 프로세스가 "이번 차례에 한 번 실행 기회를 얻었을 때 연속으로 사용하고자 하는 시간 크기"입니다.

마우스 움직임 제어나 오디오 재생처럼 지연에 민감한 대화형 작업은 극히 짧은 실행 시간(slice)을 요청합니다. 따라서 가상 마감일이 이르게 계산되어 CPU를 즉각 선점합니다.
대량 연산이나 백그라운드 파일 처리처럼 연속적인 처리량이 중요한 배치형 작업은 큰 실행 시간(slice)을 요청하여, 마감일은 뒤로 밀리는 대신 한 번 CPU를 잡으면 오래 실행됩니다.

가상 마감일 계산 예시 (두 태스크 모두 가상 시간이 80ms로 동일할 때)

Task C (마우스 입력 처리): "1ms의 짧은 실행 시간 요구"
-> 가상 마감일 = 80 + 1 = 81 (이른 마감일 형성)

Task D (동영상 인코딩): "20ms의 긴 실행 시간 요구"
-> 가상 마감일 = 80 + 20 = 100 (늦은 마감일 형성)

결과: 두 태스크 모두 자격이 있는 상태에서 경쟁할 때, 스케줄러는 가상 마감일이 훨씬 빠른 Task C(81)를 선점 구동시킴으로써 응답 속도(Latency)를 보장합니다.

3. 선점(Preemption) 판정 규칙

새로운 태스크가 대기 상태에서 깨어나거나 선점 기회가 올 때, EEVDF는 아래 두 조건을 동시에 충족하는 경우에만 즉각적인 선점(Preemption)을 승인합니다.

적격성 만족: 대기열에서 깨어난 태스크의 지연 편차가 0 이상(Lag ≥ 0)이어야 합니다 (실행 자격 획득).
데드라인 우선성: 대기열에서 깨어난 태스크의 가상 마감일이 현재 CPU를 점유 중인 태스크의 마감일보다 빨라야 합니다.

이 선점 규칙은 시스템의 공평한 누적 점유율 분배와 개별 반응성 보장 간의 균형을 맞춥니다.

새로 깨어난 태스크가 현재 실행 중인 태스크를 선점하려면 먼저 실행 자격(Eligible)을 획득해야 합니다. 이후 가상 마감일(Virtual Deadline)이 현재 실행 중인 태스크보다 더 이른 경우에만 선점이 허용됩니다.

이를 통해 과거 자원 소모량이 누적되어 지연 편차가 음수인 태스크가 반응성만을 앞세워 시스템 실행 대역폭을 독점하는 비정상적인 자원 점유율 획득 시도를 차단합니다.

EEVDF의 결정적 진화: 처리량과 응답 지연 시간의 '디커플링'

CFS 스케줄러 환경에서는 프로세스의 처리량(CPU Share)과 반응성(Latency)이 nice 우선순위라는 하나의 변수에 강력하게 결합(Coupling)되어 있었습니다. 즉, 더 자주 그리고 더 빨리 응답하게 만들려면 무조건 nice 값을 낮추어 전체 CPU 점유 분량 자체를 늘려주어야만 했습니다.

반면 EEVDF는 이 두 가지 속성을 보다 독립적으로 제어할 수 있게(Decoupling) 만듭니다.

처리량 제어: 기존과 동일하게 nice 값으로 조절되는 가중치(Weight)에 의해 누적 자원 배분율이 결정됩니다.
반응성 제어: 프로세스가 스스로 요청하는 타임 슬라이스 단위인 slice 크기를 통해 조절됩니다.

이 덕분에 백그라운드에서 백업을 돌리는 프로세스의 경우, nice 값을 높여 CPU는 총 5%만 할당받게 설정하되(낮은 대역폭), 순간적인 I/O 신호가 올 때만 즉시 반응할 수 있도록 slice 값을 최소로 인가하여 '점유율은 매우 낮지만 즉각 반응하는 지능형 스케줄링'을 효과적으로 구현할 수 있게 되었습니다.

EEVDF의 의사결정 단계별 데이터 흐름은 위 다이어그램에 도식화되어 있습니다.

적격성 판정 단계:
가상 시간 $V$ 를 기준으로 삼아 $vruntime$ 이 $V$ 의 좌측에 정렬된 Task A(초록색)는 지연 편차가 양수( $Lag_A \ge 0$ )이므로 적격(Eligible) 후보가 됩니다. 반면 $vruntime$ 이 $V$ 우측에 있는 Task B(빨간색)는 $Lag_B < 0$ 이므로 비적격(Ineligible) 처리되어 후보군에서 원천 배제됩니다.
데드라인 산출 및 최종 선출 단계:
적격 상태인 Task A와 Task C를 대상으로 마감일( $d$ )을 연산합니다. 대량 연산 중심의 Task A는 큰 가상 타임 슬라이스( $q_A = 20\text{ms}$ )를 요청하여 마감일 $d_A$ 가 늦게 형성되는 반면, 빠른 응답성이 요구되는 Task C는 최소화된 타임 슬라이스( $q_C = 2\text{ms}$ )를 요청하여 가장 이른 마감일 $d_C$ 를 부여받습니다. 스케줄러는 후보 노드 중 데드라인이 가장 빠른 Task C를 최종 주자로 선출하여 구동시킵니다.

Deferred Dequeue: 우회성 대기 태스크 방지

이전 스케줄러들은 프로세스가 Sleep 상태에 들어가면 바로 런큐에서 제거했습니다. 이 때문에 일부 프로그램들이 의도적으로 아주 잠깐 잠들었다가 깨어나 본인의 누적 가상 시간 패널티를 회피하고 초기화하는 우회 기법이 가능했습니다.

EEVDF는 Deferred Dequeue(지연된 대기열 제거) 기법을 활용합니다. 태스크가 대기 상태에 들어가도 런큐에서 즉시 지우지 않고 가상 시간이 흘러가는 동안 본인이 가진 양수(+)의 Lag가 자연스럽게 감소(Decay)하도록 지연 처리하여, 가중치 무력화 시도를 차단합니다.

3. [실습] nice 명령을 활용한 스케줄러 자원 배분 검증

커널 스케줄러가 설정된 우선순위(nice 값) 가중치에 따라 CPU 점유 시간 비율을 실제로 정밀하게 계산하고 배분하는지 실습을 통해 직접 눈으로 확인해 보겠습니다.

검증 환경 구축 및 프로세스 고정

단일 CPU 코어(0번 코어) 환경에서 두 프로세스가 자원을 두고 치열하게 경쟁하는 상황을 만들기 위해 taskset과 nice 명령을 함께 사용합니다.

# CPU 0번 코어에 고정하여 일반적인 nice 0 우선순위로 yes 명령어 실행
taskset -c 0 nice -n 0 yes > /dev/null &
PID_HIGH=$!

# 동일한 CPU 0번 코어에 고정하여 낮은 우선순위인 nice 10으로 yes 명령어 실행
taskset -c 0 nice -n 10 yes > /dev/null &
PID_LOW=$!

왜 taskset을 사용하여 0번 코어에 가둬야 할까요?
멀티코어 환경에서 코어 지정을 하지 않으면, 리눅스 커널의 SMP 로드 밸런서가 두 연산 프로세스를 부하 분산을 위해 각각 코어 0번과 코어 1번으로 자동 분리하여 배치합니다. 이 경우 두 프로세스 모두 각자 독립된 코어 점유율을 100%씩 차지하게 되므로 스케줄러 내부의 가중치 분배 메커니즘을 관찰할 수 없습니다.

따라서 taskset -c 0을 통해 단일 물리 런큐 쟁탈전을 강제함으로써 스케줄러가 두 태스크의 가중치를 계산해 Time Slice를 가르는 모습을 정상적으로 모니터링할 수 있게 됩니다.

CPU 자원 점유율 실시간 측정

두 프로세스가 하나의 코어를 점유하고 있는 퍼센트 수치를 top 명령어로 1회 출력해 확인합니다.

top -b -n 1 -p $PID_HIGH,$PID_LOW | grep -E "(PID|yes)"

실제 터미널에 노출되는 출력은 다음과 같습니다.

결과 해석과 동작 증명

실측 결과 nice 0 프로세스는 90.9%, nice 10 프로세스는 9.1%의 CPU 지분율을 나누어 가졌습니다.

이 수치는 리눅스 스케줄러 내부 가중치 소스코드 매핑 정보와 부합합니다.

nice 0에 인가된 가중치 ( $Weight_{0}$ ): 1024
nice 10에 인가된 가중치 ( $Weight_{10}$ ): 110

이상적인 이론적 비율을 공식으로 계산해 보면 다음과 같습니다.

$CPU_{HIGH} = \frac{1024}{1024 + 110} \times 100 \approx 90.3\%$

$CPU_{LOW} = \frac{110}{1024 + 110} \times 100 \approx 9.7\%$

단순히 우선순위가 높다고 해서 혼자 CPU를 100% 다 쓰는 독점 구조가 아니라, 스케줄러가 가중치 비율을 정밀하게 고려해 90.3%와 9.7% 수준으로 시분할 자원을 분배하고 있음을 명확하게 입증할 수 있는 결과입니다.

(실제 측정된 90.9%와 9.1% 역시 오차 범위 내에서 이론값과 거의 정확히 부합합니다.)

실습 환경 종료

실증 완료 후 백그라운드에서 계속 연산을 수행 중인 yes 프로세스들을 확실하게 종료해 줍니다.

kill -15 $PID_HIGH $PID_LOW

4. big.LITTLE 구조와 Heterogeneous Multiprocessing (HMP)

한줄 요약: 성능이 다른 고성능 대형 코어(Big)와 저전력 소형 코어(LITTLE)를 혼합하여, 스케줄러가 코어 용량(Capacity)에 맞춰 부하를 분산 제어하는 하드웨어 아키텍처입니다.

지금까지 살펴본 CFS와 EEVDF는 성능이 동일한 SMP 환경을 전제로 설계되었습니다.

하지만 모바일 기기의 등장으로 고성능 Big 코어와 저전력 LITTLE 코어를 함께 사용하는 big.LITTLE 아키텍처가 보편화되었고, 스케줄러는 단순한 부하 분산을 넘어 전력 효율까지 고려해야 하는 새로운 과제에 직면하게 되었습니다.

big.LITTLE 스케줄링의 진화: IKS에서 HMP로

초기 big.LITTLE 구조의 태스크 할당은 물리 코어 제어 수준이 비교적 투박했습니다.

IKS (In-Kernel Switcher) 방식:
물리적으로 1개의 Big 코어와 1개의 LITTLE 코어를 가상 쌍으로 묶어, OS에게는 마치 단 1개의 가상 코어인 것처럼 보이게 속였습니다. 부하가 적을 때는 LITTLE 코어로만 작동하고, 부하 임계치가 넘으면 하드웨어 수준에서 상태를 복제해 Big 코어로 데이터를 전환(Switching)한 뒤 LITTLE 코어를 끄는 형태였습니다. 이는 물리 코어를 동시에 완전히 가동할 수 없어 멀티스레드 대역폭 손실이 심했습니다.
HMP (Heterogeneous Multiprocessing) 방식:
현대 리눅스 커널이 채택한 범용적 방식입니다. OS 레벨에서 시스템 내부의 Big/LITTLE 물리 코어 전체를 독립된 개별 논리 프로세서로 완전히 구별합니다.

HMP 방식 하에서 스케줄러는 코어들의 상대적 연산 성능 차이를 소프트웨어적 지표인 성능 용량(Capacity, 0~1024 스케일)으로 정규화하여 관리합니다.

스케줄러는 이 격차 정보와 각 태스크의 요구 전력/부하 수준을 활용해 어떤 코어에 태스크를 얹어야 효율적인지 매핑을 수행합니다.

만약 코어 간의 처리 성능 차이를 인지하지 못하는 기존 SMP 스케줄러를 HMP 구조의 CPU에 그대로 탑재하면, 매우 무겁고 긴 연산 태스크가 느린 LITTLE 코어에 박혀 시스템 응답을 마비시키고, 가벼운 주기적 백그라운드 태스크가 Big 코어에서 작동하며 막대한 대기 전력을 낭비하는 심각한 성능 저하 및 배터리 방전 현상이 발생합니다.

5. 최신 리눅스의 지능형 전력 관리 스케줄링: EAS와 PELT

한줄 요약: PELT로 정규화된 태스크 부하를 계측하고, 태스크가 깨어나는 순간 에너지 모델(EM)을 기반으로 소비 전력이 가장 적은 최적의 코어를 찾아 배치하는 지능형 전력 관리 스케줄링 기법입니다.

성능이 서로 다른 비대칭 코어들 사이에서 전력 소모량까지 정밀하게 계산해 가며 태스크를 최적의 코어에 배치하는 고난도 과제를 해결하기 위해, 리눅스 커널은 모바일 최적화 스케줄링 프레임워크인 EAS (Energy Aware Scheduling)와 실시간 부하 측정 시스템인 PELT (Per-Entity Load Tracking)를 개발하여 연동했습니다.

PELT: 왜곡 없는 정밀 로드 측정 센서

EAS가 동작하기 위한 선결 과제는 "깨어난 태스크가 구동되기 위해 요구하는 실질적인 자원의 크기(부하량)"를 왜곡 없이 파악하는 것입니다.

이를 담당하는 PELT 모듈은 각 태스크가 CPU를 차지해 활성화되어 구동된 시간(Execution History)을 누적 지수 감쇄 평균(EWMA, Exponentially Weighted Moving Average) 방식으로 정밀 트래킹합니다.

구체적으로 PELT는 매 1024µs(약 1ms) 주기마다 태스크가 동작(Run)하고 있었는지 여부를 이진 샘플링(0 또는 1024)하며, 과거 이력의 가중치를 지속적으로 감쇄시킵니다. 이때 적용되는 지수 감쇄의 반감기(Half-life, $Y$ )는 32ms입니다.

이로 인해 32ms 전의 작업 내역은 현재 부하 계산 시 딱 50%의 가치만 가지며, 약 200ms(5~6번의 반감기 경과)가 지난 역사는 영향력이 거의 영(0)으로 수렴합니다.

이 정밀한 감쇄 필터링 덕분에 스케줄러는 시스템의 단기적 워크로드 변화에 지연 없이 민감하게 적응함과 동시에, 순간적인 노이즈 부하에 과민 반응하지 않는 신뢰도 높은 로드 프로파일을 도출합니다.

이 32ms 반감기 규칙을 예시로 들면, 시스템 내에서 100% 가동 중이던 고부하 백업 스레드가 연산을 마친 뒤 대기 상태로 전환될 때, 대기 시점의 PELT 부하 점수인 1024는 32ms 경과 시 512, 64ms 경과 시 256, 96ms 경과 시 128로 감쇄하게 됩니다.

약 200ms(5~6번의 반감기)가 지나면 부하 수치는 0에 가깝게 소멸하므로, 스케줄러는 최근 약 200ms 동안의 실행 기여도를 기준으로 태스크의 실질적인 워크로드 가치를 보정하고 과거의 잔류 부하가 신규 스케줄링에 오염을 일으키는 일을 미연에 방지합니다.

이와 함께, PELT는 비대칭 멀티코어 환경을 커버하기 위해 아래의 두 가지 핵심 정규화(Invariance) 필터를 제공합니다.

주파수 불변성(Frequency-invariance): CPU 동작 주파수(예: 500MHz vs 2.5GHz)에 따라 동일 시간 내 실행 연산량이 다른 부분을 정규화하여, CPU 클럭이 요동치더라도 해당 태스크의 절대적인 연산 요구 강도를 왜곡 없이 반환합니다.
CPU 불변성(CPU-invariance): LITTLE 코어와 Big 코어의 기본 아키텍처 성능 격차 값을 곱하여 보정함으로써, 태스크가 어떤 종류의 코어에서 실행되더라도 항상 일관된 0~1024 사이의 정규화된 자원 소모 수준(Utilization)으로 변환해 줍니다.

EAS: 전력 최소화 가상 시뮬레이션 기반 코어 배치

EAS는 태스크가 잠에서 깨어나 런큐에 새롭게 배치되는 시점(Wake-up path)에서 개입합니다. 이 결정의 가이드라인으로 커널 내부 메모리에 테이블로 등록된 디바이스 고유의 에너지 모델(EM, Energy Model)을 참조합니다.

에너지 모델(EM)은 기기의 CPU 성능 용량(Capacity, 0~1024 스케일)에 매칭되는 각 성능 상태(OPP, Operating Performance Point) 및 주파수 격차에 따른 단위당 실제 소모 전력(mW) 테이블입니다.

EAS의 설계 철학: 왜 오직 태스크가 깨어나는 시점(Wake-up Path)에만 작동할까요?
각 코어에 태스크를 옮겼을 때의 시스템 예상 총전력을 예측하는 가상 전력 시뮬레이션 연산은 그 자체로 CPU 연산 오버헤드를 동반합니다. 1ms 주기로 교체되는 모든 런큐 Context Switch 상황마다 이 시뮬레이션을 수행하면 배터리를 절감하기 위한 연산 자체가 배터리를 방전시키는 배보다 배꼽이 큰 상황이 초래됩니다.

따라서 EAS는 오직 대기 상태에서 깨어나며 목적지 코어를 정해야 하는 순간(Wake-up path)에만 작동하여 최적의 위치를 낙점하며, 일단 정상 동작이 개시된 이후(Active run phase)에는 극단적인 코어 불균형이 발생하지 않는 한 로드 밸런싱 재배치를 실행하지 않도록 설계되었습니다.

위의 EAS 의사결정 흐름도(EAS Decision Workflow)의 영문 단계들을 따라 실제로 동작하는 4단계 의사결정 프로세스는 다음과 같습니다.

과부하 상태 감지 (Over-utilized? 판정 단계):
태스크가 잠에서 깨어나 대기열에 새롭게 배치되는 진입 경로인 Task Wake-up (Wake-up Path)이 시작되면, 스케줄러는 먼저 시스템 내 전체 코어들의 부하 수준이 80%를 초과(Over-utilized)했는지 체크합니다.

만약 과부하 상태(Yes)라면, 전력 절감 가상 시뮬레이션을 수행할 연산 여유가 없으므로 EAS 제어를 즉시 중단하고 Bypass EAS 경로로 우회합니다. 이후 성능 극대화에 초점을 맞춘 전통적인 Standard CFS Balancing 모드로 신속히 복귀하여 태스크를 강제 분산시킵니다.

PELT 기반 로드 평가 (Evaluate PELT Load 단계):
시스템 부하가 정상 범주(No)여서 EAS 배치가 최종 승인되면, 깨어난 태스크가 이전에 실행되었던 정보들을 기록해 둔 PELT Utilization 값을 조회하여 해당 태스크가 실질적으로 요구하는 자원 대역폭의 크기(Task Utilization Tracking)를 판별합니다.
에너지 모델 가상 연산 (Energy Model (EM) 단계):
태스크의 부하 계측이 완료되면, 커널 내부의 Energy Model (EM)을 참조하여 해당 태스크를 수용 가능한 코어 후보군을 선정합니다. 이후 각 후보 코어에 태스크를 배치했을 때 예상되는 플랫폼 전체의 에너지 비용(Compute Platform Energy Cost)을 계산합니다.
코어 배치 및 클러스터 전달 (Optimal Energy Core Selection 단계):
계산 결과 예상 에너지 비용이 가장 낮은 후보 코어를 우선적으로 선택하여 태스크를 배치합니다.

요구 성능이 낮은 가벼운 태스크(Low Load)는 상대적으로 전력 소비가 극히 적은 LITTLE Core Cluster에 속한 코어로 전달됩니다.
요구 성능이 높은 무거운 태스크(High Load)는 최대 연산 대역폭을 보장하는 Big Core Cluster에 속한 코어로 전달됩니다.

스케줄러와 CPU 속도(주파수) 조절기(Schedutil)의 연동

스케줄러가 태스크의 동작 위치(LITTLE 코어 혹은 Big 코어)를 결정했다면, 그 코어가 얼마나 빠른 속도(동작 주파수)로 돌아가야 하는가도 매우 중요합니다. 이를 제어하는 장치가 CPU 주파수 조절기(가버너)입니다.

최신 리눅스 커널은 Schedutil 가버너를 탑재하여 스케줄러와 주파수 조절기를 유기적으로 하나로 통합했습니다.

과거의 독립 방식:
스케줄러와 주파수 조절기가 별개로 작동하여, 실시간 CPU 부하가 폭증하더라도 코어 속도가 뒤늦게 반응하여 시스템이 끊기는 현상이 잦았습니다.
Schedutil 연동 방식:
EAS가 측정한 태스크의 실시간 부하 수치(PELT)를 그대로 주파수 조절기가 받아와 CPU 속도를 비례 제어합니다. 부하가 늘어나면 지연 없이 즉각적으로 코어 속도를 최고 클럭 수준까지 높이고, 부하가 사라지면 곧바로 속도를 최저로 내려 전력 낭비를 차단합니다.

Schedutil은 CPU 사용률(PELT Utilization)을 기반으로 목표 주파수를 계산하며, 급격한 부하 증가에도 지연 없이 대응할 수 있도록 추가적인 여유값(headroom)을 반영합니다.

이 여유값의 구체적인 계산 방식은 커널 버전과 구현에 따라 달라질 수 있으며, 목적은 단기적인 부하 스파이크가 발생하더라도 응답성을 유지하는 데 있습니다.

만약 시스템 전체에 과부하가 걸려 일부 CPU 코어의 점유율이 80%를 넘어서는 과부하 상태(Over-utilization)가 발생하면, 커널은 배터리 절약을 포기합니다.

이 경우 전력 절감용인 EAS 루프를 즉시 일시 차단하고, 가용한 모든 Big/LITTLE 리소스를 최대 출력으로 강제 가동하여 시스템의 반응 지연 현상을 신속히 복구하는 비상 모드로 자동 전환됩니다.

6. 정리 (Summary Table)

아키텍처 및 세대	핵심 알고리즘	자원 배분 및 선출 방식	해결한 주요 인프라 과제
클래식 운영체제	FCFS, SJF, Round Robin, MLFQ	도착 순서, 예상 실행 시간 및 시분할 타임 슬라이스 순환	긴 작업에 밀린 짧은 작업들의 대기 병목 최소화
리눅스 중기 (v2.6.23+)	CFS (Completely Fair Scheduler)	vruntime 키값 기반 Red-Black Tree 선출 ( $O(\log N)$ )	인터랙티브 프로세스 판별 휴리스틱 제거 및 완전히 공평한 자원 분배 보장
최신 리눅스 커널 (v6.6+)	EEVDF	Lag 자격 조건 검증 후 가장 빠른 Virtual Deadline 선출	CFS가 보장하지 못했던 사운드, 마우스 등 지연 시간에 민감한 작업의 레이턴시 보장
비대칭 모바일 (big.LITTLE)	EAS + PELT	PELT 기반 정규화 로드 측정 및 Energy Model 기반 소비 전력 시뮬레이션	이종 멀티코어 환경에서 성능과 전력 효율을 동시에 최적화

유정빈

cloud

이전 포스트

HAProxy vs AWS ALB

다음 포스트