Imprecise Computation Model, Synchronous Periodic Real-time Task Sets and Total Weighted Error

Abstract

This paper proposes two scheduling approaches, one-level and two-level scheduling, for synchronous periodic real-time task sets based on the Imprecise Computation Model. The imperative of real-time systems is a reaction on an event within a limited amount of time. Sometimes the available time and resources are not enough for the computations to complete within the deadlines, but still enough to produce approximate results. The Imprecise Computation Model is motivated by this idea, which gives the flexibility to trade off precision for timeliness. In this model a task is logically decomposed into a mandatory and optional subtask. Only the mandatory subtask is required to complete by its deadline, while the optional subtask may be left unfinished. Usually, different scheduling policies are used for the scheduling of mandatory and optional subtasks. For both proposed approaches the earliest deadline first and rate monotonic scheduling algorithms are used for the scheduling of mandatory subtasks, whereas the optional subtasks are scheduled in a way that the total weighted error is minimized. The basic idea of one-level scheduling is to extend the mandatory execution times, while in two-level scheduling the mandatory and optional subtasks are separately scheduled. The single preemptive processor model is assumed.