[OS] 공평한 스케줄러 만드는 법 (Proportional Share) - OS 공부 5

안녕하세요 Pingu입니다!

 

저번 글에서 알아본 MLFQ 스케줄링 방법에 이어 이번 글에서는 스케줄러가 작업들에게 공평하게 CPU를 사용할 수 있도록 스케줄링하는 방법에 대해 알아보겠습니다. 제가 공부할 때 참고하고 있는 OSTEP 책에선 Chapter 9 - Lottery Scheduling 부분입니다.

 

Scheduling: Proportional Share

이번 글에서는 아까 말한 대로 proportional share (비례 지분) 스케줄러에 대해 알아보겠습니다. 지금까지 알아본 FIFO, SJF, STCF, RR, MLFQ에서 고려하던 Turnaround time, Response time을 잠깐 뒤로하고 스케줄러의 또 하나의 비교 기준인 fairness(형평성)을 중점적으로 볼 계획입니다. 형평성을 고려하면 프로세스들이 특정 비율로 CPU를 점유할 수 있도록 보장할 수 있습니다.

 

Proportional share 스케줄링을 구현하기 위한 초기 방법은 Lottery Scheduling입니다. 말 그대로 로또 복권처럼 이번엔 어떤 프로세스가 실행될지 추첨하는 방식입니다. 그럼 프로세스들을 어떻게 추첨할 것인지 , 만약 자주 실행되어야 하는 프로세스는 어떻게 처리할 것인지에 대해 다음 섹션에서 알아보겠습니다!

 

Basic Concept: Tickets Represent Your Share

그럼 lottery 스케줄링은 어떻게 동작하는지 알아보겠습니다. 우선 프로세스들에 로또 번호를 받는 것처럼 티켓을 부여합니다. 만약 어떤 프로세스를 자주 실행하고 싶다면 티켓을 많이 부여하면 됩니다! 그 말은 프로세스들이 보유한 티켓 비율이 해당 시스템의 자원 점유율이 됩니다.

 

예를 보며 이해해보겠습니다. A, B 프로세스가 있는데 A에게는 75장의 티켓 (0~74번 티켓)을 주고 B에게는 25장의 티켓(75~99번 티켓)을 줬다고 가정하겠습니다. 이렇게 티켓을 배분했다는 것은 사용자가 A 프로세스가 CPU를 75%의 시간만큼 사용하고 B 프로세스가 25%의 시간만큼 사용하길 바란다는 의미겠죠? 그럼 실제로 이렇게 티켓을 배분한 A, B 프로세스를 실행해보겠습니다.

어떤가요? 사용자가 원하는 대로 CPU 사용 시간이 75:25가 나왔나요? 위의 예에서는 사실 80:20으로 수행한 것을 볼 수 있습니다. 하지만 오랫동안 계속 수행하면 결국 사용 시간의 비율이 75:25에 수렴하게 됩니다.

 

Ticket Mechanisms

그럼 이제 lottery 스케줄링 방법에 대해 알았으니 lottery 스케줄링에서 사용한 ticket을 관리하는 메커니즘을 알아보겠습니다.

 

첫 번째 메커니즘은 Ticket Currency라고 하는 방법입니다. 쉽게 말하면 티켓을 마치 돈 같이 사용하는 개념입니다. 예를 들어 우리나라 돈 1000원을 국제 통화인 달러로 환산하면 대략 1달러가 됩니다. 이와 동일한 개념으로 어떤 프로세스에게 지역 통화를 부여하면 이를 CPU에서는 글로벌 통화로 바꿔서 스케줄링에 사용합니다. 이러한 방법을 Ticket Currency라고 합니다. 그럼 예를 보며 이해해보겠습니다.

