[운영체제] 6. Proportional-Share-Scheduling

Reference - Operating Systems: Three Easy Pieces

 

 

https://pages.cs.wisc.edu/~remzi/OSTEP/

Operating Systems: Three Easy Pieces

 

Proportional share scheduling은 이전 scheduler가 Turnaround time, Response time에 중점을 둔것과 달리 Fairness(형평성)에 초점을 둔다. 이점을 염두하며 각각의 scheduling 방식을 알아보겠다.

Lottery Scheduling

 

Lottery 스케줄링은 Ticket이라는 개념이 등장한다.

프로세스에 티켓을 부여하고, 티켓을 가지고 있는 만큼 자원을 점유할 수 있다.

 lottery 스케줄링에서는 티켓을 관리하기 위해 세가지 매커니즘을 사용한다.

1. Ticket currency : 글로벌 티켓을 설정하고 유저마다 티켓 수가 아닌 티켓 비율에 따라 cpu를 할당한다. 예를 들어 글로벌 티켓이 100개일 때, user A는 프로세스 a1, a2에 각각 티켓 2000개, user B는 프로세스 b에 티켓 100개를 할당했을 때

총 티켓 4000 : 100 = 2000 : 50, 즉 글로벌 티켓으로 환산했을 때 a1, a2, b는 50 : 50 : 100만큼 cpu를 사용할 수 있다.

2. Ticket transfer : 프로세스가 자기에게 너무 많은 티켓을 가지면, 바쁜 프로세스에게 티켓을 넘겨준다.

3. Ticket inflation : 프로세스가 서로 협력하는 상황이라 가정할 때, 특정 프로세스가 급히 수행되어야 하면 부여된 티켓수를 늘려 CPU를 점유하게 한다.

 

구현

구현을 위해 무작위로 티켓을 뽑는 함수와 프로세스 목록을 가진 자료구조, 총 티켓 수가 필요하다.

먼저 총 티켓 수 내에서 무작위 숫자를 골라 설정해둔다. 그 뒤 counter라는 변수에 0을 할당하고, 각각 프로세스가 가진 티켓을 counter에 더하는 일을 무작위 숫자보다 counter가 커질 때 까지 반복한다. 예를 들어 무작위 숫자가 333이고, 프로세스 A는 티켓이 100, B는 50, C는 250라고 가정해보자. 처음엔 333 > counter(=100=A), 333 > counter(=150=B), 333 < counter(=400=C)이므로 C를 스케줄링하게 된다. 이 과정을 효율적으로 하기 위해 티켓 수가 많은 순서대로 counter에 들어갈 프로세스를 고려한다면 연산 과정이 더 단순해질 것이다.

 

Fairness

fairness 관점에서 비교해보겠다. A, B프로세스가 있고 각각 프로세스가 끝나는 시간을 C1, C2라 하자.

C1이 C2보다 먼저 끝난다고 가정했을 때,  Fairness = C1/C2이다. 하지만 Lottery 스케줄러는 작업시간이 짧으면 형평성이 안좋아진다. (아래 그림 참고)

 

 

또한 이 방식은 random 변수를 쓰기때문에 결과를 보장할 수 없는 Not deterministic 방식이다. 이러한 문제를 해결하기 위해 Stride 스케줄링이 고안되었다.

 

Stride Scheduling

 

Stride 스케줄링은 lottery 방식처럼 티켓을 사용하지만, stride와 pass value라는 새로운 변수를 추가하여 fairness 문제를 해결하였다.

 

각 프로세스마다 Stride라는 '모든 티켓의 공배수를 프로세스가 가진 티켓으로 나눈 값'을 생성한다. 또한 프로세스마다 0으로 초기화된 pass value라는 값을 만들고, 각 프로세스를 수행할 때마다 pass value에 stride값만큼 더해준다.

그 후 pass value가 작은 값부터 cpu를 할당한다. 처음엔 초기값이 0이기에 랜덤하게 설정하여도, 최종적인 프로세스별 cpu 할당량은 같다.

예를 들어, 3개의 프로세스 A, B, C가 각각 티켓을 100개, 50개, 250개 가진다고 하자. 이때 10000을 티켓수만큼 나눈 값을 stride라 하면, 스케줄링 과정은 아래 그림과 같이 진행된다.

 

 

프로세스가 진행된 횟수는 티켓 비율과 같은 2 : 1 : 5이다.

Stride Scheduling의 치명적인 단점은 중간에 새로운 프로세스가 들어왔을 때 stride 값을 어떻게 설정해야 하는지이다.

새 프로세스의 stride를 0으로 설정하면 CPU를 한동안 독점하기에 Fairness 관점에서 공평하지 않을 것이다. 

 

Completely Fair Scheduler

 

Linux에서는 Fairness를 만족시키기 위해 Completely Fair Scheduler, CFS를 사용한다.

효율성 측면에서 스케줄링 과정에서의 overhead도 고려해야 하기 때문에, 최대한 연산과정을 단순화하여야한다.

CFS는 MLFQ와 달리 고정된 time slice없이 virtual runtime이라는 방법으로 모든 프로세스에게 cpu를 균등하게 분배한다.

 

각 프로세스들은 실행될때마다 virtual runtime이 누적되고, CFS는 이 vruntime이 가장 작은 프로세스에게 cpu를 할당한다.

프로세스를 자주 바꾸면 fairness는 증가하지만 context switch에 따른 overhead가 증가하여 효율이 안좋아진다.

CFS는 여러 매개변수로 이를 해결한다.

 

첫번째 매개변수로 sched latency가 있다. default 값은 48ms로, CFS에서 실행되는 프로세스 수로 이를 나누어 timeslice를 결정한다.

 

 

위 예시처럼 프로세스가 완료되어 줄어들게되면 스케줄러가 time slice를 늘린다. 하지만 이때 프로세스가 매우 많아지면 time slice가 짧아져 context switch overhead가 기하급수적으로 증가하게 된다. 

 

이때문에 두번째 매개변수인 min granularity를 추가한다. 프로세스가 아무리 많아도 min granularity보다 time slice가 작아질 수 없다. 일반적으로 6ms로 설정된다. fairness가 조금 안좋아지겠지만 최소한의 효율을 보장해준다.

 

세번째 매개변수로 nice 매개변수가 있다. CFS는 이 값으로 가중치를 부여해, 값이 작으면 우선순위를 높게 설정하고 크면 우선순위를 낮게 설정한다. 기본값은 0으로, -20~+19까지 설정할 수 있다.

 

 

교수님께서 해당값은 운영체제에 하드코딩된 값이지만 고정값이 아니라 hyperparameter로 작용할 수 있다고 한다.

이 값으로 프로세스의 vruntime을 업데이트하며, 계산식은 아래와 같다.

 

 

마지막으로 CFS는 효율성을 위해 Red-Black Tree를 사용한다. R-B Tree에 key를 vruntime으로, value에 process state를 저장하여 삽입 시 O(logn)을 보장한다.

 

마지막으로  Dealing With I/O and Sleeping Processes에 대한 문제가 있다. A, B 두 프로세스가 수행하다가 B가 I/O로 인해 blocked(sleep) 되었다가 다시 Ready가 될 때, B가 vruntime이 작아 cpu를 독점하게 된다.

이러한 문제를 해결하기 위해 CFS는 프로세스가 시작될 때 sleep 상태에서 돌아온 작업은 vruntime을 트리 내에서 가장 작은 값으로 설정한다. 이 방식을 통해 기아 상태를 방지할 수 있다.