드디어 CPU Virtualization의 마지막 장이다!
목차에는 Multi-CPU Scheduling이 있기는 한데, 당장 급한 일들이 너무 많아서 일단은 강의 중에 배우는 챕터부터 공부하려고 한다. 😢
이번 장에서는 Proportialnal Share(비례 배분) Scheduler, 또는 Fair-Share Scheduler라 불리우는 다른 유형의 스케줄러에 대해 공부할 것이다.
이 Proportional Share의 개념 자체는 정말 간단한데, Turnaround/Response time을 최적화 하는게 아니라 각각의 작업들이 CPU 사용 시간을 나눠서 가질 수 있도록 보장해준다는 점이 앞에서 배운 스케줄링 기법들과 다르다. 즉, 성능보다는 공정함에 초점을 둔 알고리즘이라 할 수 있다.
Proportional share scheduling의 한 오래된 예로 Lottery scheduling이 자주 꼽히는데, 이는 다음으로 실행될 프로세스를 추첨을 통해 결정하는 방법이다. 그러니까, 모든 프로세스들이 추첨의 대상이 되므로 앞에서 배운 여러 스케줄링 기법들과 달리 모든 작업들이 실행될 수 있을 확률이 항상 존재한다는 점에서 Lottery scheduling이 proportional share scheduling의 일종인 것이다.
이 Lottery scheduling에선 마치 집 앞 슈퍼마켓에서 얼마 이상 사면 추첨권을 한 장씩 주는 것처럼, 추첨권을 여러 장 가지고 있는 작업이 당첨될 확률이 추첨권을 적게 가지고 있는 작업보다 당연히 높다. 이러한 관점에서 Lottery scheduling을 좀 더 자세히 살펴보자.
그전에 잠깐! 위에서 Proportional share scheduling이 성능보다 공정함에 초점을 두었다고 해서 Lottery scheduling이 성능 측면에서 장점이 없는 것은 아니다.
첫째로, 앞에서 배운 MLFQ와 같은 알고리즘을 사용하려면 각각의 작업들의 CPU의 사용량을 계속해서 추적해야 하며, 프로세스가 스케줄링될 때마다 새로 갱신되어야 하는 반면 Lottery scheduling에서는 프로세스가 가진 정적인 속성들, 이를테면 프로세스가 가진 추첨권의 개수 정도만 필요하기 때문에 상대적으로 매우 가볍다.
둘째로, 난수 발생기 같은 하드웨어를 사용해 난수만 빠르게 발생시킬 수 있다면, 앞에서 질리도록 배운 여러 규칙들을 따져보는데 걸리는 시간보다 상대적으로 빠르게 다음으로 실행할 프로세스를 결정할 수 있다.
9.1. Basic Concept: Tickets Represent Your Share
방금 말했듯이 Lottery scheduling의 핵심 개념은 티켓(추첨권)으로, 이 티켓은 프로세스, 사용자 등의 무언가가 자원으로부터 할당 받을 비율을 의미한다. (예를 들어 작업 A가 75장의 티켓을, 작업 B가 25장의 티켓을 들고 있다면 CPU와 같은 공동의 자원을 A와 B가 각각 75%, 25%씩 할당 받음을 의미한다.)
Lottery scheduling은 매 time slice가 끝날 때마다 티켓을 임의로(=확률적으로=비결정적으로) 뽑아 다음으로 실행할 작업을 정한다. 자세히 살펴보자.
100장의 티켓의 각각에 0부터 99까지 번호를 붙이고, 선택된 번호가 써있는 티켓을 가진 프로세스가 스케줄링 된다고 가정해보자.
그럼 만약 프로세스 A가 0부터 74번까지 총 75장의 티켓을, 프로세스 B가 75번부터 99번까지 총 25장의 티켓을 가지고 있다고 하면, 위의 추첨 결과는 아래와 같은 스케줄링 결과를 낼 것이다.
20번의 추첨 중 A가 16번, B가 4번으로 대강 80%, 20%의 비율로 스케줄링 되었다.
기대했던 75:25의 비율과는 살짝 맞지 않지만, 알다시피 큰 수의 법칙에 의해 이러한 시행이 많아질수록 티켓 보유량의 비율과 점점 비슷해질 것이다.
9.2. Ticket Mechanisms
이런 기본적인 추첨 방식 말고도, 티켓을 다루기 위한 다양한 기법이 있다.
1. Ticket currency
Ticket currency는 티켓을 들고 있는 사용자가 임의로 티켓의 가치를 정하되, 실제로 추첨할 때에는 시스템이 알아서 이걸 환산해주는 기능을 의미한다.
예를 들어 티켓이 총 200장(Global Ticket) 있다고 가정하고, 사용자 A, B에게 공평하게 100장씩 나누어 주었다고 가정해보자.
이때 A는 티켓 100장을 1000장의 Local Ticket으로 환산하여 Local Ticket 1장당 Global ticket 0.1장의 가치를 가지도록 하였고, B는 티켓 100장을 10장의 Local Ticket으로 환산하여 Local Ticket 1장당 Global Ticket 10장의 가치를 가지도록 설정했다.
A와 B는 이 Local ticket을 각자 생성한 A1, A2, 그리고 B1에게 배분해주어 A1은 Local ticket A 500장, A2는 Local ticket A 500장, B1은 Local ticket B 10장을 가지게 되었다.
이때 A1과 A2의 Local Ticket이 500장으로 B1의 Local Ticket 10장보다 많으니, A1과 A2가 B1보다 CPU를 많이 점유하는 걸까?
당연히 아니다! 그건 Local ticket A 안에서나 500장인 거고, 다시 이걸 Global Ticket으로 환산하면 A1과 A2는 (500 * 0.1) = 50장, B1은 (10 * 10) = 100장의 Global ticket을 가지게 된 것이므로 프로세스만 놓고 보면 B1이 전체의 절반 만큼 자원을 점유할 것이다.
2. Ticket transfer
각 프로세스가 티켓을 서로 잠깐동안 주고 받게 할 수도 있다. 이 기능은 특히 클라이언트/서버 구조에서 유용한데, 클라이언트 프로세스가 서버 프로세스에 요청을 보내면 당연히 빨리 응답을 받고 싶으므로 요청을 보내 놓은 상황에서 클라이언트가 서버의 응답이 올 때까지 마땅히 할 게 없다면 안 쓰는 티켓을 굳이 들고 있지 말고 요청을 빨리 처리해주기를 바라는 서버에 잠깐 티켓을 양도해주는 것이다.
Lottery scheduling에서 티켓을 많이 보유하고 있다는 것은 스케줄러에 의해 더 많이 선택될 수 있음을 의미하므로 서버는 서버에 보유된 티켓만 사용할 때보다 훨씬 빠르게 작업을 수행할 수 있고, 작업이 끝나면 다시 클라이언트에 티켓을 돌려줌으로써 이를 정상화할 수 있게 되는 것이다!
3. Ticket inflation
직역하면 티켓 팽창인데, 말 그대로 프로세스가 일시적으로 자기가 들고 있는 티켓의 가치(개수)를 뻥튀기 할 수 있는 기능이다. Ticket currency에선 사용자가 각각의 프로세스에게 티켓을 편하게 나누어 주기 위해 일종의 단위 환산을 자동으로 해주는 기능을 지원한 것이었다면, 여기서는 Global ticket 자체를 임의로 더 할당 받는 것이라 할 수 있겠다.
물론 너도 나도 Global ticket을 막 받아다 쓰면 티켓이 늘어나봤자 스케줄링될 확률이 그대로이기 때문에 별 의미가 없지만, 프로세스가 서로 신뢰할 수 있는 환경에서는 어떤 프로세스가 갑자기 CPU 사용량이 많이 필요해졌을 때 시스템에 global ticket의 추가 발급을 요청해도 따로 다른 프로세스들에게 알려줄 필요가 없기 때문에 유용할 수 있다.
9.3. Implementation
Lottery scheduling의 가장 직관적이고 강력한 장점은 바로 구현하기 간단하는 점일 것이다. 앞에서 뭐 여러 개의 큐를 설정한다느니, 뭘 매개 변수화 한다느니, 했던 것과 달리 적당한 난수 생성기, 프로세스의 목록을 저장하기 위한 자료 구조, 프로세스별 티켓 갯수 정보 정도만 있어도 충분히 구현할 수 있다!
위 예시는 프로세스 A, B, C가 각각 100, 50, 250개의 티켓을 가지고 있는 상황을 연결 리스트로 나타낸 상황을 묘사하고 있다.
티켓은 준비 되었으니, 400장의 티켓 중 300번 티켓이 뽑힌 상황을 가정해보자.
굉장히 간단한 코드이다. 분석해보자!
- (2행) counter는 원하는 티켓을 찾기 전까지, 현재 몇 번 티켓까지 당첨 여부를 확인해봤는지를 기록하기 위한 변수 정도라고 생각하면 좋을 것 같다. 차이가 있다면 1장씩 당첨 여부를 확인하는게 아니라, 각각의 프로세스 노드를 지날 때마다 해당 프로세스 노드에 기록된 티켓 갯수만큼 counter에 값을 더해 아래 winner ticket 번호와 비교함으로써 해당 프로세스가 당첨되었는지 확인한다는 점이 다르다.
- (6행) 0부터 총 티켓 갯수(totaltickets) 범위 안의 우승 티켓을 뽑는 코드이다.
- (9행) 현재 확인중인 노드임을 기록하기 위한 노드 포인터로, Linked list에서는 맨 처음에 head node를 가리킨 다음 뒤쪽으로 하나씩 이동해가며(next) 순회한다. 즉, 위의 예시에서는 프로세스 A 노드가 첫 current가 된다.
- (10행) counter에 해당 노드의 티켓 갯수를 더해준다.
- (12행) 만약 counter 값이 winner ticket보다 더 크다면, 해당 노드가 가진 티켓의 범위 안에 winner ticket이 있다는 의미이므로 순회를 중단하고 current 노드를 winner process로 정한다.
- (14행) 만약 해당 node가 winner ticket을 가지고 있지 않다면, 다음 노드로 넘어간다.
값을 넣어서 생각해보면..
- A 노드가 head이므로, 9행에서 current가 A 노드를 가리키게 된다.
- A가 티켓 100장을 가지고 있으므로, counter가 0에서 100으로 증가한다.
- 100 < 300, 아직 winner ticket의 범위에 도달하지 않았으므로 다음 노드인 B로 넘어간다.
- B가 티켓 50장을 가지고 있으므로, counter가 100에서 150으로 증가한다.
- 150 < 300, 아직 winner ticket의 범위에 도달하지 않았으므로 다음 노드인 C로 넘어간다.
- C가 티켓 250장을 가지고 있으므로, counter가 150에서 400으로 증가한다.
- 400 > 300, C의 티켓 범위 안에 winner ticket이 있음을 확인했으므로, C를 winner process로 정하고 루프를 종료한다.
원래 가장 기초적인 Linked list에서는 current가 NULL이 될 때까지 계속해서 뒤로 순회하지만, Lottery scheduling 알고리즘에서는 winner ticket만 정해진 정의역 안에서만 뽑혔다면 맨 마지막 노드까지는 반드시 winner process가 나오기 때문에 신경쓰지 않아도 된다.
또한 이 알고리즘에서 가장 중요한 정확성에는 영향을 주지 않지만(끝까지 순회하면 반드시 winner process가 나오니까!), 이 Linked list를 ticket 갯수 내림차순으로 정렬하면 당연히 순회 초반에 winner ticket을 가진 node가 발견될 확률이 높으므로 검색 횟수가 최소화될 수 있다.
9.4. An Example
세부적인 내용은 어느 정도 파악되었으니, 이 Lottery scheduling의 작동 방식을 구체적인 예시를 통해 다시 한 번 분석해보자. (두 개의 작업이 100장씩 티켓을 가지고 있으며, 동일한 실행 시간 R을 가진다고 가정한다.)
아까 뭉뚱그려서 각각의 추첨이 독립 시행이기 때문에 큰 수의 법칙을 따르므로 추첨이 많아질수록 우리가 현재 기대하고 있는 A : B = 1 : 1의 CPU 점유율을 보일 것이라 가정할 수 있는데, Lottery scheduling은 비결정적인 알고리즘이므로 두 작업이 거의 동시에 종료되지 않고 종료 시점이 서로 좀 차이가 날 수 있다.
이 차이를 Unfairness metric(불공정 지표) U, 즉 첫 번째 작업이 종료된 시간을 두 번째 작업이 종료된 시간으로 나눈 값으로 정의하여 정량화해보자.
R=10일 때 최악의 경우, 그러니까 예상과 달리 한 프로세스가 계속 선택되어 다른 프로세스는 전혀 선택받지 못했을 때 첫 번째 작업이 시간 10, 두 번째 작업이 시간 20에 종료되므로 U = 0.5이다.
반대로 두 프로세스가 기대한대로 완전히 균등하게 CPU 사용권을 분배받은 이상적인 상황에서는, 종료 시점의 차가 예를 들어 0.0000001초 밖에 되지 않아 U = (20-0.0000001) / 20 = 0.9999.. 로, 1에 근사할 것이다.
즉, U가 작을수록 Scheduling이 불공정하게 된 것이고, 클수록 공정하게 되었다 할 수 있다.
위 그래프는 실제 시뮬레이션을 통해 작업의 길이, 즉 실행 시간에 해당하는 R이 짧을수록 불공정 지수가 최악(0.5)에 근사하고, R이 길어질수록 최선(1)으로 수렴함을 보여주고 있다. 즉, 시행 횟수에 해당하는 작업 시간이 짧을수록 스케줄러는 불공정할 수밖에 없음을 확인할 수 있다.
9.5. How To Assign Tickets?
확률론적인 스케줄링 방식의 근본적인 문제는 둘째 치더라도, 아직 Lottery scheduling에서 각각의 작업들에게 티켓을 몇 장씩 쥐어줄지에 대해서는 논의하지 않았다. 그냥 사용자가 알아서 주면 안되냐고?
그럴거면 운영체제 왜 들어 드랍해.
9.6. Stride Scheduling
Lottery scheduling가 뭐 구현하기 워낙에 단순하기도 하고 어지간하면 문제가 없을 것 같지만, 위에서 살펴 보았듯 '정확한' 점유율을 보장해줄 수가 없다. Nondeterministic하니까.
그렇기 때문에 Deterministic한 Stride scheduling이 1995년에 고안되었다.
이 Stride scheduling에서 각 작업들은 티켓이 아니라 각각의 보폭(stride)를 가지고 있는데, 이 보폭은 대강 보폭의 반비례 하는 값이다. 예를 들어 아까 A, B, C에게 티켓을 100, 50, 250장씩 주었는데, 이걸 보폭으로 계산하면 대충 100, 200, 40이 될 수 있는 것이다. (이 경우 10000을 티켓 갯수로 나누었다.)
Stride scheduling에서 각각의 작업들은 실행될 때마다 pass라는 값에 stride 값을 더하는데, 스케줄러가 이 pass값을 서로 비교해 가장 pass 값이 작은 작업을 실행하는 간단한 규칙만 가지고 있다. 교수님께서 이 Stride scheduling의 기본 원리를 "뱁새가 황새보다 유리한 상황"이라고 설명해 주셨는데, 무슨 말인지 한 번 씹고 뜯고 맛까지 봐보자!
아까 A, B, C의 보폭을 100, 200, 40으로 정한 상황에서부터 시작하겠다.
모든 작업은 시스템에 도착했을 때 pass 값이 0으로 초기화된다고 가정하고, pass 값이 같으면 그 중 아무 프로세스나 실행할 것이므로 일단 A를 먼저 골랐다고 생각해보자.
그럼 A가 먼저 실행되고, 실행된 다음 pass값을 A의 보폭인 100만큼 올려준다.
그 다음으로 B와 C의 pass 값이 A보다 작은 0이므로 이번에도 임의로 B를 골라 실행시키고 B의 보폭인 200만큼 B의 pass 값에 더해준다.
그 다음으로는 이젠 C가 유일한 pass 최솟값을 가지는 프로세스이므로, C를 실행시키고 C의 보폭인 40만큼 C의 pass 값에 더해준다.
이 다음부터는 좀 복잡하니까, 표로 정리해서 진행 상황을 추적해보자.
저기 주황색 Pass, 또는 P라고 그려둔 부분이 해당 프로세스가 스케줄러에 의해 선택되어 time slice 동안 실행되고, 각각의 pass값에 stride만큼 값을 더했음을 표시한 것이다.
오른쪽의 'Who Runs?' column을 보면 알 수 있듯이, 8번 중 A는 2번, B는 1번, C는 5번으로 stride과 같음을 알 수 있다! 여기서 황새는 보폭이 큰 B이고, 뱁새는 보폭이 작은 C가 되는 것인데, Stride가 작을수록 더 총총총총 하고 많이 스케줄링 되기 때문에 황새보다 뱁새가 유리한 상황이라고 비유하신 것이었다 ㅎ 🐤
자자 다시. Lottery scheduling이 Nondeterministic하여 (근사할지언정) 주어진 ticket의 비율만큼 CPU를 점유할 보장이 없는 반면, Stride scheduling에서는 반드시 각각의 작업들이 CPU를 정해진 비율만큼 점유함이 보장되는, Deterministic한 알고리즘임에 주목하자.
그럼 Lottery scheduling을 왜 배운거냐고?
Stride scheduling과 달리 Lottery scheduling은 티켓의 갯수를 제외하면 어떤 상태 값도 가지고 있을 필요가 없다. 반면 Stride scheduling에서는 반드시 필요한데, 바로 중간에 새 프로세스가 추가된 상황 때문이다.
Stride scheduling에서 만약 어느 정도 A, B, C가 실행되어 pass가 누적된 상황에서 새 프로세스 D가 추가되었을 때 pass 값을 0으로 초기화해준다면, 당분간은 D의 pass 값이 계속 최솟값일 것이기 때문에 쭉 D만 실행되는, 일종의 기아 상태가 지속될 것이다. 따라서 뭐.. pass값을 A, B, C의 pass값 평균으로 초기화 해준다던가, 가장 작은 pass 값으로 맞춰준다던가 하는 식으로 상태를 계속해서 저장 및 추적해야 하는데, Lottery scheduling에서는 그런거 없이 Head든 Tail이든 연결 리스트에 노드만 하나 추가해주면 되기 때문에, 이런 고민을 할 필요가 없다는 점에서 유리하다고 할 수 있다.
9.7. The Linux Completely Fair Scheduler (CFS)
Stride scheduling이 다 좋은데, 이 pass값에 대한 처리 작업만 전체 CPU 사용량의 5% 정도를 소모한다고 한다.
때문에 현재 Linux 시스템에서는 Completely Fair Scheduler(CFS)라는 것을 사용하는데, 이름 그대로 공정할 뿐만 아니라 기존의 스케줄링 방식보다 더 효율적이고, 확장성 좋은 방법이라고 한다.
Basic Operation
앞에서 배운 스케줄링 기법들이 고정된 time slice를 전제로 하는 반면, CFS는 모든 프로세스들에게 CPU를 말 그대로 균등하게 배분하고자 하는데 이걸 Virtual runtime(vruntime)이라는 간단한 카운팅 기반의 기술을 통해 구현한다.
Stride scheduling의 기본적인 개념은 유사하다.
스케줄러는 vruntime이 가장 낮은 프로세스를 다음 실행할 작업으로 선택하고, 각 프로세스는 실행될 때마다 각각의 vruntime 값을 축적시킨다. 다만 이때 Stride scheduling과 달리 stride 등의 고정된 값이 아니라 일반적으로 각각의 vruntime 값은 물리적(실제) 시간에 비례하여 동일한 비율로 증가시킨다는 점이 다르다. (그럼 이전의 stride, ticket 따위로 표현된 가중치 없이 단순한 Round Robin 방식과 time slice를 동적으로 계산한다는 점 말고 어떤 것이 다른지는 아래서 생각해볼 것이다.)
엥? 뭔가 겉도는 것 같은데, 그럼 애초에 어떻게 스케줄러가 현재 작동중인 프로세스를 중단시키고 다음 프로세스를 실행시킬 때를 결정하는 걸까? time slice가 고정 값이 아닌데?
만약 프로세스를 실행시키는 시간을 너무 짧게 해놓으면 Fairness는 증가하겠지만 Context switching 비용으로 인해 성능이 떨어질 것이고, 그렇다고 너무 길게 해놓으면 반대로 성능 측면에서는 좋아지지만 공정함의 측면에서 떨어질 것이다. 흠..
CFS는 이 voo-doo constants 느낌 나는 이 적절한 선을 다양한 값들을 사용해 계산함으로써 제어하는데, 예를 들어 sche_latency, min_granuality 같은 것들이 있다.
CFS에선 이 sche_latency 값을 사용해 context switching 발생 이전에 새로 선택된 다음 실행할 프로세스를 얼만큼 오래 실행할지 결정한다고 하는데, 솔직히 안와닿아서(...) 예시부터 살펴보겠다.
예를 들어 sched_latency 값을 48이라 하고, 4개의 프로세스가 현재 실행되고 있다면, CFS 스케줄러는 이 sched_latency 값을 실행되고 있는 프로세스의 개수인 4로 나누어 각각의 프로세스가 CPU를 사용할 수 있는 시간인 time slice를 12ms로 동적으로 계산한다.
아하. 한 100ms까진 프로세스 A, B, C, D가 시스템에 있으므로 time slice를 12ms로 짧게 주고, C와 D가 끝난 이후로는 A, B 밖에 없으므로 A, B가 24ms씩 RR로 실행되도록 했다는 거구나! sched_latency 값은 시스템에 존재하는 프로세스들이 모두 한 번씩 실행될 때까지 소요할 시간 정도로 이해할 수 있을 것 같다.
Stride scheduling에서는 새 프로세스가 들어왔을 때 pass 값을 어떻게 초기화해주어야 할지 고민해야 했는데, CFS에서는 vruntime 값을 비교해서 다음으로 실행할 프로세스를 찾는데 시간이 들어가는건 동일하지만 상태값을 비교하는 작업 외에는 추가적으로 뭘 더 해줄 필요가 없다. 그냥 상수 시간 만큼 소요해서 그때그때 각각의 프로세스가 CPU를 점유할 시간을 계산해 주기만 하면 되니까!
그런데 만약 너무 많은 프로세스가 시스템에 존재한다면 어떻게 될까? sched_latency가 48ms인데 프로세스가 96개이면? 48/96 = 0.5ms로 time slice를 정해야 하는데, 1ms보다 작은 단위로는 timer가 작동할 수 없다면,,? 심지어 12개의 프로세스가 4ms씩 CPU를 점유한다고 하더라도, Context switching이 너무 잦아져 성능이 측면에서 나빠질 수도 있다.
그렇기 때문에 필요한 또 다른 매개 변수가 바로 min_granularity이다. 모르는 단어라서 사전을 찾아 봤는데 직역하면 '최소 세분성' 정도 되는 것 같다.
말 그대로 모든 프로세스가 최소 min_granuality보다는 오래 CPU를 사용할 수 있도록 하기 위한 값으로, 위에서 12개의 프로세스, sched_latency가 48ms로 설정되어 있는 상황에서 min_granuality가 6ms로 설정되어 있다면 시스템에 존재하는 모든 프로세스들을 한 번씩 다 실행시켜주는데 총 6 * 12 = 72ms가 소요될 것이다. Fairness 측면에서는 살짝 손해를 보겠지만,, 그래도 잦은 context switching으로 인해 성능이 와장창 무너지는 것보다는 낫지 않겠는가!
Weighting (Niceness)
이외에도 CFS에서는 임의로 프로세스의 우선 순위, 그러니까 CPU 점유율을 제어할 수 있는 방법을 제공하는데, 이걸 앞의 Lottery scheduling에서의 티켓이나, Stride scheduling에서의 보폭 같은 것이 아니라 프로세스의 Nice level 메커니즘으로 해결한다.
각 프로세스의 nice 값은 기본적으로 0으로 설정되어 있고, -20부터 +19까지 설정 가능하다.
이때 +19에 가까워질수록 우선 순위가 낮음을 의미하고, -20에 가까워질수록 우선 순위가 높음을 의미한다.
이 nice level은 위와 같이 각각의 weight에 mapping 되어 아래와 같이 time slice를 계산하는데 사용된다.
여기서 weight_k는 해당 프로세스에 부여한 가중치를 의미하고, 분모에 해당하는 값은 현재 시스템에 존재하는 모든 프로세스들의 가중치 합을 의미한다.
즉, niceness가 낮다면 weight가 높아 상대적으로 sched_latency 중 높은 비율을 차지하게 되는 것이고, niceness가 높다면 weight가 낮아 상대적으로 sched_latency 중 낮은 비율만을 차지하게 되는 것이다.
구체적인 수치로 예를 들자면, 높은 가중치인 niceness -5를 가지는 프로세스 A와 가중치가 따로 재설정되지 않은 프로세스 B가 있을 때, 각각의 가중치가 3121, 1024로 대강 A가 sched_latency의 75% 정도, B가 25% 정도를 차지하게 되는 것이다.
CFS에선 time slice 뿐만 아니라 vruntime에도 이러한 가중치를 반영하고 있는데, 아래와 같다.
여기서 weight_0은 niceness가 0일 때의 가중치, 그러니까 각 프로세스가 기본적으로 갖는 가중치를 의미하고, weight_i는 해당 프로세스에 부여된 가중치, runtime_i는 위의 time slice 계산식과 min_granuality 등의 여러 요소등에 의해 결정된 실제 프로세스의 실행 시간을 의미한다.
여기서 저 아무렇게나 만들어놓은 것 같은 prio_to_weight 값의 진가가 드러나는데, nice 값의 차이만 일정하면 두 프로세스의 nice 값의 절대적인 위치는 상관이 없도록 되어 있다!
예를 들어 A와 B의 niceness가 각각 -5, 0이어서 weight가 3121, 1024라고 하면, 각각 약 sched_latency * 0.753, sched_latency * 0.247만큼을 점유하고, 만약 A와 B의 niceness를 5, 10으로 조정한다고 하더라도 두 프로세스의 niceness 차이는 5로 동일한데, 이 경우 weight가 각각 335, 110이므로 time slice를 sched_latency * 0.753, sched_latency * 0.247만큼씩 점유한다. 와!
Using Red-Black Trees
CFS를 개선할 수 있는 방법이 또 남아 있는데, Lottery, Stride scheduling에서 연결 리스트를 사용했던 것과 달리 프로세스의 정보를 저장하기 위해 더 복잡한 자료 구조인 Red-Black Tree를 사용할 수도 있다고 한다.
Red-Black Tree를 사용하면 선형 시간보다 짧은 로그 시간 안에 실행할 프로세스를 찾고, blocked 되었을 때 트리에서 해당 프로세스를 삭제하며, 다시 ready로 전환되었을 때 트리에 프로세스를 다시 삽입하는 과정 역시 로그 시간 안에 수행할 수 있다.
Dealing with I/O And Sleeping Processes
마지막으로 I/O, Sleep 상황에서 가장 작은 vruntime을 가지는 프로세스를 선택하는데서 문제가 발생할 수 있다!
예를 들어 프로세스 A는 계속 실행되고 있고, B가 한 10초 정도의 긴 시간 동안 sleep 상태인 상황을 떠올려보자.
B가 sleep 상태로부터 깨어나게 되면, 그 시점의 A의 vruntime보다 B의 vruntime이 10초만큼 작을 것이기 떄문에, A는 영문도 모른채 다음 10초동안 거의 대부분의 CPU 사용권을 B에게 넘겨 기아 상태에 빠지게 될 것이다.
CFS에서는 sleep 상태에 빠져 있었던 프로세스가 다시 깨어날 때, 위에서 얘기한 Red-Black Tree의 가장 작은 vruntime 값으로 설정해 줌으로써 해결한다. Red-Black Tree이므로 최솟값을 가지는 노드를 탐색하는데 로그 시간 만큼만 소요되므로 overhead도 없고, A의 기아 상태 역시 해결할 수 있는 것이다!
마무리
Proportional share scheduling에 해당하는 Lottery scheduling, stride scheduling, CFS를 공부했다.
음 사실.. Lottery scheduling에서 Stride scheduling으로는 Nondeterministic -> Deterministic으로 흐름이 확실히 이해가 되었는데, Stride scheduling -> CFS는 연결이 잘 안된다.
- CFS가 weightness를 상수 시간 안에 계산할 수 있는건 알겠는데 Stride scheduling에서도 마찬가지로 각각의 프로세스 정보에 들어 있는 stride 값을 그냥 더해주기만 하면 되는거니까 크게 차이가 없는 것 같고,
- 어차피 최소 vruntime(pass)을 가지는 프로세스를 찾아야 한다는 점에선 또 똑같고
- Stride scheduling에서 RB Tree를 사용할 수 없기 때문에 최소 pass 값을 연결 리스트에서 찾아야 하는건 받아들이겠는데, 왜 Stride scheduling에서 RB Tree를 사용할 수 없는지
이 세 가지 의문이 아직 풀리지 않은 것 같다. 강의나 전공서에서 놓친 부분이 있는 것 같으니 시험공부 리뷰 할 때 다시 찾아봐야겠다. 오늘은 너무 피곤해 ㅠ
