역자 : 송형주(hyungjoo.song@gmail.com)

새로운 강력한 성능의 0(1) 스케쥴러의 목표들, 설계 그리고 구현

이 문서는 2002년 1월 4일에 Ingo molnar이 LKML에 보낸 이메일을 편집한 것이다. 본 문서는 Ingo가 새롭게 제안한 강력한 성능의 O(1) 스케쥴러의 목표, 설계, 그리고 구현에 대해서 설명한다.

목표

새로운 스케쥴러의 주요 목표는 기존의 리눅스 스케쥴러의 장점을 그대로 유지하는 것이다.

• 과도한 시스템 부하에도 불구한 뛰어난 응답 성능 : 만약 사용자가 키보드나 마우스를 클릭했다면, 시스템은 상당한 양의 background 작업을 처리하고 있더라도, 즉시 반응하고, 사용자의 작업을 부드럽게 처리해야 한다.
  
  
• 1-2개의 실행 가능한 프로세스로들을 통한 뛰어난 스케쥴링/wakeup 성능
  
  
• 공평성 : 어떤 프로세스도 부당한 시간 동안 타임 슬라이스 없이 계속 실행될 수 없다. 어느 프로세스도 부당하게 cpu 시간을 추가로 사용할 수 없다.
  
  
• 우선순위 : 더 중요한 태스크들은 낮은 우선 순위를 실행되며, 더 중요한 태스크들은 더 높은 우선순위를가지고 실행될 수 있다.
  
  
• SMP 효율성 : 수행할 작업이 있다면, 어느 CPU도 idle 상태에 대기하지 않는다.
  
  
• SMP 친밀성 : 특정 CPU에서 동작중인 프로세스들은 해당 CPU에 더 친밀성을 갖는다. 프로세스들은 CPU 사이를 자주 옮겨다니지 않아야 한다.
  
  
• 추가적인 특징 : RT 스케쥴링, CPU 바인딩
  
  

목표에 다음과 같은 새로운 특징이 추가됐다.

• 완전한 O(1) 스케쥴링. 매번 L1 캐시의 내용을 날려버리는 재계산 루프에 지치지 않았는가? 실행 가능한 프로세스가 많다면, goodness 루프의 수행 시간이 꽤 길어진다고 생각하는가? 이 새로운 스게쥴러는 wakeup(), schedule(), 타이머 인터럽트 모두가 O(1) 알고리즘으로 동작한다. 재계산 루프 및 goodness 루프 역시 수행하지 않는다.
  
  
• 완전한' SMP 확장성.''' 새 스케쥴러는 '부하가 큰' runqueue_lock'를 사용하지 않고, 모든 cpu별로 자체 실행큐와 lock을 사용한다. 때문에 두 개의 서로 다른 cpu에서 동작하는 각각의 태스크들을 병렬적으로 상호간에 어떤 locking 없이도 깨우거나, 스케쥴링 또는 컨텍스트 스위칭 할 수 있다.
  
  
• 더 뛰어난 SMP 친밀성. 예전 스케쥴러는 우선순위가 높거나 상호작용 태스크가 어떤 CPU에 할당될지를 모르는 약점이 있었다. 이것은 많은 사람들에게 발견됐고, 보고 됐다.(역자주, 보통 특정 CPU에서 한 번 실행된 프로세스는 다음에도 같은 CPU에서 실행되는 것이 캐시 등의 활용에서도 좋은 성능을 가져온다. 물론 부하가 큰 프로세스가 특정 CPU에서만 동작한다거나 로드 밸런싱 차원에서 다른 CPU로 해당 태스크를 이동할 수도 있다.) 이것의 원인은 우선 타임슬라이스를 재계산하는 루프가 현재 모든 CPU에서 실행중인 타임 슬라이스를 소진시켜야 하기 때문이다. 가령 8 way 시스템에서 이러한 특성은 추가 CPU들이 프로세스를 실행시키는데 있어 기아 현상을 일으킨다. 일단 타임 슬라이스가 남아 있는 마지막 태스크가 타임 슬라이스를 다 소진하면, 재계산 루프가 동작하고 CPU들은 어느 정도의 타이머 틱 동안 대기한 후에야 다시 태스크를 실행할 수 있다. CPU가 많아질 수록, 이것은 더 안좋은 효과를 초래한다.
  
  게다가 이러한 현상은 바운싱 효과를 일으킨다. 전역 실행큐에서 타이슬라이스의 소진이 있을 때 마다, 대기중인 프로세서들은 자신에게 친밀하지 않은 태스크를 시작한다. (왜냐하면 친밀한 태스크들은 이미 타임 슬라이스가 끝났기 때문이다.)
  
  새로운 스케쥴러는 이러한 문제를 어떤 전역적인 동기화나 쟤계산 없이 CPU별로 타임 슬라이스 관리를 분배함으로써 해결했다.
  
  
