Enhancing performance and fault tolerance in reward-based scheduling.

摘要

Reward-based scheduling is based on the principle of trading precision for timeliness and it is particularly suitable for real-time applications where worst-case guarantees can not be provided due to overload conditions and/or faults. In this framework, a real-time task comprises a mandatory part and an optional part. The mandatory part produces an approximate result, which is subsequently refined by the optional part. Further, a nondecreasing reward function is associated with the optional execution.; In this dissertation, we explore reward-based scheduling as a comprehensive and cohesive framework for researching real-time scheduling problems with different metrics and goals. In particular, we solve some open problems, and study the application of the reward-based framework to power management and fault tolerance. In periodic reward-based scheduling, we provide an efficient and optimal solution to compute service times of optional parts, which can be used with scheduling policies that fully utilize the processor(s). We also investigate relaxing some fundamental assumptions.; Power-aware scheduling consists of dynamic adjustments of the CPU speed, aiming at obtaining energy savings at the expense of increased response time. We devise three schemes that still satisfy the application timing constraints, namely: (a) Static Optimal, based on the reward-based framework, when tasks consume the worst-case workload, (b) Dynamic Reclaiming, based on detecting early completions in the actual workload, and (c) Aggressive, which anticipates early completions by taking into account the expected workload.; Finally, we develop a Fault Tolerant (FT) Optimality framework for reward-based realtime tasks. Within this framework, our approach is to schedule the optional parts intelligently to allow recovery time for mandatory parts in case of errors, while maximizing the total reward. We provide FT Optimal algorithms for independent tasks and tasks having linear precedence constraints, analyzing both single deadline and distinct deadlines cases.; As a whole, the dissertation provides a justification of the reward-based scheduling framework as a general paradigm to express and incorporate multiple requirement dimensions for real-time computing. Our results show that the framework is particularly promising for emerging applications where timeliness, utility (reward), power-efficiency and fault tolerance dimensions need to be simultaneously addressed.