• 2024.06.07: 복습 및 글 다듬기

Operating Systems : Three Easy Pieces를 보고 번역 및 정리한 내용들입니다.

이번 장에서는 비례 배분(proportional-share), 혹은 공정 배분(fair-share) 스케줄러라 부르는, 또 다른 종류의 스케줄러에 대해서 공부한다. 비례 배분 스케줄러의 아이디어는 단순하다. 반환 시간이나 응답 시간을 최적화하는 대신, 각 작업들이 CPU 시간의 일정 비율을 차지할 수 있도록 보장하는 것이다.

비례 배분 스케줄링의 초기 예제 중 하나로 추첨 스케줄링(lottery scheduling)이라 불리는 것이 있다. 기본 아이디어는 간단히 어떤 프로세스를 실행할지 결정하기 위해서 추첨을 하는 것이다. 더 자주 실행되어야 하는 프로세스들은 추첨에서 더 높은 승리 확률을 가진다.

1. Basic Concept: Tickets Represent Your Share

추첨 스케줄링에서는 티켓(ticket)이라는 개념을 사용한다. 이 티켓은 한 프로세스가 얼마나 많은 자원을 분배받아야 하는지를 표현하며, 프로세스가 가지고 있는 티켓의 비율은 이 프로세스가 시스템에서 얼마나 많은 자원을 가지고 있어야 하는지를 나타낸다. 만약 추첨을 자주, 많이 하게 된다면 해당 비율에 근사할 수 있게 될 것이다.

추첨 과정은 직관적이다. 우선 스케줄러는 얼마나 많은 티켓이 있는지를 알아야 한다. 그러고 나면 스케줄러는 당첨 티켓을 하나 뽑고, 해당 티켓을 가지고 있는 프로세스가 실행된다.

예를 들어, 총 100개의 티켓이 있고 A는 0~74, B는 75~99번의 티켓을 가지고 있다고 하자. 만약 스케줄러가 50번 티켓을 뽑으면 프로세스 A가 실행될 것이다.

추첨 스케줄링의 무작위성은 원하던 비율로 확률적으로 맞아 떨어질 수 있게 해주기는 하지만, 이를 보장하지는 않는다. 하지만 여러 작업들이 오랫동안 계속해서 경쟁하는 경우 그 비율에 근사해 가기는 할 것이다.

2. Ticket Mechanisms

추첨 스케줄링은 티켓을 다루기 위한 여러가지 유용한 메커니즘들을 제공한다.

Ticket Currency

어떤 방식에서는 티켓 통화(ticket currency)라는 개념을 사용한다. 통화 개념을 통해, 사용자들은 자신의 화폐 가치에 기반해 작업에 티켓을 마음대로 분배할 수 있게 되고, 시스템은 이 통화를 그에 맞는 전역 값으로 변환한다.

예를 들어, 유저 A, B가 각각 100개의 티켓을 가지고 있다고 하자. 유저 A는 두 개의 작업 A1, A2를 실행하고 있고, 그들에게 A 통화 기준 1000개의 티켓 중 각각 500개 씩의 티켓을 준다고 하자. 유저 B는 하나의 작업만을 실행하며, 이 작업에 총 10개의 티켓을 준다. 시스템은 A1과 A2에 할당된 A 통화 티켓 500개를 전역 통화 티켓 50개로 바꾸고, B 통화 티켓 10개도 전역 통화 티켓 100개로 변환한다. 이후 추첨은 전역 통화로 진행되며 실행될 작업들을 결정한다.

Ticket Transfer

다른 유용한 메커니즘으로는 티켓 양도(ticket transfer)라 부르는 것이 있다. 티켓 양도를 통해 프로세스는 자신의 티켓을 다른 프로세스에 넘겨줄 수 있다. 이는 클라이언트-서버 세팅에서 특히 유용하다.

클라이언트 프로세스가 서버에게 자신의 일을 대신 하도록 요청을 한다고 하자. 이 작업을 좀 더 빠르게 하기 위해 클라이언트는 서버에 티켓을 넘기고 서버가 자신의 요청을 처리할 때 성능을 최대한으로 높일 수 있게 한다. 요청에 대한 처리를 마치면 서버는 자신이 받은 클라이언트의 티켓을 클라이언트에게 되돌려준다.

Ticket Inflation

