cfs scheduler 9 & 주요함수 분석 (2) find_busiest_group cfs 스케쥴러



   "
                                창문 열고 편히 앉아 
                                  주역을 읽노라니
                                가지 끝의 흰 것 하나
                                  하늘 뜻이 보이노라    "
                                                           
                                                          by 정도전



 이전 글에서 select_task_rq 함수에 대한 기본 기능을 살펴 보았습니다.
 passive 한 소극적 로드 분산 기능을 수행하는데, 함수가 불리는 path는
 sys_fork(),sys_exec()상의 sched_fork , sched_exec()에서 불리게 됩니다.
 부모 프로세스가 실행되던 cpu에서 실행할지 , 다른 cpu에서 실행될지를 결정하는 역할을 합니다.
 다른 하나의 path는  sleep 상태에서 깨어 날 때 , 기존의 cpu에서 실행할지를 결정하는 역할도 합니다.

 이외에 로드 밸런싱 관련 함수는 2가지 경우가 더 있는데, cpu가 idle 상태에 들어갈때 , 자신이 한가해 지니,
 다른 분주한 cpu에서 process를 옮겨오는 경우가 있고,
 마지막 경우는 주기적인 timer를 통해  rebalance_domains()를 통해 로드 밸런싱을 수행하는 경우 입니다.

 이전 커널 소스에서는 첫 번재 case를 passive load balancing , 후자들을 active load balacing이라고 칭했습니다.

 active load balacing함수들의 가장 중요한 함수는  find_busiest_group입니다.
 이전 글에서 sched_domain  ,sched_group을 설명했습니다.
 이중 sched_group은 physical level이면 , 물리적 cpu내에 있는 코어들, 그리고 각 코어에 속한 logical cpu(hyperthreading)
 상에 속한 cpu run queue들의 load의 총합이 누적되어 저장되어 있습니다.

 간단한 예를 들어 보죠!
 이 시스템은  intel dual core cpu이고 hyperthreading이 지원된다면 총 cpu 갯수는 2x2입니다.
 
                                                                         sched_group(physical)  
                                                                                                |
                                          (CORE D)                                        |        ( CORE E )
                           sched_group(core)   (1024+1024+512)                   sched_group(core)    ( 1024+1024+1024)
                                         |                                                                             |
                                         |                                                                             |
       sched_group (CPU A)     sched_group (CPU B)             sched_group (CPU C)        sched_group (CPU D)       
       ( 1024 + 1024)                                 (512  )                               (1024 + 1024)                     ( 1024)

 
 물리적 cpu가 1개 이므로 node는 1밖에 없고 , 각 코어별로 sched_group 이 있고,
 논리적 cpu의 경우 각각에 대해 sched_group이 생성되어 있습니다.
 
 cpu A의 경우 run queue에  nice가 0인 두개의 프로세스가 돌아가고 있고 load.weight = 2048이라는 누적값이 저장됩니다.
 상위의 코어는 cpu A,B를 포괄하니  sched_group 상의 로드 총 합은 1024+1024+512가 됩니다.

 감이 오시죠! 위의 트리를 타고 오르면서  각 sched_group의 load 총합을 계산해 가장 분주한 그룹을 찾고,
 그 그룹에서 한가한 cpu로 로드를 분산해 주는 방식입니다.

 커널 버전 2.6.3x 부터  로드의 통계자료를 관리하는 struct sg_lb_stats 가 등장하는데,
 이전 버전에서 계산된 값들을 구조적으로 정돈하는 역할을 할 뿐이지, 로드 분산을 계산하는 기본 함수와 논리는
 2.6.23 버전과 거의 동일합니다.그리고 3.x 버전도  기본 논리는 동일합니다.

 지금 설명하는 코드의 참조는 2.6.23을 기준으로 설명드리겠습니다. 

 다시 위의 그림에서  core D , E의 로드는 현재 상태의 로드를 단순 비교하는 상황을 나타낸 것 입니다.
 그런데 , 커널상에서는 여러 시나리오 상의 로드 밸런싱시 다른 로드를 사용합니다.
 예를 들어  CPU가 idle 상태에 진입할때 , fork, exec일때등 다른 통계값을 사용해 로드를 비교해
 가장 분주한 group을 선택하고, 그 group내에서 가장 바쁜 논리적 cpu를 찾습니다.

 이를 위해 각 cpu의 run queue 구조체에는 cpu_load[]라는 배열 멤버를 갖게 되는데 배열의 index가
 idle상황, fork, exec상황일때의 로드 총합을 저장하고 있습니다.

 단순히 현재 상태의 cpu 로드의 총합이 아닌, 과거 history 정보를 포함합니다.
 이 cpu_load[]는 timer interrupt 시 update_cpu_load(struct rq *this_rq)라는 함수에서 갱신되는데,
 그 기간에 새롭게 queue상에 진입한 process나 exit한 load 정보를 갱신합니다.

 static void update_cpu_load(struct rq *this_rq)
{
 unsigned long this_load = this_rq->load.weight;
 int i, scale;

 this_rq->nr_load_updates++;

 /* Update our load: */
 for (i = 0, scale = 1; i < CPU_LOAD_IDX_MAX; i++, scale += scale) {
  unsigned long old_load, new_load;

 

  old_load = this_rq->cpu_load[i];
  new_load = this_load;
  /*
   * Round up the averaging division if load is increasing. This
   * prevents us from getting stuck on 9 if the load is 10, for
   * example.
   */
  if (new_load > old_load)
   new_load += scale-1;
  this_rq->cpu_load[i] = (old_load*(scale-1) + new_load) >> i;
 }
}

복잡해 보이지만
cpu_load[0] =  new_load (현시점 로드)
로 단순히 현재값만 저장..

cpu_load[1] =    ( old_load(이전 로드) + new_load  )/2 
로 평균값
cpu_load[2] =    ( 3*old_load(이전 로드) + new_load  )/4
cpu_load[3] =    ( 7*old_load(이전 로드) + new_load  )/8
로 weighted average라는 수학적 통계값을 사용합니다.

이 함수가 다음 번 timer tick에서 호출되면 ,

cpu_load[2] =   (3*(  ( 3*old_load(이전 로드) + new_load  )/4 )  + new_load_1 )/4
                   =    9/16*old_load + 3/16*new_load + 1/4*new_load_1 
로 이전 history 값들이 계속 누적되어 저장됩니다.

나중에 커널 버전 3.8에 이르면 , exponential average 값들을 사용하는데, 위의 기본 원리만 이해하면 동일한 논리로
접근할 수 있습니다.

여기서 중요한 점은 로드 밸런싱시 ,정책을 결정하는 핵심 metric이 단순한 현재의 cpu의 로드가 아닌,
여러 상황에 따른 과거 history 정보를 활용한다는 점입니다.





 


덧글

댓글 입력 영역