[TIL 39일차]비례 배분 스케줄링

 

 

비례 배분(Proportional Share) 스케줄러, 혹은 공정 배분(fair a share)이라고 하는 유형의 스케줄러에 대해 봐보자.

반환 시간이나 응답 시간을 최적화 하는 대신 스케줄러가 각 작업에게 CPU의 일정 비율을 보장하는 것이 목적이다.

비례배분 스케줄링의 좋은 예가 추첨 스케줄링(lottery scheduling)으로 알려져 있다.

기본 아이디어는 간단하다.

다음 실행될 프로세스를 추첨을 통해 결정한다. 더 자주 수행되어야 하는 프로세스는 당첨 기회를 더 많이 준다.

기본 개념 : 추첨권이 당신의 지분이다.

추첨권(티켓)이라는 기본적인 개념이 추첨 스케줄링의 근간을 이룬다. 추첨권을 경품권의 개념과 유사하다.

추첨권은 특정 자원에 대한 프로세스에게 할당될 몫을 나타낸다. 프로세스가 소유한 티켓 개수와 전체 티켓간의 비율이 자신의 몫이다.

예를 봐보자.

A와 B 두 프로세스가 있다고 가정하자. A는 75장의 추첨권을, B는 25장의 추첨권을 가지고 있다.
A에게 75%의 CPU를 B에게 남은 25%를 할당하는 것이 목적이다.

추첨 스케줄링은 이러한 목적을 확률 기반으로 달성한다. 방식은 간단하다. 스케줄러는 추첨권의 총 개수를 파악한다.

추첨 스케줄러의 큰 장점 중 하나는 무작위성. 이거는 강력하고 쉬운 방법중하나이다.

무작위 방식은 결정 방식에 비해 3가지 장점이 있다.

 

1. 무작위 방식은 더 전통적인 방식이 잘해결하지 못하는 특이 상황을 잘 대처함. 예로 LRU교체 정책을 생각해보면 더 좋은 교체 알고리즘이지만 순차적인 접근 패턴을 보이는 곳에서는 최악의 성능을 낸다. 근데 무작위성이 들어가면 최악의 경우는 발생하지 않는다.

2. 무작위 추첨방식은 매우 가볍다. 관리해야할 상태 정보가 거의 없기 때문이다. 전통적인 공정 배분 스케줄링에서는 각 프로세스가 사용한 CPU 양을 기록해야한다.(MLFQ)와 같이.... 무작위에서는 프로세스 상태정보만 필요하다.

3. 무작위 추첨 방식은 매우 빠르다. 난수 발생 시간이 빠르기만 하면 결정 역시 빠르게 되고 따라서 속도가 요구되는 많은 경우에 사용될 수 있다.

예시를 봐보자

스케줄러는 추첨권을 뽑는다.

0 ~ 99의 숫자라고 가정

뽑힌 추첨권 값에 따라 다음에 실행될 프로세스가 결정된다.

A , A ,B A,B, A,A,A,B,B,A,A 라는 타임 슬라이스가 나오면 B가 자원을 덜 받은 것 같지만 이는 시간이 지나면 원하는 비율에 수렴하게 된다.

추첨 기법

추첨권을 다루는 다양한 기법이 있다. 한 가지 기법은 추첨권 화폐(ticket currency)의 개념이다. 이 개념은 사용자가 추첨권을 자신의 화폐 가치로 자유롭게 할당할 수 있도록 허용한다.

시스템은 자동적으로 화폐 가치를 변환한다. 

예를 들어 사용자 A,B 가 각각 100장의 추첨권을 받았다고 가정하자. 사용자 A는 A1과 A2의 두 개의 작업을 실행중이고 자신이 정한 화폐로 각각 500장의 추첨권을 할당하였다.(1000장 중 ) 사용자 B는 하나의 작업을 실행 중이고 자신의 기준 화폐 10장중 10장을 할당하였다. 시스템은 A1과 A2의 몫을 A의 기준 화폐 500장에서 전체 기준이 되는 화폐 각각 50장으로 변환한다. 마찬 가지로 B1의 추첨권 10장은 전체 기준이 되는 추첨권 100장으로 변환된다.(전체 200장중)

