CPU 스케줄링 CPU Scheduling

멀티프로그래밍의 목적은 언제나 무언가가 CPU에서 돌게 해 이용률을 최대화하는 것이다. 한 프로세스가 I/O를 기다리며 멈추면, OS는 그 코어를 빼앗아 다른 프로세스에 준다. 누구에게, 언제, 얼마나 줄 것인가 — 이 결정을 내리는 것이 CPU 스케줄러다. 현대 OS에서 스케줄링되는 것은 사실 프로세스가 아니라 커널 수준 스레드지만, 일반 개념을 말할 때는 관례적으로 “프로세스 스케줄링”이라 부른다.

0학습 지도

1기본 개념 — 버스트 사이클·선점·디스패처 📘 OSC 5.1

CPU 스케줄링이 성립하는 근거는 프로세스 실행에 대한 한 가지 관찰이다: 프로세스 실행은 CPU 실행(CPU burst)과 I/O 대기(I/O burst)의 사이클이라는 것이다. 프로세스는 CPU 버스트로 시작해 I/O 버스트, 다시 CPU 버스트… 를 반복하다가 마지막 CPU 버스트가 종료 시스템 콜로 끝난다. 한 프로세스가 I/O를 기다리는 동안 CPU를 놀리지 않고 다른 프로세스에 넘기는 것이 멀티프로그래밍의 본질이다.

1.1 CPU–I/O 버스트 사이클

CPU 버스트의 길이를 대량으로 측정하면 지수(exponential) 또는 하이퍼지수 분포를 따른다: 짧은 버스트가 아주 많고, 긴 버스트는 드물다. I/O 바운드(I/O-bound) 프로그램(예: 대화형 편집기)은 짧은 CPU 버스트가 많고, CPU 바운드(CPU-bound) 프로그램(예: 행렬 곱)은 긴 버스트가 몇 개뿐이다. 이 분포 지식은 스케줄러 설계에 결정적이다 — 짧은 버스트를 우대하면 대화형 응답이 좋아진다.

1.2 CPU 스케줄러와 준비 큐

CPU가 놀게 되면 OS는 준비 큐(ready queue)에서 실행할 프로세스를 하나 골라야 한다. 이 선택을 하는 것이 CPU 스케줄러(단기 스케줄러)다. 중요한 오해 하나: 준비 큐가 반드시 FIFO일 필요는 없다. 알고리즘에 따라 FIFO 큐, 우선순위 큐, 트리(CFS의 레드블랙 트리), 혹은 정렬되지 않은 연결 리스트로 구현될 수 있다. 큐에 들어가는 레코드는 일반적으로 프로세스의 PCB(Process Control Block)다.

1.3 선점형과 비선점형 스케줄링

스케줄링 결정은 다음 네 가지 상황에서만 일어난다.

상황 1·4에서만 스케줄링이 일어나면 비선점형(nonpreemptive) 또는 협력적(cooperative)이라 한다 — 일단 CPU를 받은 프로세스는 자발적으로 놓을 때까지(종료하거나 대기 상태로 전환) CPU를 쥔다. 상황 2·3에서도 스케줄링하면 선점형(preemptive — 실행 중인 프로세스를 강제로 멈추고 CPU를 빼앗음)이다. Windows·macOS·Linux·UNIX 등 거의 모든 현대 OS는 선점형이다.

1.4 디스패처와 디스패치 지연

스케줄러가 “누구를 돌릴지” 고르면, 실제로 그 프로세스에 코어 제어권을 넘기는 모듈이 디스패처(dispatcher)다. 디스패처가 하는 일은 세 가지다.

• 한 프로세스에서 다른 프로세스로 문맥 교환(context switch)
• 사용자 모드로 전환
• 사용자 프로그램의 올바른 위치로 점프하여 재개

디스패처는 모든 문맥 교환마다 호출되므로 최대한 빨라야 한다. 한 프로세스를 멈추고 다른 프로세스를 시작하는 데 걸리는 시간을 디스패치 지연(dispatch latency)이라 한다.

2스케줄링 기준 — 무엇을 최적화하나 📘 OSC 5.2

알고리즘마다 성질이 다르고, 어떤 기준으로 비교하느냐에 따라 “최선”이 달라진다. 교재가 드는 다섯 가지 기준은 다음과 같다.

대부분 평균값(average)을 최적화하지만, 때로는 최소/최대값이 더 중요하다. 예를 들어 모든 사용자에게 좋은 서비스를 보장하려면 최대 응답시간을 최소화해야 한다. 또 연구자들은 대화형 시스템에서 평균 응답시간보다 응답시간의 분산(variance)을 줄이는 게 더 중요하다고 본다 — 평균은 빠르지만 들쭉날쭉한 시스템보다, 합리적이고 예측 가능한 시스템이 더 좋게 느껴진다.

3스케줄링 알고리즘 — FCFS부터 MLFQ까지 📘 OSC 5.3

이 절의 예제는 모두 단일 코어를 가정한다(멀티코어는 5절). 각 알고리즘을 간트차트(Gantt chart — 어느 시각에 어느 프로세스가 CPU를 점유하는지 보여주는 막대 도표)로 그리고 평균 대기시간을 직접 계산한다.

