Björn Andersson
Abstract
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.
- B. Andersson. A pseudo-medium-wide 8-competitive interface for two-level compositional real-time scheduling of constrained-deadline sporadic tasks on a uniprocessor. In Proc. of 2nd Workshop on Compositional Theory and Technology for Real-Time Embedded Systems (Co-located with RTSS), 2009.Google Scholar
- S. Baruah and N. Fisher. The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems. IEEE Transactions on Computers, 55(7):918--923, 2006. Google ScholarDigital Library
- S. K. Baruah, A. K. Mok, and L. E. Rosier. Scheduling hard-real-time sporadic tasks on one processor. In Proc. of 11th Real-Time Systems Symposium (RTSS), pages 182--190, 1990.Google ScholarCross Ref
- L. Bass, P. Clements, and R. Kazman. Software Architecture in Practice. Addison Wesley, second edition, 2003. Google ScholarDigital Library
- A. Easwaran, M. Anand, and I. Lee. Compositional analysis framework using EDP resource models. In Proc. of 28th Real-Time Systems Symposium (RTSS), pages 129--138, 2007. Google ScholarDigital Library
- C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the Association for the Computing Machinery, 20:46--61, 1973. Google ScholarDigital Library
- A. Mok, X. Feng, and D. Chen. Resource partition for real-time systems. In Proc. of 7th IEEE Real-Time Technology and Applications Symposium (RTAS), pages 75--84, 2001. Google ScholarDigital Library
- I. Shin and I. Lee. Periodic resource model for compositional real-time guarantees. In Proc. of 24th Real-Time Systems Symposium (RTSS), pages 2--10, 2003. Google ScholarDigital Library
- I. Shin and I. Lee. Compositional real-time scheduling framework. In Proc. of 25th Real-Time Systems Symposium (RTSS), pages 57--67, 2004. Google ScholarDigital Library
Index Terms
- 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
Recommendations
Improved Uniprocessor Scheduling of Systems of Sporadic Constrained-Deadline Elastic Tasks
RTNS '23: Proceedings of the 31st International Conference on Real-Time Networks and SystemsThe elastic task model was proposed to allow for the accurate modeling of recurrent real-time workloads that are somewhat flexible with regards to the frequency at which they must be invoked. This is achieved by specifying a range of values for each ...
The Partitioned Multiprocessor Scheduling of Deadline-Constrained Sporadic Task Systems
A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks, each constrained to have its relative-deadline parameter be no larger than its period parameter, among the processors of an identical multiprocessor platform. ...
Competitive Two-Agent Scheduling and Its Applications
We consider a scheduling environment with m (m ≥ 1) identical machines in parallel and two agents. Agent A is responsible for n1 jobs and has a given objective function with regard to these jobs; agent B is responsible for n2 jobs and has an objective ...
Comments