마지막으로 티켓 인플레이션(ticket inflation)도 (때로는) 유용한 테크닉이 될 수 있다. 티켓 인플레이션은 한 프로세스가 일시적으로 자신이 가지고 있는 티켓의 수를 올리거나 내리는 것이다. 물론 프로세스들이 서로 경쟁하는 환경에서는 이를 사용할 수 없다. 왜냐하면 한 프로세스가 자신의 티켓을 뻥튀기해서 CPU를 독차지해버릴 수 있기 때문이다.

티켓 인플레이션은 프로세스 그룹이 서로를 믿을 수 있는 환경에서 적용될 수 있다. 이 경우 만약 한 프로세스가 CPU 시간을 더 필요로 하면, 자신의 티켓 가치를 올림으로써 다른 프로세스들과 통신하지 않으면서도 자신의 요구를 시스템에 반영할 수 있다.

3. Implementation

추첨 스케줄링의 구현은 몹시 간단하다. 이를 구현하는 데에 필요한 것은 당첨 티켓을 뽑기 위한 좋은 난수 생성기, 시스템 내 프로세스들을 추적하기 위한 자료 구조, 그리고 전체 티켓의 수 밖에 없다.

예시

세 개의 작업 A, B, C가 있고 각각은 100, 50, 250개의 티켓을 가지고 있다. 프로세스들을 리스트로 관리된다고 하자. 스케줄링을 위해서는 우선 전체 티켓의 수=400 미만의 수 중 임의의 당첨 티켓을 뽑아야 한다. 만약 300을 뽑았다면, 우리는 그냥 리스트를 순회하면서 당첨된 프로세스를 찾으면 된다.

// counter: 당첨 프로세스를 찾았는지를 추적하기 위해 사용된다. 
int counter = 0;

// winner: 난수 생성기를 이용해, 0 이상 전체 티켓 수 미만의 정수 하나를 뽑는다
int winner = getrandom(0, totaltickets);

// current: 작업 리스트를 순회하기 위해서 사용한다 
node_t *current = head;
while (current) {
	counter = counter + current->tickets;
	if (counter > winner)
	break; // 당첨 프로세스를 찾은 경우 
	current = current->next;
}
// ’current’가 당첨 프로세스이므로 스케줄링한다. 

이 과정을 좀 더 효율적으로 만들기 위해서는 리스트를 각 프로세스가 가진 티켓의 수에 따라 내림차순으로 정렬는 방법이 있을 수 있다. 순서를 바꾸는 것이 알고리즘의 정확성에 영향을 주지는 않지만, 이는 일반적으로는, 특히 적은 수의 프로세스가 대부분의 티켓을 차지하고 있는 경우, 최소한의 리스트 반복 조회를 보장한다.

4. How To Assign Tickets?

다만, 어떻게 작업에 티켓을 할당하느냐 하는 문제가 여전히 남아 있다. 시스템의 작동 방식은 티켓의 할당 방식에 강하게 의존하기 때문에, 이 문제는 중요하면서도 어려운 문제다.

한 가지 방법은, 유저가 그 방식을 가장 잘 알고 있다고 가정하는 것이다. 이 경우 각 유저는 티켓을 가지고 원하는 작업에 마음대로 할당하면 된다.

하지만 이 해결법은 시스템이 어떤 문제를 해결해주는 게 아니기 때문에 사실상 해결법이라고 할 수 없다. 작업의 집합이 주어졌을 때의 티켓을 어떻게 할당할 것인가 하는 문제는 여전히 남아있다.

5. Stride Scheduling

난수 생성과 무작위성을 꼭 사용해야만 할까? 무작위성은 간단한 스케줄러를 만드는 데에는 도움이 되지만, (특히 짧은 시간의 경) 정확히 원하는 비율을 보장하지 못할 수 있다.

그래서 만들어진 게 결정론적인 공정-배분 스케줄러인 보폭 스케줄링(stride scheduling)이다.

보폭 스케줄링도 직관적으로 작동한다. 시스템 내 각 작업들은 보폭을 가지고 있고, 이 값은 이 작업이 가지고 있는 티켓의 수에 반비례한다. 앞서의 예제를 보자. 작업 A, B, C는 각각 100, 50, 250개의 티켓을 가지고 있다. 이 작업들의 각 보폭은 어떤 큰 수를 각 프로세스가 할당받은 티켓의 수로 나눔으로써 얻을 수 있다. 예를 들어, 10000을 각 티켓의 값으로 나누면 각 프로세스의 보폭값 100, 200, 40을 얻을 수 있다. 이 값들은 매번 프로세스가 실행될 때 해당 프로세스의 카운터(패스, pass)에 더해져, 전체적인 진행 상황을 추적할 수 있게 한다.

