OSTEP 비례 배분 스케줄링: Lottery·Stride와 Linux EEVDF 비교

OSTEP의 ‘Scheduling: Proportional Share’를 읽으며 Lottery와 Stride 스케줄링을 정리했다. 두 방식은 각 작업에 티켓이라는 지분을 주고 CPU 시간을 그 비율에 가깝게 나누려 한다.

예전 글에서는 이를 Linux CFS와 곧바로 비교했지만, 현재 Linux 스케줄러 설명에는 업데이트가 필요하다. Linux 커널은 6.6부터 CFS의 선택 방식을 EEVDF로 전환하기 시작했다. Lottery·Stride는 비례 배분을 배우기 위한 모델이고, CFS·EEVDF는 실제 커널의 다양한 제약을 다루는 설계다.

비례 배분 문제

작업 A에 75장, B에 25장의 티켓을 주면 목표 지분은 75%와 25%다. 여기에는 서로 다른 두 질문이 있다.

1. 긴 시간 동안 목표 비율에 가까워지는가?
2. 짧은 시간에도 한 작업이 지나치게 오래 기다리지 않는가?

Lottery는 첫 질문에 확률적으로 답하고, Stride는 누적값으로 더 결정적인 답을 준다.

Lottery Scheduling

매 스케줄링 시점에 전체 티켓 범위에서 임의의 번호를 뽑고 그 티켓을 가진 작업을 실행한다.

A: 75 tickets  → [0, 74]
B: 25 tickets  → [75, 99]

당첨 번호가 074이면 A, 7599이면 B가 실행된다. 각 추첨은 흔들릴 수 있지만 시행 횟수가 충분히 커지면 실행 비율이 티켓 비율에 가까워질 것으로 기대한다.

winner = random integer in [0, total_tickets)
counter = 0

for each runnable task:
    counter += task.tickets
    if counter > winner:
        run task
        break

장점과 경계

• 아이디어와 기본 구현이 단순하다.
• 티켓 양도·통화 같은 정책을 표현하기 쉽다.
• 짧은 구간에는 운에 따른 편차가 있다.
• 난수와 티켓 합산·탐색 방식이 결과와 비용에 영향을 준다.

“코너 케이스에 강하다”거나 “항상 가볍다”고 일반화할 수는 없다. 티켓 수 변경, 작업 진입·종료, 작은 지분의 대기 시간도 설계해야 한다.

Stride Scheduling

Stride는 무작위 추첨 대신 각 작업의 보폭과 누적 통과값을 사용한다.

stride = large_number / tickets

티켓이 많을수록 stride가 작다. 매번 pass가 가장 작은 작업을 실행하고 그 작업의 pass에 stride를 더한다.

task = queue.remove_min_by_pass()
run(task)
task.pass += task.stride
queue.insert(task)

최소 힙을 쓰면 선택과 재삽입에 O(log N)이 든다. 새 작업의 초기 pass, 정수 나눗셈 오차와 누적값 overflow를 어떻게 처리할지가 구현의 핵심이다.

Lottery와 Stride 비교

기준	Lottery	Stride
지분 반영	확률적 추첨	누적 pass의 결정적 선택
짧은 구간 편차	상대적으로 큼	상대적으로 작음
주요 상태	티켓과 난수	티켓, stride, pass
새 작업 처리	티켓 집합에 추가	초기 pass 정책 필요
구현 자료구조	리스트·트리 등	최소 힙·균형 트리 등

어느 쪽도 시간 제한, I/O 대기, 멀티코어, 캐시 친화성과 지연 요구를 이 표 하나로 해결하지는 않는다.

Linux CFS와 EEVDF는 어떻게 이어질까

CFS는 실행한 시간을 가중치로 보정한 vruntime을 사용해 덜 받은 작업을 선택하는 설계로 설명돼 왔다. nice 값에 대응하는 가중치가 상대적인 CPU 지분에 영향을 준다.

Linux 커널 문서에 따르면 6.6부터 선택 알고리즘은 EEVDF(Earliest Eligible Virtual Deadline First)로 전환되기 시작했다. EEVDF는 가상 런타임에서 계산한 lag로 CPU를 받을 자격이 있는 작업을 가리고, 그중 가상 deadline이 가장 이른 작업을 선택한다. 짧은 time slice를 요청하는 지연 민감 작업의 응답성도 고려할 수 있다.

따라서 “현재 Linux 기본 스케줄러는 red-black tree에서 vruntime이 가장 작은 작업을 고르는 CFS”라고만 설명하면 버전에 따라 낡은 설명이 된다. 실제 서버를 분석할 때는 커널 버전, scheduling class와 cgroup CPU 설정을 함께 확인해야 한다.

DevOps 관점에서 가져갈 것

Lottery의 티켓을 Kubernetes CPU request·limit나 cgroup weight와 같은 것으로 직접 등치시키지는 않는다. 대신 공유 자원에서 확인할 질문을 얻을 수 있다.

• 설정한 가중치가 실제 처리량과 CPU 시간에 어떤 비율로 반영되는가?
• 짧은 관측 구간에서 특정 워크로드가 굶고 있지 않은가?
• CPU quota 제한과 CPU weight 경쟁을 구분했는가?
• 멀티코어·NUMA·캐시와 애플리케이션 병목을 함께 봤는가?

책의 단순한 모델은 운영 설정값을 복사하는 답이 아니라, 지분·공정성·지연을 서로 다른 지표로 관찰하게 만드는 출발점으로 남았다.

참고 자료

• OSTEP: Scheduling — Proportional Share
• Linux kernel: EEVDF Scheduler
• Linux kernel: CFS Scheduler