3.1 FCFS (First-Come, First-Served)

가장 단순하다: 먼저 요청한 프로세스가 먼저. FIFO 큐 하나로 구현된다. 다음 세 프로세스가 시각 0에 P1, P2, P3 순으로 도착한다고 하자(버스트: 24, 3, 3).

FCFS의 두 가지 병폐: ① 호위 효과(convoy effect) — CPU 바운드 프로세스 하나가 CPU를 길게 쥐면, I/O 바운드 프로세스들이 모두 그 뒤에 줄 서고 I/O 장치는 놀게 되어 전체 이용률이 떨어진다. ② 비선점형이라 대화형 시스템에 부적합하다 — 한 프로세스가 CPU를 오래 점유하는 것을 막을 수 없다.

3.2 SJF (Shortest-Job-First)와 버스트 예측

각 프로세스의 다음 CPU 버스트가 가장 짧은 것을 먼저 실행한다(정확히는 최단 다음 버스트). 예제(버스트: P1=6, P2=8, P3=7, P4=3):

SJF는 주어진 집합에 대해 평균 대기시간이 증명상 최적(provably optimal)이다 — 짧은 작업을 긴 작업 앞으로 옮기면, 짧은 작업의 대기 감소가 긴 작업의 대기 증가보다 크기 때문이다. 그러나 치명적 문제: 다음 CPU 버스트의 길이를 미리 알 수 없다. 그래서 과거 버스트로 예측한다. 다음 버스트는 보통 과거 버스트의 지수 평균(exponential average)으로 추정한다.

τ(n+1) = α · t(n) + (1 − α) · τ(n)        0 ≤ α ≤ 1

  t(n)   = n번째 실제 측정 버스트
  τ(n)   = n번째에 대해 예측했던 값
  α      = 최근 측정에 두는 가중치

  α = 0 → τ(n+1) = τ(n)        (최근 무시, 과거가 전부)
  α = 1 → τ(n+1) = t(n)        (과거 무시, 최근이 전부)
  α = ½ → 최근과 과거를 동등 가중 (가장 흔함)

전개하면: τ(n+1) = α·t(n) + (1−α)α·t(n−1) + ... + (1−α)^(n+1)·τ(0)
→ 오래된 항일수록 (1−α)^j 만큼 지수적으로 가중치가 줄어든다.

3.3 SRTF — 선점형 SJF (Shortest-Remaining-Time-First)

SJF는 선점형도 될 수 있다. 실행 중인 프로세스보다 남은 시간(remaining time)이 더 짧은 새 프로세스가 도착하면 선점한다. 이를 SRTF라 한다. 예제(도착시각/버스트: P1=0/8, P2=1/4, P3=2/9, P4=3/5):

3.4 라운드로빈 (RR)

FCFS에 선점을 더한 것이다. 타임 퀀텀(time quantum / time slice)이라는 작은 시간 단위(보통 10~100ms)를 정한다. 준비 큐를 원형 큐로 보고, 각 프로세스에 최대 1퀀텀씩 돌아가며 CPU를 준다. 퀀텀 내에 끝나면 자발적으로 반납하고, 넘으면 타이머 인터럽트로 선점되어 큐 꼬리로 간다. 예제(버스트 P1=24, P2=3, P3=3, 퀀텀=4):

RR 성능은 퀀텀 크기에 크게 좌우된다. 퀀텀이 아주 크면 RR은 FCFS와 같아지고, 아주 작으면(예: 1ms) 문맥 교환이 폭증한다. 경험칙: 문맥 교환 시간이 퀀텀의 10%면 CPU의 10%를 교환에 낭비한다. 또 퀀텀이 너무 작으면 반환시간이 늘고, 80%의 CPU 버스트가 퀀텀보다 짧도록 잡는 것이 좋다.

3.5 우선순위 스케줄링 — 기아와 노화

SJF는 “우선순위 = 예측 버스트의 역수”인 우선순위 스케줄링(priority scheduling)의 특수 경우다. 각 프로세스에 우선순위를 주고 가장 높은 것에 CPU를 준다(이 교재는 낮은 숫자 = 높은 우선순위로 가정). 예제(버스트/우선순위: P1=10/3, P2=1/1, P3=2/4, P4=1/5, P5=5/2):

3.6 다단계 큐 (MLQ, Multilevel Queue)

모든 프로세스를 하나의 큐에 두면 최고 우선순위를 찾는 데 O(n) 탐색이 들 수 있다. 실전에서는 우선순위마다 별도 큐를 두는 것이 효율적이다. 더 일반적으로는 프로세스 유형별로 큐를 나눈다: 실시간 → 시스템 → 대화형 → 배치. 각 큐는 자기만의 알고리즘(예: 전경은 RR, 배경은 FCFS)을 쓸 수 있다. 큐 사이의 스케줄링은 보통 고정 우선순위 선점(상위 큐가 비어야 하위 큐 실행)이거나 타임 슬라이스 분배(전경 80%, 배경 20%)다.

3.7 다단계 피드백 큐 (MLFQ, Multilevel Feedback Queue)

