리눅스 CPU 스케줄러는 MLFQ가 아니라 EEVDF다

CPU 스케줄링을 배우면 FIFO에서 시작해 SJF, 라운드 로빈을 거쳐 MLFQ에서 끝난다. 각 알고리즘이 앞 알고리즘의 단점을 하나씩 메우는 흐름이라 이야기가 깔끔하고, 마지막에 “오늘날 운영체제는 MLFQ를 쓴다”로 닫히면 정리가 된다

리눅스 CPU 스케줄러는 그 목록에 없다. 2.6.23부터 CFS(Completely Fair Scheduler)를 썼고, 6.6에서 EEVDF로 바뀌었다(EEVDF Scheduler, Linux Kernel documentation). 둘 다 우선순위 큐를 여러 개 놓고 프로세스를 아래로 내리는 방식이 아니다. 그러면서도 FIFO와 라운드 로빈은 SCHED_FIFO, SCHED_RR이라는 이름으로 리눅스 안에 그대로 살아 있다. 교과서의 알고리즘들이 실제 커널에서 어떤 자리를 차지하고 있는지가 이 글의 주제다

정책을 바꿔 가며 같은 작업을 돌려 반환 시간과 I/O 사용률을 쟀고, nice 값에 따른 CPU 배분이 문서의 예측과 맞는지도 확인했다. 마지막 실험에서는 내가 예상한 숫자가 나오지 않았고 그 이유를 찾는 데 지면을 조금 썼다

이 글에서 자주 나오는 용어

  • CPU 버스트 / I/O 버스트: 프로세스가 연속해서 CPU를 쓰는 구간과 입출력을 기다리는 구간
  • 선점(Preemption): 스케줄러가 실행 중인 프로세스에게서 CPU를 강제로 빼앗는 것
  • 타임 슬라이스(Time Slice): 한 번에 CPU를 쥘 수 있는 시간. 타임 퀀텀이라고도 한다
  • 대기 시간(Waiting Time): 준비 큐에서 CPU를 못 받고 기다린 시간의 합
  • 반환 시간(Turnaround Time): 도착부터 완료까지 걸린 전체 시간
  • 기아(Starvation): 어떤 프로세스가 계속 뒤로 밀려 CPU를 받지 못하는 상태
  • nice 값: 리눅스에서 일반 프로세스의 CPU 몫을 조절하는 값. -20이 가장 높고 +19가 가장 낮다
  • 틱(Tick): 커널이 주기적으로 받는 타이머 인터럽트. 스케줄러가 시간을 확인하는 지점이다

스케줄러가 답해야 하는 질문은 두 개다

메모리에는 수많은 프로세스가 CPU를 기다리고 있다. 스케줄러는 매번 두 가지를 정한다. 어떤 프로세스에게 줄 것인가, 그리고 얼마 동안 쥐게 할 것인가. 이 두 결정이 체감 성능의 대부분을 만든다

기다리는 프로세스는 큐에 담긴다. 정확히는 프로세스가 아니라 그 정보를 담은 PCB가 들어간다

                     ┌─ 우선순위 높은 준비큐 ─┐
       준비 상태 ──────┤  ...              ├──▶ CPU 스케줄러 ──▶ 실행
                     └─ 우선순위 낮은 준비큐 ─┘            │
                                                      │   I/O 요청
       대기 상태 ─── HDD 큐 / 네트워크 큐 / 키보드 큐 ◀───────┘
                        │ 인터럽트로 완료 통보
                        └──▶ 준비큐로 복귀

대기 큐가 장치별로 갈리는 이유는 완료 통보가 장치별 인터럽트로 오기 때문이다. 하드디스크 인터럽트가 오면 HDD 큐만 뒤지면 된다

스케줄러의 목표는 하나가 아니다

목표내용
리소스 사용률CPU와 입출력 장치를 놀리지 않는다
오버헤드 최소화스케줄링 계산과 컨텍스트 스위칭에 드는 비용을 줄인다
공평성특정 프로세스만 CPU를 독차지하지 않게 한다
처리량같은 시간에 더 많은 작업을 끝낸다
대기 시간요청부터 실제 실행까지의 시간을 줄인다
응답 시간사용자 입력에 대한 반응을 빠르게 한다

