A Pseudo-Medium-Wide 8-Competitive Interface for Two-Level Compositional Real-Time Scheduling of Constrained-Deadline Sporadic Tasks on a Uniprocessor
Ref: HURRAY-TR-091103 Publication Date: 1, Dec, 2009
A Pseudo-Medium-Wide 8-Competitive Interface for Two-Level Compositional Real-Time Scheduling of Constrained-Deadline Sporadic Tasks on a Uniprocessor
Ref: HURRAY-TR-091103 Publication Date: 1, Dec, 2009Abstract:
Compositional real-time scheduling clearly requires
that ”normal” real-time scheduling challenges are addressed
but challenges intrinsic to compositionality must be
addressed as well, in particular: (i) how should interfaces be
described? and (ii) how should numerical values be assigned
to parameters constituting the interfaces? The real-time systems
community has traditionally used narrow interfaces for
describing a component (for example, a utilization/bandwidth-like
metric and the distribution of this bandwidth in time).
In this paper, we introduce the concept of competitive ratio
of an interface and show that typical narrow interfaces cause
poor performance for scheduling constrained-deadline sporadic
tasks (competitive ratio is infinite). Therefore, we explore more
expressive interfaces; in particular a class called medium-wide
interfaces. For this class, we propose an interface type and
show how the parameters of the interface should be selected.
We also prove that this interface is 8-competitive.
Björn AnderssonDocument:
View
Download2nd Workshop on Compositional Theory and Technology for Real-Time Embedded Systems.
Washington, U.S.A..
Notes: In conjunction with IEEE Real-Time Systems Symposium.
Record Date: 1, Nov, 2009