MLQ는 단순하지만 경직(inflexible)되어 있다 — 프로세스가 큐를 옮기지 못한다. MLFQ는 프로세스가 큐 사이를 이동하게 허용한다. 핵심 아이디어: CPU를 너무 많이 쓰면 하위 큐로 강등한다. 그러면 짧은 버스트의 I/O 바운드·대화형 프로세스가 자연히 상위 큐에 남는다. 또 하위 큐에서 너무 오래 기다린 프로세스는 상위로 승격(노화)해 기아를 막는다.

MLFQ는 다섯 매개변수(큐 개수, 각 큐의 알고리즘, 승격 기준, 강등 기준, 진입 큐 결정)로 정의되어 가장 일반적인 스케줄러다 — 어떤 시스템에도 맞출 수 있다. 그러나 그만큼 가장 복잡하다(매개변수 튜닝이 어렵다).

4스레드 스케줄링 — PCS vs SCS 📘 OSC 5.4

현대 OS가 실제로 스케줄링하는 것은 프로세스가 아니라 커널 수준 스레드다. 사용자 수준 스레드는 스레드 라이브러리가 관리하고 커널은 이를 모른다 — CPU에서 돌려면 결국 커널 스레드에 매핑되어야 한다(LWP를 거칠 수도 있다).

4.1 경합 범위 — PCS와 SCS

• PCS (Process-Contention Scope, 프로세스 경합 범위): 다대일·다대다 모델에서, 스레드 라이브러리가 같은 프로세스 안의 사용자 스레드들을 가용 LWP에 스케줄한다. CPU 경쟁이 한 프로세스 내부 스레드끼리 일어난다. 보통 우선순위 기반이며 — 같은 우선순위 스레드 사이의 타임 슬라이싱은 보장되지 않는다.
• SCS (System-Contention Scope, 시스템 경합 범위): 커널이 시스템 전체의 커널 스레드들을 두고 어느 것을 CPU에 올릴지 정한다. 일대일 모델(Windows·Linux)은 오직 SCS만 쓴다.

4.2 Pthread 스케줄링 API

POSIX는 스레드 생성 시 경합 범위를 지정하는 두 값을 제공한다: PTHREAD_SCOPE_PROCESS(PCS)와 PTHREAD_SCOPE_SYSTEM(SCS). 단, Linux와 macOS는 PTHREAD_SCOPE_SYSTEM만 허용한다(일대일 모델이므로).

#include <pthread.h>
#include <stdio.h>
#define NUM_THREADS 5

void *runner(void *param) {
    /* ... 작업 ... */
    pthread_exit(0);
}

int main(int argc, char *argv[]) {
    int i, scope;
    pthread_t      tid[NUM_THREADS];
    pthread_attr_t attr;

    pthread_attr_init(&attr);                       /* 기본 속성 */

    /* 현재 경합 범위 조회 */
    if (pthread_attr_getscope(&attr, &scope) != 0)
        fprintf(stderr, "Unable to get scheduling scope\n");
    else if (scope == PTHREAD_SCOPE_PROCESS)
        printf("PTHREAD_SCOPE_PROCESS\n");
    else if (scope == PTHREAD_SCOPE_SYSTEM)
        printf("PTHREAD_SCOPE_SYSTEM\n");

    /* SCS(=PCS 또는 SCS)로 설정 */
    pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);

    for (i = 0; i < NUM_THREADS; i++)
        pthread_create(&tid[i], &attr, runner, NULL);
    for (i = 0; i < NUM_THREADS; i++)
        pthread_join(tid[i], NULL);
}

5다중 처리기 스케줄링 📘 OSC 5.5

코어가 여럿이면 부하 공유(load sharing)로 진짜 병렬이 가능해지지만, 스케줄링은 그만큼 복잡해진다. “다중처리기”는 이제 단일 정의가 아니라 멀티코어 CPU · 멀티스레드 코어(SMT) · NUMA 시스템 · 이기종 멀티프로세싱(HMP)을 모두 포괄한다.

5.1 접근법 — 비대칭 vs SMP

• 비대칭 다중처리(asymmetric): 마스터 서버 하나가 모든 스케줄링·I/O를 맡고 나머지 코어는 사용자 코드만 실행. 데이터 공유가 적어 단순하지만 마스터가 병목이 된다.
• 대칭 다중처리(SMP): 각 처리기가 스스로 스케줄링한다. 표준 접근이다(Windows·Linux·macOS·Android·iOS). 두 가지 큐 조직 전략이 있다.

5.2 멀티코어와 멀티스레드 코어 — 메모리 스톨과 CMT

처리기가 메모리에 접근하면 데이터가 올 때까지 상당 시간을 기다리는 메모리 스톨(memory stall)이 생긴다(메모리가 코어보다 훨씬 느리거나 캐시 미스). 이때 코어 시간의 최대 50%가 낭비될 수 있다. 해법: 멀티스레드 코어 — 한 코어에 하드웨어 스레드를 2개 이상 두어, 한 스레드가 스톨하면 다른 스레드로 전환해 실행 유닛을 채운다. 이를 칩 멀티스레딩(CMT) 또는 인텔 용어로 하이퍼스레딩 / SMT(simultaneous multithreading)라 한다.

5.3 부하 균형 — push와 pull 이주

코어별 사설 큐를 쓰면 작업량이 불균등해질 수 있어 부하 균형(load balancing)이 필요하다(공통 큐면 불필요 — 노는 코어가 즉시 꺼내가므로). 두 가지 접근이 있다.