다른 유용한 기법은 **추첨권 양도(ticket transfer)** 이다. 양도를 통하여 프로세스는 일시적으로 추첨권을 다른 프로스에게 넘겨 줄 수 있다.

이 기능은 클라이언트/ 서버 환경에서 특히 유용하다. 클라이언트 프로세스는 서버에게 메시지를 보내 자신을 대신하여 특정 작업을 해달라고 요청한다. 작업이 빨리 완료 될 수 있도록 클라이언트는 서버에게 추첨권을 전달하고 서버가 자신의 요청을 수행하는 동안 서버의 성능을 극대화하려고 한다. 요청을 완수하면 서버는 추첨권을 다시 클라이언트에게 되돌려주고 먼저와 같은 상황이 된다.

마지막으로 추첨권 팽창 (ticket inflation) 도 유용하게 사용된다.

이 기법에서 프로세스는 일시적으로 자신이 소유한 추첨권의 수를 늘이거나 줄일 수 있다. 물론 서로 신뢰하지 않는 프로세스들이 상호 경쟁하는 시나리오에서는 의미가 없다. 하나의 욕심 많은 프로세스가 매우 많은 양의 추첨권을 자신에게 할당하고 컴퓨터를 장악할 수 있다. 많은 CPU 시간을 필요로 한다면, 시스템에게 이를 알리는 방법으로 다른 프로세스들과 통신하지 않고 혼자 추첨권의 상향 조정한다.

구현

// 당첨자 발견시 사용
int count = 0;

//0주터 총 추첨권의 수 사이의 임의의 값을 얻기 위해 사용
int winner = getrandom(0,totaltickets);

//current = 작업 목록을 탐색하는데 사용

node_t *current = head;

while(current){
	counter = counter + current->tickets;
	if(counter > winner){
		break;
	}
	current = current->next;
}

리스트를 사용하여 프로세스를 관리한다고 가정하자.

A,B 및 C 세개의 프로세스로 구서오디고 각자 몇 장의 추첨권을 얻는다.

헤드 -> 작업 : A ,tix = 100 -> 작업 : B, tix = 50 -> 작업 : C, tix = 250 -> NULL

스케줄을 결정하기 위해 먼저 총 추첨권의 개수(400)^2 중에서 한 숫자를 선택해야 한다.

300 이 선택 되었다 하자. 리스트를 순회하면서 카운터 값을 이용하여 당첨자는 찾아낸다.

프로세스 리스트를 순회하면서 coutner의 값이 winner의 값을 초과할 때 까지 각 추첨권의 개수를 counter에 더한다. 

값이 초과하게 되면 리스트의 현재 원소가 당첨자가 된다. 당첨 번호가 300인 예시에서는 다음과 같이 진행된다.

먼저 A의 추첨권 개수가 더해져 counter = 100. 계속 간다 그다음 50 더해져서 150. 한번 더 간다. 400이 되고 이는 당첨자가 C라는걸 알려준다.

일반적으로 리스트를 내림차순으로 정렬하면 이 과정이 가장 효율적이 된다.
정렬순서는 알고리즘의 정확성에 영향을 주지는 않는다. 그러나 리스트를 정렬해놓으면 검색 횟수가 최소화 되는것을 보장한다. 

적은 수의 프로세스가 대부분의 추첨권을 소유하고 있는 경우 효과적인 방법이다.

예제

추첨 스케줄링 동작을 쉽게 이해하기 위해서 CPU를 공유하는 두 개의 작업의 수행 시간을 살펴보자. 각 프로세스는 같은 개수의 추첨권(100)을 가지고 있으며 동일한 실행 시간을 갖는다. 

우린 두 작업을 동시에 종료시키고자 한다. 그러나 추첨 스케줄리의 무작위성 떄문에 한 작업이 다른 작업보다 먼저 종료될 수 는 있다. 이 차이를 정량화 하기 위해 간단한 불공정 지표(unfairness metric)인 U를 정의한다.


### 추첨권 배분 방식

추첨 스케줄리에서 아직 언급하지 않은 문제는 추첨권을 작업에게 나누어주는 방식이다.
시스템 동작이 추첨권 할당하는 방식에 따라 크게 달라지기 때문에 상당히 어려운 문제이다.

한 가지 접근 방식은 사용자가 가장 잘 알고 있다고 가정하는것.

