A preliminary idea for an 8-competitive, log2 DMAX + log2 log2 (1/U) asymptotic-space, interface generation algorithm for two-level hierarchical scheduling of constrained-deadline sporadic tasks on a uniprocessor
Ref: HURRAY-TR-110201 Publication Date: Mar 2011
A preliminary idea for an 8-competitive, log2 DMAX + log2 log2 (1/U) asymptotic-space, interface generation algorithm for two-level hierarchical scheduling of constrained-deadline sporadic tasks on a uniprocessor
Ref: HURRAY-TR-110201 Publication Date: Mar 2011Abstract:
Consider a single processor and a software system.
The software system comprises components and interfaces
where each component has an associated interface and each
component comprises a set of constrained-deadline sporadic
tasks. A scheduling algorithm (called global scheduler) determines
at each instant which component is active. The active
component uses another scheduling algorithm (called local
scheduler) to determine which task is selected for execution
on the processor. The interface of a component makes certain
information about a component visible to other components;
the interfaces of all components are used for schedulability
analysis. We address the problem of generating an interface
for a component based on the tasks inside the component. We
desire to (i) incur only a small loss in schedulability analysis
due to the interface and (ii) ensure that the amount of space
(counted in bits) of the interface is small; this is because such
an interface hides as much details of the component as possible.
We present an algorithm for generating such an interface.
Document:
Published in SIGBED Review, ACM, Volume 8, Issue 1, pp 22-29.
New York, NY, U.S.A..
DOI:10.1145/1967021.1967024.
Record Date: 16, Feb, 2011
Workshop on Compositional Theory and Technology for Real-Time Embedded Systems (CRTS 2009)