스케줄러는 다음에 실행될 프로세스가 무엇인지 결정하기 위해 보폭과 패스를 사용한다. 기본 아이디어는 간단하다. 어느 특정 시점에 가장 낮은 패스 값을 가지고 있는 프로세스를 골라 실행시키고, 해당 프로세스의 패스 값을 보폭만큼 증가시킨다. 의사 코드는 아래 같다.

curr = remove_min(queue); // 가장 작은 pass 값을 갖는 것을 찾는다.
schedule(curr); // 시간 단위 동안 실행한다
curr->pass += curr->stride; // pass를 stride를 이용해 업데이트 한다
insert(queue, curr); // 현재 프로세스를 다시 큐에 넣는다.

위 예제에서 프로세스 A, B, C,는 각각 보폭 값 100, 200, 40을 얻는다. 처음에는 세 프로세스 모두 패스 값이 0이므로 어떤 프로세스든 실행될 수 있다. A가 선택되어 실행되었다고 하자. A의 패스는 100만큼 오른다. 다음으로는 B가 실행됐다고 하자. B의 패스는 200이 된다. 마지막으로 C가 실행된다. C의 패스는 40이 된다. 세 프로세스 중 최소 패스 값을 가지는 것은 여전히 C이므로 다시 C가 실행된다. 패스 값은 80이 된다 ...

Pass(A)	Pass(B)	Pass(C)	Who Runs?
0	0	0	A
100	0	0	B
100	0	0	C
100	200	40	C
100	200	80	C
100	200	120	A
200	200	120	C
200	200	160	C
200	200	200	...

표에서 볼 수 있듯 A는 2번, B는 1번, C는 5번 실행되고 있는데 이 비율은 정확히 해당 프로세스들에 원했던 것과 같다. 추첨 스케줄링의 경우 시간에 지남에 따라 확률적으로 해당 비율을 얻을 수 있었지만, 보폭 스케줄링의 스케줄링 사이클이 끝나면 해당 비율을 얻을 수 있음이 보장된다.

그럼 보폭 스케줄링이 그렇게 정확하면 추첨 스케줄링은 왜 쓸까? 추첨 스케줄링은 보폭 알고리즘이 가지고 있지 않은 훌륭한 특징을 하나 가지고 있는데, 바로 전역 상태가 없다는 것이다. 만약 새로운 작업이 보폭 스케줄링이 진행되고 있는 중에 들어왔다고 한다면, 이 프로세스의 패스 값은 어떻게 설정되어야 할까? 만약 패스가 0으로 설정되면 CPU를 독점하게 될 것이다.

한편 추첨 스케줄링의 경우에는 프로세스에 대한 상태를 따로 생각할 필요가 없다. 우리는 프로세스가 몇 개의 티켓을 가지고 있든지와 상관없이, 그냥 알고리즘을 따라 간단히 새로운 프로세스를 추가할 수 있다.

6. The Linux Completely Fair Scheduler (CFS)

위와 같은 초기 스케줄러들이 공정-배분 스케줄러의 역할을 잘 하기는 하지만, 현대 리눅스는 다른 방법으로 같은 목표를 달성하고 있다. Completely Fair Scheduler(CFS)라고 불리는 이 스케줄러는 공정-배분 스케줄링을 몹시 효율적이고 확장 가능한 방법으로 구현한다.

효율성이라는 목표를 위해, CFS는 스케줄링 결정을 내리기 위해 아주 적은 시간만을 쓸 것을 목표로 한다. 최근의 연구들에 따르면 스케줄러의 효율성은 매우 중요하다. 구글 데이터 센터에서의 연구에서는 적극적인 최적화에도 불구하고, 스케줄링이 전체 데이터 센터의 CPU 타임 중 5%를 차지함이 밝혀졌다. 현대 스케줄러 설계에서는 이 오버헤드를 줄이는 것이 핵심 목표가 된다.

Basic Operation

대부분의 스케줄러들은 고정된 time slice를 사용하지만, CFS에서는 조금 다르다. 목표는 간단하다. CPU를 두고 경쟁하는 프로세스들에게 CPU를 공정하게 나눠주는 것이다. CFS는 이를 가상 런타임(virtual runtime, vruntime)이라 불리는, 간단한 카운팅 기반 기술을 통해 해결한다.

