Replication-Based Fault-Tolerant Scheduling Algorithm for Heterogeneous Real-Time Systems
摘要
In real-time systems, low response time and high reliability are critical yet conflicting performance metrics. The scheduling of parallel applications with data dependencies in heterogeneous systems has been proven to be an NP-complete problem. Traditional active replication methods, while improving reliability, often introduce resource contention, increasing task response times and jeopardizing real-time requirements. To address this challenge, this paper proposes a Maximum Reliability Fault-Tolerance Algorithm based on Limited Replication (LDFTS). Our algorithm first generates an initial scheduling solution using a limited replication strategy, then iteratively replicates tasks starting from the least reliable ones while verifying temporal constraints, ultimately yielding an optimal replication scheme that maximizes system reliability. Experiments on heterogeneous multi-core platforms demonstrate that, compared to DB-FAST and BLMR, our algorithm significantly enhances system reliability while reducing the overall scheduling length.