지난 시간에는 성능의 관점에서 반환 시간(Turnaround Time)과 응답 시간(Response Time)이라는 두 가지 상충하는 목표를 최적화하기 위한 가정과 방법론들에 대해 학습했다.
이번 시간에는 스케줄링의 목표를 '성능 최적화'에서 '공정성(Fairness)'으로 전환한, 또 다른 중요한 스케줄링 계열인 비례 배분 스케줄러(Proportional Share Scheduler)에 대해 알아볼 것이다.
1. 왜 비례 배분 스케줄러가 필요한가?
지금까지 다룬 STCF, RR, MLFQ와 같은 스케줄러들은 모두 반환 시간이나 응답 시간을 줄이는 것을 주된 목표로 한다. 하지만 시스템을 운영하다 보면, 단순히 빠르게 처리하는 것보다 각 프로세스가 예측 가능하게 자신의 몫만큼의 자원을 보장받는 것이 더 중요할 때가 있다.
예를 들어, 여러 사용자가 비용을 내고 사용하는 클라우드 서버 환경을 생각해보자. 특정 사용자의 작업이 다른 사용자의 작업 때문에 무한정 지연되어서는 안 된다. 각 사용자는 지불한 비용에 상응하는 CPU 시간을 보장받아야 한다. 이처럼 스케줄러의 목표가 성능이 아닌 '공정한 지분 보장'일 때, 비례 배분 스케줄러가 해답이 될 수 있다.
비례 배분 스케줄러의 핵심 목표는 각 작업이 CPU 시간의 특정 비율(percentage)을 얻도록 보장하는 것이다.
2. 기본 개념: 티켓 (Tickets)
비례 배분 스케줄링의 아이디어를 구현하는 가장 기본적인 메커니즘은 티켓이다.
티켓(Tickets): 프로세스가 받아야 할 자원의 몫을 나타내는 추상적인 단위이다.
지분(Share): 전체 티켓 수에서 해당 프로세스가 보유한 티켓의 비율이 곧 그 프로세스의 CPU 시간 지분이 된다.
예시: 프로세스 A가 75개의 티켓을, 프로세스 B가 25개의 티켓을 가지고 있다면, 시스템에 총 100개의 티켓이 있는 셈이다. 따라서 A는 CPU의 75%를, B는 25%를 할당받는 것을 목표로 스케줄링이 이루어진다.
이 티켓 개념을 실제로 구현하는 대표적인 두 가지 알고리즘이 바로 로터리 스케줄링과 스트라이드 스케줄링이다.
3. 로터리 스케줄링 (Lottery Scheduling)
로터리 스케줄링은 이름처럼 '복권 추첨' 방식을 사용하여 스케줄링을 결정하는, 무작위성(Randomness)에 기반한 비례 배분 스케줄러이다.
원리: 스케줄러는 전체 티켓 범위 내에서 무작위로 '당첨 티켓 번호'를 하나 뽑는다. 그리고 해당 번호가 포함된 구간의 티켓을 소유한 프로세스를 다음 타임 슬라이스 동안 실행시킨다.
예시: 총 100개의 티켓(0~99번)이 있고, A가 75개(0~74번), B가 25개(75~99번)를 가졌다고 하자. 스케줄러가 무작위로 뽑은 번호가 63이면 A가, 85이면 B가 실행된다. 이 과정을 반복하면, 실행 횟수가 길어질수록 각 프로세스는 자신의 티켓 비율(A:B = 3:1)에 근접한 CPU 시간을 할당받게 된다.
 |