각 프로세스는 실행됨에 따라 vruntime을 축적한다. 가장 기본적인 케이스로, 각 프로세스의 vruntime을 실제 물리적 시간에 비례해 증가시킬 수도 있다. 스케줄링 결정이 일어날 때 CFS는 가장 낮은 vruntime의 프로세스를 골라 다음으로 실행한다.

그렇다면 스케줄러는 언제 현재 실행 중인 프로세스를 멈추고 다음 프로세스를 실행할지를 어떻게 알 수 있을까? CFS가 전환을 너무 자주 하면 공정성은 올라가지만 성능은 떨어진다. 반대로 CFS가 전환을 너무 적게 하면 성능은 올라가겠지만 공정성은 떨어지게 된다. CFS는 이 공정성과 성능 사이의 긴장을 여러 파라미터들을 통해 제어한다.

첫 번째 파라미터는 sched_latency다. CFS는 전환 여부를 판단하기 전에 이 값을 통해 해당 프로세스가 얼마나 오래 실행되어야 할지를 결정한다. 대표적인 sched-latency 값은 48ms인데, CFS는 이 값을 CPU에서 실행되고 있는 프로세스들의 수로 나눠 각 프로세스의 time slice를 결정해, 완전히 공정하게 작동한다.

하지만 동시에 너무 많은 프로세스들이 실행되고 있는 경우에는 어떨까? 이 경우 time slice는 너무 작아질 것이고 문맥 전환은 너무 많아질 것이다. 이 문제를 해결하기 위해서 CFS는 또 다른 파라미터 min_granularity를 사용하는데, 이 값은 보통 6ms이다. CFS는 프로세스에 이 값보다 작은 time slice를 할당하지는 않도록 해서 스케줄링의 오버헤드가 과도하게 늘어나는 것을 방지한다.

CFS가 주기적인 타이머 인터럽트를 사용한다는 것, 즉 고정된 시간 간격을 가지고 결정을 내릴 수 있다는 것을 명심하자. 이 인터럽트는 1ms에 한 번 꼴로 자주 일어난다. CFS는 이 인터럽트가 일어날 때 깨어나 현재의 작업이 실행 완료 됐는지를 확인한다.

Weighting

CFS를 이용하면, 유저나 admin이 프로세스들에 더 높은 CPU를 줄 수 있게 해, 프로세스에 대한, 우선 순위에 기반한 제어도 가능하게 한다. 이는 티켓이나 보폭을 이용해서가 아니라 프로세스의 nice level로 알려져있는 고전적인 UNIX 메커니즘을 사용해서 해결된다. 프로세스의 nice 파라미터는 -20에서 19 사이의 어떤 값으로든 설정될 수 있다. 기본값은 0이며, 양수 값은 낮은 우선 순위를, 음수 값은 높은 우선 순위를 가리킨다.

static const int prio_to_weight[40] = {
	/* -20 */ 88761, 71755, 56483, 46273, 36291,
	/* -15 */ 29154, 23254, 18705, 14949, 11916,
	/* -10 */ 9548, 7620, 6100, 4904, 3906,
	/* -5 */ 3121, 2501, 1991, 1586, 1277,
	/* 0 */ 1024, 820, 655, 526, 423,
	/* 5 */ 335, 272, 215, 172, 137,
	/* 10 */ 110, 87, 70, 56, 45,
	/* 15 */ 36, 29, 23, 18, 15,
};

CFS는 각 프로세스의 nice 값들을 위와 같은 테이블을 통해 각각에 해당하는 weight에 매핑한다. 이 weight는 다음과 같이 각 프로세스에서 효과적인 time slice를 그 우선 순위를 바탕으로 계산할 수 있게 한다.

time slice 계산을 일반화하는 것과 더불어 CFS는 vruntime을 계산하는 방법에도 이를 반영한다.

여기서 $runtime_i$는 실제 실행 시간을, $weight_0$은 초기 가중치(그러니까 nice level이 0일 때의 가중치)를, $weight_i$는 부여된 가중치를 말한다.

여기서 weight 테이블의 신기한 특징이 하나 나타나는데, 두 프로세스의 nice 값의 차이가 일정하면, 두 프로세스는 nice level의 절댓값과 상관없이 CPU 사용에 있어서의 비율을 유지한다는 것이다.

예를 들어 프로세스 A, B가 각각 -5, 0의 nice level을 가지고 있다고 해보자. 우선 순위 -5의 weight는 3121, 0의 weight는 1024다. 따라서 A의 time slice는 $3121/(3121+1024) * sched\_latency= 0.753 * sched\_latency$가 되고, B의 경우는 $1024/(3121 + 1024) * sched\_latenct = 0.247 * sched\_latency)$가 된다.

