[OS/OSTEP] 09.CPU-sched-lottery : 비례, 배분을 이용한 스케줄링 #6

09.CPU-sched-lottery

 

# 시작하며

 비례 배분(Proportional Share) 혹은 공정 배분(fair share)의 개념은 우리가 지금까지 다뤄왔던 스케줄러와는 목적이 다르다. 지금까지는 반환시간이나 응답 시간을 최적화하는 방법으로 스케줄링을 했다면, 비례배분 방식은 CPU의 일정 비율을 실행 할 수 있도록 보장하는 것이 주된 목적이다.

 비례 배분 스케줄링의 좋은 예가 추첨 스케줄링(lottery scheduling)라고 한다. 다음 실행될 프로세스를 추첨하여 결정하는데 더 자주 수행되어야 하는 프로세스는 당첨 기회를 더 많이 준다. 

 이 기법이 과연 효과적인지, 또 어떻게 설계할 수 있는지에 대해서 알아보는 것이 목적이다.

 

# 추첨(lottery)권은 나(작업)의 몫이다.

 lottery 스케줄링이라는 이름에 걸맞게 추첨권을 통해 추첨을 한다. 추첨권은 프로세스가 받아야할 자원의 몫을 나타낸다. 간단히 말해 전체비율에서 해당 프로세스의 추첨권을 나눈 비율이 그 프로세스의 몫이 되는 것이다. 

 전체 100장의 추첨권중 A프로세스는 75장 B프로세스는 25장을 가진다면, 각각 75%와 25%의 비율을 가지고 있는 셈이다. 앞선 스케줄링에서는 타임슬라이스가 끝나면 반환시간과 여러가지를 고려해서 다음 프로세스를 결정했다면, 추첨스케줄링에서는 100장의 추첨권중 한장을 뽑고 거기에 A가 적혀 있으면 A, B가 적혀있으면 B프로세스를 선택한다. 당연히 비결정적이다. 이런 무작위 방식의 장점은 매우 빠르다는 것이고 생각보다 관리해야할 정보가 적어 가볍고, 일정 패턴을 띄는 작업에서는 오히려 더 효율적이다. VM단원에서 메모리 스왑을 결정하는 방식을 공부할때 LRU방식과 FIFO 랜덤등 여러 방식을 비교하는데, 랜덤이 은근 좋은 결과를 냈다.

## 그래서 무슨 말이냐고?

 75장과 25장을 가지고 A,B를 추첨하여 결정하는 방식을 자세히 봐보자. A는 0 ~74까지 숫자의 추첨권을 B는 75 ~ 99 까지 숫자의 추첨권 도합 100의 추첨권을 가진다. 이제 추첨을 시작한다.

위의 결과를 추첨권에 해당하는 작업과 대조해보자.

 이제 한가지 의문이 들어야한다. 현재까지 나온 결과를 봐보면 A는 16번, B는 4번 선택 됐다. 16/20, 4/20의 비율로 각각 80%와 20%의 비율을 보인다. 예상했던 75%와 25%와는 다른 결과를 보이는데 당연히 무작위성의 특징때문이다. 그러나 계속해서 시행해 나갈수록 근사치에 가까워질 것이다. 

 

# 추첨 기법

 추첨권 화폐(ticket currency)는 추첨권을 다루는 방법 중하나이다. 사용자가 추첨권을 자신의 화폐 가치로 자유롭게 할당한다는 개념이다. 마치 나라마다 다른 화폐가치(환율)이 적용되는 것과 비슷한 논리다. 아래 이미지를 보면서 다시 한번 생각해보자.

A와 B는 각각 100장, 결국 모두가 공용되는 공간 (기축통화 달러라고 생각하면 될거 같다)에서는 200의 정량적인 값을 가지고 있지만, A안에서의 A1과 A2에는 각각 500씩 1000을 부여한다. B는 10을 B1에 부여한다.  그리고 추첨은 전역에서의 추첨권(달러)로 하는 것이다.

 

## 그밖에 다른 방법

이 밖에도 추첨권양도( ticket transfer)와 추첨권 팽창(ticket inflations)방법이 존재한다.

양도의 경우 일시적으로 추첨권을 다른 프로세서에게 넘겨 주는 것이다. 클라이언트/서버 방식에서 유용하게 쓰인다고 한다.

팽창 방식은, 일시적으로 자신의 추첨권 수를 늘린다. 대신 가정이 붙는데 서로 신뢰하지 않는 그러니까 서로 CPU점유를 위해 경쟁하는 시나리오는 배제한다. 여튼 그렇게 신뢰하는 프로세스 사이에서 CPU 시간이 많이 필요하다면 추첨권의 가치를 늘려 더 많이 추첨이 되도록 한다.

 

# 추첨 스케줄링의 구현

 추첨 스케줄링은 구현이 단순하다고 했다. 난수발생기와 프로세스들의 집합을 가지는 자료구조, 추첨권 전체 개수가 끝이다. 

프로세스들의 집합을 관리하는 리스트

