프로그래밍공부(Programming Study)/CS-운영체제(OS)

OSTEP: 9. Scheduling: Proportional Share

Chann._.y 2025. 10. 7.

728x90

이 글은 OSTEP(Operating Systems: Three Easy Pieces)의 ‘Scheduling: Proportional Share’ 문서를 직접 읽고 정리한 내용이다.
DevOps 관점(왜 중요한가/적용 방식)은 글 맨 마지막에 의견(Opinion) 으로 분리했다.

1) Proportional-Share 스케줄링 개요

목표: 각 작업(프로세스/태스크)이 CPU를 비율대로 나누어 갖도록 설계한다.
핵심 아이디어: 각 작업에 티켓(ticket) 또는 가중치(weight) 를 부여하고, 그 비율이 기대 자원 점유율이 되도록 스케줄링한다.

2) 핵심 개념 정리

2.1 Ticket(티켓)

작업이 가져갈 지분을 수치화한 토큰.
예: A=75장, B=25장 → 장기적으로 A≈75%, B≈25%의 CPU 획득 기대.

2.2 Lottery Scheduling(로터리)

매 타임슬라이스마다 전체 티켓 범위에서 무작위 당첨 번호를 뽑고, 그 구간에 속한 작업을 실행한다.
반복 횟수가 많아질수록 티켓 비율에 수렴하는 확률적 공정성.

2.3 Stride Scheduling(스트라이드)

난수 없이 결정적(deterministic) 으로 비례 배분을 달성한다.
각 작업에 stride = K(큰 상수) / tickets를 부여하고, 매번 pass(누적값) 가 가장 작은 작업을 실행한 뒤 pass += stride.

2.4 CFS(Completely Fair Scheduler)

Linux의 기본 스케줄러. vruntime(가상 런타임) 을 사용해 “덜 받은 태스크”를 우선 실행하는 공정 지향 구현.
각 태스크는 nice/weight로 상대 지분을 갖고, 실제 실행 시간에 weight 보정을 곱해 vruntime을 누적한다. 가장 작은 vruntime이 다음 실행 대상이다.

3) Lottery Scheduling 상세

3.1 동작 절차

1) 각 작업의 티켓 수와 전체 합을 관리한다.
2) [0, total_tickets-1] 범위에서 난수를 뽑아 당첨 티켓을 결정한다.
3) 작업 리스트를 누적합으로 순회하다가 누적합 > 당첨 번호가 되는 지점의 작업이 승자다.

3.2 의사코드(단순 리스트 버전, 들여쓰기 코드)

// winner: [0, total_tickets-1] 범위의 난수
int winner = getrandom(0, total_tickets);
int counter = 0;
node_t* current = head;

while (current) {
  counter += current->tickets;
  if (counter > winner) {
    break;           // current가 승자
  }
  current = current->next;
}
// current를 스케줄

메모: 리스트를 티켓 내림차순으로 유지하면 평균 탐색 단계가 줄어든다.

3.3 장점/제약

장점: 구현이 간단하고 상태 관리가 가볍다. 다양한 코너 케이스에 강하다.
제약: 짧은 시간 구간에서는 기대 비율과 변동(오차) 가 발생할 수 있다.

3.4 직관 예시

A=75, B=25, 20회 추첨 시 B가 4회(20%)만 당첨될 수 있으나, 횟수가 쌓일수록 75:25로 수렴한다.

3.5 티켓 도구 3종

Ticket Currency: 테넌트 내부에서 자체 “통화”로 배분해도 시스템이 전역 통화로 환산해 전체 비례를 유지.
Ticket Transfer: 클라이언트가 서버 호출 시 티켓을 임시 위임해 서버 처리를 가속, 완료 후 회수.
Ticket Inflation: 신뢰된 경계 내부에서 일시적으로 티켓을 늘려 우선순위를 올림(불신 환경에는 부적절).

4) Stride Scheduling 상세

4.1 핵심 규칙

각 작업: stride = K / tickets, 초기 pass = 0.
선택: pass가 가장 작은 작업을 실행.
갱신: 실행 후 pass += stride, 다시 자료구조에 삽입.

4.2 추상 의사코드(min-heap 사용, 들여쓰기 코드)

