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

dc.contributor.authorGuo, Yifeng
dc.contributor.authorSu, Hang
dc.contributor.authorZhu, Dakai
dc.contributor.authorAydin, Hakan
dc.description.abstractIn 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.
dc.description.departmentComputer Science
dc.publisherUTSA Department of Computer Science
dc.relation.ispartofseriesTechnical Report; CS-TR-2012-009
dc.subjectperiodic real-time tasks
dc.subjectpreference-oriented execution
dc.subjectscheduling algorithms
dc.titlePreference-Oriented Scheduling Framework and its Application to Fault-Tolerant Real-Time Systems (Extended Version)
dc.typeTechnical Report


Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
153.15 KB
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
1.86 KB
Item-specific license agreed upon to submission