Preference-Oriented Scheduling Framework and its Application to Fault-Tolerant Real-Time Systems (Extended Version)

Date

2012-05-15

Authors

Guo, Yifeng
Su, Hang
Zhu, Dakai
Aydin, Hakan

Journal Title

Journal ISSN

Volume Title

Publisher

UTSA Department of Computer Science

Abstract

In fault-tolerant systems, the primary and backup copies of different tasks can be scheduled together on one processor, where primary tasks should be executed as soon as possible (ASAP) and backup tasks as late as possible (ALAP) for better performance (e.g., energy efficiency). To address such mixed requirements, in this paper, we propose the concept of preference-oriented execution and study the corresponding scheduling algorithms. Specifically, we formally define the optimality of preference-oriented schedules and show that such schedules may not always exist for general periodic task sets. Then, we propose an ASAP-Ensured Earliest Deadline (SEED) scheduling algorithm, which guarantees to generate an ASAP-optimal schedule for any schedulable task set. Moreover, to incorporate the preference for ALAP tasks, we extend SEED and develop a Preference-Oriented Earliest Deadline (POED) scheduling heuristic. For a dual-processor fault-tolerant system, we illustrate how such algorithms can be exploited to improve the energy savings. We evaluate the proposed schedulers through extensive simulations. The results confirm the optimality of SEED for ASAP tasks. When compared to the well-known EDF scheduler, both SEED and POED can perform better in preference-oriented settings with reasonable overheads. Moreover, for a dual-processor fault-tolerant system, significant energy savings (up to 20%) can be obtained under POED when compared to the state-of-the-art standby-sparing scheme.

Description

Keywords

periodic real-time tasks, preference-oriented execution, scheduling algorithms, optimality

Citation

Department

Computer Science