이 목표들은 서로 당긴다. 처리량을 올리려면 한 프로세스에 CPU를 길게 줘야 하고, 응답 시간을 줄이려면 짧게 나눠 줘야 한다. 둘을 동시에 최고로 만들 수는 없으므로 시스템의 성격에 따라 어느 쪽에 무게를 둘지 정한다. 터치스크린 기기는 응답 시간, 과학 계산 서버는 처리량이다

FIFO는 짧은 작업을 긴 작업 뒤에 세운다

먼저 큐에 들어온 순서대로 CPU를 주고, 한 프로세스가 완전히 끝나야 다음이 시작된다. 마트 계산대와 같다. 구현이 단순하고 순서가 예측 가능하다는 것이 장점이고, 30만 원어치를 산 손님 뒤에 아이스크림 하나를 든 손님이 서면 답이 없다는 것이 단점이다

숫자로 보면 차이가 분명하다. 세 프로세스가 동시에 큐에 들어왔고 실행에 필요한 시간이 각각 25, 5, 4일 때 도착 순서대로 실행하는 경우와 짧은 순서로 실행하는 경우를 계산했다

FIFO — 도착 순서 P1, P2, P3
  실행 순서 : P1[0-25] P2[25-30] P3[30-34]
  대기 시간 : P1=0 P2=25 P3=30
  평균 대기 시간 = 55/3 = 18.33

SJF  — 짧은 것 먼저 (P3, P2, P1)
  실행 순서 : P3[0-4] P2[4-9] P1[9-34]
  대기 시간 : P3=0 P2=4 P1=9
  평균 대기 시간 = 13/3 = 4.33

전체 작업량은 34로 같고 순서만 바꿨는데 평균 대기 시간이 18.33에서 4.33으로 줄었다. 짧은 작업 하나가 긴 작업 뒤에 서면 그 작업 혼자 손해를 보는 것이 아니라 평균이 통째로 나빠진다

FIFO는 교과서에만 있는 것이 아니다. 리눅스에는 SCHED_FIFO라는 정책이 실제로 있고, 실시간 처리가 필요한 프로세스가 쓴다. sched(7)은 이 정책의 동작을 이렇게 적는다

A SCHED_FIFO thread runs until either it is blocked by an I/O request,
it is preempted by a higher priority thread, or it calls sched_yield(2).

타임 슬라이스라는 개념 자체가 없다. 커널에게 물어보면 그렇게 답한다

$ ./interval
SCHED_RR  이 태스크의 타임 슬라이스 = 0.100000000 s
SCHED_FIFO 이 태스크의 타임 슬라이스 = 0.000000000 s

sched_rr_get_interval(2)로 현재 태스크의 타임 슬라이스를 물은 결과다. SCHED_RR은 100밀리초를 돌려주고 SCHED_FIFO는 0을 돌려준다. 같은 우선순위끼리는 먼저 들어온 쪽이 끝날 때까지 CPU를 놓지 않는다는 뜻이다

그래서 앞의 계산을 실제 커널에서 재현할 수 있다. CPU 연산 1.8초가 필요한 A와 0.6초가 필요한 B를 코어 하나에 묶고, A가 30밀리초 먼저 도착하게 한 뒤 둘 다 SCHED_FIFO 우선순위 50으로 돌렸다

  0.17s  A(긴 작업)  1/12
  0.32s  A(긴 작업)  2/12
   ... (중략)
  1.74s  A(긴 작업) 11/12
  1.89s  A(긴 작업) 12/12
  1.89s  A(긴 작업) 완료 — 쓴 CPU 시간 1.84s, 반환 시간 1.89s
  2.09s  B(짧은 작업)  1/4
  2.24s  B(짧은 작업)  2/4
  2.39s  B(짧은 작업)  3/4
  2.54s  B(짧은 작업)  4/4
  2.54s  B(짧은 작업) 완료 — 쓴 CPU 시간 0.60s, 반환 시간 2.54s
        전체 2.54s

B는 CPU를 0.6초만 쓰면 되는데 2.54초를 기다렸다. 30밀리초 늦게 도착했다는 이유 하나로 A가 끝날 때까지 한 줄도 실행되지 못했다. 출력에서 A의 진행이 0.93초와 1.13초 사이에 0.2초 끊기는데, 이것은 실시간 프로세스가 CPU를 100% 가져가 시스템을 마비시키지 못하도록 커널이 매 1초 중 50밀리초를 비워 두는 스로틀링이다(/proc/sys/kernel/sched_rt_period_us는 1000000, sched_rt_runtime_us는 950000이었다)

