Scheduling: Proportional Share

proportional share란?

비례 배분, 공정 배분(fair share)으로도 불린다.

정해진 비율대로 cpu를 나눠쓰게 하는 것에 집중한다. performance보다는 fairness에 초점을 맞추는 것이다.

 

 

Lottery scheduling

말그대로 추첨권 티켓의 소유권에 따라서 cpu를 분배하는 스케줄링 기법이다.

예를 들어 프로세스 a,b가 75%. 25%로 cpu를 나눠쓰게 하고싶으면 a에게 티켓 75장을, b에게 25장을 주는 것이다.

그리고 추첨된 각 티켓을 가지고있는 프로세스가 당첨된 것이므로 그 비율만큼 cpu를 사용한다.

Random number를 생성하며 진행되기 때문에, 시도할때마다 결과는 달라진다. (비결정적)

 

Ticket Mechanisms

1. Ticket currency

티켓을 화폐로 본다. 즉, 사용자가 발행한 티켓을 액면가 그대로 인정하지 않고, 각 사용자가 발행한 티켓의 가치(local currency)를 전체 티켓가치(global currency)로 환산한다.

2. Ticket transfer

티켓을 양도한다. client가 server에게 요청을 보내고 그 요청을 server가 처리할 때 server의 성능을 최대화하기 위해 client가 자신이 가진 티켓을 일부 서버에게 빌려준다. 그리고 처리가 끝나면 다시 client에게 티켓을 돌려준다.

 

3. Ticket inflation

티켓을 팽창시킨다. 필요한 경우 화폐를 팽창하여 global currency를 늘리고 cpu를 더 사용한다. 이를 위해서는 각 프로세스가 서로 신뢰관계에 있어야 한다. 그렇지 않으면 경쟁적 티켓발행으로 인해 공정 배분이 어려워진다.

 

lottery scheduling은 유연하다는 장점도 있지만, job을 일단 실행해보기 전에는 그 길이를 미리 알 수 없다는 근본적인 문제로 인해 각 job들에게 처음 티켓을 부여할 때 그 기준을 어떻게 해야하는가를 명확하게 결정하기 어렵다는 한계가 있다.

 

 

Lottery scheduling의 평가기준

lottery scheduling은 performance보다는 fairness에 집중한다. 그래서 fairness metric(=unfairness metric)이라는 수식을 만들어서 이를 평가한다.

예를들어 j1,j2라는 두개의 job이 있고, 둘의 실행시간은 R로 같다.

그리고  j1,j2순으로 실행되었다고 가정하면 각각 R, 2R에 실행이 끝날것이다.

여기서 "j1이 끝나는 시간/j2가 끝나는 시간"이 불공정 지표 u가 된다. 이 경우에 u는 0.5가 된다.

그런데 두 job이 번갈아가면서 공평하게 실행된다면 두 job이 끝나는 시간은 점점 더 유사해지고, u가 1에 가까워진다.

job의 길이 R이 길어질수록 u가 1에 수렴한다.

 

 

Stride scheduling

lottery scheduling에서는 어떤 시점에 어느 job에게 cpu를 스케줄링했는가가 random한 요소에 의존하기 때문에 비결정적이다.(non-deterministic) 

이것을 deterministic하게 만드는 스케줄링 기법이 stride scheduling이다. 이는 각 job마다 보폭을 다르게 주고 스케줄링하는 방식이다.

3개의 job a, b, c가 각각 100, 50, 250개의 티켓을 가지는 상황일 때,(즉 short job인 c를 우대할 때) 이것을 걸음수로 재해석한다.

즉, 10000이라는 거리를 가야한다고 생각하면 a는 100걸음을 가야하므로 보폭이 100, b는 50걸음을 가야하므로 보폭이 200, c는 250걸음을 가야하므로 보폭이 40이 된다.

또, 알고리즘을 가지고 pass값이 가장 작은 job에 cpu를 부여한다. 그리고 cpu를 한번 썼으면 한걸음을 갔다고 판단하고 그 결과를 큐에 다시 추가한다. 이 과정을 반복하면 아래 그래프와 같이 결국 우리가 원하는 비율대로 cpu를 나눠쓰게 된다.