위 예제에서는 총 400의 추첨권중 난수발생기를 이용하여 한 숫자를 선택한다. 그리고 300이 뽑힌 상황을 가정한다.

 프로세스 리스트를 순회하면서 counter의 값이 winner의 값을 초과할 때 까지 각 추첨권 개수를 counter에 더한다. 값이 초과하게 되면 리스트의 현재 원소가 당첨자가 되는 것이다. 위 예에서는 counter에 먼저 100이 더해져 counter == 100이 된다. 그리고 winner(300)와 counter(100)를 비교 counter가 더 작기 때문에 다음으로 넘어간다. 이번에는 50을 더해 counter == 150이 되고 winner(300)랑 비교 작으니까 넘어간다. C랑 비교한다. counter == 400 이되고 winner(300)이기 때문에 선택된다. 이 방식이 뭔말인지 이해가 안갈 수 도 있다. 그래서 나도 몇번이고 다시보면서 counter의 의미를 이해하려고 했다.

 즉 리스트로 묶은 저 값들과 더해가는 counter는 해당 프로세스 티켓의 범위를 나타내는 것이다. 

A : 0 ~ 99 

B : 100 ~ 149

C : 150. ~ 399 

을 가지고 있기 때문에 winner를 비교하는 것이다. 근데 여긴 초과라는 표현을 사용했는데 이런 가정이라면 이상이라는 가정을 사용해야하지 않나 싶다. 그래서 0부터 시작이 아니라 1부터 시작인거 같다.

 

# 불공정 지표(unfairness metric)의 등장 (그러나 최신 개정안에서는 fairness mertric으로 변경..)

 두 작업을 동시에 종료시키기를 원한다. 그러나 추첨 스케줄링은 무작위성을 가지기 때문에 추첨이 어떻게 진행됐냐에 따라서 두개의 종료시간을 다를 수 밖에 없다. 불공정 지표(unfairness metric)를 나타내는 U는 첫번째 종료된 시간을 두번째 작업이 종료된 시간으로 나눈 값이다. 비슷한 시간에 종료될 수록 1에 가까워진다. 예를 들어 첫번째 작업이 10, 두번째 작업이 20에서 종료 했다면 U = 10/20 = 0.5가 된다. 당연히 분모는 마지막에 종료된 시간이어야 한다. 반대로 나누면 1보다 커지게 된다! 1이 최대이기 때문..

작업의 길이가 길어질수록 점점 1에 가까운 수치 즉 공평해지는 것(종료시간이 비슷해지는)을 볼 수 있다. 

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

 무작위성을 이용하면 스케줄러가 단순해져서 구현이 쉽고 어느정도의 정확성을 유지 할 수 있지만, 정확한 비율을 보장 할 수 없다. 특히 짧은 기간에만 실행되는 경우는 더욱 더 그러하다.  그렇기 때문에 일정 작업마다 체크포인트를 만들고 작업을 보정해나가는 방식인 보폭 스케줄링(stride scheduling)가 생겨났다.

## 보폭 스케줄링(stride scheduling)

보폭은 자신이 가지고 있는 추첨권의 개수와 반비례 한다. 즉 총량이 10,000이라면 결국 큰 보폭이든 작은 보폭이든 그 10,000에 도착을 해야한다. 

예를 들어 A,B,C가 아래와 같이 추첨권을 가지고 있고, 임의의 큰 값 10,000의 숫자로 나누면 보폭(stride)가 된다.

A	B	C
100 개( 추첨권 )	50 개( 추첨권 )	250 개( 추첨권 )

아래는 보폭

A	B	C
100 보폭	200 보폭	40 보폭

 

### 보폭 스케줄링을 사용

 보폭 스케줄러는 보폭과 pass 값을 사용하여 어느 프로세스를 실핼시킬지 결정한다. 처음에는 가장 작은 pass 값을 가진 프로세스를 선택한다. 프로세스는 실행시킬 때마다 pass값을 보폭만큼 쌓아간다. 처음에는 모두 다 pass 값이 0이기 때문에 아무거나 선택한다.

 선택은 보폭의 크기가 아닌 가장 작은 Pass값이다. 두번째 부터 B, C 가 모두 0이기 때문에 둘중 아무거나 선택하면 된다. 예제에서는 B를 선택한 경우이다. 어떠한 수를 추첨권의 갯수로 나눴기때문에 보폭은 결국 일정 비율을 유지할 수 있게 해준다. 

 A는 2번, B는 1번, C는 5번 실행 됐는데,  추첨권의 갯수(각각 100개, 50개, 250개) 의 비율과 정확히 비례한다.

 그렇다면 이러한 이점을 지니는 보폭 스케줄링 대신 추첨 스케줄링을 사용하는 이유는 무엇일까?

 보폭 스케줄링 중간에 새로운 작업이 들어온다면, pass값을 얼마나를 줘야하냐는 것이다. 만일 0을 준다면 pass가 500까지 진행 됐다면 새로 들어온 작업은 독점을 할 것이다. 뭐 이건 알맞은 pass값을 줘서 해결하면 된다~ 마법의 Voo Doo다

 또 CPU 사용 현황과 pass값을 추첨 스케줄링을 별도로 기록하고 유지할 필요가 없다.

 즉 추첨 프로세스는 새로운 프로세스가 들어오면 그냥 추첨권의 개수와 전체 추첨권의 개수만 갱신한다. 그렇기 때문에 추첨 스케줄링은 새로운 프로세스를 쉽게 추가할 수 있게 되는 것이다.

 

# 마치며

 이러한 추첨권 스케줄링의 무작위성을 보폭 스케줄링으로 극복하여 결정성을 띄게 만들어, 작은 횟수를 실행해도 비슷한 공정비율을 만들기 위해 노력했다. 그러나 여러 이유로 두 방법 모두 CPU 스케줄러로서 널리 사용되고 있지 않다고 한다.