이번 장은 비례 배분(Proportional Share) 스케줄링을 다룹니다. 앞의 장들이 반환 시간, 응답 시간, 대화형 작업의 반응성에 초점을 맞췄다면, 이 장의 핵심 질문은 조금 다릅니다. 여러 작업이 있을 때 CPU를 정해진 비율로 나누어 줄 수 있는가가 주제입니다.
OSTEP은 그 대표적인 방법으로 Lottery Scheduling을 소개합니다. 이름 그대로 CPU를 사용할 다음 작업을 추첨으로 고르되, 각 작업이 가진 추첨권(ticket)의 수가 CPU 몫을 나타냅니다.
한 문장 요약
Lottery scheduling은 각 작업에 추첨권을 나누어 주고, 매 타임 슬라이스마다 무작위 추첨으로 실행할 작업을 골라 장기적으로 티켓 비율에 가까운 CPU 배분을 달성하는 스케줄링 방식입니다.
핵심 질문
| 질문 | 핵심 답변 |
|---|---|
| CPU를 정해진 비율로 배분하려면 어떻게 해야 하는가? | 각 작업에 추첨권을 나누어 주고, 작업의 티켓 수를 전체 티켓 수로 나눈 값이 CPU 몫이 되게 합니다. |
| Lottery scheduling은 어떻게 다음 작업을 고르는가? | 전체 티켓 범위에서 난수를 하나 뽑고, 준비 큐를 순회하며 누적 티켓 수가 당첨 번호를 넘는 첫 작업을 실행합니다. |
| 무작위 방식인데 공정한가? | 짧은 구간에서는 목표 비율과 어긋날 수 있지만, 실행 시간이 길어질수록 실제 CPU 배분은 티켓 비율에 가까워집니다. |
| Stride scheduling은 왜 등장하는가? | Lottery scheduling의 무작위성을 없애고 비례 배분을 결정론적으로 달성하기 위해 등장합니다. |
비례 배분과 티켓
Lottery scheduling에서 티켓은 CPU 지분을 표현하는 단위입니다. 예를 들어 A가 75장, B가 25장의 티켓을 가지고 있으면 전체 티켓은 100장이고, 장기적으로 A는 약 75%, B는 약 25%의 CPU를 받게 됩니다.
| 작업 | 티켓 수 | 기대 CPU 몫 |
|---|---|---|
| A | 75 | 75% |
| B | 25 | 25% |
| 전체 | 100 | 100% |
스케줄러는 매 타임 슬라이스마다 전체 티켓 중 하나를 뽑고, 그 티켓을 가진 작업을 실행합니다. 중요한 점은 이 방식이 매 순간 정확한 비율을 보장하는 것이 아니라 확률적으로 장기 비율에 가까워지는 방식이라는 점입니다.
추첨 과정
준비 큐에 A, B, C가 있고 티켓 수가 각각 100, 50, 250이라고 가정해 보겠습니다. 전체 티켓은 400장입니다. 당첨 번호가 300이면, 누적합이 300을 처음 넘는 C가 선택됩니다.
핵심 로직은 다음과 같이 정리할 수 있습니다.
|
1 2 3 4 5 6 7 8 |
counter = 0 winner = random(0, total_tickets) for job in ready_queue: counter += job.tickets if counter > winner: run(job) break |
이 구현은 관리해야 할 상태가 적습니다. 작업별 티켓 수와 전체 티켓 수만 있으면 됩니다. 새 작업이 들어와도 해당 작업의 티켓 수를 추가하고 전체 티켓 수만 갱신하면 됩니다.
무작위성의 의미
Lottery scheduling은 무작위 추첨을 사용하므로 짧은 실행 구간에서는 불공정해 보일 수 있습니다. A와 B가 같은 티켓 수를 가지고 있어도, 짧은 시간 동안은 한쪽이 더 자주 뽑힐 수 있습니다.
| 실행 기간 | 특징 |
|---|---|
| 짧음 | 운의 영향이 커서 목표 비율과 차이가 날 수 있습니다. |
| 김 | 추첨 횟수가 늘어나 실제 비율이 목표 비율에 가까워집니다. |
이 특성 때문에 lottery scheduling은 즉각적인 공정성보다 장기적인 확률 공정성이 중요한 상황에 더 잘 맞습니다.
티켓을 다루는 기법
OSTEP은 티켓을 더 유연하게 다루기 위한 세 가지 기법을 소개합니다.
| 기법 | 의미 | 사용 예 |
|---|---|---|
| Ticket currency | 사용자나 그룹이 자기 기준의 로컬 티켓을 쓰고, 시스템이 전역 티켓으로 환산합니다. | 사용자별 몫은 같게 유지하되, 각 사용자가 자기 작업 안에서 자유롭게 지분을 나눕니다. |
| Ticket transfer | 한 작업이 다른 작업에 티켓을 잠시 넘깁니다. | 클라이언트가 서버에 요청을 맡긴 동안 서버가 클라이언트의 티켓까지 받아 빠르게 처리합니다. |
| Ticket inflation | 작업이 자신의 티켓 수를 일시적으로 늘리거나 줄입니다. | 서로 신뢰 가능한 환경에서 급한 작업이 자기 CPU 몫을 임시로 키웁니다. |
특히 ticket inflation은 신뢰할 수 없는 환경에서는 위험합니다. 아무 작업이나 티켓 수를 마음대로 늘릴 수 있다면 CPU를 독점할 수 있기 때문입니다.
Stride Scheduling
Stride scheduling은 lottery scheduling과 같은 비례 배분 목표를 결정론적으로 달성하려는 방식입니다. 핵심 값은 stride와 pass입니다.
| 값 | 의미 |
|---|---|
tickets |
작업의 CPU 지분입니다. |
stride |
큰 수 / tickets로 계산합니다. 티켓이 많을수록 stride는 작아집니다. |
pass |
지금까지 CPU를 얼마나 받았는지 나타내는 누적 값입니다. |
스케줄러는 항상 pass가 가장 작은 작업을 실행하고, 실행 후 그 작업의 pass에 stride를 더합니다.
예를 들어 A=100 tickets, B=50 tickets, C=250 tickets이고 큰 수를 10000으로 잡으면 stride는 A=100, B=200, C=40입니다. 한 주기에서 C는 5번, A는 2번, B는 1번 실행되며, 이는 티켓 비율 250:100:50과 일치합니다.
Lottery와 Stride 비교
| 구분 | Lottery scheduling | Stride scheduling |
|---|---|---|
| 선택 방식 | 무작위 추첨 | 가장 작은 pass 선택 |
| 비례 배분 | 장기적으로 근접 | 짧은 구간에서도 더 정확 |
| 상태 관리 | 작업별 티켓 수와 전체 티켓 수 정도면 충분 | 각 작업의 pass, stride를 유지해야 함 |
| 새 작업 추가 | 상대적으로 쉬움 | 새 작업의 초기 pass 설정이 민감함 |
| 핵심 장점 | 단순함, 낮은 상태 비용, 동적 변화에 강함 | 결정론적이고 비율 오차가 작음 |
실습 코드
이 장의 homework 시뮬레이터는 ostep-homework/cpu-sched-lottery/lottery.py입니다. 작업 목록 형식은 다음과 같습니다.
|
1 |
실행시간:티켓수 |
예를 들어 10:100,20:100은 실행 시간이 10인 작업과 20인 작업이 각각 100장의 티켓을 가진다는 뜻입니다. 숙제를 풀 때는 먼저 -c 없이 직접 계산하고, 이후 -c로 결과를 검산하는 흐름이 좋습니다.
정리
Lottery scheduling은 CPU 몫을 티켓 수로 표현하고 무작위 추첨으로 다음 실행 작업을 고르는 비례 배분 스케줄러입니다. 구현이 단순하고 상태가 적으며, 작업이 오래 실행될수록 실제 CPU 배분은 티켓 비율에 가까워집니다.
하지만 짧은 실행 구간에서는 운의 영향으로 불공정할 수 있고, 티켓을 누구에게 얼마나 줄지 정하는 문제도 쉽지 않습니다. Stride scheduling은 같은 목표를 결정론적으로 달성하지만, pass 같은 상태를 유지해야 하므로 동적인 작업 추가와 상태 초기화가 더 까다롭습니다.
따라서 이 장의 핵심은 CPU 스케줄링 목표가 항상 반환 시간이나 응답 시간만은 아니며, 때로는 정해진 지분을 얼마나 단순하고 유연하게 보장할 수 있는지도 중요하다는 점입니다.