• push 이주(migration): 특정 태스크가 주기적으로 각 코어 부하를 점검해, 과부하 코어에서 한가한 코어로 스레드를 밀어낸다.
• pull 이주: 노는 코어가 바쁜 코어에서 대기 중인 태스크를 끌어온다.

둘은 배타적이지 않고 함께 쓰인다(Linux CFS, FreeBSD ULE 모두 둘 다 구현). “균형 잡힌 부하”의 의미도 다양하다 — 큐별 스레드 수가 같은 것, 우선순위 분포가 같은 것, 혹은 CFS처럼 부하(우선순위+CPU 이용률)의 합이 같은 것.

5.4 처리기 친화성과 NUMA

스레드가 한 코어에서 돌면 그 코어 캐시가 “따뜻해진다(warm cache)”. 다른 코어로 이주하면 첫 코어 캐시를 무효화하고 둘째 코어 캐시를 다시 채워야 하므로 비싸다. 그래서 OS는 스레드를 같은 코어에 붙들려 한다 — 이것이 처리기 친화성(processor affinity)이다. 코어별 사설 큐는 친화성을 공짜로 제공한다(항상 같은 코어에 스케줄되므로).

• 소프트 친화성(soft affinity): 같은 코어 유지를 시도하지만 보장하지 않음(부하 균형 시 이주 가능).
• 하드 친화성(hard affinity): 실행 가능한 코어 집합을 지정. Linux의 sched_setaffinity() 시스템 콜.

NUMA(Non-Uniform Memory Access)에서는 각 CPU가 로컬 메모리에 빠르게, 원격 메모리에 느리게 접근한다. OS의 스케줄러와 메모리 배치 알고리즘이 NUMA-aware하면, 스레드를 올린 CPU에 가장 가까운 메모리를 할당해 최선의 접근 속도를 준다.

5.5 이기종 멀티프로세싱 (HMP) — big.LITTLE

모바일 시스템은 같은 명령 집합을 쓰되 클럭과 전력 관리가 다른 코어를 섞는다 — 이기종 멀티프로세싱(HMP). ARM의 big.LITTLE이 대표로, 고성능 big 코어와 저전력 LITTLE 코어를 결합한다. (비대칭 다중처리와 다르다 — 시스템·사용자 태스크 모두 어느 코어에서나 돌 수 있다.) 목적은 전력 관리: 백그라운드 작업처럼 성능이 덜 필요한 태스크는 LITTLE에, 대화형처럼 짧고 강한 성능이 필요한 태스크는 big에 배치한다. 절전 모드면 big 코어를 끄고 LITTLE만 쓴다. Windows 10도 스레드별 전력 정책 선택으로 HMP를 지원한다.

6실시간 CPU 스케줄링 — RMS·EDF 📘 OSC 5.6

실시간 시스템은 특별한 이슈가 있다. 소프트 실시간(soft real-time)은 임계 작업에 우선권만 보장한다(언제 스케줄될지는 보장 안 함). 하드 실시간(hard real-time)은 마감(deadline)까지 반드시 서비스해야 한다 — 마감 후의 서비스는 서비스 안 한 것과 같다.

6.1 지연 최소화 — 인터럽트 지연과 디스패치 지연

이벤트 지연(event latency)은 이벤트 발생부터 서비스까지의 시간이다(ABS 브레이크는 3~5ms, 항공기 레이더는 수 초도 허용). 실시간 성능에 영향을 주는 두 지연이 있다.

• 인터럽트 지연(interrupt latency): 인터럽트 도착부터 ISR(인터럽트 서비스 루틴) 시작까지. 현재 명령 완료 + 인터럽트 유형 판별 + 현재 상태 저장이 포함된다. 인터럽트가 비활성화된 시간이 주요 기여 요인이라, 실시간 OS는 인터럽트 비활성 구간을 아주 짧게 유지하고, 하드 실시간에서는 경계(bound)까지 둔다.
• 디스패치 지연(dispatch latency): 디스패처가 한 프로세스를 멈추고 다른 것을 시작하는 시간. 선점형 커널이 이를 낮추는 가장 효과적 기법이다. 충돌(conflict) 단계 = ① 커널에서 돌던 프로세스의 선점 + ② 저우선순위가 쥔 자원의 해제, 그 뒤 디스패치 단계가 고우선순위를 코어에 올린다.

6.2 우선순위 기반 스케줄링과 주기 태스크

실시간 OS의 핵심은 선점 + 우선순위 기반 스케줄러다. 그러나 이것만으로는 소프트 실시간만 보장된다. 하드 실시간은 추가 기능이 필요하다. 하드 실시간 분석을 위해 태스크를 주기적(periodic)이라 가정한다: 처리시간 t, 마감 d, 주기 p (관계 0 ≤ t ≤ d ≤ p), 비율(rate) = 1/p. 태스크가 마감을 알리면 입장 제어(admission-control) 알고리즘이 “마감 보장 가능하면 입장, 불가능하면 거부”한다.

6.3 Rate-Monotonic 스케줄링 (RMS)

