Bounding completion times of jobs with arbitrary release times, variable execution times and resource sharing
Authors:
- 1 January 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. 23 (10) , 603-615
Abstract
The workload of many real-time systems can be characterized as a set of preemptable jobs with linear precedence constraints. Typically their execution times are only known to lie within a range of values. In addition, jobs share resources and access to the resources must be synchronized to ensure the integrity of the system. This paper is concerned with the schedulability of such jobs when scheduled on a priority-driven basis. It describes three algorithms for computing upper bounds on the completion times of jobs that have arbitrary release times and priorities. The first two are simple but do not yield sufficiently tight bounds, while the last one yields the tightest bounds but has the greatest complexity.Keywords
This publication has 7 references indexed in Scilit:
- Timing analysis for fixed-priority scheduling of hard real-time systemsIEEE Transactions on Software Engineering, 1994
- Applying new scheduling theory to static priority pre-emptive schedulingSoftware Engineering Journal, 1993
- Fixed Priority Scheduling Theory for Hard Real-Time Systems1991
- Priority inheritance protocols: an approach to real-time synchronizationIEEE Transactions on Computers, 1990
- Fixed priority scheduling of periodic task sets with arbitrary deadlines1990
- A stack-based resource allocation policy for realtime processes1990
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973