짧은 작업 먼저는 계산은 맞지만 구현이 안 된다

위 계산에서 SJF(Shortest Job First)가 FIFO보다 네 배 나은 평균 대기 시간을 냈다. 그런데 실제 스케줄러에 SJF는 없다. 두 가지가 막는다.

첫째, 어떤 프로세스가 얼마나 실행될지 미리 알 수 없다. 브라우저를 열어 날씨만 보고 닫을지 두 시간을 쇼핑할지는 사용자가 정한다. 스케줄러는 그 값을 모른 채 순서를 정해야 한다

둘째, 긴 작업이 영원히 밀린다. 짧은 작업이 계속 들어오면 긴 작업은 큐 앞으로 나오지 못한다. 이것이 기아다. 표준적인 대응은 에이징(aging)으로, 큐에서 오래 기다린 프로세스의 우선순위를 시간에 비례해 올려 준다. 기다림 자체가 우선순위가 되게 만드는 장치다

여기서 알고리즘을 가르는 축 하나를 짚어 둬야 한다. 실행 중인 프로세스에게서 CPU를 빼앗을 수 있는가다

구분알고리즘성질
비선점FIFO, SJF한 번 CPU를 주면 스스로 놓을 때까지 기다린다
선점SRTF, 라운드 로빈, MLFQ스케줄러가 언제든 빼앗을 수 있다

SJF에도 선점형이 있다. SRTF(Shortest Remaining Time First)는 실행 중에 더 짧은 작업이 도착하면 즉시 교체한다. 남은 시간을 알아야 한다는 첫 번째 문제는 그대로 남으므로 실전 스케줄러가 되지는 못했다. 반면 선점이라는 성질 자체는 그다음 알고리즘 전부가 물려받는다

라운드 로빈은 타임 슬라이스를 쥐여 주고 뺏는다

FIFO의 문제는 한 프로세스가 끝날 때까지 다음이 못 온다는 것이다. 그러면 시간을 잘라서 주면 된다. 정해진 시간이 지나면 강제로 빼앗아 큐 맨 뒤로 보내는 것이 라운드 로빈이다

작업 시간이 25, 4, 10인 세 프로세스를 타임 슬라이스 10으로 돌리면 이렇게 된다

FIFO — 도착 순서 P1, P2, P3
  실행 순서 : P1[0-25] P2[25-29] P3[29-39]
  대기 시간 : P1=0 P2=25 P3=29
  평균 대기 시간 = 54/3 = 18.00

라운드 로빈 — 타임 슬라이스 10
  실행 순서 : P1[0-10] P2[10-14] P3[14-24] P1[24-34] P1[34-39]
  대기 시간 : P1=14 P2=10 P3=14
  평균 대기 시간 = 38/3 = 12.67

P1은 세 번에 나눠 실행되고 그 사이에 P2와 P3가 끼어든다. 평균 대기 시간이 18.00에서 12.67로 줄었다. 다만 전체 완료 시각은 39로 같고, 실제 시스템에서는 여기에 컨텍스트 스위칭 비용이 더 붙는다. 평균 대기 시간이 비슷하게 나오는 상황이라면 라운드 로빈 쪽이 오히려 손해다

리눅스에는 이것도 그대로 있다. SCHED_RR은 같은 우선순위끼리 100밀리초씩 돌아가며 실행한다. 앞의 FIFO 실험과 완전히 같은 작업을 정책만 바꿔 돌렸다

SCHED_RR
  0.25s  A(긴 작업)  1/12
  0.35s  B(짧은 작업)  1/4
  0.60s  A(긴 작업)  2/12
  0.70s  B(짧은 작업)  2/4
  0.86s  A(긴 작업)  3/12
  0.95s  B(짧은 작업)  3/4
  1.21s  A(긴 작업)  4/12
  1.30s  B(짧은 작업)  4/4
  1.31s  B(짧은 작업) 완료 — 쓴 CPU 시간 0.61s, 반환 시간 1.31s
   ... (A는 계속)
  2.53s  A(긴 작업) 완료 — 쓴 CPU 시간 1.82s, 반환 시간 2.53s