| Lottery Scheduling |
로터리 스케줄링의 부가 기능
티켓 통화 (Ticket Currency): 사용자가 자신에게 할당된 총 티켓을 자신만의 '통화' 단위로 여러 프로세스에 분배할 수 있는 기능이다. 시스템은 이 사용자 단위 통화를 전역 티켓 값으로 자동 변환하여 유연성을 높인다.
티켓 양도 (Ticket Transfer): 한 프로세스가 다른 프로세스에게 자신의 티켓을 일시적으로 넘겨줄 수 있는 기능이다. 예를 들어, 클라이언트 프로세스가 서버 프로세스에게 빠른 처리를 요청하며 자신의 티켓을 양도했다가, 작업이 끝나면 돌려받는 방식으로 동작할 수 있다.
티켓 인플레이션 (Ticket Inflation): 프로세스가 스스로 자신의 티켓 수를 늘리거나 줄일 수 있는 기능이다. 신뢰하는 프로세스들 사이에서는 유용할 수 있지만, 악의적인 프로세스가 자신의 티켓을 무한정 늘려 시스템을 독점할 위험이 존재한다.
장점과 단점
장점: 로터리 스케줄링의 가장 큰 장점은 구현의 단순성이다. 필요한 것은 난수 생성기, 프로세스 목록, 그리고 전체 티켓 수뿐이다. 또한 새로운 프로세스가 추가되어도 전체 티켓 수만 갱신하면 되므로, 별도의 복잡한 전역 상태를 관리할 필요가 없다.
단점: 무작위성에 의존하기 때문에, 특히 실행 시간이 짧은 경우에는 정확한 비율을 보장하지 못하고 불공정성(Unfairness)이 발생할 수 있다. 두 작업의 티켓 수가 같더라도, 운에 따라 한 작업이 다른 작업보다 훨씬 먼저 끝날 수 있다.
불공정성 지표 (Unfairness Metric, U): 로터리 스케줄링의 공정성은 '첫 번째 작업이 완료된 시간 / 두 번째 작업이 완료된 시간'으로 측정할 수 있다. 이 값이 1에 가까울수록 공정하다고 본다. 작업 실행 시간이 충분히 길어질수록(즉, 많은 타임 슬라이스를 가질수록) U는 1에 수렴하지만, 짧은 작업에서는 운에 따라 큰 편차를 보인다.
 |
