O(1) 스케줄러의 문제점과 CFS 스케줄러

출처: http://blog.naver.com/redcultuer?Redirect=Log&logNo=130109802510

※ O(1) 스케줄러의 문제점

1. nice값 0(timeslice 100ms)을 가지는 두개의 태스크가 실행 된다고 가정하자.
   컨텍스트 스위칭은 100ms 간격으로 발생 할 것이다.
   nice값 20(timeslice 5ms)을 가지는 두개의 태스크가 실행 된다고 가정하자.
   컨텍스트 스위칭은 5ms 간격으로 발생 할 것이다.
   프로세서가 1000ms 동안 실행 된다고 가정 할 경우 과연 올바른 스케줄링 동작인가?
   이와 같은 문제는 nice 값이 절대적인 timeslice를 결정 하는데서 발생한다.

2. nice값 0과 1을 가지는 두개의 태스크가 실행 된다고 가정하자.
   timeslice는 100ms, 95ms가 할당 될 것이다. 
   nice값 18과 19를 가지는 두개의 태스크가 실행 된다고 가정하자.
   timeslice는 10ms, 5ms가 할당 될 것이다.
   똑같이 nice값이 1차이가 나지만 두번째 경우에는 timeslice의 차이가 두배가 되었다.
   이 문제 또한 nice값이 절대적인 timeslice를 결정 하는데서 발생한다.
 
3. timeslice가 timer tick에 의존하여 변화한다.

4. Interactive task를 우선시 하는 문제가 있다.
   Interactive task가 휴면 상태에서 깨어날 때 즉시 실행되게 하므로 (심지어 timeslice를 
   모두 소진 했을지라도 active 큐로 들어오는 보너스를 받는다.) expired 큐에 존재하는 
   태스크의 실행이 지연된다.

※ CFS 스케줄러

 Schedule() 함수는 Linux에서 스케줄링을 담당하는 함수이다. 이 함수가 호출되는 시점은 시스템이 현

재 프로세스를 계속 수행할 수 없는 상황을 만났을 때가 되며, 이러한 예로서는 더 높은 우선순위를 가

지는 프로세스가 수행가능한 상태가 되었거나, 현재의 프로세스가 I/O를 위해서 wait하는 경우, 그리고, 

현재 프로세스의 time slice를 다 사용한 경우로 나누어 볼 수 있다. 따라서, 이 함수가 호출될 경우에

는 어떤 식으로든 다음에 실행할 프로세스를 결정해 주어야 하며, 해당 프로세스의 context를 복구 하

고, 현재 수행중이던 프로세스의 context를 save하는 일이 필요하다. 호출의 결과로 나중에 다시 현재 

프로세스가 수행될 기회를 얻어게되면, schedule() 함수를 호출한 다음에 오는 instruction을 수행할  것

이다. 

1. CFS는 nice값을 태스크가 할당 받을 proportion of processor에 대한 weight로 
   사용한다. 각각의 태스크는 실행 가능한 태스크들의 weight의 총 합을 기준으로 
   자신의 weight만큼만 비례적으로 timeslice를 할당 받는 것이다. 예를 들어 프로세서가
   100ms 동안 실행 된다고 가정하고 같은 nice값을 가지는 태스크 두개만 존재 한다고
   생각해보자. 이 두 태스크가 nice값 -19를 가지든 20을 가지든 상관없이 timeslice는 
   50ms씩을 얻게 된다. 만일 4개의 태스크만 존재하고 모두 같은 nice 값을 가진다면
   4개의 태스크는 모두 25ms의 timeslice를 얻게 된다. nice값을 절대적인 timeslice와
   분리 함으로써 O(1) 스케줄러의 문제점 1번이 해결 되었다.

2. 이번에도 프로세서가 100ms 동안 실행 된다고 가정해보자. nice값 0과 5를 가지는 두개의 
   태스크만 실행 된다고 할 경우 CFS는 두개의 태스크에게 각각 1024와 335의 weight를 
   주게 된다. 그러므로 각각의 태스크가 가지는 weight의 비율은 1024/(1024+335), 
   335/(1024+335) 대략 3:1이 된다. 그러므로 nice값 0인 태스크는 75ms의 timeslice를 
   nice값 5인 태스크는 25ms의 timeslice를 얻게 된다. nice값 5와 10를 가지는 두개의 
   태스크만 실행 된다고 할 경우에도 weight의 비율은 3:1이 되므로 두개의 태스크는
   각각 75ms, 25ms의 timeslice를 얻게 된다. 마찬가지로 nice값을 절대적인 timeslice와
   분리 함으로써 O(1) 스케줄러의 문제점 2번이 해결 되었다.

