Resource-Aware Scheduling for Dependable Multicore Real-Time Systems: Utilization Bound and Partitioning Algorithm

摘要

As the computing devices and software executions are susceptible to manifold faults, fault tolerance has been an important research topic in safety-critical real-time systems. Moreover, multicore processors have recently emerged as prevailing computing engines for modern embedded systems. However, there exists rather rare work on the fault-tolerant scheduling of real-time tasks executing on multicores with shared resources, where the task synchronization originated from resource access contention may significantly degrade the schedulability of task system. With the focus on the partitioned-EDF scheduler with the MSRP (Multiprocessor Stack Resource Policy) protocol and primary/backup recovery mechanism, we first investigate a utilization bound and then identify its anomaly where the bound may decrease when more cores are deployed. Next, following the insights gained by the analysis of the bound, we propose a reliability and synchronization aware task partitioning algorithm (RSA-TPA) together with an efficient version to implement the joint management of task synchronization and system reliability, where several resource-oriented heuristics are developed to improve both the schedulability performance and workload balancing. The extensive simulation results show that the RSA-TPA schemes can obtain higher acceptance ratio (e.g., 60 percent more) and generate more balanced partitions, when compared to the existing schemes that consider either reliability management or task synchronization. Finally, with the different fault arrival rates being considered, the actual implementation in Linux kernel further demonstrates the applicability of RSA-TPA that has lower run-time overhead (e.g., 20 percent less) in comparison with other mapping algorithms.