| Fairness Metric |
4. 스트라이드 스케줄링 (Stride Scheduling)
스트라이드 스케줄링은 로터리 스케줄링의 무작위성을 배제하고, 결정론적(deterministic)으로 공정한 배분을 달성하는 스케줄러이다.
원리:
스트라이드(Stride): 각 프로세스는
(큰 수 / 티켓 수)에 비례하는 '보폭' 값을 가진다. 즉, 티켓이 많을수록 보폭(stride)은 작아진다.패스(Pass): 각 프로세스는 자신이 얼마나 '전진'했는지를 나타내는
pass값을 가진다. 프로세스가 한 번 실행될 때마다, 자신의stride만큼pass값이 증가한다.선택: 스케줄러는 항상 가장 작은
pass값을 가진 프로세스를 선택하여 실행한다.
예시: A(티켓 100, stride 100), B(티켓 50, stride 200), C(티켓 250, stride 40) 세 프로세스가 있다고 하자(큰 수 = 10000). 이 과정을 반복하면, 정확히 티켓 수에 비례하여(C:A:B = 5:2:1) 실행되는 것을 보장할 수 있다.
장점: 무작위성이 없으므로, 짧은 시간 내에도 매우 정확하고 결정론적인 비율 보장이 가능하다.
단점: 새로운 프로세스가 시스템에 진입할 때 문제가 발생한다. 만약 새로 들어온 프로세스의 pass 값을 0으로 설정하면, 기존 프로세스들의 pass 값이 아무리 작아도 이 새로운 프로세스가 CPU를 독점하게 된다. 이처럼 전역적인 pass 값을 관리하고 동기화하는 것이 복잡하다는 한계가 있다.
5. 현대적 구현: Linux Completely Fair Scheduler (CFS)
로터리와 스트라이드 스케줄링이 비례 배분의 핵심 아이디어를 제공했다면, 현대 운영체제는 이를 어떻게 구현하고 있을까? 대표적인 예가 바로 리눅스의 CFS(Completely Fair Scheduler)이다.
CFS는 '완벽하게 공정한' 스케줄러를 지향하며, 스트라이드 스케줄링과 유사한 아이디어에 기반하지만 훨씬 더 정교하고 효율적으로 동작한다.
가상 실행 시간 (vruntime): CFS는 각 프로세스마다
vruntime이라는 값을 추적한다. 이는 스트라이드 스케줄링의pass값과 유사하며, 프로세스가 실행된 시간을 기록한다. CFS는 항상 이vruntime이 가장 작은 프로세스를 다음 실행 대상으로 선택한다.가중치 (Weighting)와 nice 값: 티켓 대신
nice값(-20 ~ +19)을 사용하여 프로세스의 우선순위를 정한다. 이nice값은 특정weight(가중치)로 변환된다. 우선순위가 높은 프로세스(nice 값이 낮은)는 가중치가 크고, 다음 공식에 따라vruntime이 실제 실행 시간보다 더 느리게 증가한다. 이 덕분에vruntime이 오랫동안 낮은 상태를 유지하여 더 자주 선택될 기회를 얻는다.
\[ vruntime_i+=\frac{weight_0}{weight_i}runtime_i\](weight0는 nice 값 0의 가중치,는 해당 프로세스의 가중치이다.) 동적 타임 슬라이스: CFS는 고정된 타임 슬라이스를 사용하지 않는다. 대신 두 가지 매개변수로 실행 시간을 관리한다.
sched_latency: 이 시간 동안 모든 실행 가능한 프로세스가 적어도 한 번은 실행되도록 보장하는 목표 시간이다. 타임 슬라이스는(sched_latency / 실행 가능한 프로세스 수)로 동적으로 결정된다.min_granularity: 프로세스 수가 너무 많아져 컨텍스트 스위치가 과도하게 발생하는 것을 막기 위한 최소 타임 슬라이스 값이다. 계산된 타임 슬라이스가 이 값보다 작아지는 것을 방지한다.
효율적인 자료구조 (Red-Black Tree): 수많은 프로세스 중에서
vruntime이 가장 작은 프로세스를 매번 빠르게 찾아내기 위해, CFS는 단순 리스트()가 아닌 레드-블랙 트리라는 균형 이진 탐색 트리를 사용한다. 이를 통해 작업 탐색에 드는 시간을 $O(log N)$으로 줄여 매우 효율적이고 확장성 있는 스케줄링을 구현했다. I/O 및 기아 상태 처리: I/O 대기로 잠들었던(sleep) 프로세스는 깨어날 때 자신의
vruntime이 다른 프로세스들보다 훨씬 작아 CPU를 독점할 수 있다. 이 기아 상태를 방지하기 위해, CFS는 잠들었다 깨어난 프로세스의vruntime을 현재 레드-블랙 트리 내의 최소vruntime값으로 설정하여 공정성을 유지한다.
6. 최신 발전: EEVDF (Earliest Eligible Virtual Deadline First)
CFS는 오랜 기간 리눅스의 표준 스케줄러였지만, 복잡한 휴리스틱이 추가되면서 예측 가능성이 떨어진다는 비판을 받았다. 이를 개선하기 위해 리눅스 6.6 커널부터 CFS의 핵심이 EEVDF로 대체되었다.
EEVDF는 CFS의 공정성 개념을 계승하면서도, 두 가지 핵심 개념을 도입했다.
지연 (Lag): 프로세스가 할당받아야 할 CPU 시간과 실제로 받은 CPU 시간 간의 차이이다.
Lag > 0이면 서비스를 받아야 할 상태(Eligible)로 간주된다.가상 마감일 (Virtual Deadline, VD): 프로세스가 Eligible 상태가 된 시간에 가중치가 적용된 타임 슬라이스를 더하여 계산된다. (\(VD=t_{now}+slice_i/weight_i\))
EEVDF는 Lag > 0 인 프로세스 중에서 가장 이른 VD를 가진 프로세스를 스케줄링한다. 이를 통해 더 수학적으로 예측 가능한 공정성을 보장하고, 지연 시간에 민감한 작업들을 더 효과적으로 처리할 수 있게 되었다.
결론
비례 배분 스케줄러의 발전은 '얼마나 많은가'의 문제에서 '얼마나 공정한가'의 문제로 스케줄링의 패러다임을 전환시켰다. 단순한 티켓 기반의 아이디어에서 시작하여, 무작위성을 이용한 로터리 스케줄링, 결정론적 접근인 스트라이드 스케줄링을 거쳐, 현대 리눅스의 CFS와 EEVDF에 이르기까지 그 핵심에는 '각 프로세스에 응당한 몫을 보장한다'는 철학이 깊게 자리 잡고 있다.
추천글:
[운영체제] CPU 가상화 | Logical Control Flow에서 Context Switch까지
[운영체제] 운영체제란? | Virtualization, Concurrency, Persistence 핵심 개념 이해