각 사용자에게 추첨권을 나누어 준 후 사용자가 알아서 실행시키고자 하는 작업들에게 추첨권을 배분 하는 방식
하지만 이건 해결책이 아니다.
어떤 일을 해야하는 지 전혀 제시하지 않는다. 주어진 작업 집합에 대한 "추첨권 할당 문제"는 여전히 미해결 상태이다.

왜 결정론적(Deterministic) 방법을 사용하지 않는가?

무작위성을 이용하면 스케줄러는 단순하게 만들 수 있지만, 정확한 비율을 보장할 수 없다.
짧은 기간만 실행되는 경우 더 그렇다.
이 떄문에 Waldspurger는 결정론적 공정 배분 스케줄러인 보폭 스케줄링(stride scheduling)을 고안했다.
보폭 스케줄링 역시 이해하기 쉽다. 시스템의 각 작업은 보폭을 가지고 있다. 보폭은 자신이 가지고 있는 추첨권 수에 반비례하는 값이다. 

예시로 100, 50 ,250의 추첨권을 가지고 있으며 임의의 큰 값을 각자의 추첨권 개수로 나누어 보폭을 계산할 수 있다. 예를 들어 10,000을 각자의 추첨권 개수로 나누면 각 작업의 보폭은 100,200 및 40이 된다. 이 값을 보폭(stride)이라고 부르며, 프로세스가 실행될 때마다 pass라는 값을 보폭만큼 증가시켜 얼마나 CPU를 사용했는지 추적한다.

curr = remove_min(queeu); // pass 값이 최소인 클라이언트 선택
schedule(curr); // 자원을 타임 퀀텀 만큼 선택된 프로세스에게 할당
curr->pass += curr->stride; // 다음 pass 값을 보폭 값을 이용하여 갱신
insert(queue, curr); // curr를 다시 큐에 저장

예시를 들면 다음과 같다.

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


보폭 스케줄링은 각 스케줄링 주기마다 정확한 비율로 CPU를 배분한다.

보폭 스케줄링의 정확도를 고려할 때, 추첨 스케줄링을 왜 사용하는가?

추첨 스케줄링은 보폭 스케줄링이 가지고 있지 않은 멋진 특성을 가지고 있다.

상태 정보가 필요없고, 보폭 스케줄링의 예에서 스케줄링 중간에 새로운 작업이 시스템에 도착했다고 상상해보면 pass값이 얼마가 되어야하는지 애매해진다. 그렇다면 CPU를 독점하게 될 것이다. 추첨 스케줄링에서는 프로세스 상태를 유지할 필요가 없다.
새 프로세스를 추가할 때, 새로운 프로세스가 가진 추첨권의 개수, 전체 추첨권의 개수만 갱신하고 스케줄한다. 이런 이유로 추첨 스케줄링에서는 새 프로세스를 쉽게 추가할 수 있다.

리눅스 CFS(Completely Fair Scheduler)

 

현재 Linux는 기존과는 다른 방식으로 공정 배분 스케줄링을 구현하였다. 이른바 Completely Fair Scheduler이다. 

이 스케줄러의 장점은 효율성과 확장성이다. 효율성을 위해 CFS는 최적의 내부 설게와 자료 구조 사용을 통해 스ㅡ케줄링 결정을 매우 신속히 진행한다. 최근 연구결과에 따르면 스케줄러의 효율성이 전체 시스템 성능에 매우 중요한 영향을 갖는다고 한다.

기본 연산

대부분의 기존 스케줄러들은 고정된 길이의 타임 슬라이스를 사용한다. CFS는 이 점에서 기존 스케줄러와 다르다.

CFS는 모든 프로세스들에게 CPU를 공평하게 배분하는 것을 목표로 한다.

virtual runtime이라는 간단한 counting 기반 테크닉을 사용한다.

프로세스가 실행되서, 스케줄러는 해당 프로세스의 vruntime 값을 누적시킨다.

가장 기본 적인 경우, 각 프로세스의 vruntime은 실제 시간 같은 속도로 증가한다. 스케줄링시 CFS는 가장 낮은 vruntime을 가진 프로세스를 다음에 실행할 프로세스로 선택한다.