이후에는 두 프로세스가 그 차이를 유지하면서, 각각 5, 10의 nice level을 갖도록 바뀌었다고 해보자. 5의 weight는 335, 10의 weight는 110인데, 이를 계산해보면 두 프로세스는 여전히 같은 time slice를 가지고 있음을 확인할 수 있다.

Using Red-Black Trees

CFS의 주된 목적 중 하나는 효율성이다. 즉 스케줄러는 다음으로 실행할 작업을 찾아야 할 때, 최대한 빠르게 해야한다는 것이다.

수천 개의 프로세스들로 구성되는 현대 시스템에서, 이 작업을 위해 단순한 리스트를 쓰게 된다면,긴 프로세스 리스트를 탐색하기 위해 수 밀리세컨드를 낭비해야 하게 될 수 있다.

CFS는 프로세스를 레드-블랙 트리에 넣음으로써 해결한다. 레드-블랙 트리는 균형 트리의 한 종류로, 간단한 이진 트리와 달리, 트리의 깊이를 얕게 유지해 여러 연산들이 로그 시간에 이루어질 수 있도록 보장한다.

CFS가 모든 프로세스들을 이 구조에 저장하는 것은 아니다. 이 자료 구조에는 오직 실행 중인, 혹은 실행 가능한 프로세스들만이 들어간다. 만약 프로세스가 I/O 작업을 대기하는 등의 이유로 sleep하게 되면, 이 프로세스는 트리에서 사라지고 다른 어딘가에서 따로 추적된다.

예시

10개의 작업들이 있고 각 작업의 vruntime은 1, 5, 9, 10, 14, 18, 17, 21, 22, 24라 하자. 만약 이 작업들을 정렬된 리스트에서 관리한다면 다음으로 실행할 작업을 찾기 위해 할 일은 그냥 맨 첫 번째 원소를 삭제하는 것 뿐이다. 하지만 그 작업을 다시 리스트에 넣기 위해서는 리스트를 스캔해 삽입할 장소를 찾아야 하고, 이는 $O(n)$의 시간이 걸린다.

한편 같은 값들을 레드-블랙 트리에 넣으면 대부분의 작업을 좀 더 효율적으로 할 수 있다. 프로세스들은 트리 내에서 vruntime 값으로 정렬되고 모든 작업들은 $O(\log{n})$에 끝날 수 있다. 만약 시스템 내에 수 천개의 프로세스가 있으면 로그 시간은 선형 시간보다 확실히 더 효율적이다.

Dealing With I/O And Sleeping Processes

가장 낮은 vruntime 값으로 프로세스를 고르는 것은 오랫 동안 sleep 중인 프로세스가 있는 경우 문제가 될 수 있다. 두 프로세스 A, B가 있고, A는 연속적으로 실행되고 B는 10초 정도로 오랫동안 sleep 중이라 하자. B가 깨어났을 때, 그 vruntime은 A보다 10 작다. 그러므로 B는 다음 10초 동안은 CPU를 독점하게 되고 A는 기아 상태에 빠진다.

CFS는 이러한 문제를 작업이 깨어났을 때 해당 작업의 vruntime을 트리에서 찾을 수 있는 가장 작은 값으로 바꿈으로써 해결한다. 이렇게 함으로써 CFS는 기아 문제를 피할 수 있다. 하지만 여기에는 대가가 있는데, 그것은 자주 sleep하는 작업들의 경우에는 CPU를 공정하게 배분받지 못할 수 있다는 것이다.

7. Summary

• 추첨 스케줄링은 확률적으로, 보폭 스케줄링은 결정론적으로 비례-배분을 달성한다.
• CFS는 현재 존재하는 것들 중 가장 널리 쓰이는 공정-배분 스케줄러다.
• 만병통치약인 스케줄러는 없고, 공정-배분 스케줄러들도 문제를 가진다.
  + I/O 작업이 있는 경우를 잘 처리하지 못한다
  + 짧게 자주 sleep하는 작업들이 있는 경우.
  + 티켓이나 우선 순위 할당과 같은 어려운 문제들을 가지고 있다.
  + MLFQ 등은 이 문제를 자동적으로 처리해준다.
  + 그래도 이 문제가 크게 관심 대상은 아닌 영역들이 많기 때문에, 비례-배분 스케줄러는 효율적이다.