예를 들어 사용자 A, B가 있고 각각 100개의 글로벌 티켓을 가지고 있다고 하겠습니다. A는 2개의 프로세스를 가지고 있고 B는 하나의 프로세스를 가지고 있습니다. A는 두 개의 프로세스에게 500개의 A 티켓을 제공하고 B는 하나의 프로세스에 10개의 B 티켓을 제공합니다. 만약 이를 그대로 스케줄링하게 되면 500:500:10의 비율로 스케줄링될 것이며 이는 공평하지 않습니다. 즉 A 티켓 1000장과 B 티켓 10장을 글로벌 티켓으로 바꿔줘야 합니다. 처음에 A, B가 가지고 있던 글로벌 티켓이 100개였기 때문에 이를 환산하면 A의 두 프로세스는 50개의 글로벌 티켓을 가지며 B의 프로세스는 100개의 글로벌 티켓을 갖게 됩니다. 결국 50:50:100의 비율로 스케줄링 되게 됩니다.

 

두 번째 메커니즘은 Ticket transfer입니다. 말 그대로 티켓을 전송하는 방법입니다. 예를 들어 어떤 프로세스가 자기에게 부여된 티켓이 과하게 많아서 바쁜 프로세스에게 티켓을 넘겨주는 방식입니다. 이러한 메커니즘은 클라이언트 / 서버 설정에서 유용합니다. 클라이언트 프로세스가 서버에게 어떤 작업을 하라는 메시지를 보냈습니다. 서버는 메시지를 받으면 해당 작업을 열심히 수행해야 합니다. 하지만 클라이언트는 그동안 할 일이 없다면 클라이언트는 자신에게 부여된 티켓을 서버에게 잠시 빌려줍니다. 그렇게 되면 서버는 더 자주 스케줄링 되게 되며 작업을 끝마치면 다시 클라이언트에게 티켓을 돌려주게 됩니다.

 

세 번째 메커니즘은 Ticket inflation입니다. 이는 프로세스들이 서로 협력하는 상황에서 사용할 수 있으며 만약 프로세스들이 경쟁 상태라면 의미가 없습니다. 프로세스들이 서로 협력하는 상황이라고 가정하고 예를 들면 어떤 프로세스가 갑자기 엄청 빠르게 수행되어야 하는 상황이 생깁니다. 이 경우 이 프로세스에게 부여된 티켓 수를 엄청나게 늘려서 CPU를 차지하게 만들 수 있습니다. 

Implementation

Lottery 스케줄링 방법의 가장 좋은 점은 간단하다는 것입니다. 지금까지 함께 알아봤는데 이를 만들기 위해서는 뭐가 필요할까요? 무작위로 티켓을 뽑는 것, 프로세스 목록을 가진 자료구조, 그리고 총 티켓수만 있다면 이를 구현할 수 있습니다. 예를 한 번 보겠습니다.

위의 그림과 같이 3개의 프로세스들이 있고 각 프로세스는 티켓을 가지고 있습니다. 여기서 총 티켓수는 400이 되겠네요. 우선 세 작업 중 어떤 작업을 스케줄링할지 정하기 위해 400 이하의 무작위 한 숫자를 하나 고릅니다. 만약 333이 나왔다고 가정하겠습니다. 그럼 어떤 프로세스를 스케줄링할지 어떻게 알아낼 수 있을까요? 우선 counter라는 변수를 하나 만들고 0을 할당합니다. 그런 뒤 A의 티켓인지 확인하기 위해 A의 티켓수만큼 counter에 더해줍니다. 즉 counter는 100이 되겠네요. 이번에 수행할 프로세스는 333번 티켓을 가진 프로세스인데 A는 갖고 있지 않습니다. 그러므로 B의 티켓 수를 counter에 더해줍니다. counter는 150이 되고 B 역시 333번 티켓을 가지진 않았네요. 그래서 마지막 C의 티켓 수를 더해주고 counter는 400이 됩니다. 즉 C가 333번 티켓을 가진 프로세스인 것을 알아냈고 C를 스케줄링하면 됩니다. 이를 C언어로 구현한 코드입니다.

이러한 과정을 좀 더 효율적으로 만들기 위해서는 티켓 수가 가장 많은 프로세스를 먼저 고려하는 것이 좋습니다. 그 이유는 아주 단순하게 확률적으로 티켓 수가 가장 많은 프로세스가 무작위로 생성한 티켓을 가질 확률이 높기 때문이죠!

 

An Example

