With the widespread of multi-core architectures, real-time multi-core scheduling research has been steadily gaining importance. In spite of some remarkable achievements in real-time multi-core scheduling in the past, there are still significant research challenges that remain. In particular, the vast majority of existing research considers simple scheduling models, such as sequential tasks under RM and EDF scheduling, originally developed with uni-core platforms. Therefore, there is a need to take into account more general scheduling models that can take full advantage of multi-core processing. In this dissertation, we aim to apply successful results to more general scheduling models. To this end, we understand the fundamental differences between each scheduling model and introduce novel concepts that explain the differences. Building upon them, we develop new techniques that can easily extend existing approaches to general scheduling models, significantly advancing the state-of-the-art scheduling algorithms and schedulability analysis for real-time multi-core systems.
For a scheduler component, although job-level priority assignment (JPA) is a generalization of task-level priority assignment (TPA), there is no clear dominance relation between existing TPA and JPA scheduling techniques. We focus on understanding fundamental differences between TPA and JPA and derive a condition under which JPA is able to behave exactly the same way as TPA. Then, we present the first algorithm (SPDF- Smallest Pseudo-Deadline First) that generalizes TPA scheduling to JPA scheduling with a simple task-level parameter called pseudo-deadline. We show that SPDF dominates all TPA algorithms when pseudo-deadlines are appropriately determined.
For a task component, although a number of studies extensively investigated the schedulability analysis of sequential tasks with many influential results, the insights behind those successful results are not directly applicable or easily extensible to parallel tasks. We extend the notion of interference to capture thread-level parallelism for parallel tasks. We then leverage the proposed notion of parallelism-aware interference to derive the first schedulability test that is directly applicable to parallel tasks on multi-core platforms.
For a resource component, almost all scheduling approaches for heterogeneous multi-core platforms have been focused on partitioned scheduling rather than global scheduling, due to difficulties of applying existing work on homogeneous platforms to global heterogeneous multi-core scheduling. We extend scheduling guidelines and algorithms for optimal homogeneous multi-core scheduling toward two-type heterogeneous global scheduling to develop the first optimal scheduling algorithm for two-type heterogeneous multi-core platforms.
하드웨어와 소프트웨어 기술이 발전함에 따라, 실시간 스케줄링 이론 연구 역시 이에 맞게 새로운 기술들의 이점을 최대한 활용할 수 있도록 함께 발전해야 한다. 본 학위논문에서는 새로운 또는 좀 더 일반적인 스케줄링 모델에 대해, 기존 모델과의 근본적인 차이를 스케줄링 관점에서 잘 이해하고 표현할 수 있는 새로운 개념을 제시한다. 또한, 이러한 개념을 바탕으로 기존 모델에서 잘 정립된 스케줄링 기법들을 쉽게 새로운 모델에 맞게 확장할 뿐만 아니라 스케줄링 성능을 크게 향상시킬 수 있는 방법론을 개발한다. 이를 통해, 실시간 멀티코어 시스템을 위한 스케줄링 알고리즘 및 스케줄 가능성 분석 기법의 기술적 수준을 크게 발전시키고자 한다.
이를 위해, 구체적으로 세가지 연구를 진행하였다. 첫 번째로, 테스크 단위 우선순위 할당 (Task-level Priority Assignment - TPA)과 작업 단위 우선순위 할당 (Job-level Priority Assignment - JPA) 방법 간의 차이를 이해할 수 있는 테스크간 우선순위 관계를 밝혀냈다. 이를 바탕으로 가상 마감시간 (pseudo-deadline)이라는 간단한 변수를 통해 TPA 와 JPA 스케줄링을 일반화할 수 있는 SPDF (Smallest Pseudo-Deadline First) 스케줄링 알고리즘을 개발하였다. SPDF 스케줄링 알고리즘으로 성능이 뛰어난 TPA 스케줄링 기법들을 JPA 스케줄링에 적용가능 하도록 하여 멀티코어 스케줄링 성능을 크게 향상 시켰다.
두 번째로, DAG (Directed Acyclic Graph) 병렬 테스크 스케줄링에 초점을 맞춰서, 스케줄 가능성 분석 기법에서 많이 쓰이는 간섭 (interference)개념을 병렬 테스크의 특징인 스레드 단위 동시실행성 (thread-level parallelism)을 표현할 수 있도록 확장하였다. 이러한 새로운 간섭 개념을 바탕으로, 병렬 테스크에 바로 적용 가능한 간섭기반 스케줄 가능성 분석 기법을 개발하여 병렬 테스크 스케줄링 성능을 크게 향상 시켰다.
세 번째로, 최적의 동종 (homogeneous) 멀티코어 스케줄링을 위한 스케줄링 가이드라인과 알고리즘을 두 가지 타입의 이종 (heterogeneous) 멀티코어 스케줄링 환경으로 확장하였다. 이종 멀티코어 플랫폼의 특징으로 추가적으로 고려해줘야 하는 문제들을 잘 구분하여, 기존의 동종 멀티코어 스케줄링의 결과를 최대한 이용할 수 있는 효율적인 최적 이종 멀티코어 스케줄링 알고리즘을 개발하였다.
본 학위논문에서 제시한 각 연구는 실시간 멀티코어 스케줄링 이론의 수준을 한 단계 진보시키기 위해 좀 더 일반적인 스케줄링 모델을 위한 새로운 개념과 스케줄링 기법들을 제시하였다. 본 학위논문의 연구 결과는 실시간 멀티코어 스케줄링의 기술적 수준을 발전시킬 뿐만 아니라, 후속 연구에도 토대가 될 것이다.