• 배치 스케쥴링. 컴퓨팅 중심의 작업이 주된 테스크들은 타임 슬라이스가 길고, 계속 순환되며 스케쥴링 하는 배치 스케쥴링 방식에서 이득을 얻는다. 새로운 스케쥴러는 이러한 프로세서 중심의 태스크에게 가장 낮은 우선순위로 배치 스케쥴링을 한다. 그래서 nice 값이 19인 작업들은 자동적으로 배치 스케쥴링된다. 새로운 스케쥴러에서 nice값이 19이 작업들은 상호 반응성 측면에서는 볼때, SCHED_IDLE 스케쥴링 정책으로 동작한다고 보면된다.
  
  
• 심각한 과부하 상태에서 작업이 끊기거나 과도한 스케쥴링 오버헤드 없이, 좀더 유연하게 처리한다.
  
  
• O(nr_running) 성능의 goodness loop와 recalculation loop에 민감한 RT 태스크들에 대한 O(1) RT 스케쥴링.
  
  
• 부모보다 fork()로 생성된 자식 프로세스를 먼저 수행. Andrea가 몇 달전에 이것에 대한 장점을 지적해줬지만, 이것을 적용한 패치는 기존 스케쥴러 및 새 스케쥴러에서 수행되지 않을 것이다. 왜냐하면, idle 프로세스들은 보통 foking 하는 CPU가 새로운 프로세스를 실행하기 전에, 새로운 프로세스를 가로채기 때문이다.
  
  

설계

새로운 스케쥴러는 다음과 같은 핵심 메커니즘을 포함한다.

• CPU마다 우선 순위 배열 2개 사용 : 'active' 배열과 'expired' 배열. 'active' 배열은 타임 슬라이스가 남은 CPU에서 처리가능한 모든 태스크를 포함한다. 'expired' 배열은 타임 슬라이스를 모두 소진한 태스크들을 포함한다. 이 두 배열은 모두 우선순위를 기준으로 정렬된다. 'active' 배열과 'expired' 배열을 직접 접근하는 것이 아니라, 각 CPU의 실행큐에 포함된 두 포인터를 이용해서 접근한다. active 배열에 포함된 active task들이 모두 소진되면, 우리는 'active' 배열과 'expired' 배열의 두 포인터를 스위칭해서, 이제부터 기존의 'expired' 배열을 'active' 배열로 동작되게 한다. 그리고 기존의 비어있는 'active' 배열은 'expired' 배열로 동작하며, 타임 슬라이스를 소진한 태스크들을 저장하는 역할을 하게된다.
  
  
• 우선순위 배열을 인덱싱하는 64-bit의 비트맵 캐시가 있다. 최고 우선 순위를 가진 태스크를 찾는 작업은 대개 두번의 x86 BSFL 비트 검색 명령어를 사용한다.
  이런 '분할 배열' 해결책은 임의 개의 acitve 태스크와 expired 태스크들을 가질 수 있겠 끔 해주며, 또한 타임 슬라이스의 재계산은 타이 슬라이스가 만료된 즉시 계산 가능해진다. 두 배열은 항상 실행큐의 포인터로 접근할 수 있기 때문에, 두 우선 순위 배열을 스위칭 하는 것은 매우 빠르게 처리될 수 있다.
  이것은 라운드 로빈 스케쥴링과 타임 슬라이스를 분배하는 배열-스위칭 방법을 결합한 우선순위 리스트 검색 방법이다.
  
  