A와 B가 번갈아 나온다. 리눅스 기본 정책인 SCHED_OTHER까지 포함해 셋을 나란히 놓으면 이렇다

정책A 반환 시간 (CPU 1.8s 필요)B 반환 시간 (CPU 0.6s 필요)평균 반환 시간
SCHED_FIFO1.89s2.54s2.22s
SCHED_RR2.53s1.31s1.92s
SCHED_OTHER2.41s1.24s1.83s

긴 작업 A는 FIFO에서 가장 빨리 끝난다. 아무도 방해하지 않으니 당연하다. 짧은 작업 B는 FIFO에서 2.54초, 나머지 둘에서 1.3초 안팎으로 두 배 차이가 난다. 평균 반환 시간은 FIFO가 가장 나쁘다. 선점을 도입하면 긴 작업이 조금 손해 보고 짧은 작업이 크게 이득을 본다는 것이 교과서의 설명이고, 그 손익이 숫자로 그대로 나온다

타임 슬라이스를 줄이면 I/O 장치가 놀지 않는다

타임 슬라이스를 얼마로 잡을지는 프로세스의 성격에 따라 답이 달라진다. 프로세스는 대략 두 부류다. CPU 연산에 시간을 거의 다 쓰는 CPU-bound와, 잠깐 계산하고 오래 기다리는 I/O-bound다. 앞은 처리량이 중요하고 뒤는 응답 속도가 중요하다

둘이 코어 하나를 나눠 쓸 때 타임 슬라이스가 크면 I/O-bound 쪽이 손해를 본다. 입출력이 끝나 다시 계산할 준비가 됐는데 CPU-bound 프로세스의 긴 슬라이스가 끝날 때까지 기다려야 하고, 그동안 입출력 장치는 논다

이 상황을 만들어 실제로 쟀다. CPU만 쓰는 프로세스 하나와 “CPU 10밀리초 → 입출력 100밀리초”를 반복하는 프로세스 하나를 코어 하나에 묶고, /proc/sys/kernel/sched_rr_timeslice_ms를 바꿔 가며 10초 동안 입출력이 실제로 진행된 시간의 비율을 계산했다

CPU만 쓰는 프로세스 1개 + (CPU 10ms → I/O 100ms) 반복 프로세스 1개, 코어 1개, 10초

   1000 ms | I/O 사용률  16.4% | CPU 작업 처리량 17059 단위 | CPU 프로세스가 뺏긴 횟수    22
    300 ms | I/O 사용률  32.7% | CPU 작업 처리량 16780 단위 | CPU 프로세스가 뺏긴 횟수    43
    100 ms | I/O 사용률  46.4% | CPU 작업 처리량 16633 단위 | CPU 프로세스가 뺏긴 횟수    57
     30 ms | I/O 사용률  65.5% | CPU 작업 처리량 16171 단위 | CPU 프로세스가 뺏긴 횟수    92
     10 ms | I/O 사용률  73.7% | CPU 작업 처리량 16309 단위 | CPU 프로세스가 뺏긴 횟수   127
      1 ms | I/O 사용률  80.9% | CPU 작업 처리량 16415 단위 | CPU 프로세스가 뺏긴 횟수   179

타임 슬라이스를 1000밀리초에서 1밀리초로 줄이니 입출력 장치가 일한 시간이 16.4%에서 80.9%로 다섯 배 늘었다. CPU는 어느 경우에나 쉬지 않고 일했으므로 CPU 사용률은 계속 100%에 가깝다. 즉 타임 슬라이스를 줄여서 얻은 것은 공짜에 가까운 이득이다. 놀고 있던 자원을 일하게 만든 것이지 CPU에서 빼앗아 온 것이 아니다

측정한 값은 이 워크로드에 한정된다. 입출력 100밀리초, CPU 10밀리초라는 비율을 바꾸면 곡선의 모양도 바뀐다. 여기서 확인한 것은 비율의 방향이지 특정 퍼센트가 아니다

작은 타임 슬라이스의 오버헤드는 생각보다 늦게 온다

위 표의 오른쪽 두 열을 보면 이야기가 하나 더 있다. 타임 슬라이스를 1000밀리초에서 1밀리초로 줄이는 동안 강제 전환은 22회에서 179회로 여덟 배 늘었는데, CPU 작업 처리량은 17,059에서 16,415로 3.8%밖에 줄지 않았다