주기 태스크를 정적(static) 우선순위 + 선점으로 스케줄한다. 주기가 짧을수록 높은 우선순위(CPU를 자주 필요로 하는 태스크 우대). 예: P1(p=50, t=20), P2(p=100, t=35). 이용률 = 20/50 + 35/100 = 0.40 + 0.35 = 0.75. RMS는 P1을 더 높게 둔다.

RMS는 정적 우선순위 중 최적(이 알고리즘으로 못 짜면 어떤 정적 우선순위로도 못 짠다)이다. 그러나 한계가 있다: 이용률 상한이 있어 항상 100%를 못 쓴다. N개 프로세스의 최악 이용률 경계는 N(2^(1/N) − 1)로, N→∞면 약 69%로 수렴한다(2개면 ≈83%). 예로 P1(p=50,t=25), P2(p=80,t=35)는 이용률 94%라 RMS로 짜면 P2가 마감(80)을 놓친다(85에 완료).

6.4 Earliest-Deadline-First (EDF)

EDF는 동적(dynamic) 우선순위를 마감에 따라 준다 — 마감이 이를수록 높은 우선순위. 새 프로세스가 실행 가능해지면 마감을 알리고, 우선순위가 재조정된다(RMS는 고정이라는 점이 다르다). 앞서 RMS가 실패한 P1(p=50,t=25), P2(p=80,t=35)를 EDF는 성공시킨다.

EDF는 주기성도, 일정한 버스트도 요구하지 않으며 — 오직 “실행 가능해질 때 마감을 알릴 것”만 요구한다. 이론상 최적(100% 이용률 달성 가능)이지만 실전에서는 문맥 교환·인터럽트 비용 때문에 그 수준은 못 미친다.

6.5 비례 배분 스케줄링과 POSIX 실시간

비례 배분(proportional share): 총 T 셰어를 앱들에 나눠, N 셰어를 받은 앱은 전체의 N/T 시간을 보장받는다. 역시 입장 제어와 함께 동작한다(셰어가 모자라면 거부). POSIX 실시간(POSIX.1b)은 두 클래스를 정의한다: SCHED_FIFO(같은 우선순위 간 타임 슬라이스 없는 FIFO, 종료/블록까지 점유)와 SCHED_RR(같은 우선순위 간 RR). SCHED_OTHER도 있으나 구현은 시스템마다 다르다.

#include <pthread.h>
#include <stdio.h>
#define NUM_THREADS 5

int main(int argc, char *argv[]) {
    int i, policy;
    pthread_t      tid[NUM_THREADS];
    pthread_attr_t attr;

    pthread_attr_init(&attr);

    /* 현재 정책 조회 */
    if (pthread_attr_getschedpolicy(&attr, &policy) != 0)
        fprintf(stderr, "Unable to get policy.\n");
    else if (policy == SCHED_OTHER) printf("SCHED_OTHER\n");
    else if (policy == SCHED_RR)    printf("SCHED_RR\n");
    else if (policy == SCHED_FIFO)  printf("SCHED_FIFO\n");

    /* 정책 설정 — FIFO / RR / OTHER */
    if (pthread_attr_setschedpolicy(&attr, SCHED_FIFO) != 0)
        fprintf(stderr, "Unable to set policy.\n");

    for (i = 0; i < NUM_THREADS; i++)
        pthread_create(&tid[i], &attr, runner, NULL);
    for (i = 0; i < NUM_THREADS; i++)
        pthread_join(tid[i], NULL);
}

7운영체제 사례 — Linux · Windows · Solaris 📘 OSC 5.7

7.1 Linux — CFS (Completely Fair Scheduler)

Linux 스케줄러 역사: 2.5 이전의 전통 UNIX 방식 → 2.5의 O(1) 스케줄러(태스크 수와 무관한 상수 시간, SMP 우수했으나 대화형 응답 나쁨) → 2.6.23부터 기본이 된 CFS. Linux는 스케줄링 클래스(scheduling class) 기반이다: (1) 기본 CFS 클래스, (2) 실시간 클래스(POSIX SCHED_FIFO/RR). 스케줄러는 최고 우선순위 클래스의 최고 우선순위 태스크를 고른다.

CFS는 시간 퀀텀을 직접 안 쓰고 각 태스크에 CPU 시간의 비율(proportion)을 준다. 이 비율은 nice 값(−20~+19, 낮을수록 높은 우선순위, 기본 0)으로 정해진다. 또 목표 지연(targeted latency) — 모든 실행 가능 태스크가 최소 한 번은 돌아야 하는 구간 — 을 정의하고 그 안에서 비율로 시간을 배분한다(태스크가 많아지면 목표 지연도 늘어난다).

Linux 실시간은 POSIX(0~99 정적 우선순위), 일반 태스크는 100~139(nice −20→100, +19→139)로 매핑된다 — 전역 우선순위 체계에서 낮은 숫자가 높은 우선순위다. CFS의 부하 균형은 스케줄링 도메인(scheduling domain) 계층(L2 공유 → domain, L3 공유 → NUMA 노드)을 따라 가장 낮은 수준부터 균형을 잡으며, NUMA 노드 간 이주는 심각한 불균형일 때만 한다.

7.2 Windows — 32단계 우선순위 디스패처

