Schedulability Analysis for Task Migration on Distributed Mixed-Criticality Systems

Abstract

In safety-critical domains such as autonomous driving, software component interference is rising. Software components such as vehicle communication may control critical components, such as acceleration. However, the difficulty in guaranteeing all these components and the relation between them is the catastrophic cost of computing resources and the electronic control unit in the domain of vehicles required for every task. To satisfy both cost and safety requirements, a resilient method using software algorithms are considered in this dissertation.

The primary research mission is to satisfy the dynamic safety requirement, which is highly related to guaranteeing the deadline in the context of safety-critical systems, specifically the hard real-time embedded systems. To fulfill dynamic safety requirements, the dissertation offers a distributed mixed-criticality (MC) scheduler based on EDF-based MC schedulers and task migration. Task migration should be employed to satisfy the offline schedulability of the periodic MC system and the online schedulability of sporadic requests from dynamic criticality changed tasks in hard real-time constraints. Both schedulability analyses have proven that the sporadic task migration request can be fulfilled even under the worst-case CPU overload assumption. Furthermore, the proposed schedulers are implemented in real-time Linux, allowing investigations of real system scheduling behaviors and demonstrating predicted results in terms of overcoming criticality inversion and ensuring dynamic criticality changes. The proposed scheduler could be employed in dynamic criticality change scenarios such as switching from driver to autopilot mode and re-grouping truck platooning in the future.

In detail, this dissertation presents theoretically and practically the safety-guaranteed and inexpensive scheduling by borrowing the computational power of neighbored systems, obviating the need for additional hardware components. The sustainability of the task systems has shown improvement in Linux PREEMPT_RT systems and rt-test benchmarks. Based on the deadline test, the compatibility of our approach with the task-level mixed-criticality (MC) scheduler was higher than that of the system-level MC scheduler, such that the task-level had all dropped LC tasks recovered while the system-level only had 25.5% recovery. Conversely, from the worst-case measurement of violated HC tasks, the HC tasks were violated by the task-level MC scheduler more often than by the system-level MC scheduler, with 70.3% and 15.4% average response time overhead, respectively. In conclusion, under the condition that the HC task ratio has lower than 47% of the overall task systems at 80% of total utilization, the task-level approach with task migration has extensively higher sustainability on LC tasks.

From a technical point of view, the reduction and the optimization of the task migration technique for the time-critical situation are introduced. In vehicle domains, the electronic control unit (ECU) suffers from a design problem called single point of failure, which can induce system malfunctions such as unintended accelerations. This problem can be addressed via redundancy, which increases the reliability of a mission-critical system by allowing multiple ECUs to perform a single function but incurs additional ECU and maintenance costs. This dissertation proposes a method that migrates critical tasks in an infeasible ECU to a replaceable ECU by using the network connection between them. Furthermore, to demonstrate the feasibility of the method, an implementation of a task migration method on a Lego vehicle composed of three ECUs performed to prevent sudden unintended acceleration accidents caused by faults in an ECU managing the acceleration task.|자율 주행과 같은 안전이 중요한 분야에서 소프트웨어 구성요소 간 상호작용이 증가하고 있다. 차량 통신과 같은 소프트웨어 구성요소가 가속과 같이 중요한 구성요소를 제어하는 경우도 있다. 그러나 이러한 모든 구성요소를 안전하게 보장하고 구성요소 간 상호작용까지 모두 고려하고자 하기 위해서는 컴퓨팅 리소스와 전자 제어 장치의 치명적인 비용 발생하기 마련이다. 따라서, 적은 비용을 통한 안전 요구 사항을 만족시키기 위해, 본 논문에서는 소프트웨어 알고리즘을 사용하는 자율복원적인 방법을 고려한다.

해당 학위논문의 가장 주된 연구 목적은 동적 안전 요구 사항을 충족하는 것인데, 이는 안전 중요 시스템, 특히 하드 실시간 임베디드 시스템의 맥락에서 마감기한을 보장하는 것과 관련이 높다. 동적 안전 요구 사항을 충족하기 위해 본 논문은 EDF 기반 혼합 중요도(MC) 스케줄러 및 태스크 마이그레이션을 기반으로 하는 분산 혼합 중요도 스케줄러를 제공한다. 태스크 마이그레이션은 주기적인 MC 시스템의 오프라인 스케줄링 가능성과 하드 실시간 제약조건에서 동적으로 중요도가 변경된 태스크에서 발생하는 산발적인 요청의 온라인 스케줄링 가능성을 만족시키기 위해 사용되어야 한다. 두 스케줄링 가능성 분석 모두 최악의 경우 CPU 과부하 가정에서도 산발적인 태스크 마이그레이션 요청이 수행될 수 있음을 증명하였다. 또한 제안된 스케줄러는 실시간 리눅스에서 구현되어 실제 시스템 스케줄링 동작을 조사할 수 있으며 중요도 반전을 극복하고 동적 중요도 변경을 보장하는 측면에서 예측 결과를 보여준다. 제안된 스케줄러는 운전자에서 오토파일럿모드로 전환하거나 트럭 군집주행을 다시 결성하는 것과 같은 동적 중요도 변경 시나리오에 사용될 수 있다.

더 세부적으로, 본 논문은 추가적인 하드웨어 구성 요소의 필요성을 없애기 위해 분산시스템 가정 하에 인접한 시스템의 연산능력을 이용하여 이론적으로 그리고 실질적으로 안전이 보장되는 비용 효과적인 스케줄링을 제시한다. 태스크 시스템의 지속 가능성은 Linux PREEME_RT 및 RT 테스트 벤치마크를 통해 실험하였다. 마감기한 테스트를 기반으로, 태스크 수준 혼합 중요도(MC) 스케줄러와의 접근 방식의 호환성이 시스템 수준 MC 스케줄러의 호환성보다 높았으며, 태스크 수준은 모든 드롭된 LC 태스크가 복구된 반면 시스템 수준은 25.5%만 복구되었다. 반대로, 위반된 HC 태스크의 최악의 경우 측정에서 HC 태스크은 시스템 수준 MC 스케줄러보다 태스크 수준 MC 스케줄러에 의해 각각 70.3%와 15.4%의 평균 응답 시간 오버헤드로 더 자주 위반되는 현상을 관찰하였다. 결론적으로, HC 태스크 비율이 전체 활용도의 80%에서 전체 태스크 시스템의 47%보다 낮다는 조건에서 태스크 마이그레이션을 사용한 태스크 수준 접근 방식은 LC 태스크에서 훨씬 더 높은 지속 가능성을 갖는다.

기술적 관점에서, 시간 중요도 상황에 대한 태스크 마이그레이션 기술의 최적화 기법이 소개된다. 특히 차량 영역에서는 전자 제어 장치(ECU)가 단일 실패지점이라고 하는 설계 문제를 겪으며, 이는 의도하지 않은 가속과 같은 시스템 오작동을 유발할 수 있다. 이 문제는 다중성을 통해 해결할 수 있으며, 다중 ECU가 단일 기능을 수행하도록 허용하여 미션 크리티컬 시스템의 신뢰성을 증가시키지만 추가적인 ECU 및 유지보수 비용이 발생한다. 본 논문은 실현 불가능한 ECU의 중요한 태스크을 네트워크 연결을 사용하여 교체 가능한 ECU로 마이그레이션하는 방법을 제안한다. 또한, 이 방법의 타당성을 입증하기 위해, 가속 태스크을 관리하는 ECU의 고장으로 인한 갑작스러운 의도하지 않은 가속 사고를 방지하기 위해 3개의 ECU로 구성된 레고 차량에 태스크 마이그레이션 방법을 구현했다.