교차계층 자원관리와 스케줄링을 통한 소프트웨어 플랫폼 최적화

Abstract

소프트웨어 플랫폼의 거대화 및 복잡화 문제에 대응하기 위해 플랫폼은 필연적으로 계층적인 소프트웨어 구조를 채택한다. 이러한 계층 구조에서 성능 최적화는 개별 계층에서 타 계층에 독립적으로 수행되며, 인접한 계층들의 제한된 정보만을 이용할 수 있기 때문에 전체론적 성능 최적화의 측면에서 한계가 있다. 이와 같이 계층적 소프트웨어 구조에 기인하는 성능 최적화의 문제를 해결하기 위해 고안된 기법이 교차계층 최적화이다. 이는 전체 성능에 영향을 주는 각 계층의 정보를 필요한 계층에 선택적으로 전달하고, 이를 통해 전체론적인 성능 최적화를 달성하는 것에 그 목적이 있다. 따라서 최근에는 교차계층적인 최적화를 통하여 플랫폼의 전체론적 성능을 향상시키려는 노력이 경주되고 있다. 특히, 스케줄링은 소프트웨어 플랫폼에서 발생하는 다양한 성능 최적화 문제 중에 시스템 전체에 영향을 끼칠 수 있는 중요한 문제이다. 본 학위논문은 계층적 소프트웨어 플랫폼에서 발생할 수 있는 두 가지 성능 최적화 문제를 교차계층 자원관리와 스케줄링을 통해 해결 할 수 있는 기법을 제안한다. 첫째, 본 연구는 내장형 사용자 단말에서 사용자 반응성 최적화를 위한 교차계층 자원관리 기법을 제안한다. 제안하는 기법은 크게 두 가지 구성 요소들로 이루어진다. 첫째, Framework-assisted Task Characterization(FTC)은 상위 프레임워크 계층과 하위 Linux kernel 계층 사이의 교차계층적 자원관리 기법이다. 상위 계층에서는 사용자 상호적 태스크 체인이 런타임에 검출되고, 하위 계층에서는 이 중 사용자 반응성에 영향을 끼치는 태스크들의 우선순위를 동적으로 증진한다. 결과적으로, 이 태스크들은 다른 태스크에 의해 선점 당하지 않고 오랫동안 CPU를 점유 가능해지기 때문에 매우 작은 선점 지연시간을 보장한다. 둘째, Virtual Time-based Completely Fair Scheduler(VT-CFS)는 Linux의 태스크 스케줄러인 CFS를 교차계층적으로 최적화한다. 구체적으로, 이는 weighted fair queueing 방식의 스케줄링을 하여 보다 높은 응답성을 보장한다. 또한, 상위 계층 FTC로부터 판별된 사용자 상호적 태스크들이 바운드 된 실행 지연시간에 스케줄링 될 수 있도록 그들의 virtual runtime을 조정한다. 둘째, 본 연구는 멀티코어 스케줄링을 통해 비례공정성 최적화 달성을 위한 Progress Balancing 기법을 제안한다. 이는 태스크의 상대적 진척 정도를 virtual runtime으로 정의하고, 이를 균등하게 부하분산 하는 진척 기반 부하분산 기법이다. 구체적으로, Progress Balancing은 시스템 내 태스크들을 CPU 코어의 개수만큼의 태스크 그룹으로 분할하고 상대적으로 진척이 빠른 태스크를 느린 코어에 할당하고, 모든 코어들 간 로드 차이를 바운드 시킨다. 결과적으로, 태스크 간 virtual runtime 차이는 작은 상수로 바운드 되어서 비례공정성의 최적화를 달성한다. 본 연구에서 제안한 기법들의 효용성을 하기 위해서, 본 연구는 이들이 달성하고자 하는 성능 지표에 따라 선별된 대상 시스템에 각 기법들을 구현하였다. FTC와 VT-CFS는 Android 스마트폰에 구현되었다. 실험 결과, 기존 시스템 대비 무려 77.35% 더 짧게 양단간 사용자 반응시간을 단축함으로써 사용자 반응성의 최적화를 달성하였다. 이 최적화 결과는 FTC가 선점 지연시간을 80.23%, VT-CFS가 실행 지연시간을 78.42% 감소시켰다는 사실에 기인 한다. 또한, Progress Balancing은 Linux 기반 서버에 구현되었다. 실험 결과, 모든 태스크들의 virtual runtime의 차이가 작은 상수로 바운드 됨을 확인하였다. 이러한 virtual runtime 차이의 바운드는 서버 환경에서 호스팅 되는 사용자들에 모두 공정한 CPU 자원을 보장할 수 있음을 뜻한다. 이러한 결과는 본 논문에서 제안하는 교차계층 자원관리와 스케줄링 기법이 대상 시스템에 효과적으로 적용되어 보다 높은 수준의 성능 최적화가 가능함을 보이며, 또한 계속해서 다각화되고 복잡화되는 소프트웨어 플랫폼의 전체론적 성능 최적화를 위한 실용적인 수단임을 드러낸다.

