Real-time embedded systems have been designed to perform specific functionalities and they have been evolving in very complex structures as computing and control technology have developed. A cyber physical system (CPS) is a computer system that controls multiple physical devices. Such physical systems need to meet various requirements simultaneously, including high performance, real-time functioning, and a high level of reliability and security. Among the requirements, this dissertation proposes mechanisms to satisfy the requirements of high performance and security. For the high performance requirement, we address the scheduling problem of multi-processor. For several decades, real-time scheduling on uni-processor have been well studied. Earliest deadline first (EDF), the optimal scheduling algorithm on uni-processor, is a typical example of successful results of such researches. Unlike uniprocessor scheduling, EDF shows relatively poor performance on global multiprocessor scheduling. As no other global JFP multiprocessor algorithms are illuminated beyond EDF, this dissertation proposes one, called earliest quasi-deadline first (EQDF). This dissertation then seeks to explore how it can improve the schedulability of global JFP scheduling. For the security requirement, this dissertation proposes mechanisms to meet both of time and security constraints simultaneously. Since real-time systems typically relies on real-time scheduling, to conserve real-time property is the fundamental issue for security mechanism design. Addressing this issue, previous works have proposed approaches to add a security constraint to the real-time properties to cope with the information leakage problem that can arise between real-time tasks with different security levels. However, conventional works have mainly focused on non-preemptive scheduling and have suggested a very naive approach for preemptive scheduling, which shows limited analytical capability. In this dissertation, we present a new preemptive fixed-priority scheduling algorithm incorporating a security constraint, called lowest security-level first (LSF) and its strong schedulability analysis to reduce the potential of information leakage.
실행 및 제어 기술들이 발전함에 따라 실시간 내장형 시스템은 여러 복잡한 물리 장치들을 조작하는 사이버 물리 시스템으로 진화 되어 왔다. 이러한 물리 시스템은 고성능, 실시간 실행, 높은 수준의 신뢰성과 보안성 등의 여러가지 요구사항들은 동시에 만족시켜야 한다. 이 논문에서는 이러한 요구사항들 중 고성능과 보안 요구사항들을 만족시키기 위한 방법들을 제안한다. 우선 고성능 요구사항을 위해, 멀티 프로세서에서의 스케줄링 문제를 다룬다. 멀티 프로세서에서는 최단 마감시간 우선 알고리즘 (EDF) 을 능가하는 작업 단위 우선순위 선정 기법이 없는 것에 착안하여, 이 논문에서는 EDF의 확장으로서 최단 가상 마감시간 우선 알고리즘 (EQDF) 을 제안한다. 두번째 요구사항인 보안을 위해, 시간 제약사항과 보안 제약사항을 동시에 만족시키는 기법에 대해 다룬다. 기존의 연구들은 주로 선점 불가능 스케줄링 기법으로만 한정 되었고, 선점 가능 스케줄링 기법에는 간단한 방법들만을 제안함으로써 실시간성 분석 성능에 한계를 가지고 있다. 이 논문에서 우리는 최하위 보안 수준 작업 우선 알고리즘 (LSF) 이라는 보안 제약 사항을 포함하는 새로운 선점 가능 스케줄링 알고리즘과, 이를 지원하는 강력한 성능의 실시간성 분석 기법을 제안한다.