프로세스를 늘리면 달라질 것 같아 CPU만 쓰는 프로세스 여덟 개를 코어 하나에 몰아넣고 다시 쟀다

코어 1개에서 CPU만 쓰는 프로세스 8개를 10초 동안 돌린다

  타임 슬라이스   100 ms | 총 처리량  19001 단위 | 총 강제 전환     119회
  타임 슬라이스    10 ms | 총 처리량  18899 단위 | 총 강제 전환     820회
  타임 슬라이스     1 ms | 총 처리량  18939 단위 | 총 강제 전환    2392회

전환 횟수는 20배가 됐는데 처리량은 측정 오차 안에서 움직이지 않았다. 컨텍스트 스위칭 한 번이 수 마이크로초라면 2,392회는 10초 중 십수 밀리초, 0.1% 남짓이다. 계산이 맞는다

그런데 숫자 하나가 예상과 어긋났다. 타임 슬라이스를 1밀리초로 잡았으면 코어가 꽉 찬 상태에서 초당 1,000번쯤 전환돼야 한다. 10초에 2,392회는 초당 239회이고, 전환 간격으로 환산하면 약 4.2밀리초다. 요청한 1밀리초의 네 배다. 나는 처리량이 눈에 띄게 떨어질 것이라고 보고 이 실험을 짰는데, 떨어지지 않은 이유가 오버헤드가 작아서가 아니라 애초에 타임 슬라이스가 요청한 만큼 작아지지 않았기 때문일 수 있었다

커널 설정을 확인했다

$ zcat /proc/config.gz | grep -E '^CONFIG_HZ'
CONFIG_HZ_250=y
CONFIG_HZ=250

CONFIG_HZ가 250이면 타이머 인터럽트가 초당 250번, 즉 4밀리초마다 들어온다. 관측한 전환 간격 4.2밀리초는 이 값과 거의 같다. 스케줄러가 타임 슬라이스를 다 썼는지 확인하는 지점이 이 틱이고, 틱과 틱 사이에는 강제로 빼앗을 계기가 없다는 것이 내 해석이다. 틱 주기보다 짧은 타임 슬라이스를 요청해도 그대로 반영되지 않는다는 뜻인데, 이 인과를 명시한 문서를 찾지는 못했다. sched_rr_get_interval(2)은 기본값이 100밀리초이고 Linux 3.9부터 /proc/sys/kernel/sched_rr_timeslice_ms로 조절할 수 있다는 것까지만 적는다

그래서 “타임 슬라이스를 너무 작게 하면 배보다 배꼽이 커진다”는 경고는 조건을 달아야 한다. 밀리초 단위에서는 그런 일이 일어나지 않고, 애초에 커널이 틱보다 잘게 자르지도 않는다. 오버헤드가 실제로 문제가 되는 지점은 전환 자체의 비용보다 캐시와 TLB가 매번 식는 쪽이며, 이것은 프로세스 수와 작업 특성에 따라 달라진다

측정은 전부 코어 하나에 묶어서 했다. 코어가 여러 개면 스케줄러는 큐를 코어마다 따로 두고 주기적으로 부하를 옮기는 일을 추가로 하며, 그 비용과 캐시 지역성은 이 글에서 다루지 않았다

MLFQ는 큐를 여러 개 두고 프로세스를 아래로 내린다

CPU-bound와 I/O-bound에 서로 다른 타임 슬라이스를 주면 양쪽 다 만족시킬 수 있다. 문제는 어느 쪽인지 미리 알 수 없다는 것인데, 행동을 보면 알 수 있다. 슬라이스를 다 쓰기 전에 스스로 CPU를 놓으면 I/O-bound일 가능성이 높고, 슬라이스를 초과해 강제로 빼앗기면 CPU-bound일 가능성이 높다. 이 시리즈 2편에서 voluntary_ctxt_switches와 nonvoluntary_ctxt_switches로 갈라 봤던 바로 그 신호다

MLFQ(Multi-Level Feedback Queue)는 이 관찰을 규칙으로 만든다. 우선순위가 다른 큐를 여러 개 두고, 위쪽 큐일수록 우선순위가 높고 타임 슬라이스가 짧다. 규칙은 다섯 개다(OSTEP, Scheduling: The Multi-Level Feedback Queue)