Windows는 우선순위 기반·선점형으로 항상 최고 우선순위 스레드를 돌린다(이 부분을 디스패처라 부른다). 32단계: 가변 클래스(1~15)와 실시간 클래스(16~31), 그리고 메모리 관리용 0. 우선순위마다 큐가 있고 높은 데서 낮은 데로 훑는다(없으면 idle 스레드). API의 6개 우선순위 클래스(IDLE~REALTIME)와 상대 우선순위(IDLE~TIME_CRITICAL)의 조합으로 수치 우선순위가 정해진다.

가변 클래스 스레드는 퀀텀이 만료되면 우선순위가 낮아지고(기준 우선순위 밑으로는 안 감 — compute-bound 억제), 대기에서 풀리면 올라간다(키보드 I/O는 크게, 디스크는 중간 — 대화형 응답 강화). 전경(foreground) 프로세스는 퀀텀을 보통 3배로 늘려준다. Windows 7의 UMS(user-mode scheduling)는 커널 개입 없이 사용자 모드에서 스레드를 스케줄(과거 fiber의 한계 극복), ConcRT 같은 라이브러리가 그 위에 얹힌다.

7.3 Solaris — 6개 스케줄링 클래스 → 전역 우선순위

Solaris는 우선순위 기반 스레드 스케줄링으로, 스레드가 6개 클래스 중 하나에 속한다: TS(time sharing, 기본), IA(interactive), RT(real time), SYS(system), FSS(fair share), FP(fixed priority). TS/IA는 MLFQ로 동적 우선순위·가변 퀀텀을 쓴다 — 우선순위와 퀀텀은 역관계(우선순위 높으면 퀀텀 작음). 디스패치 테이블이 “퀀텀 만료 시 새 우선순위(낮춤)”와 “sleep 복귀 시 우선순위(50~59로 부스트)”를 정의해 대화형 응답을 좋게 한다. 각 클래스의 클래스별 우선순위를 전역 우선순위(global priority)로 변환해 최고를 고른다(인터럽트 스레드 160~169가 최상위).

8알고리즘 평가 — 모델링·큐잉·시뮬레이션 📘 OSC 5.8

특정 시스템에 어느 알고리즘을 쓸지 어떻게 고를까? 먼저 기준의 상대적 중요도를 정한다(예: “최대 응답 300ms 제약 하에 CPU 이용률 최대화”). 그다음 네 가지 평가 방법을 쓴다.

8.1 결정적 모델링 (Deterministic Modeling)

특정한 사전 결정 워크로드를 두고 각 알고리즘의 성능을 정확한 숫자로 계산하는 해석적 방법이다. 예제(모두 시각 0 도착, 버스트 P1=10, P2=29, P3=3, P4=7, P5=12)를 FCFS·SJF·RR(q=10)로 비교:

8.2 큐잉 모델과 Little's Law

매일 프로세스가 달라지면 정적 집합이 없다. 대신 CPU/I/O 버스트의 분포(보통 지수 분포)와 도착 분포를 측정해 평균 처리량·이용률·대기시간을 계산한다 — 큐잉 네트워크 분석. 시스템을 “큐를 가진 서버들의 네트워크”로 본다(CPU는 준비 큐를 가진 서버, I/O는 장치 큐를 가진 서버).

           n = λ × W

  n = 평균 큐 길이 (서비스 중인 것 제외)
  λ = 평균 도착률 (예: 초당 7개 프로세스)
  W = 큐에서의 평균 대기시간

직관: 프로세스가 W 시간 기다리는 동안 λ×W 개가 새로 도착한다.
정상 상태(steady state)면 들어오는 수 = 나가는 수 → n = λ·W.

예: λ = 7 프로세스/초, n = 14 → W = n/λ = 14/7 = 2초.
임의의 스케줄링 알고리즘·도착 분포에 모두 성립(범용).

큐잉 분석은 알고리즘 비교에 유용하지만, 다룰 수 있는 알고리즘·분포 클래스가 제한적이고, 수학적 편의를 위해 비현실적 가정을 하므로 결과가 근사에 그칠 수 있다.

8.3 시뮬레이션과 구현

• 시뮬레이션(simulation): 시스템 모델을 프로그래밍하고 시뮬레이션 클록을 돌린다. 데이터는 난수 발생기(균등·지수·푸아송)로 만들거나, 실제 시스템을 모니터링한 추적 파일(trace file)로 구동한다. 추적 파일은 동일한 실제 입력으로 두 알고리즘을 비교하게 해 정확하지만, 저장 공간과 시뮬레이터 개발 비용이 크다.
• 구현(implementation): 가장 정확한 유일한 방법은 알고리즘을 실제 OS에 코딩해 돌려보는 것이다. 비용이 크고(코딩·회귀 테스트), 환경이 알고리즘에 반응해 변한다(짧은 프로세스 우대 시 사용자가 큰 작업을 쪼개거나, 인터랙티브 우대 시 단말에 의미 없는 출력을 흘려 우선순위를 가로채는 식). 가장 유연한 알고리즘은 관리자/사용자가 튜닝할 수 있는 것이다(Solaris의 dispadmin, Java/POSIX/Windows API).

9CFS 내부·EEVDF·스케줄러 역사·실무 튜닝 ⊕ 교재 외 확장

