Memory-aware Fair Share Scheduling for Refined Fairness in the Linux Kernel

학위논문 (박사) -- 서울대학교 대학원 : 융합과학기술대학원 융합과학부(지능형융합시스템전공), 2020. 8. 홍성수.최근에 등장한 컴퓨팅 시스템에서 데이터 집약적 응용이 빠르고 광범위하게 확산됨에 따라 quality-of-service(QoS)와 best-effort(BE) 응용들 간의 성능 간섭이 더욱 심화되고 있다. 리눅스 커널의 completely fair scheduler(CFS)는 멀티태스킹(multitasking) 수행 환경에서 성능 고립화를 지원하기 위해 광범위하게 사용되어 오고 있지만, 메모리 접근 경합과 불충분 한 캐시 제공 범위로 인해 메모리 관련 간섭 문제를 해결하지 못 하고 있다. 비록 많은 메모리 인지 성능 고립화 메커니즘들이 학계에서 제안되어 왔지만, 대다수의 메커니즘들이 하드웨어에 기반한 해결책, 유연하지 않은 자원 관리 또는 비효율적인 사용률 조절 기법에 의존하기 때문에 널리 배포된 리눅스와 같은 운영 체제에서 사용되기 어렵다. 본 학위논문은 리눅스가 탑재된 COTS(commercial off the shelf) SoC 플랫폼에서 수행되는 QoS 응용이 함께 수행되는 다른 응용들과의 메모리 관련 간섭으로부터 영향을 더 적게 받을 수 있는 메모리 인지 비례 공정 스케줄링 알고리즘을 제안한다. 제안된 알고리즘은 수행 중인 태스크의 CPU 사이클로부터 메모리에 관련된 실질적인 스톨을 분리한다. 그리고 그 태스크가 바람직한 양의 CPU 사용률을 제공받도록 그 태스크에게 CPU 시간을 보상해준다. 제안된 접근 방식은 메모리 하드웨어 자원의 정적 할당 또는 파티셔닝에 의존하지 않는다. 그리고 무시할 수 있는 런타임 오버 헤드만으로 QoS 응용의 성능을 향상한다는 관점에서 적응성, 효과성 그리고 효율성을 제공한다. 또한 최소한의 커널 수정만으로 커널 스케줄러에 쉽게 통합될 수 있는 소프트웨어 전용 해결책이다. 본 학위논문은 제안된 알고리즘을 리눅스의 CFS에 구현하고 최종적인 산출물을 mCFS로 명명하였다. 마지막으로 광범위한 실험을 통해 본 연구의 접근 방식의 유용성과 효과를 검증한다.Performance interference between QoS and best-effort applications is getting more aggravated as data-intensive applications are rapidly and widely spreading in recently emerging computing systems. While the completely fair scheduler (CFS) of the Linux kernel has been extensively used to support performance isolation in a multitasking environment, it falls short of addressing memory-related interference due to memory access contention and insufficient cache coverage. Though quite a few memory-aware performance isolation mechanisms have been proposed in the literature, many of them rely on hardware-based solutions, inflexible resource management or ineffective execution throttling, which makes it difficult for them to be used in widely deployed operating systems like Linux running on a COTS SoC platform. We propose a memory-aware fair-share scheduling algorithm that can make QoS applications less susceptible to memory-related interference from other co-running applications. Our algorithm carefully separates the genuine memory-related stall from a running tasks CPU cycles and compensates the task for the memory-related interference so that the task gets the desired share of CPU before it is too late. The proposed approach is adaptive, effective and efficient in the sense that it does not rely on any static allocation or partitioning of memory hardware resources and improves the performance of QoS applications with only a negligible runtime overhead. Moreover, it is a software-only solution that can be easily integrated into the kernel scheduler with only minimal modification to the kernel. We implement our algorithm into the CFS of Linux and name the end result mCFS. We show the utility and effectiveness of the approach via extensive experiments.제 1 장 서론 1 제 1 절 연구 배경 6 제 2 절 연구 내용 9 제 3 절 논문 구성 10 제 2 장 관련 연구 11 제 1 절 공간적 메모리 자원 고립화 기법 11 제 2 절 시간적 메모리 자원 고립화 기법 14 2.1 예방 기반 시간적 메모리 자원 고립화 기법 14 2.2 보상 기반 시간적 메모리 자원 고립화 기법 18 제 3 장 배경 지식 23 제 1 절 NVIDIA Jetson AGX Xavier 플랫폼 23 제 2 절 Carmel PMU 소개 24 제 3 절 CPU 사이클의 분류 28 제 4 절 리눅스 커널의 CFS 30 제 4 장 메모리에 관련된 간섭에 관한 지표 정의와 검증 34 제 1 절 백엔드 스톨 사이클 분류와 지표 정의 34 제 2 절 지표에 대한 실험적 검증 37 제 5 장 문제 정의 45 제 1 절 대상 시스템과 태스크 모델 44 제 2 절 문제 정의 49 제 6 장 메모리 인지 비례공정 스케줄링 52 제 1 절 mCFS 아키텍처 51 제 2 절 메모리 관련 간섭 추정 기법 54 제 3 절 User와 interfacing 61 제 4 절 커널 모듈과의 interfacing 62 제 7 장 실험적 평가 65 제 1 절 실험 환경 64 제 2 절 실험 결과 67 제 8 장 결론 76 참고문헌 78Docto