운영체제 공부 3 - Scheduler 2(CFS)

[ 시작하기에 전에 ]

 CFS 알고리즘은 이전 배경지식에서 말했던 대부분의 문제를 해결하고 상당히 합리적인 Scheduling을 가능하게 해준다. 이를 이해하기 위해서는 프로세스의 state에 대해서 이해를 해야하고 이전 priority에 따른 scheduling에 관해서 이해하고 있으면 조금 더 이해가 쉽다.

 

[ CFS 알고리즘 ]

 CFS는 운영체제 공부 3에서 말한 모든 상태들에 대해서 괜찮은 답을 내준다. CFS에서 알아야 될 개념은 Weight, time slice, vruntime이다.

 

Weight는 priority에 따라 프로세스 자체가 가지는 비중을 의미한다. wieght에 따라서 time slice의 값과 vruntime에서의 값이 결정되게 된다. MLFQ에서의 Priority와 뭐가 다른지는 모든 설명이 다 끝나고 이야기를 하려고 한다.

 

[ Weight ]

Weight는 프로세스의 priority에 따라서 정해지며 이전에 과제로 CFS 스케쥴러 구현에서 사용했던 weight 값을 구하는 공식은 아래와 같다.

 

weight = 1024 / (1.25)^(priority-20)

 

이렇게 되면 priority값이 클수록 더 작은 weight 값을, priority가 작을 수록 더 큰 weight 값을 가지게 된다. 이 weight를 통해서 time slice와 vruntime을 구하게 된다. 실질적으로 계산하기에는 생각보다 float의 거듭제곱 연산은 꽤 많은 resource를 요구하기에 priority 개수만큼의 값을 미리 하드코딩해서 사용한다.

 

 

[ Time slice ]

time slice는 프로세스의 작동시간으로 다음과 같이 구한다.

 

time slice = scheduling latency x (weight of current process / total weight of runnable process)

 

이 말은 Runnable process, 즉, 이전 게시글에서 ready 상태에 있는 프로세스의 모든 weight 값의 합에 대한 현재 scheduling되는 프로세스의 weight 값의 비율을 구하고 그 값에 임의로 정한 scheduling latency를 곱하여 정상종료 시 작동할 시간을 구한다. latency는 linux 기준으로 6ms였던 것으로 기억을 한다.

 

[ vruntime ]

vruntime은 프로세스의 scheduling되는 기준을 정하는 것으로 작동시간과 그 프로세스의 weight에 따라 계산이 된다.

 

vruntime += d(runtime) x (1024 / weight of current process)

 

vruntime에서 d(runtime)이 가지는 의미는 실제 작동 시간을 고려하여 계산을 하겠다는 것을 의미하고 해당 프로세스의 weight에 대해서도 고려를 하겠다는 것을 의미한다. 또한 vruntime이 낮은 프로세스를 먼저 scheduling 함으로써 작업 중인 모든 프로세스의 vruntime을 유사하게 하여 CFS 알고리즘은 작동한다.

 

이 3가지 개념을 알고나면 이런 의문이 들 수도 있다. 새로운 프로세스가 기존 작동하던 프로세스로부터 fork 되면? 이전에는 없었던 프로세스가 Ready 대기열 상태로 들어오면? 기존 vruntime이 엄청 누적되면 결국 기아 상태가 생길 수 있지 않을까? 이런 의문이 들 수도 있겠지만 이에 대한 방법을 모두 다 적는 것은 불가능하다고 생각했다.

 

[ CFS의 장점 ]

 

이를 통해 알 수 있는 점 첫 번째는 priority에 대한 처리이다. MLFQ에도 Priority가 있지만 생기는 문제는 Priority가 같은 우선순위 값이 있으면 동일한 Priority에 대해선 RR 방식으로 돌아가므로 우선 순위가 낮은 프로세스는 실행을 할 수 없다는 문제가 있었다. 하지만 CFS에서는 이 문제를 작동시간의 차이로 priroity를 사용함으로써 기아상태가 되는 프로세스가 없게 만들어준다. 또한 중요한 프로세스는 더 오래 작동시킴으로써 공평함과 차등성을 동시에 보여준다.

 

 두번째는  FILE I/O, Lock, sleep 같은 상황을 고려한 scheduling이 가능하게 된다. vruntime에 보면 계산되는 값이 d(runtime)으로 되어있다. 프로세스는 일반적으로 위에서 언급한 상황에서 yield()를 통해서 본인의 작동순서를 다른 프로세스에게 넘겨준다. 이것도 고려해서 우선순위를 정해야 하는데 이전에 설명한 scheduler에는 이런 부분에 대한 구현이 부족했다. 이 부분을 구현했기 때문에 리눅스에서 사용이 되지 않았을까 싶다.

 

  이상으로 CFS에 대한 설명을 마치려고 한다. CFS에 대한 이해에 도움이 되었으면 한다.