이제 lottery 스케줄링을 fairness라는 관점으로 다시 살펴보겠습니다. Fairness는 예를 들어 A, B 프로세스가 있고 A 프로세스가 끝나는 시간을 C1, B 프로세스가 끝나는 시간을 C2라고 하겠습니다. 그리고 먼저 끝나는 작업을 A라고 하겠습니다. 여기서 Fairness를 구하면 C1/C2의 값이 됩니다. 이 값은 0.5일 때 가장 형평성이 안 좋다고 할 수 있고 1일 때 가장 좋다고 할 수 있습니다. 자세히 살펴볼까요?

 

A 프로세스 도착시간 0초, 수행 시간 : 10초, 완료 시간 10초 C1 = 10초

B 프로세스 도착시간 0초, 수행시간 : 10초, 완료시간 20초 C2 = 20초

fairness = C1 / C2 = 10 / 20 = 0.5

 

위와 같은 상황이 최악의 상황입니다. A 프로세스가 모두 끝난 뒤에야 B 프로세스가 동작하기 때문이죠. 그럼 가장 좋은 경우를 살펴보겠습니다.

 

A 프로세스 도착시간 0초, 수행시간 : 10초, 완료시간 19.9999초 C1 = 19.9999초

B 프로세스 도착시간 0초, 수행시간 : 10초, 완료시간 20초 C2 = 20초

fairness = C1 / C2 = 19.9999 / 20 = 1

 

어떤가요? A 프로세스와 B 프로세스가 lottery 스케줄러로 잘 스케줄링되어 번갈아가며 수행되어 완료되는 시간이 동일하게 되면 그때 fairness가 1이 나옵니다!

위의 그림을 보면 두 작업의 길이가 1에서 1000까지 있을 때 평균 fairness를 나타낸 그래프입니다. 그래프에서 볼 수 있듯이 작업 시간이 짧으면 형평성이 안 좋을 수 있습니다. 즉 작업 시간이 길어서 lottery 스케줄러가 오랫동안 실행되어야 공정한 결과에 수렴하게 됩니다. 여기서 lottery 스케줄링의 문제점이 보입니다. 작업시간이 짧으면 공평하지 않을 수 있다는 거죠!

 

How To Assign Tickets?

아까 본 문제점과 같이 lottery 스케줄링에서 해결 못 한 문제는 티켓을 프로세스에 어떻게 할당할 것이지에 대한 방법입니다. 한 가지 방법은 사용자가 가장 잘 안다고 가정하는 것입니다. 이 경우 각 사용자에게 티켓을 전달하고 사용자는 원하는 대로 프로세스들에게 티켓을 나눠주는 것이죠. 어떤가요? 여러분이 프로그램을 실행할 때마다 음.. 이건 중요하니까 티켓 많이 줘야지! 하면서 프로그램을 실행한다면.. 많이 귀찮지 않을까요?

 

실제 사용되는 티켓 할당 방법에는 Cloud Computing에서는 요금제에 따라 티켓을 할당하는 방법도 있고 실시간 시스템에서는 우선순위에 따라 티켓을 할당하는 방법이 있습니다.

 

티켓을 어떻게 줄 것인지를 정했다고 하더라도 지금은 말 그대로 복권 방식으로 누가 수행될지는 랜덤이죠. 이렇게 어떤 결과를 가져올지 확실하지 않은 것을 Not deterministic이라고 합니다. 그럼 어떻게 이를 deterministic 하게 만들 수 있을까요? 바로 다음 섹션에서 나타나는 Stride 스케줄링로 이를 구현할 수 있습니다!

Stride Scheduling

아까도 언급한 대로 lottery 스케줄러는 간단하게 구현이 가능하지만 늘 공평하게 프로세스들을 스케줄링할 수는 없습니다. 따라서 언제나 공평한 스케줄러를 만드는 방법을 연구했고 Waldspurger라는 분이 Stride Scheduling을 발명했습니다!

 

