Dynamic scheduling of periodic skippable tasks in an overloaded real-time system

The need for supporting dynamic real-time environments where changes in workloads may occur requires a scheduling framework that explicitly addresses overload conditions, allows the system to achieve graceful degradation and supports a mechanism capable of determining the load to be shed from the system to handle the overload. In applications ranging from video reception to air-craft control, tasks enter periodically and have response time constraints, but missing a deadline is acceptable, provided most deadlines are met. Such tasks are said to be occasionally skippable and have an assigned skip parameter. We look at the problem of uniprocessor scheduling of skippable periodic tasks which consists in maximizing the robustness of the system defined as the global completion ratio. In this paper, we propose a novel scheduling Skip-over algorithm, called RLP/T, a variant of Earliest-Deadline First which adjusts the system workload such that tasks adhere to their timing and skip constraints and guarantees the best robustness.