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 UniprocessorRef: HURRAY-TR-091103 Publication Date: 1, Dec, 2009
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.
2nd Workshop on Compositional Theory and Technology for Real-Time Embedded Systems.
Notes: In conjunction with IEEE Real-Time Systems Symposium.