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

 이제 cfs의 group 스케쥴러를 살펴보겠습니다.
 이전 글을 이해했다면,  일사천리입니다

 아이디어는 다음과 같습니다.
 cpu의 실행 시간을 어떤 특정그룹에 한정해서 할당하고 싶은겁니다.
 대학의 A학과와 B학과에게 다른 cpu실행 시간을 할당해서 차별화를 두는 아이디어 이며,
 가상화 서버에서  요금에 따른 서버 사용량 제한등이 이에 해당합니다.

 예를 들어 그룹a에는  cpu의 power를 10% 주고 , 그룹b에는 90%를 할당합니다.

 이를 어떻게 구현 할까요?

 표준 cfs 스케쥴러에서   real time slice를   priority에 따라 다르게 분배 했듯이
 그룹 a의 실제실행시간 : 그룹b의 실행시간 = 1:9 로 제한 하게 되고  이를 위해
 shares라는 개념을 도입합니다.

 그러면 새로운 공식인
   a그룹의  실제 그룹 실행 시간 = 실행주기(period) * (a의 shares) / ( a의 shares + b의 shares)라는     --공식 3
 공식을 사용합니다.

이의 구현을 위해 task_group과 sched_entity라는 두 구조체가 도입됩니다.

 쉬운 예을 들면,
   현재 실행 큐에  그룹 A (프로세스 a (priotity 100) , b(priority 200) ) , 그룹 B(프로세스 c) 의  프로세스가 대기 중입니다.
 그룹을 하나의 프로세스처럼 봅니다.
 
  이때 그룹 A의 priority(shares)는 10이고 , b의 priority(shares)는 90이 되어
 A 그룹의 실제 실행시간은 =  10ms* 10 / (10 +90 ) 이 되어 1m가 할당되고
 B 그룹은 9ms가 됩니다.
 
 스케쥴러는 A그룹을 선택하고 , 이 때 A가 일반 프로세스가 아닌 그룹인지를 판별해,
  그룹이면 , 그룹내에서 또다시 실행할 프로세스를 선택합니다.
 이때 a가 선택되었다면 ,
 a의 실제 실행 시간은
     그룹 A의 실제 실행시간 * a의 priority / (a's priority + b's priority)가 되어
이전 공식 1과 비교하면  실행주기가 각 그룹별로 다르게 shares의 비율에 따라 주어지는 방식입니다.

 이때 스케쥴러는 A그룹내의 a 프로세스가 실행이 끝나면 , A그룹의 time slice가 초과되었는지를 판별하고
 아니면, b프로세스 등을 선택합니다.
 그룹 A의 slice가 다 소진 되면 그룹 B가 선택되고 , 동일한 논리로 B내의 프로세스중 가장 적은 vruntime을 갖는
프로세스를 선택하는 동작방식을 취합니다. 즉 그룹도 하나의 프로세스로 보며 , vruntime을 갖는 구조를 갖습니다.

이를 위해 각 그룹별로   cfs 의 실행큐를 따로 가지고 있고,  스케쥴링의 기본 단위를 전통적인 task_struct 대신
sched_entity를 사용해 구현하며,  그룹을 생성하는 인터페이스는 cgroup의 cpu subsystem을 통해 task_group
생성 , 삭제 등을 수행합니다.

여기서는 직관적인 아이디어를 파악하는게 중요하고,   이전 글을 통해 실제 코드를 살펴보는 과정을 거치면
그룹 스케쥴링도 쉽게 이해할 수 있습니다.

지금 커널 버전은 4.x 버전인데,  스케쥴링 관련 코드는 kernel/sched 안에 존재하며
가히 코드의 정글이라 할 만 합니다.

여기서 다 논의 할 수 없지만,   multiprocessor 구조에서 load balancing , hot plug cpu,  no_hz scheduling,
bandwidth scheduling, statistics 관련 자료처리 , 등 분석하기가 아주 까다롭습니다.

제 개인적인 경험으로는 , 리눅스 커널 상에서 가장 까다로운 부분은 scheduling , timer wheel , acpi가
아닌가 생각합니다.

추천사항으로는 2007년에 ingor monlar가 최초로 cfs를 구현한, 2.6.21(?) 이나 2.6.23(^.^)을 먼저 살펴보는게
쉽게 다가가는 방법이 될 것입니다.


 

덧글

  • nijiho 2015/08/31 17:42 # 삭제 답글

    안녕하세요 블로그 잘 보고 있습니다 ^^
    혹시 리눅스 커널에 스케줄러 부분 수정 후 컴파일 하려고 하는데
    매번 필요없는 커널의 다른 부분까지 전부 컴파일 같이해야 되나요?
    아니면 따로 스케줄러 부분만 하는 방법이 있을까요
  • 솔개가하늘을가르네 2015/09/02 00:10 # 답글

    수정한 부분을 그냥 make -j8 처럼 컴파일 하시면 됩니다.
    make 라는 툴이 dependency를 계산해 , 연관된 부분만 컴파일해서 링크시켜요..
  • 2015/09/09 18:03 # 비공개

    비공개 답글입니다.
  • 솔개가하늘을가르네 2015/09/11 02:46 # 답글

    네 ^.^ 저는 big.little core는 잘 모르는데, 어떤 부분인가요? 그 코어에 cfs를 포팅하려는지요?
  • 2015/09/14 20:05 # 비공개

    비공개 답글입니다.
  • 솔개가하늘을가르네 2015/09/16 23:12 # 답글

    네 처음 커널을 접하시면 좀 많이 버거울 텐데요. 그리고 커널중, 스케쥴러 부분이 좀 복잡해서 좀 쉬운 부분부터 분석하시는게
    나을겁니다. 우선 linux2.6.23의 스케쥴러 부분을 보시구요, 제가 big.little.core를 보진 않았지만 커널 분석을 어렵게 하는 부분이,
    rcu , lock dep , hrtimer, memory block(smb,mb.), debugging 코드(trace)가 뒤섞여 복잡하게 합니다. 이 부분은 linux kernel 소스의 documentation 폴더나,
    linux kernel development 책, linux kernel architecture 책, http://lwn.net/Kernel/ 에서 관련 부분 검색으로 스터디 하시면 됩니다.

    스케줄러 부분중 , 먼저 cfs의 기본개념 ,로드 밸런싱 ,그룹스게줄링이 핵심이구요 , 제 post에 올린글대로 차근차근 시간을 갖고 분석해 보시는 방안을
    추천드려요.. 그 후 big.little.core에서 scheduler class의 멤버 함수가 어떻게 정의 되고 <enqueue, ..> , hrtimer의 interrupt routine에서 ( 사실은 로컬 cpu의 high resoultion timer를 동적 시간 간격으로 프로그래밍해서 , 구현) 스케쥴러의 time slice 계산 ,통계 계산 과정을 살펴 보시구요, 그 다음에는 hmp 스케줄러가
    어떤 정책에 따라 process를 선택하시는지 ,linaro의 관련 문서를 살펴 보시고 , 커널 메일링 루틴을 찾아서 , hmp의 rfc를 살펴보셔야 할 겁니다.
    최근의 커널은 좀 많이 버거워 져서, 특히 스케쥴러나, memory managment 부분을 분석하려면, 제 경험으론, 전체적인 분석과정이 수반되야 하더라구요..
  • 2015/09/21 17:11 # 비공개

    비공개 답글입니다.
댓글 입력 영역