Real-time embedded systems are becoming more complex to include more functionalities. Sharing a computing platform is a natural and effective solution to reducing the cost of those systems. However, the sharing can cause serious problems in mixed-criticality systems where applications have different levels of criticality. Certifying the mixed-criticality systems requires efficient scheduling algorithms and schedulability tests different from the ones used in single criticality systems. In this thesis, we propose a dynamic scheduling algorithm called CBEDF for certifiable mixed-criticality systems on a uniprocessor platform. We show that CBEDF dominates previously proposed algorithms. In addition, we propose a schedulability condition for CBEDF. Then, we demonstrate that the schedulability of CBEDF outperforms those of the previously proposed algorithms by performing simulations using randomly generated instances of jobs.
최근, 실시간 내장형 시스템 개발자들은 시스템의 가격과 시스템 크기, 시스템이 사용하는 에너지 소비량과 같은 물리적 자원의 소비를 최소화 하기위해 노력하고 있다. 하나의 컴퓨팅 플랫폼을 공유해 여러 가지 기능을 구현하는 것은 시스템의 가격과 물리적 자원의 소비를 최소화 하는데 매우 효과적인 방법이다. 하지만, 서로 다른 중요도를 가진 작업들이 하나의 컴퓨팅 플랫폼을 공유해 스케줄링 되는 것은 심각한 문제를 야기할 수 있다. 예를 들어, 차량용 ABS 시스템과, 내비게이션 시스템이 하나의 컴퓨팅 플랫폼을 공유한다고 가정해보자. 이 때, 낮은 중요도를 가진 내비게이션 시스템 작업이 높은 중요도를 가진 ABS 시스템의 작업보다 먼저 컴퓨팅 자원을 선점한다면 ABS 시스템 작업의 마감 시간 초과를 야기 시킬 수 있다. 이는 차량 브레이크 시스템의 오작동을 야기 시켜, 차량 사고와 같은 심각한 안전 문제를 발생시킨다. 이러한 문제를 해결하기 위해, 서로 다른 중요도를 가진 작업들이 하나의 컴퓨팅 플랫폼을 공유하고 있을 때, 높은 중요도의 작업이 낮은 중요도의 작업에 의해 마감 시간 초과가 발생하지 않음을 보증할 수 있는 스케줄링 기법이 필요하다. 우리는 본 논문에서 단일 프로세서 환경에서 이중 중요도 시스템을 위한 보증가능한 스케줄링 기법인 CBEDF를 제안하였다. 우리가 제안한 스케줄링 기법은 EDF 기반의 동적 스케줄링 기법으로써 효율적인 자원의 활용을 가능하게 하며 높은 중요도를 가지는 작업이 원활하게 수행 될 수 잇음을 보장한다. 이 기법은 런타임 이전에 Empty Slack을 계산하는 알고리즘과, 런타임시에 스케줄링을 수행하는 알고리즘을 합쳐 두 가지의 부분 알고리즘으로 이루어져 있다. 또한 우리는 본 논문에서 우리가 제안한 CBEDF 알고리즘에 대한 스케줄 가능성 분석을 통해 기존에 제안된 OCBP 알고리즘과 실시간 시스템에서 흔히 사용되고 있는 EDF 알고리즘보다 뛰어난 성능을 보임을 실험을 통하여 보였다.