// 최소 pass 작업 선택 → 실행 → pass 누적 → 재삽입
Task* curr = remove_min(heap_by_pass);  // O(log N)
schedule(curr);
curr->pass += curr->stride;
insert(heap_by_pass, curr);             // O(log N)

4.3 특징/주의

난수 없이 단기/장기 모두 비율을 정확히 맞추는 경향.
min-heap/균형 트리로 각 선택 O(log N).
새 작업 유입 시 초기 pass 설정 정책이 필요하다(공정성 보존).

5) CFS(Completely Fair Scheduler) 상세

5.1 목표

모든 태스크가 공정하게 CPU를 나눠 갖도록 지속적으로 보정한다.

5.2 핵심 메커니즘

vruntime: 실제 실행 시간에 가중치(weight) 를 반영해 누적한 값.
덜 받은 태스크일수록 vruntime 증가가 느려 앞서 실행될 가능성이 크다.
weight와 nice: nice(우선순위) 값에 대응하는 내부 weight(예: nice 0 ≈ 1024).
상대 weight가 지분처럼 작동해 결과적으로 비례 공유에 가깝게 동작한다.
선택 구조: 런큐를 균형 트리(레드-블랙 트리) 로 관리, 가장 작은 vruntime 노드를 O(log N)으로 선택한다.

5.3 특징

결정적 + 연속적 보정: 추첨이 아니라 누적 런타임에 기반한 보정으로 공정성 유지.
실전 지향: 인터랙티브·배치 등 다양한 워크로드에서 안정적인 체감 공정성.

6) Lottery · Stride · CFS 비교

항목	Lottery	Stride	CFS
공정성 방식	확률적 수렴	결정적 비례 유지	연속 보정(vruntime)
단기 공정성	변동성 있음	높음	높음
장기 공정성	비율로 수렴	비율 유지	비례에 근접
구현 난이도	매우 단순	중간(자료구조 필요)	높음(커널, 트리/vruntime)
상태/관리	가벼움	pass 초기값 정책 필요	nice/weight, vruntime 관리
새 작업 유입	자연스러움	초기 pass 전략 필요	vruntime 기준 자연 통합

7) 구현 팁

난수 품질(Lottery): 편향 난수는 공정성을 해친다.
정밀도/Overflow(Stride/CFS): stride·pass·vruntime 누적 시 정밀도와 오버플로를 주의(고정소수/큰 정수 활용).
자료구조(Stride/CFS): min-heap/균형 트리로 O(log N) 선택을 보장.
타임슬라이스/선점 주기: 실제 체감 공정성은 슬라이스 길이, 선점 정책과 결합되어 결정된다.

8) 본문 총정리

티켓/가중치 = 지분이며, 스케줄러는 이를 단기·장기 관점에서 반영하려고 설계된다.
Lottery: 간단·경량, 장기적으로 비례 수렴하나 단기 변동성이 있다.
Stride: 난수 없이 결정적으로 비례 유지, min-heap 등으로 효율 달성.
CFS: vruntime 기반 연속 보정으로 실전 환경에서 안정적 공정성을 제공.

(부록) DevOps 관점 — 왜 중요하고, 어떻게 적용하나

A) 왜 중요한가 (Opinion)

리소스 분쟁의 명시화: “누가 얼마나 가져갈까”를 수치로 합의해 팀 간 마찰을 줄인다.
SLO/요금제 연동: 테넌트/팀/요금제에 따라 목표 CPU 지분을 정의하고 관찰한다.
예측 가능성 확보: 배포·핫픽스·실시간 트래픽 등 중요 순간에 일관된 공정성 제공.

B) 적용 방식

멀티테넌트 CI/빌드팜: 팀/서비스별 티켓(가중치) 로 비율화.
요청-응답 체인 최적화: Ticket Transfer 개념을 아이디어로 삼아, 게이트웨이→백엔드→워커에 “지금 중요한 요청”의 지분을 실어준다.
오버커밋 환경: Stride(또는 Lottery+단기 오차 캡)로 단기 변동성 억제.
신뢰 경계 설계: 외부 테넌트 혼재 환경에서는 Inflation 금지. 내부만 쓰되 시간 제한·승인·감사를 둔다.