Scheduling Tasks with Mixed Preemption Relations for Robustness to Timing Faults

John Regehr
regehr@cs.utah.edu

University of Utah, School of Computing
50 South Central Campus Drive, Room 3190
Salt Lake City, Utah 84112-9205
http://www.cs.utah.edu/flux/

Abstract

This paper introduces and shows how to schedule two novel scheduling abstractions that overcome limitations of existing work on preemption threshold scheduling. The abstractions are task clusters, groups of tasks that are mutually non-preemptible by design, and task barriers, which partition the task set into subsets that must be mapped to different threads. Barriers prevent the preemption threshold logic that runs multiple design-time tasks in the same run-time thread from violating architectural constraints, e.g. by merging an interrupt handler and a user-level thread.

We show that the preemption threshold logic for mapping tasks to as few threads as possible can rule out the schedules with the highest critical scaling factors --- these schedules are the least likely to miss deadlines under timing faults. We have developed a framework for robust CPU scheduling and three novel algorithms: an optimal algorithm for maximizing the critical scaling factor of a task set under restricted conditions, a more generally applicable heuristic that finds schedules with approximately maximal critical scaling factors, and a heuristic search that jointly maximizes the critical scaling factor of computed schedules and minimizes the number of threads required to run a task set. We demonstrate that our techniques for robust scheduling are applicable in a wide variety of situations where static priority scheduling is used.

In Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS 2002), pages 315-326, Austin, TX, December 3-5 2002.

• paper (PDF, PS.gz)
• slides (PDF, PPT)

© 2002 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

Note: SPAK, the tool that was used to produce all quantitative results in this paper, is free software and can be obtained at the:
SPAK page.

A previous version of this paper appeared as Flux Group Technical Note 2002-01, May 2002. We will provide an electronic version of this paper on request. However, we prefer that you please read and cite the RTSS paper instead.