pass값이 다 똑같으면 그냥 먼저 들어온 job에게 cpu를 준다.

이것은 결정적이므로 다시 시작해도 결과는 같다.

그런데 문제는 중간에 새로운 d라는 job이 추가되었을 때 그 pass값을 0으로 주면 d가 cpu를 독점하게 된다는 것이다. 따라서 d의 pass초기값을 적절히 주어야 한다. (voodoo constant, 정확한 기준은 없음)

만약 job의 증감에 유연하게 반응하는 lottery scheduling이었다면 추가 job이 생겼을 때 그냥 total tickets을 늘리고 진행했을 것이다.

 

 

CFS(completely fair scheduler)

윈도우에서는 MLFQ기반으로 스케줄러를 만들어 사용하지만, 리눅스에서는CFS라는 스케줄러를 쓴다.

share하는 것에 더 집중하여 cpu를 비례 배분하는 스케줄러이다.

 

round robin이나 MLFQ에서는 timeout을 결정하는 time slice가 큐 단위로 고정되어있었지만 stride scheduling이나 CFS에서는 그렇지 않다.

특정 job을 실행할때 time slice를 지정하여 타이머를 맞추고 실행시켜준다.

또 stride scheduling에서의 pass개념이 CFS에서는 virtual runtime인데, 개념은 같지만 계산하는 방식이 다르다.

CFS에서는 특정 cpu 사용구간(=schedule latency)을 현재 ready상태에 있는 process개수로 1/n하여 사용한다.

각 프로세스가 사용하는 cpu의 양은 매 schedule latency의 시작마다 공평하게 나누어 결정된다.

 

그런데 프로세스마다 우선순위가 다르므로, 무작정 1/n하는것이 아니라 weight, 즉 가중치를 반영하는 방법도 있다.

위로 갈수록 우선순위가 높아 weight를 크게 준다.

weight에 따라 우선순위에 차등을 두는 방법으로는 두가지를 살펴볼 수 있는데, 첫번째는 시간 폭(time slice)를 정할때 자기 weight값을 반영하는 방식이 있다.

다음으로는 vruntime(virtual runtime)에 weight값을 반영하는 방식이 있다.

즉 pass처럼 한걸음 한걸음 진행하는 과정에서도 가중치에 따라 걸음을 다르게 하는것이다.

weight0는 default weight

위의 식의 분모로 들어가는 weight i가 자기 자신의 weight값인데, 우선순위가 높은 쪽은 weight가 커서 이 분모가 커지므로 결국 vruntime은 작아져서 작은 보폭으로 job을 수행하게 되고, vruntime이 작으면 결국 cpu를 얻을 확률이 높아지는 것이다.

 

 

Using Red-Black trees

새로운 job이 추가될 때, queue형태에서는 전체를 다 scan해야 하므로 O(n)의 시간이 든다.

하지만 red-black tree를 사용하면 O(log n)에 해결이 가능하다.

red-black tree는 balanced tree이기 때문에, insert/delete가 일어날 때 마다 전체 균형을 맞추는 일을 끊임없이 한다.

 

 

Dealing with I/O and sleeping process

io가 발생했다는 것은 프로세스가 block되어 queue(or tree)에서 아예 사라진 것이다. (running > io요청 > blocked)

이 io처리가 끝나면 해당 프로세스는 ready상태로 가고 다시 queue로 들어가게 된다.

이때 CFS는 이 job의 vruntime값을 0이 아니라 현존하는 pass값들의 최소값으로 결정한다. (이 job의 cpu독점으로 인한 나머지 job들의 starvation을 막기 위해)

 

* 2023 국민대학교 소프트웨어학부 황선태 교수님의 운영체제 수업을 듣고 정리한 내용입니다.

* 원서 출처 : https://pages.cs.wisc.edu/~remzi/OSTEP/