cfs scheduling 1 & cfs group scheduling (1) cfs 스케쥴러

  "
  그리운 고향집에 이르느니, 집안 동복이 정답게 반기며,
      문 옆 어린것이 오셨나고 빙긋 올려다보네!  "
                                                                   도연명의 귀거래사중에서.

 

  cfs 스케쥴러는 문자그대로  " 완전히 공정한 스케쥴러"라는 뜻입니다.
  각각의 프로세스(태스크)에게 동일한 가상 time slice(quantum)가 할당됩니다.

  보통의 스케쥴러의 구현에서 각 각의 프로세스에게 10ms의  동일한 time slice를 부여하던 방식과 유사합니다.
  이 time slice를 vruntime이라고 하는데 , 중요한 점은 가상이라는(v는 virtual) 점입니다.

  프로세스 A 와 B가 실행 큐에 삽입 될 때 , 프로세스들의 vruntime은 큐상의 가장 적은 vrutime으로 초기화 됩니다.
  설명의 편의를 위해  가상 런타임의 time slice가 20으로 주어 진다고 가정하면,
  각 프로세스의 vrutime의 실행시간이 20에 도달하면 태스크 스위칭(스케쥴링)이 발생합니다.
  (단 이 상황은 이상적인 상황이고 실제 코드는 , vruntime으로 판단하지 않고 real time slice를 계산해 스케쥴링이
   결정됩니다.)

 즉 , timer 인터럽트 핸들러 -> vruntime 증가 -> 가상 실행시간의 증가량이 20을 초과하면 ->스케쥴링 수행
 식으로 동작합니다.

 여기서 중요한 점은 각 프로세스의 vruntime의 수행시간(slice)은 고정 되어 있으나,
 실제 real 수행시간, 즉 real time slice는 각 프로세스의 priority에 따라 다른 값을 갖는 점입니다.

 이의 구현을 위해 실제 코드 상에서는 프로세스의 priority에 해당하는 배열을 사용합니다.
 리눅스의 priority는 nice라는 값으로 표현되고 , -20 ~ 20의 범위를 갖습니다.( 값이 적을수록 더 큰 priority)

 간단한 예를 들면 ,   int piroty[2]={ 200, 100} 이라는 배열을 설정하고,
 nice 값이 0일때 200 , 1일때 100이 할당된다고 가정하겠습니다.
 
 그리고 중요한 개념이 스케쥴링 주기(period)라는 값입니다.
 이는 이 주기 동안 스케쥴러상의 실행 큐에 대기 중인 프로세스가 모두 실행되는 시간입니다.
 
 간단히 10ms 라고 할 때,
 프로세스 A의 실제 실행 시간은 = ( 실행주기) * (A의 priotiry) / ( A's priority + B's priority) 가 됩니다.   ----공식 1
 프로세스 A의 nice는 0 -> piority[0] = 200  ,, B: 100이 되며
 이를 계산하면  
 프로세스 A의 실제 수행 시간은   10ms *200/ 200+100) = 6.6ms 가 주어지며
 B는 3.3ms 가 주어 집니다.
 (여기서는 직관적인 이해를 위해 단순화한 공식을 제시합니다. 추후에 실제 코드상으로 정확한 공식을 제시하겠으나,
  단순화한 모델도 실제 공식과 동일한 논리와 개념이 적용됩니다.)
 즉 스케쥴러 큐에 대기 중인 프로세스의  priority에 따른 비율에 따라  스케쥴링 주기를 나누어 실제 실행시간이
 주어지게 됩니다.

 check_preempt_tick()라는 함수가 timer interrupt에서 호출 되는데, 이 함수에서 현재 실행되는 프로세스의
 time slice가 다 소진되었는지를 계산합니다.

 여기서 중요한 점은  각 프로세스의 실제 실행시간인 time slice는 priority에 따라 가변이지만 , 가상실행 시간은 동일한 값이
 주어집니다.
 이는 간단한 산수로 되는데,
 실제 실행시간은  ( 실행주기) * (A의 priotiry) / ( A's priority + B's priority) 이지만
 가상실행 시간은 위의 값에 (A의 priority)를 한 번 더 나눠줘서 process dependent부분을 상쇄시켜 줍니다.
 즉
  A의 vrutime 증가량 =  ( 실행주기) * (A의 priotiry) / ( A's priority + B's priority)  / (A의 priotiry)=          --공식 2
                             = ( 실행주기)/ ( A's priority + B's priority)

  B의 vrutime 증가량 =  ( 실행주기) * (B의 priotiry) / ( A's priority + B's priority)  /(B의 priotiry)=
                             = ( 실행주기)/ ( A's priority + B's priority)
 가 되어서 각 프로세스의 vruntime은 동일한 값으로 증가하게 됩니다.