Stride는 보폭이라는 뜻으로 프로세스가 실행되면 보폭만큼 걷는다는 아이디어에서 출발합니다. Stride 스케줄링 방법에서도 프로세스들에게 티켓을 주는 것은 동일합니다. 하지만 stride라는 티켓 수에 반비례하는 변수를 하나 추가해서 fairness 문제를 해결한 방법입니다. 각 프로세스마다 Stride 구하는 방법은 티켓수를 어떤 값으로 나누면 됩니다. Stride 스케줄링에는 프로세스마다 pass value라는 변수가 있습니다. 처음엔 모두 0으로 초기화되어 있으며 프로세스를 한 번 수행할 때마다 해당 프로세스의 pass value 값에 아까 구한 stride 값만큼 더해줍니다. 실행할 프로세스는 이 pass value 값이 가장 작은 프로세스를 실행하게 됩니다. 예를 보며 stride 스케줄링 방법을 알아보겠습니다.

위의 표에서 보면 A, B, C라는 프로세스가 있습니다. A 프로세스는 티켓을 100개, B 프로세스는 티켓을 50개, C 프로세스는 티켓을 250개 가지고 있습니다. 저희는 stride 스케줄링을 할 계획이므로 각 프로세스 별 stride 값을 구해줘야 합니다. 이때 동일한 값을 티켓 수로 나눠주면 되는데요 10000을 가지고 나눠보겠습니다. 그렇게 하면 A 프로세스는 10000 / 100 = 100, B 프로세스는 10000 / 50 = 200, C 프로세스는 10000 / 250 = 40이라는 stride 값을 갖게 됩니다. 그런 뒤 pass value 값이 가장 작은 프로세스를 실행합니다. 위의 예에서는 A 프로세스를 가장 먼저 실행했네요! 그렇다면 A 프로세스의 pass value 값에 stride 값을 더해줍니다. 이렇게 반복하다 보면 200초에 어떤 결과가 나타날까요? 결과를 보기 전에 아까 프로세스 별 할당된 티켓 수의 비를 확인해보겠습니다. A : B : C = 100 : 50: 250 = 2: 1: 5 였습니다. 200초에 각 프로세스 별 수행된 횟수가 티켓의 비율과 동일한 2: 1: 5입니다. 프로세스들이 공평하게 수행됐을 뿐 만 아니라 횟수도 티켓 수의 비율과 일치합니다. 

 

그럼 Stride 스케줄링에는 문제가 없을까요? 이러한 상황을 가정해 보겠습니다. 아까 위의 예처럼 계속해서 작업들이 수행되고 있는 도중 갑자기 D 프로세스가 새로 들어왔다고 가정하겠습니다. 이때 D 프로세스의 pass value 값은 어떻게 설정해줘야 할까요? 만약 0으로 설정한다면 일정 시간 동안 D 프로세스가 CPU를 독점하게 되는 문제가 발생합니다. 이러한 부분은 Stride 스케줄링 보다 Lottery 스케줄링의 처리방법이 더 간단할 수 있습니다.

The Linux Completely Fair Scheduler (CFS)

지금까지 proportional share 스케줄링의 방법을 열심히 알아봤지만 Linux에서는 알아본 방식과는 다른 방식으로 fairness를 만족시킵니다. 바로 CFS(Completely Fair Scheduler)라는 이름의 스케줄링입니다. 이번 섹션에서는 CFS에 대해 알아보겠습니다!

 

효율성이라는 부분을 만족하기 위해 스케줄러는 아까 Stride 스케줄러에서 수행 도중 새로운 프로세스가 발생했을 때 pass value를 얼마로 설정할지에 대한 결정과 같은 부분에서 시간을 쓰지 않아야 합니다. 실제 스케줄링하는 작업이 CPU 사용시간의 5% 정도를 사용한다고 하니 효율적인 스케줄러는 아주 중요하다고 할 수 있습니다.

 

지금까지 알아본 스케줄링 방법에서 time slice는 고정되어 있었습니다. MLFQ에서는 큐마다 time slice가 다르긴 했지만 값이 변하진 않았었죠. 하지만 CFS는 virtual runtime이라는 기술로 모든 프로세스에게 CPU를 균등하게 분배하는 목표를 수행합니다.

 

각 프로세스들은 실행될 때마다 virtual runtime이 누적됩니다. CFS 스케줄러가 어떤 프로세스를 다음에 실행할지 결정할 때 프로세스들 중 virtual runtime이 가장 작은 프로세스를 선택합니다.

 

