멀티코어 시스템에서공정성 보장을 위한 가상런타임 기반 로드 밸런싱 알고리즘 = Virtual Runtime based Load Balancing Algorithm for Guaranteeing Fairness on Multicore Systems

국문 초록 (Abstract)

리눅스의 기본 스케줄러인 CFS는 클라우드 서버와 같은 대규모 시스템에서 널리 사용되고 있지만, 이는 시스템의 규모가 극도로 커짐에 따라 시스템이 요구하는 수준의 공정성을 보장하지 못한다. 이 논문은 CFS에 대한 심도 깊은 분석을 통해 공정성 보장의 실패의 원인을 규명하고, 이를 해결하기 위한 virtual runtime 기반의 로드 밸런싱 알고리즘을 제안한다. 이는 태스크들의 virtual runtime 차이를 바운드시키기 위해 주기적으로 태스크 이주를 수행한다. 이를 위해 알고리즘은 인접한 두 CPU의 load 차이가 최대 가중치 차이 이하가 되도록 바운드 하고, virtual runtime이 큰 태스크들을 load가 큰 CPU에서 수행되게 보장한다. 우리는 제안된 알고리즘을 리눅스 커널 2.6.38.8 상에 구현하고 일련의 실험을 수행하였다. 그 결과 기존 CFS의 경우 virtual runtime 차이는 선형적으로 증가하는데 반해 제안된 기법은 50.53 단위 시간으로 virtual runtime 차이를 바운드시킬 수 있으며 고작 0.14%의 런타임 오버헤드를 야기시킴을 보였다.

다국어 초록 (Multilingual Abstract)

While the primary task scheduler of Linux, CFS, is widely adopted for the large-scale cloud system,it cannot provide a desired level of fairness when a system scales up to an extreme degree. This paper formally analyzes the behavior of CFS to precisely characterize the reason why it fails to achieve the fairness in multicore systems. Based on the analysis, we present a virtual runtime-based load balancing algorithm which directly bounds the maximum virtual runtime difference among tasks by periodically migrating tasks. In doing so, it bounds the load difference between two adjacent cores by the largest weight in the task set and makes the core with larger virtual runtimes receive a larger load and thus runs more slowly. We have implemented the algorithm into Linux kernel 2.6.38.8. Experimental results show that the maximal virtual runtime difference is 50.53time units while incurring only 0.14% of run-time overhead comparing to CFS.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. CFS의 분석
• 4. 멀티코어 환경에서 CFS의 문제점
• 5. Virtual Runtime 기반 로드 밸런싱
• 6. 실험 및 검증 결과
• 7. 결론
• 참고문헌

참고문헌 (Reference)

1 "http://www.mattheaton.com/?p=222."

2 "http://www.hpl.hp.com/research/linux/kernel/ o1-starve.php"

3 "http://people.redhat.com/mingo/cfs-scheduler/."

4 "http://people.redhat.com/mingo/O(1)-scheduler /README"

5 "http://ck.kolivas.org/kernbench/"

6 Molnar, "The Completely Fair Scheduler"

7 B. Caprita, "Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling" 72-81, 2006

8 B. Caprita, "Group ratio round-robin: O (1) proportional share scheduling for uniprocessor and multiprocessor systems" 337-352, 2005

9 A. Srinivasan, "Fair scheduling of dynamic task systems on multiprocessors" 77 (77): 67-80, 2005

10 T. Li, "Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robin" 44 (44): 65-74, 2009

11 L. A. Torrey, "A comparison of interactivity in the Linux 2.6 scheduler and an MLFQ scheduler" 37 (37): 347-364, 2007