3. Virtual Runtime은 normalized 또는 weighted 된 태스크의 실제 실행된 시간이다. 
   Virtual Runtime의 units은 나노초 단위이다. 그러므로 CFS는 HZ상수의 분해능을 가지는
   timer tick에 의존하지 않는다. => 이 부분은 아직 정확히 이해하지 못했습니다. ㅋ   
   
   CFS에서 Virtual Runtime을 어떻게 사용하는지 알아보자.
   같은 nice값으로 인해 100ms의 동일한 timeslice를 가지는 두개의 태스크만 실행 되고
   스케줄러는 20ms 주기로 컨텍스트 스위칭을 수행한다고 가정하자.
   CFS(완전히 공평한) 스케줄링 이론에 따르면 60ms의 시간이 지난 후에 두 태스크는 
   30ms씩 실행이 되어야 한다. 하지만 스케줄러는 태스크의 20ms 주기로 컨텍스트 스위칭을 
   수행 하므로 두 태스크는 40ms, 20ms씩 실행이 된다. 그러나 CFS는 자신의 역할을 충실히 
   달성하기 위해 20ms를 실행한 태스크를 선택하여 40ms를 실행한 태스크를 따라잡게 한다. 
   이러한 방법으로 스케줄링을 한다면 두 태스크의 실행 시간 차이는 20ms를 넘어서지 
   않을 것이다.

   이번에는 서로 다른 nice값 3:1의 weight 비율을 가지는 두개의 태스크만 실행 되고
   스케줄러는 20ms 주기로 컨텍스트 스위칭을 수행한다고 가정하자. 
   이상적인 CFS 이론에 따르면 60ms의 시간이 지난 후에 두 태스크는 45ms, 15ms씩 실행이
   되어야 한다. 하지만 위와 마찬가지로 두 태스크는 40ms, 20ms씩 실행이 된다.
   이 상황에서 다음번에는 어떤 태스크가 스케줄링 되어야 할까?
   스케줄러는 이러한 상황을 판단하기 위해서 각 태스크의 실행 시간에 scale factor를 
   곱하여 virtual runtime을 생성한다. 예를 들어 40ms 실행 된 태스크는 scale factor가 
   1이고, 20ms 실행 된 태스크는 scale factor가 3이다. 두 태스크의 virtual runtime은
   40ms, 60ms가 된다. 이제 상황이 명확해졌다. virtual runtime 40ms를 실행한 태스크가
   더 뒤쳐져있다. 그러므로 스케줄러는 이 태스크를 실행해서 뒤쳐진 시간을 따라잡을 
   것이다. 즉, virtual runtime이라는 개념이 도입되면서 낮은 우선순위의 태스크는 
   높은 우선순위의 태스크가 timeslice를 모두 소비 할때까지 기다려야 하는 불공평한 
   문제가 해결 된것이다.      

4. 3번과 같은 상황만을 고려하여 생각 한다면 새로 생성되는 태스크나 잠들었다 깨어난
   태스크는 이미 존재하는 태스크들의 실행 시간을 따라잡을 때까지 실행하게 될 것이다.
   이는 바람직하지 못한 상황이다. 그러므로 새로 생성되는 태스크는 기존에 실행 되고 
   있던 태스크들 중에서 가장 작은 virtual runtime 실행한 태스크와 동일한 
   virtual runtime을 가지게 되고 약간 조절되게 된다. 

   
   CFS의 run queue는 virtual runtime을 기준으로 정렬한 red-black tree로 유지된다.
   CFS가 컨텍스트 스위칭을 수행 할 때 선택하는 태스크는 RB tree에서 가장 작은 
   virtual runtime을 가진 태스크이다. 이 태스크는 RB tree의 가장 왼쪽에 위치하게 된다.

   CFS의 timeslice는 다음과 같다.
   
   timeslice = (se->load.weight / cfs_rq->load.weight) * period
    
   se는 struct sched_entity 구조체로 struct sched_class *sched_class와 함께
   struct task_struct에 새롭게 추가된 녀석이다. se를 태스크라고 생각해도 무방하다.
   period는 스케줄러가 모든 태스크들을 수행하는데 걸리는 시간으로 default 20ms이다.
   특정 태스크의 timeslice는 모든 태스크들의 weight의 총 합에서 자신의 weight가
   차지하는 비율로 계산된다.

   실행 중에 있는 특정 태스크의 virtual runtime은 다음과 같다.

   vruntime += (NICE_0_LOAD / se->load.weight) * delta_exec

   NICE_0_LOAD는 상수값 1024이다.      
   delta_exec은 실제로 CPU를 할당받아 실행된 시간이다.
   태스크의 weight값이 클수록 vruntime이 작아지는 것을 알 수 있다.
   즉, CPU 시간을 더 할당 받을 수 있는 기회가 커지는 것이다.

 

[출처] CFS 스케줄러|작성자 MoonLight