그렇다면 CFS 스케줄러는 고정된 time slice가 없는데 프로세스를 얼마나 실행할지 어떻게 알 수 있을까요? 만약 CFS가 실행 중인 프로세스들을 자주 바꾸면 fairness는 증가할 수 있지만 너무 잦은 context switch 때문에 성능은 저하될 것입니다. 그렇다고 너무 적게 바꾸면 fairness가 나빠집니다. CFS는 다양한 매개 변수를 통해 이러한 것을 해결합니다.

 

첫 번째 매개변수는 sched latency(예정된 지연 시간)입니다. CFS는 어떤 프로세스가 전환되기 전에 이 값을 사용하여 다음 프로세스를 얼마나 실행이 결정합니다. 보통 이 값은 48ms이지만 CFS 스케줄러는 CPU에서 이 값을 실행되는 프로세스 수로 나누어 time slice를 결정합니다. 그 결과로 CFS는 완벽하게 공평한 스케줄링을 할 수 있게 됩니다. 예를 하나 보며 이해하겠습니다.

 

위의 예에서는 처음에는 A, B, C, D 프로세스가 실행 중이지만 어느 순간부터 A, B 작업만 수행합니다. 이렇게 CPU에서 수행되는 작업 수가 줄어들면 CFS는 time slice를 늘립니다. 위의 그래프에서도 A, B 프로세스만 남았을 때 한 번 실행되는 시간이 더 길어진 것을 볼 수 있습니다. 그렇다면 위의 방식의 문제점은 무엇일까요? 위의 예에서는 프로세스가 최대 4개였으니 큰 문제는 없었지만 만약 프로세스가 아주 많다면 어떻게 될까요? time slice가 너무 작아져서 context switch가 너무 자주 발생하게 될 것이고 이는 성능 저하로 연결될 거 같아요!

 

프로세스가 아주 많아졌을 때 발생하는 문제를 해결하기 위해 새로운 매개변수인 min granularity를 추가해줍니다. 이름에서 보이는 min이라는 단어로 이 매개변수의 역할을 생각해볼 수 있을 거 같아요. 이 매개변수는 아무리 프로세스가 많아도 min granularity보다 time slice가 작아지지 않도록 하는 역할을 해줍니다. 이때 min granularity는 보통 6ms로 설정됩니다. 이를 사용하는 예를 보자면 10개의 프로세스가 있고 time slice를 구한다면 아까의 방식대로라면 48ms / 10 = 4.8ms라는 time slice를 가져야 합니다. 하지만 이젠 min granularity가 있기 때문에 6ms가 되는 것이죠. 이렇게 되면 fairness는 나빠질 수 있지만 효율성 부분에서는 좋아집니다.

 

 

CFS - Weighting(Niceness)

CFS 스케줄러는 프로세스 우선순위를 제어할 수 있습니다. 따라서 어떤 프로세스에게 높은 CPU 점유율을 제공할 수 있습니다. 이는 티켓으로 구현되지 않고 UNIX 메커니즘을 통해 수행됩니다. nice라는 매개변수는 프로세스에 대해서 -20 ~ +19까지 설정할 수 있으며 기본값은 0입니다. 우선순위라고 하니 이 값이 어떤 역할을 하는지 느낌이 오시나요? 맞습니다. 바로 이 값이 작으면 우선순위가 높은 것이고 크면 우선순위가 낮습니다.

위의 구조체는 우선순위 별 가중치입니다. 이 가중치를 사용해서 프로세스의 time slice를 구할 수 있습니다. 가중치를 사용해서 time slice를 구하는 식은 아래와 같습니다!

위의 식으로 실제 time slice를 한 번 구해보겠습니다. A, B 프로세스가 있고 A에는 nice 값을 -5로 B는 0으로 설정하겠습니다. 해당 값으로 가중치 값을 찾고 위의 식에 대입하여 time slice를 구해보면 A 프로세스는 43, B는 약 14가 나오게 됩니다. 이렇게 time slice 만으로 우선순위를 사용하는 것이 아닌 CFS에서 virtual runtime을 계산하는 방법에도 사용할 수 있습니다.

