서지주요정보
Advancing multi-core scheduling for real-time embedded systems = 실시간 임베디드 시스템을 위한 멀티코어 스케줄링 연구
서명 / 저자 Advancing multi-core scheduling for real-time embedded systems = 실시간 임베디드 시스템을 위한 멀티코어 스케줄링 연구 / Hoon Sung Chwa.
저자명 Chwa, Hoon Sung ; 좌훈승
발행사항 [대전 : 한국과학기술원, 2016].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8028794

소장위치/청구기호

학술문화관(문화관) 보존서고

DCS 16009

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

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) 멀티코어 스케줄링 환경으로 확장하였다. 이종 멀티코어 플랫폼의 특징으로 추가적으로 고려해줘야 하는 문제들을 잘 구분하여, 기존의 동종 멀티코어 스케줄링의 결과를 최대한 이용할 수 있는 효율적인 최적 이종 멀티코어 스케줄링 알고리즘을 개발하였다. 본 학위논문에서 제시한 각 연구는 실시간 멀티코어 스케줄링 이론의 수준을 한 단계 진보시키기 위해 좀 더 일반적인 스케줄링 모델을 위한 새로운 개념과 스케줄링 기법들을 제시하였다. 본 학위논문의 연구 결과는 실시간 멀티코어 스케줄링의 기술적 수준을 발전시킬 뿐만 아니라, 후속 연구에도 토대가 될 것이다.

서지기타정보

서지기타정보
청구기호 {DCS 16009
형태사항 v, 113 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 좌훈승
지도교수의 영문표기 : Insik Shin
지도교수의 한글표기 : 신인식
수록잡지명 : "Capturing urgency and parallelism using quasi-deadlines for real-time multiprocessor scheduling ". Journal of Systems and Software, v.101, pp.15-29(2015)
학위논문 학위논문(박사) - 한국과학기술원 : 전산학부,
서지주기 References : p. 102-109
주제 real-time systems
multi-core scheduling
scheduling algorithm
schedulability analysis
embedded systems
실시간 시스템
멀티코어 스케줄링
스케줄링 알고리즘
스케줄 가능성 분석
임베디드 시스템
QR CODE qr code