스케줄러가 어느 시점에서 실행 중인 프로세스를 멈추고, 다음 프로세스를 실행할지 어떻게 결정할까? CFS가 자주 실행되면 각 프로세스가 작은 시간 간격으로 CPU를 사용하게 되어 공정성이 좋아짐..

하지만 많은 문맥 교환이 발생하여 전체 시스템 성능에 악영향을 미칠 수 있다.

드물게 CFS가 실행되면 문맥 교환의 횟수가 감소하여 전체 시스템 성능은 향상되지만, 공정성은 악화된다.

CFS는 다양한 통제 변수들을 통해 관리하는데, 
첫 번째 변수로 sched_latency가 있다. 이 값은 여러 프로세스가 CPU를 번갈아 가면서 사용하 상황에서 하나의 프로세스가 CPU를 사용한 후, 다음 번 CPU를 사용할 수 있을 때까지의 최대 시간 간격을 나타낸다.

보통 sched_latency = 48(ms)이다. CFS는 이값을 현재 실행 중인 프로세스의 개수(n)으로 나눠서 프로세스의 타임 슬라이스를 결정한다.

시간이 흐름에 따라,CFS 기법은 CPU를 프로세스들에게 공정하게 배분하게 된다.

예를들어 4개의 프로세스가 실행 중이라 가정하자.(n = 4) CFS는 sched_latency를 n으로 나누고, 프로세스 당 타임 슬라이스으 길이는 12ms가 된다.

그러면 CFS는 첫 번째 작업을 12ms 실행시간 동안 실행한다. 그 후 더 적은 vruntime값을 가진 작업이 있는지 검사한다. CFS는 3개의 다른 작업 중에서 한 개를 선택하고, 선택된 작업으로 CPU를 전환한다. 

만약 "너무 많은 "프로세스가 실행 중이면 어떨까?

타임 슬라이스의 크기가 매우 작아지고 따라서 너무 많은 문맥전환이 일어날 것이다.

이 문제를 해결하기 위해 CFS는 최소 타임 슬라이스 min_granularity라는 변수를 사용한다.

최소 값은 보통 6ms로 설정되어 있다. CFS는 각 프로세스에게 할당된 시간 조각 이하 되지 않도록 하여 스케줄링에 너무 많은 시간을 소비하지 않도록 한다.

예를 들어 10개의 프로세스가 실행중이라면, 기존 스케줄러는 sched_latency를 10으로 나누어 타임 슬라이스를 결정할 것이다.

그러면 sched_latency는 보장이 어려워지지만 스케줄링은 효율적이 된다. 프로세스간에 CPU를 공평하게 배분하는 데에는 문제가 없다.

CFS는 주기적으로 발생하는 타이머 인터럽트에 근간하여 작동한다. 즉 CFS는 특정 시간 간격으로만 스케줄링 결정을 내린다. 타이머 인터럽트는 짧은 간격으로 발생하여 CFS는 현재 작업의 타임 슬라이스 소진 여부를 판단한다.

타임 슬라이스 길이가 타이머 인터럽트 주기의 정수배가 아닐 경우를 대비하여 설계되었다.

그래서 CFS는 vruntime을 정확히 계산하고 이를 기반으로 스케줄링한다.

가중치

CFS는 사용자나 관리자가 프로세스의 우선 순위를 조정하여 다른 프로세들 더 보다 많은 CPU시간을 할당 받게 된다.

티켓이 아닌 프로세스의 nice레벨이라는 고전적 Unix 메커니즘을 사용한다. nice는 0을 기본값으로 가지고 -20부터 19까지 이상하긴 하지만, nice가 양수값이면 낮은 우선순위를 의미하고 음수 값이면 높은 우선 순위를 의미한다. 너무 친절하면 관심(스케줄링)을 많이 못받는 것과 같다. 

CFS는 각 프로세스의 nice 값을 다음의 가중치(weight)에 대응 시켜 놨다.

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 */ 355, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45, 
/* 15 */ 36, 29, 23, 18, 15,
}

이 가중치는 프로세스의 실질적인 타임 슬라이스를 계산하는데 사용됨.

지금까지와 달리 프로세스 간의 우선순위 차이도 고려한다. 구체적인 수식은

time_slice = (weight/ 시그마 i =0 -> n - 1 weight_i) * sched_latency 이다.