위의 식을 사용하여 아까 A, B의 virtual runtime 비율을 구해보면 1:3이 됩니다. 즉 A의 시간이 마치 3배 느리게 가는 거처럼 만드는 것입니다. 

 

CFS - Using Red-Black Tree

CFS는 효율성에 초점을 둔다고 처음 소개에서 말했습니다. 스케줄러가 좋은 효율성을 갖고 있다는 말은 다음에 실행할 작업을 빨리 찾을 수 있다는 말이 됩니다. 이는 아까 lottery나 stride에서 프로세스들의 종류를 저장하는 단순한 자료구조로는 발전시킬 수 없습니다. 그렇기 때문에 CFS는 red-black Tree라는 자료구조에 프로세스 정보를 저장하여 이러한 부분을 해결합니다. Red-black Tree는 단순한 이진트리와 달리 균형이 잡힌 트리이기 때문에 낮은 깊이를 유지하기 위해 추가 작업을 수행하기 때문에 연산수가 선형이 아님을 보장합니다. 

 

CFS는 이 구조에 모든 프로세스를 유지하지 않습니다. 실행 중이거나 실행 가능한 즉 Run, Ready 상태의 프로세스만 이 구조에 저장합니다. 예를 보며 이해해보겠습니다.

 

위의 트리에서 노드가 작업이고 각 노드에 적힌 수가 virtual runtime이라고 한다면 10개의 작업이 있고 각각 virtual runtime이 있습니다. 여기서 실행될 작업은 virtual runtime이 가장 작은 작업입니다. lottery, stride에서 사용하던 자료구조에서 실행할 프로세스를 찾는 작업은 O(N)의 시간 복잡도를 갖는 작업이었습니다. 하지만 tree구조를 사용하게 되면 시간 복잡도가 O(logN)으로 바뀌게 됩니다.

 

CFS - Dealing With I/O And Sleeping Processes

다음에 실행하는 가장 작은 virtual runtime을 선택하는 방법의 문제는 오랫동안 sleep상태에 있는 프로세스를 실행해야 할 때 발생합니다. 예를 들어 A, B작업이 수행되다가 B작업이 I/O를 발생해서 sleep 상태로 바뀌었다고 가정하겠습니다. 이 상태가 10초 동안 지속되어 A가 10초동안 CPU를 혼자 사용합니다. 그러다 B작업이 다시 ready가 되어 실행하려고 할 때 virtual runtime이 작은 작업을 계속 수행하게 되면 B가 CPU를 독점하는 문제가 발생합니다.

 

CFS는 이러한 문제를 작업이 시작될 때 작업의 virtual runtime을 변경하여 처리합니다. Sleep 상태에서 돌아온 작업은 virtual runtime을 트리에서 가장 작은 값으로 설정합니다. 이는 트리에는 실행 중인 작업만 포함되어있기 때문에 기아 상태를 방지할 수 있게 됩니다. 이렇게 CFS는 기아 상태를 방지하지만 오버헤드는 발생하지 않습니다.

 

Other CFS Fun

CFS에서는 더 많은 기능이 있다고 합니다. 그런데 책에서 지금 논의하기엔 너무 많다고 하네요 ㅜㅜ.. 책의 뒷부분에서 또 언급이 된다고 하니 그때 가서 더 알아봐야 할 거 같습니다! 빨리 알고 싶으신 분들은 따로 CFS를 더 깊게 공부해야겠지만요..

 

Summary

이번 글에서는 프로세스를 스케줄링하는 방법에서 고려할 사항 중 Fairness를 좋게 하는 방법에 대해 중점적으로 알아봤습니다. lottery 방법은 fairness를 좋게 만드는데 시간이 필요하기 때문에 이를 해결하기 위해 stride 방법을 만들었습니다. 그리고 실제 Linux에서 사용하는 스케줄러인 CFS에 대해서도 알아봤습니다. 

 

제 글이 스케줄러를 이해하시는데 도움이 되셨길 바랍니다.

 

감사합니다!

 

다음 글 : 멀티 프로세서 스케줄링