An FPTAS for Interface Selection in the Periodic Resource Model
Résumé
The periodic resource model of Shin and Lee [19] provides a °exible, simple framework for design- ing compositional real-time systems. Each compo- nent in the periodic resource model has an inter- face which speci¯es the period and capacity of the resource used to schedule the component. Unfortu- nately, the best-known exact algorithms for determin- ing the interface parameters for a component in the periodic resource model potentially require exponential or pseudo-polynomial time. In this paper, we obtain an FPTAS for the problem of selecting an interface period given a capacity-determination algorithm. We also apply our approach to obtain an FPTAS for the problem of selecting both a period and capacity for components consisting of sporadic task systems. Our algorithms obtain interface parameters with interface bandwidth at most (1 + ²) times the optimal for any ² > 0.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...