• 태스크 단위 부하 측정기가 있다. 시스템 과부하 동안에도 뛰어난 인터액티브 성능을 보이는 것은 힘든 일이다. 다양한 스케쥴러을 운영해 보면서 나는 인터액티브한 태스크를 중요시 여기는 것 대신에, CPU 시간을 기본 값보다 더 많이 사용하기를 원하는 태스크에 벌점을 주므로써 가장 뛰어난 인터액티브 성능을 얻을 수 있다는 것을 알아냈다.이 방법은 O(1) 스케쥴러 방식으로 굉장히 수월하게 동작한다.
  
  태스크가 시스템에 영향을 미치는 실제 부하 정도를 측정하기 위해, 복잡해 보이지만 매우 정확한 다음과 같은 방법 이용된다: 최근 4초 동안 태스크의 동작을 저장한하는 4개의 엔트리를 가진 '히스토리(history)' ringbuffer를 사용한다.링 버퍼는 큰 오버헤드 없이 동작한다. 각 엔트리들은 스케쥴러에게 태스크의 부하(지난 N 초 동안 CPU 시간을 더 많이 혹은 더 적게 사용했는지에 대한 정보)에 대한 history 정보를 매우 정확하게 알려준다. 보통은 N의 크기는 4이고 4초의 주기가 매우 많은 실험 결과에 의해 구해졌다. 이 값은 유연하며, 변경 가능하다.
  
  CPU가 처리 할 수 있는 것보다 더 많은 부하를 생성한 태스크들이 받은 벌점은 우선순위를 감소시킨다. 이러한 벌점은 태스크의 정적 우선 순위에 대해 상대적인 값으로서 그 최대값이 결정되기 때문에 최대값의 벌점을 받을 완전한 CPU 중심의 태스크들 조차, 각자 우선 순위를 얻고 CPU를 적절히 나눠 쓸 것이다.
  
  SMP 로드 밸런서는 추가적인 병렬 컴퓨팅과 캐시 계층성 기능을 통해 확장될 수 있다. : NUMA 스케쥴링, 멀티코어 CPU는 로드 밸런스를 수정해서 쉽게 지원할 수 있다. 바로 지금 그것은 내 SMP 시스템에서 수정되고 있다.
  
  나는 prev->mm == next->mm에 장점을 무시했다.- 내가 생각하기에는 이것은 그렇게 큰 장점을 보이지 않는다. 그것은 현재 실행중인 태스크와 한 단계 아래의 우선순위 가진 태스크들의 mm을 비교하기 위해 O(1) schedule() 함수를 수정함으로써 추가될 수 있다. 그러나 이 작업으로 인해 수많은 중요한 작업 동안 꽤 많은 사이클을 소모하게 된다. 그래서 나는 가능한한 이것을 피하기를 원했다.
  
  
• SMP idle 태스크의 startup 코드는 여전히 경쟁적이고 새 스케쥴러는 경쟁 상황을 유발한다. 그래서 나는 idle 태스크의 setup 코드를 약간 간소화 했다. 우리는 모든 프로세서가 완전히 시작되고, 모든 idle 스레드가 동작하기 전에는 schedule() 함수를 호출하지 않는다.
  
  
• 이 패치는 또한 sched.c의 많은 부분을 없앴다. 몇몇 코드를 커널의 적절한 다른 곳으로 옮기고, 특정 코드 수행 및 자료 생성 부분을 단순화했다. 그 결과, 새 스케쥴러의 코드 크기는 기존 스케쥴러 보다 더 작아졌다.
  
  
  

Ingo