교재는 CFS를 “vruntime이 작은 태스크를 고른다” 수준으로 소개한다. 여기서는 그 내부 자료구조와 수학, 그리고 2023년의 후계자 EEVDF, 역사적 맥락, 실무 튜닝을 더 깊이 본다.

9.1 vruntime · nice · weight — 공정성의 산술

CFS의 “공정”은 가중 공정(weighted fair)이다. 각 태스크의 nice 값은 weight로 변환된다(커널 테이블 sched_prio_to_weight[], nice 0 = 1024). vruntime은 실제 실행 시간에 1024/weight를 곱해 누적된다 — 고우선순위(큰 weight)는 vruntime이 천천히 자라 더 자주 선택된다. nice 한 단계 차이는 약 1.25배의 CPU 비율 차이를 만든다.

/* nice → weight: 한 단계마다 약 1.25배. nice 0 → 1024 */
static const int prio_to_weight[40] = {
    /* -20 */ 88761, 71755, 56483, 46273, 36291,
    /* ...  */ /* ... 중략 ... */
    /*   0 */ 1024,  820,   655,   526,   423,
    /* +19 */ 15
};

/* 태스크가 delta_exec(ns)만큼 실제로 돈 뒤 호출 */
void update_vruntime(struct sched_entity *se, u64 delta_exec) {
    /* 가중 보정: weight가 클수록(고우선순위) vruntime이 천천히 증가 */
    se->vruntime += delta_exec * NICE_0_WEIGHT / se->load.weight;
    /*               (= delta_exec * 1024 / weight)               */
}

/* 다음에 돌릴 태스크: 레드블랙 트리의 최좌측(min vruntime) */
struct sched_entity *pick_next(struct cfs_rq *rq) {
    return rq->rb_leftmost;     /* O(1): 캐시된 최좌측 노드 */
}

9.2 레드블랙 트리 — O(log N) 선택과 O(1) 캐시

CFS는 준비 큐를 레드블랙 트리(자가 균형 이진 탐색 트리)로 유지한다. 키는 vruntime. 실행 가능해진 태스크는 트리에 삽입, 블록되면 제거된다. vruntime이 작은(덜 돈) 태스크가 왼쪽에 모이므로, 최좌측 노드 = 다음에 돌릴 태스크다. 트리가 균형이라 탐색은 O(log N)이지만, 커널은 최좌측을 rb_leftmost에 캐시해 실제 선택은 O(1)이다.

9.3 EEVDF — CFS의 후계자 (6.6+)

2023년 말 Linux 6.6은 CFS를 EEVDF(Earliest Eligible Virtual Deadline First)로 대체했다. CFS의 약점은 지연(latency) 보장이 없다는 것이었다 — vruntime 공정성은 “장기적으로 공평”하지만 “지금 당장 얼마나 빨리 돌지”를 표현하지 못했다. EEVDF는 각 태스크에 가상 마감(virtual deadline)을 주고, 자격(eligible)이 있는 태스크 중 가상 마감이 가장 이른 것을 고른다 — 6절 EDF의 정신을 공정 스케줄러에 이식한 셈이다. lag(받아야 할 시간 대비 실제 받은 시간의 차)으로 자격을 판정하고, 태스크별 sched_attr의 latency-nice로 지연 민감도를 표현한다. nice·weight·레드블랙 트리 골격은 그대로 재사용한다.

9.4 실무 튜닝 — chrt · taskset · nice

이론을 실제 시스템에 적용하는 도구들이다.

# 1) nice — 일반(CFS/EEVDF) 태스크의 우선순위 비율 조정 (-20~19)
nice -n 10 ./batch_job          # 낮은 우선순위로 시작
renice -n -5 -p 1234            # 실행 중 PID 1234 우선순위 올림

# 2) chrt — 실시간 정책 지정 (SCHED_FIFO / SCHED_RR / SCHED_OTHER)
chrt -f 80 ./audio_engine       # SCHED_FIFO, 우선순위 80 (저지연 오디오)
chrt -r 50 ./control_loop       # SCHED_RR, 우선순위 50
chrt -p 1234                    # PID 1234의 현재 정책/우선순위 조회

# 3) taskset / sched_setaffinity — 하드 친화성 (CPU 핀닝)
taskset -c 2,3 ./latency_app    # CPU 2,3에만 고정 → 따뜻한 캐시 유지
taskset -p 0x1 1234             # PID 1234를 CPU0에 핀

# 4) cgroup v2 cpu 컨트롤러 — 그룹 단위 비례 배분 (컨테이너)
echo 200 > /sys/fs/cgroup/myapp/cpu.weight     # 기본 100의 2배 비율
echo "50000 100000" > .../cpu.max               # 100ms당 50ms 상한(쿼터)

#define _GNU_SOURCE
#include <sched.h>
#include <pthread.h>

void pin_to_cpu(int cpu) {
    cpu_set_t set;
    CPU_ZERO(&set);
    CPU_SET(cpu, &set);                          /* cpu 하나만 허용 집합에 */
    /* 현재 스레드(0)를 지정 CPU에만 스케줄되도록 고정 */
    if (sched_setaffinity(0, sizeof(set), &set) != 0)
        perror("sched_setaffinity");
    /* pthread 버전: pthread_setaffinity_np(pthread_self(), ...) */
}

