A pseudo-medium-wide 8-competitive interface for two-level compositional real-time scheduling of constrained- deadline sporadic tasks on a uniprocessor

摘要

Compositional real-time scheduling clearly requiresthat ”normal” real-time scheduling challenges are addressedbut challenges intrinsic to compositionality must beaddressed as well, in particular: (i) how should interfaces bedescribed? and (ii) how should numerical values be assignedto parameters constituting the interfaces? The real-time systemscommunity has traditionally used narrow interfaces fordescribing a component (for example, a utilization/bandwidthlikemetric and the distribution of this bandwidth in time).In this paper, we introduce the concept of competitive ratioof an interface and show that typical narrow interfaces causepoor performance for scheduling constrained-deadline sporadictasks (competitive ratio is infinite). Therefore, we explore moreexpressive interfaces; in particular a class called medium-wideinterfaces. For this class, we propose an interface type andshow how the parameters of the interface should be selected.We also prove that this interface is 8-competitive.