Layering software platform is known to be a promising mean to deal with many problems incurred by its colossal and complex structure. In a layered structure, a performance optimization is performed locally at each individual layer independently from other layers, and restricted to use information provided from its adjacent layers. This leads many difficulties and challenges in achieving holistic system-wide performance optimization. A cross-layer optimization is an optimization paradigm which is proposed to solve such difficulties in layered software structure. It carefully delivers relevant information, which affects overall performance to other appropriate layers. Its objective is to lead a holistic performance optimization by violating the layering principle to a certain degree. Recently, due to its effectiveness, there have been a number of demands and efforts to improve an overall performance using the cross-layer optimization. In particular, task scheduling in a layered software platform is one of the most crucial problems which can affect an overall performance improvement of the platform. This thesis proposes a cross-layer resource control and scheduling to solve two performance optimization problems in layered software platforms. First, we present a cross-layer resource control to optimize a user interactivity for embedded user equipment. The proposed one consists of two components. First, Framework-assisted Task Characterization (FTC) is a cross-layer scheme between Android application framework and its underlying operating systems kernel. At the upper level, it identifies user-interactive tasks using the notion of a user-interactive task chain. It then enables the lower level scheduler to selectively promote the priorities of tasks appearing in the task chain. This effectively reduces the preemption latency of a user-interactive task since it can occupy a CPU longer without being preempted. Second, Virtual Time-based Completely Fair Scheduler (VT-CFS) is a cross-layer refinement of CFS in terms of interactivity. Specifically, it schedules a task in a WFQ fashion and allows a task to be preempted at every smaller period. It also adjusts the virtual runtime of the user-interactive task identified by FTC to ensure that a dispatch latency of a user-interactive task is reduced to a small value. Second, we present Progress Balancing in order to optimize a multicore proportional fairness in a server. It defines tasks relative progress as virtual runtimes and periodically balances them. Specifically, it partitions runnable tasks such that a core with larger virtual runtimes receives a larger load and the load difference among cores is bounded. As a result, the virtual runtime difference converges to the balancing period multiplied by some constant derived from the bounded load difference. To show a viability and evaluate an effectiveness of the proposed schemes, we have applied them to the target software platform product line. We have implemented FTC and VT-CFS into Android smartphone and empirically evaluated them with well-known benchmark programs and real-world applications. Results show that the end-to-end response time was reduced by up to 77.35% compared to the legacy one. This improvement comes from the facts that the modified framework achieved 80.23% shorter preemption latency than the legacy framework and that the VT-CFS yielded 78.42% shorter dispatch latency for user-interactive tasks than CFS. We have also implemented Progress Balancing into a multicore Linux-installed server. Experimental results report that virtual runtime difference between tasks is bounded by a small constant by adopting our scheme. Such bounding virtual runtime differences implies that tenants hosted from our target server are able to guarantee a use of fair amount of CPU resources. As such qualitative and quantitative analyses indicate, our cross-layer resource control and scheduling schemes effectively improve the overall system performance of the existing software platforms.