10오해 정리 · 한 장 요약 · 복습 📘 OSC 5.9

10.1 흔한 오해 바로잡기

• ❌ “준비 큐는 항상 FIFO다.” → FIFO·우선순위 큐·트리(CFS 레드블랙)·연결 리스트 등 알고리즘에 따라 다르다.
• ❌ “SJF는 항상 쓸 수 있다.” → 평균 대기시간 최적이지만 다음 버스트 길이를 알 수 없어 CPU 스케줄링 수준에서는 구현 불가. 지수 평균으로 예측만 한다.
• ❌ “퀀텀을 작게 할수록 RR이 공평하고 좋다.” → 너무 작으면 문맥 교환 오버헤드가 폭증하고 반환시간이 오히려 늘어난다.
• ❌ “우선순위만 잘 주면 된다.” → 순수 우선순위는 기아를 낳는다. 노화(aging)가 필요하다.
• ❌ “RMS가 최적이니 75% 이용률이면 무조건 짜진다.” → RMS는 정적 우선순위 중 최적일 뿐, 이용률 경계(N→∞ 시 ≈69%)가 있다. 94% 같은 경우엔 EDF가 낫다.
• ❌ “부하 균형은 항상 이득이다.” → 스레드를 옮기면 따뜻한 캐시·NUMA 지역성을 잃어 친화성과 상충한다.
• ❌ “CFS는 우선순위 큐다.” → CFS는 우선순위를 직접 안 쓰고 vruntime으로 공정성을 만든다(6.6+는 EEVDF의 가상 마감).
• ❌ “SMT 코어 2개면 성능이 2배.” → 실행 유닛·캐시를 공유하므로 자원을 다투면 1+1 < 2일 수 있다.

10.2 한 장 정리

10.3 복습 — 답을 가리고

Q1. 같은 세 프로세스(버스트 24,3,3)인데 FCFS 평균 대기시간이 17ms에서 3ms로 바뀐다. 무엇이 그 차이를 만드나?

도착(서비스) 순서다. 긴 P1이 앞서면 짧은 둘이 다 기다려 (0+24+27)/3=17ms, 짧은 둘을 앞세우면 (0+3+6)/3=3ms. FCFS는 비선점이라 호위 효과에 취약하다.

Q2. SJF가 평균 대기시간 최적인데도 CPU 스케줄러에 못 쓰는 이유와, 그 대안은?

다음 CPU 버스트의 길이를 알 수 없기 때문. 대안은 과거 버스트의 지수 평균 τ(n+1)=α·t(n)+(1−α)·τ(n)으로 예측해 가장 짧을 것 같은 프로세스를 고르는 것(근사 SJF).

Q3. RR 퀀텀을 1ms로 극단적으로 줄이면 무슨 일이 일어나나?

문맥 교환이 폭증한다. 교환 시간이 퀀텀의 10%면 CPU의 10%를 교환에 낭비하고, 반환시간도 늘어난다. 경험칙은 “80%의 CPU 버스트가 퀀텀보다 짧게” 잡는 것.

Q4. RMS와 EDF의 우선순위 부여 방식 차이를 한 문장씩.

RMS는 정적 — 주기가 짧을수록 높은 우선순위(영구 고정). EDF는 동적 — 마감이 이를수록 높은 우선순위(실행 가능해질 때마다 재조정). 그래서 RMS는 94% 이용률에서 마감을 놓치지만 EDF는 지킨다.

Q5. 처리기 친화성이 왜 성능에 중요하고, 부하 균형과 어떻게 충돌하나?

스레드를 같은 코어에 두면 따뜻한 캐시를 재사용해 메모리 접근이 빠르다(NUMA에선 로컬 메모리 지역성까지). 그러나 부하 균형은 스레드를 다른 코어로 옮겨 이 이득을 무효화하고 NUMA 패널티까지 줄 수 있다 — 본질적 긴장 관계.

Q6. CFS는 우선순위를 어떻게 “기록”하며, 다음 태스크를 어떻게 O(1)로 고르나?

각 태스크의 vruntime을 weight로 보정해 누적한다(고우선순위는 천천히 증가). 준비 큐를 vruntime 키의 레드블랙 트리로 유지하고, 최좌측(최소 vruntime) 노드를 rb_leftmost에 캐시해 선택을 O(1)로 만든다.

Q7. Little's law n=λW로, 초당 7개가 도착하고 큐에 평균 14개가 있으면 평균 대기시간은?

W = n/λ = 14/7 = 2초. 이 공식은 임의의 스케줄링 알고리즘·도착 분포에 성립하는 정상 상태 항등식이다.

Q8. SCHED_FIFO로 무한 루프 스레드를 돌리면 왜 시스템이 멈출 수 있고, Linux는 어떻게 막나?

SCHED_FIFO는 같은/낮은 우선순위에 타임 슬라이스를 안 줘 그 코어를 독점, 커널 스레드까지 굶긴다. Linux는 sched_rt_runtime_us(기본 95% 상한)로 RT가 CPU를 100% 못 쓰게 막아 일반 태스크가 숨 쉴 틈을 보장한다.

10.4 연관 자료 · 더 깊이