매니코어 스케쥴링 연구

매니코어OS
이동: 둘러보기, 검색

연구 배경

현재 리눅스 운영체제의 기본 스케쥴러인 CFS스케쥴러는 task들 간의 fairness를 유지하는 것을 원칙으로 한다. 따라서 fairness를 유지하기 위한 많은 특징들이 존재한다. 그러나 매니코어 프로세서 환경에서는 충분한 코어수로 인해 fairness를 유지하기 위한 작업들이 불필요할 수 있다. 또한, high-performance computing 같은 fairness의 유지보다 성능을 더 중요시하는 환경에서는 CFS 스케쥴러의 무거운 동작이 성능 저하의 원인이 될 수 있다.

최근 발표된 논문(Jean-Pierre Lozi et al., “The Linux Scheduler: a Decade of Wasted Cores”, eurosys 16)에 의하면 리눅스 CFS 스케쥴러에서 동작 가능한 쓰레드들이 runqueue에 막혀 idle 한 cpu가 발생하는 문제점이 발견되었다. 이러한 문제로 인해 실제 성능보다 14%의 성능저하가 있음이 발견되었다. 다음 그림은 위 논문에서 인용한 것으로, 리눅스 커널 컴파일 과정에서 idle한 cpu가 발생하고 있음을 보여준다.

RTENOTITLE

연구 목표

본 연구의 목표는 리눅스 운영체제의 CPU 스케쥴링 알고리즘을 개선하여 매니코어 프로세서 환경에 적합한 스케쥴러를 개발하는 것이다.

문제점

다음 표는 리눅스 운영체제의 기본 스케쥴러인 CFS 스케쥴러의 문제점을 확인하고자 Xeon Phi에서 hackbench를 수행하였을 때, 주요 스케쥴링 함수들의 수행 횟수와 평균 수행 시간을 조사한 것이다.

RTENOTITLE

굵게 표시된 함수는 스케쥴링에 필수적으로 수행되는 함수를 의미한다. 조사한 결과에 의하면 가장 많이 호출된 함수는 update_curr 함수였으며, 평균 수행 시간이 가장 긴 함수는 load_balancing 함수였다. 이 두 함수는 task들 간의 fairness를 유지하기 위해 수행되는 함수로, 위 두 함수가 스케쥴러의 성능에 많은 비중을 차지하고 있음을 쉽게 짐작할 수 있다. 따라서 본 연구에서는 위와 같은 비용을 최소화 하는 경량화된 스케쥴러를 고안하는 방향으로 연구를 진행하였다.


Feather-Like(FL) Scheduler

본 연구에서는 스케쥴링 오버헤드를 최소화 하는 것을 목표로 하는 스케쥴러인 Feather-Like Scheduler(FLSCHED)를 구현하였다. FLSCHED는 기존의 리눅스 Round Robin 스케쥴러 기반의 경량 스케쥴러로, 다음의 특징을 갖는다.

  1. Lockless 구현
    다음 표는 리눅스 커널 2.6.38 버전(Xeon Phi 공식버전)에서 lock 관련 함수가 등장한 횟수를 보여준다. 표의 CORE는 스케쥴러의 필수적인 부분에 들어가는 lock이며, CFS는 CFS 스케쥴러에 별도로 사용되는 lock, FIFO/RR은 FIFO/RR 스케쥴러에 별도로 사용되는 lock을 의미한다. 스케쥴러에서 사용되는 lock은 global한 lock은 제거되었기 때문에 per-runqueue lock을 의미한다. 리눅스 커널 4.5.4 버전에서는 각각 74, 42, 21회로 증가하였다.
    Cfs lock.png 
    FLSCHED에서는 FIFO/RR에서 사용하고있는 15개의 lock을 모두 제거하였다. CORE에서 사용하는 lock은 여전히 남아있지만, FIFO/RR이 자체적으로 갖는 lock은 존재하지 않는다. 
  2. Context switch 최소화
    Time-slice에 의한 context switch를 제외하면 주로 선점이 발생하는 경우에 context switch가 동작하게 된다. 선점은 주로 priority에 의해 발생하는데, FLSCHED에서는 priority를 제거하여 선점을 줄였다. 다음 그래프는 AIM7 벤치마크에서 각 스케쥴러 별 수행시간과 context switch 수를 보여준다.
    RTENOTITLE
    FLSCHED가 CFS 스케쥴러에 비해 최대 28%의 수행시간 감소를 보였고, context switch 횟수는 다른 스케쥴러와 비교하였을 때 가장 낮은 수치를 보였다.
  3. 각종 특징들 제거
    FLSCHED에서는 리눅스 CFS 스케쥴러에서 많은 수행시간을 차지하였던 특징들인 load balancing이나 scheduling information(update_curr 함수)등을 제거하였다. load balancing은 주기적으로 수행되는 load balancing과 fork 같은 상황에 의해 조건적으로 수행되는 load balancing이 존재한다. FLSCHED는 주기적으로 수행되는 load balancing을 제거하여 그에 사용되는 lock도 5개 제거하였다. 그 외에도 Xeon Phi 환경에서는 불필요하다고 생각되는 여러 특징들이 제거되었다. 다음 표는 위에 hackbench로 조사한 함수 호출 횟수 및 평균 수행시간을 CFS와 FLSCHED로 비교한것이다.
    Cfs fl analysis.png
    update_curr 함수가 제거되었고 load_balancing의 감소, 선점 관련 함수의 감소 등으로 인해 필수 스케쥴링 함수들도 같이 줄어든것을 확인할 수 있다. 이 결과에서 각 스케쥴러의 총 수행시간은 CFS스케쥴러의 경우 30.81초, FLSCHED의 경우 14.429초 였다.  

NAS Parallel Benchmark(NPB)

본 연구에서는 High-performance computing에서의 FLSCHED의 성능평가를 위해 병렬 벤치마크 프로그램인 NPB를 사용하여 성능평가를 수행하였다. 다음 표와 그래프는 벤치마킹에 사용된 어플리케이션 종류와 성능평가 결과를 보여준다.

Npb contents.png RTENOTITLE

is의 경우를 제외하면 모든 경우에서 CFS스케쥴러보다 좋은 성능을 보였다. 특히 cg, mg, sp, ua의 경우는 최대 1.73배의 뛰어난 성능을 보였다. 분석결과 spinlock에 의한 병목현상이 성능에 상당부분 영향을 미쳤다. 다음은 spinlock에 의한 수행시간 비율을 나타낸 표이다.

Npb spinlock.png

ep의 경우를 제외하고는 모든 어플리케이션에서 lock이 차지하는 수행시간이 제일 적었다. 또한 lock에의한 수행시간의 차이가 많이 발생한 어플리케이션에서 실제 성능이 많이 좋아진것을 확인할 수 있었다.

향후 계획

현재 구현된 FLSCHED는 Xeon Phi에 최적화되어 있다. 향후 계획에서는 리눅스 커널 4.5.4버전에서의 스케쥴러를 목표로 하고 있다. 또한 FLSCHED는 NUMA 아키텍처를 고려하지 않았는데, 이러한 점도 같이 고려하여 구현할 예정이다. 이어서 스케쥴러의 CORE 부분의 lock을 줄이는 연구도 함께 진행중이다.

결과물

  • 리눅스 커널 패치 및 Eurosys에 논문 제출(추후 업로드)