Rule 1: If Priority(A) > Priority(B), A runs (B doesn't).
Rule 2: If Priority(A) = Priority(B), A & B run in round-robin fashion
        using the time slice (quantum length) of the given queue.
Rule 3: When a job enters the system, it is placed at the highest
        priority (the topmost queue).
Rule 4: Once a job uses up its time allotment at a given level
        (regardless of how many times it has given up the CPU),
        its priority is reduced (i.e., it moves down one queue).
Rule 5: After some time period S, move all the jobs in the system
        to the topmost queue.

Rule 3과 Rule 4가 자동 판별 장치다. 모든 프로세스는 가장 높은 큐에서 시작하고, 할당된 시간을 다 써 버리면 한 칸 내려간다. CPU-bound 프로세스는 몇 번 만에 아래로 내려가 긴 타임 슬라이스를 받고 연속으로 일하게 되고, I/O-bound 프로세스는 슬라이스를 다 쓰기 전에 스스로 멈추므로 위쪽 큐에 남아 빠른 응답을 유지한다

Rule 5가 없으면 이 구조는 무너진다. OSTEP은 그 이유를 이렇게 적는다

if there are "too many" interactive jobs in the system, they will
combine to consume all CPU time, and thus long-running jobs will
never receive any CPU time (they starve).

위쪽 큐가 계속 차 있으면 아래로 내려간 CPU-bound 프로세스는 영영 실행되지 않는다. 그래서 일정 시간마다 전부 최상위 큐로 끌어올린다. 앞에서 SJF의 기아를 막는 장치로 언급한 에이징이 MLFQ에서는 이 형태로 들어간다. 규칙 넷까지만 알고 있으면 MLFQ가 기아를 어떻게 피하는지 설명할 수 없다

리눅스는 EEVDF, 윈도우는 우선순위 32단계를 쓴다

MLFQ는 잘 만든 설계지만 오늘날 쓰이는 스케줄러가 전부 MLFQ인 것은 아니다

리눅스는 2.6.23에서 CFS를 도입하며 우선순위 큐를 여러 개 두는 방식 자체를 버렸다(CFS Scheduler, Linux Kernel documentation). CFS는 이상적인 다중 작업 CPU를 가정하고 각 프로세스가 “받았어야 할 CPU 시간”을 가상 런타임으로 추적해, 그 값이 가장 작은 프로세스를 고른다. 지금까지 가장 적게 실행된 것을 다음에 실행한다는 규칙 하나다. 6.6에서는 이것이 EEVDF(Earliest Eligible Virtual Deadline First)로 바뀌었다. 커널 문서는 선택 과정을 두 단계로 설명한다. 먼저 받을 몫보다 덜 받은(lag가 0 이상인) 프로세스만 후보로 남기고, 그중 가상 마감 시각이 가장 이른 것을 고른다(EEVDF Scheduler, Linux Kernel documentation)

여기서 공평성은 “똑같이 나눠 준다”가 아니라 “정해진 몫만큼 나눠 준다”다. 몫을 조절하는 값이 nice이고, sched(7)은 그 효과를 수치로 못 박는다

each unit of difference in the nice values of two processes results
in a factor of 1.25 in the degree to which the scheduler favors the
higher priority process.

한 단계에 1.25배라면 다섯 단계 차이는 1.25의 5제곱인 3.05배, 열 단계 차이는 9.31배가 나와야 한다. 코어 하나에 CPU만 쓰는 프로세스 두 개를 6초 동안 올려 두고 각자가 실제로 쓴 CPU 시간을 쟀다

=== 대조군: 둘 다 nice 0 ===
nice  0 프로세스가 쓴 CPU 시간 : 3.00s
nice  0 프로세스가 쓴 CPU 시간 : 3.01s
비율 1.00 : 1

=== nice 0 대 nice 5 ===
nice  0 프로세스가 쓴 CPU 시간 : 4.52s
nice  5 프로세스가 쓴 CPU 시간 : 1.48s
비율 3.05 : 1

=== nice 0 대 nice 10 ===
nice  0 프로세스가 쓴 CPU 시간 : 5.42s
nice 10 프로세스가 쓴 CPU 시간 : 0.59s
비율 9.23 : 1

3.05와 9.23이 나왔다. 문서가 예고한 3.05와 9.31에 각각 소수점 둘째 자리, 1% 안쪽으로 맞는다. 스케줄러가 공평성을 어떻게 정의하고 있는지가 이 세 줄에 들어 있다. 같은 값이면 정확히 반씩, 다른 값이면 정해진 배수만큼이다

윈도우는 다른 길을 갔다. 스레드마다 0에서 31까지의 우선순위를 두고, 실행 가능한 스레드 중 가장 높은 우선순위 집단에게만 라운드 로빈으로 타임 슬라이스를 나눠 준다. 더 높은 우선순위 스레드가 준비되면 실행 중인 스레드는 슬라이스를 다 쓰지 못한 채 즉시 밀려난다(Scheduling Priorities, Microsoft Learn). 여기에 상황에 따라 우선순위를 일시적으로 올려 주는 부스트가 붙는다. 큐를 여러 개 두고 우선순위를 오르내린다는 점에서 MLFQ에 가깝지만, 리눅스처럼 몫을 계산해 배분하는 구조는 아니다

교과서의 FIFO와 라운드 로빈이 리눅스에서 사라진 것도 아니다. SCHED_FIFO와 SCHED_RR은 실시간 우선순위 1~99를 쓰는 정책으로 남아 있고, 이 우선순위를 가진 태스크는 일반 태스크보다 항상 먼저 실행된다. 오디오 처리나 산업 제어처럼 “언제 실행되는지”가 “얼마나 빨리 끝나는지”보다 중요한 작업이 쓴다. 이 글의 실험이 정책을 바꿔 가며 같은 워크로드를 돌릴 수 있었던 것도 이 정책들이 실제로 동작하기 때문이다

스케줄러방식우선순위 조절
교과서 MLFQ우선순위 큐 여러 개, 슬라이스 초과 시 강등주기적 전체 부스트
리눅스 EEVDF (6.6~)lag와 가상 마감 시각으로 다음 태스크 선택nice 값이 몫의 가중치
리눅스 SCHED_FIFO/SCHED_RR실시간 우선순위 1~99, 일반 태스크보다 우선프로그램이 직접 지정
윈도우우선순위 0~31, 최상위 집단끼리 라운드 로빈상황별 일시적 부스트

마무리

FIFO에서 MLFQ까지의 흐름은 각 단계가 앞 단계의 어떤 문제를 풀었는지 보여 주기 때문에 여전히 배울 값이 있다. 짧은 작업이 뒤에 서면 평균이 나빠진다는 것, 그래서 선점이 필요하다는 것, 타임 슬라이스를 줄이면 놀던 입출력 장치가 일하기 시작한다는 것은 실제 커널에서 그대로 재현된다

바뀐 것은 마지막 칸이다. 오늘날 스케줄러는 우선순위 큐를 오르내리는 대신 각 프로세스가 받아야 할 몫을 계산해서 배분한다. 리눅스에서 nice 값 5를 주면 정확히 3.05배 덜 받는다는 사실이 그 계산이 실재한다는 증거다

다음 편 예고

다음 편은 동기화와 교착상태다. 여러 프로세스가 같은 자원을 건드릴 때 무엇이 깨지는지, 세마포어와 모니터가 그것을 어떻게 막는지, 그리고 자바의 synchronized가 실제로 잠그는 대상이 무엇인지를 다룬다

출처와 범위

이 시리즈는 인프런의 그림으로 쉽게 배우는 운영체제(감자님) 강의를 따라 정리한 것이고, 강의 전체를 일곱 편으로 나눈 세 번째 편이다. 알고리즘 구성과 예시 수치의 출처는 강의이며, 현재 커널과 운영체제의 동작을 말하는 문장은 본문에 건 man 페이지·커널 문서·벤더 문서로 확인했다. 평균 대기 시간 계산은 직접 만든 파이썬 스크립트로 검산했고, 정책별 반환 시간·I/O 사용률·nice 배분 측정은 CONFIG_HZ 250, 커널 6.18인 2코어 x86-64 리눅스 가상 머신에서 실행한 결과 그대로다. 물리 장비나 다른 CONFIG_HZ 값에서는 숫자가 달라진다. 측정에 쓴 C 프로그램과 스크립트는 본문에 인용한 부분 외에는 싣지 않았고 공개 저장소도 없다

참고 자료