이제 실제 커널상의 구현을 살펴 보겠습니다.
static const int prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};  이 변수가  프로세스의 priority에 따른  real time slice를 결정하는 배열입니다.

 맨 윗줄의 prio_to_weight[0]은  88761 로  priority가 -20으로 가장 높은  nice 우선순위를 갖는 값입니다.

이제 스케쥴러 런 큐에   priority가 다른 세개의 프로세스 a,b,c가 있고, 각각의 nice(priority)가 -20 , -15 , -16이 존재하는
상황을 살펴 보겠습니다. 그리고 실행주기는 10ms입니다.

a의 실제 실행 시간값( real time slice)는
   위의 공식에 의존해  10ms * ( 88761 ) / ( 88761 + 29154 +  36291) 가 됩니다.

커널 코드에 보면 , calc_delt_fair( 실제 수행 시간 )의 함수가   실제수행시간 - > 가상 실행시간(vruntime)의 증가량을
계산하는 함수이며 , 계산의 편의를 위해  공식2에서  priority의 역수를 곱해주어서 , 나누기 연산을 회피하는데,
이를 위해  prio_to_weight[]의 역수를 저장하는 배열 prio_to_wmult[]를 사용합니다.

실제 코드는 normalize를 위해서 redundant한 2*32의 값을 곱하는 계산 과정등이 추가 되는데,
이를 무시해도 지금까지 논의한 사항은 정확합니다.

그리고 check_preempt_tick()함수에서 sched_slice()함수를 호출하는데 , 이 함수가 실제 수행된 시간을 계산하는 함수이며,
공식1 을 가지고 계산한 후  ,  time slice가 초과되면, scheduling이 실행됩니다.



cfs의 스케쥴러는 현재 실행 큐에서  vruntime이 가장 작은 프로세스를 선택합니다.
이를 위해 red-black트리를 사용해 프로세스를 저장하고 선택합니다.
논의의 편의를 위해서 rb tree는 다른 자료를 통해 익숙하다고 가정하겠습니다.
지금은 직관적인 이해를 위해 단순화한 모델로 설명하겠습니다.

시나리오::  1 .처음에 프로세스 A가 실행큐에 삽입(rb tree에)되고 vruntime은 0 , nice값은 0 의 값을 갖고 있습니다.
  
 prio_to_weight[]의 실제값은 계산이 지저분해서
 prit_to_weight[]={300,200,100}으로 단순화해서 계산하겠습니다.

 A의 실제실행시간(real time slice)은 공식 1에 의해
   = 10ms* 300/300 = 10ms가 되어 전 주기를 혼자 다 독식합니다.

 계산의 편의를 위해 vruntime의 timeslice는 20으로 주어진다고 가정하겠습니다.

 2 .A의 vruntime이 10인 상황에서 새로운 프로세스 B가 fork등을 통해 실행큐에 삽입되며고 , nice값 1을 갖는 프로세스일 때
    B의 vruntime은 실행큐에서 가장 적은 min_vruntime을 갖게 되고  이는 현재 A 한개 뿐이므로
    10을 갖습니다.

   B   의 실제실행시간(real time slice)은 공식 1에 의해
   =   10ms* ( 200)/(300+200) = 4ms가 되고,
   A 는 = 10ms* ( 300)/(300+200) = 6ms로 변화됩니다.

  timer 인터럽트에서  , A의 vruntime은 증가하고(1증가라고 가정) , check_preempt_tick()가 호출되고 A의 real 실행시간이 6ms가 되는 시점에  스케쥴링이 발생합니다.

 이때 a의 vruntime: 11   b의 vruntime:10이 되어 b가 선택됩니다.

이처럼,  cfs상에서 실제 time slice는 현재 큐에 대기중인 프로세스의 수와 priority에 따라 가변적으로 결정됩니다.
그리고 vruntime은  큐상에 존재하는 process들 중 가장 작은 값을 , 새로 실행되는 프로세스에게 부여하는 구조를 갖고,
스케쥴러는  가장 작은 vruntime을 갖는 프로세스를 선택합니다.
왜냐하면 , 완전 공정한 스케쥴러이기 때문이며 , 이는 여러분이 여러 시나리오와 코드를 살펴보면 이해할 수 있습니다.




 
              





덧글

댓글 입력 영역