가중치 표의 장점은 nice 값의 차이가 유지 되면 CPU 배분 비율도 유지 된다는것이다.

Red-Black 트리의 활용

CFS의 핵심은 알고리즘 효율성이다. 효율적 알고리즘을 이요하여 실행할 프로세스를 신속히 선정하는 것이 매우 중요하다. 대기중인 프로세스를 관리하는 데 있어서 다양한 자료구조를 사용할 수 있다.

리스트를 사용할 수 있지만 이거는 숫자가 커지면 탐색 시간이 오래걸린다.

CFS는 프로세스 관리에 red-black 트리를 사용함으로써 이 효율성 문제를 해결하였다.

균형 트리의 일종으로 자세한건 따로 공부해보자.

간단하게 생각해서 프로세스들의 vruntime들을 기준으로 레드블랙트리에 있다고 하면 탐색과 삽입, 삭제 모든 것이 O(log(n))이 소요된다.

I/O와 잠자는 프로세스 다루기

또 해결해야할 사항은 장기간 잠자고 있는 프로세스 처리이다.

A와 B 두 프로세스가 있다고 가정해보자.

A는 계속 실행해왔다. B는 장시간(10초) 잠자고 있다고 가정.

B가 깨어나면 B의 vruntime은 A보다 10초 뒤처져 있을 것이다. 이렇게 되면 B는 다음 10초 동안 CPU를 독점하게 될 것이다. A는 B가 깨어난 후 10초간 CPU를 할방받지 못하고, 기아상태에 빠지게 된다.

CFS는 이것을 해결하기 위해 작업이 깨어날 때 vruntime을 적절히 재설정한다.
구체적으로, CFS는 깨어난 작업의 vruntime을 트리에서 찾을 수 있는 가장 작은 값으로 설정한다.
이를 통해 CFS는 큰 오버헤드 없이 기아 현상을 방지한다. 이 기법의 문제점이 없지는 않은데, 짧은 시간 간격으로 자주 잠자기에 들어가는 작업들은 CPU 배분에 있어서 손해를 보게 된다.

요약

비례 배분 스케줄링을 소개하고 추첨권 스케줄링, 보폭 스케줄링, 그리고 리눅스의 CFS 라는 세가지 구현방식에 대해 간단하게 배워보았다. 추첨권 스케줄링은 무작위성을 이용하여 구현하고,
보폭 스케줄링은  같은 목적을 결정적 방법을 통해 달성한다.
이 챕터에서 다룬 유일한 실제 스케줄러인 CFS는 동적 타임 슬라이스를 가진 가중치 라운드 로빈 방식 같지만, 부하에 잘 견디도록 확장성과 성능을 보장하는 스케줄러이다.

우리가 가는 아는대로 CFS는 현존하는 공정성 배분 스케줄러 중 가장 널리 쓰인다.

모든 경우에서 다 좋은 성능을 보이는 스케줄러는 존재하지 않는다.

공정 배분 스케줄러들은 공정성 문제가 있다.

예를들어 공정 배분 스케줄러가 입출력 스케줄러와 서로 맞물리면, CPU 스케줄러가 원하는 식으로 CPU를 할당할 수 없다. 자주 I/O를 수행하는 작업들은 CPU를 원하는 데로 배분받지 못할 수도 있다.또 다른 문제는 티켓이나 우선순위를 얼만큼 씩 할당해야하는 가에 대한 보다 근본적인 문제다.

즉 브라우저에 티켓을 얼마나 할당하고, 또 문서 편입기에 nice 값을 얼만큼 할당 할 것인가? 에 관련된 문제이다.

범용 스케줄러는 이 문제를 더 직관적으로 해결한다.

다행히 배분 문제가 그리 중요하지 않은 경우가 많다.

이 경우들에서는 비례 배분 스케줄러들이 유용하게 사용된다.

예를 들어, 가상화 데이터 센터에서 윈도우즈 가상 머신에 CPU 사이클의 1/4를 할당하고 나머지는 리눅스 시스템에 할당하고 싶은 경우라면 비례 배분이 간단하고 효과적이다.

이 아이디어는 다른형태의 자원들을 할당하는 데에도 사용될 수 있다.

VMware ESX 서버에서 메모리를 비례 배분하는데에도 사용된다.