Dynamic scheduling of hard real-time tasks and real-time threads
- 1 January 1992
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. 18 (8) , 736-748
- https://doi.org/10.1109/32.153383
Abstract
The authors investigate the dynamic scheduling of tasks with well-defined timing constraints. They present a dynamic uniprocessor scheduling algorithm with an O(n log n) worst-case complexity. The preemptive scheduling performed by the algorithm is shown to be of higher efficiency than that of other known algorithms. Furthermore, tasks may be related by precedence constraints, and they may have arbitrary deadlines and start times (which need not equal their arrival times). An experimental evaluation of the algorithm compares its average case behavior to the worst case. An analytic model used for explanation of the experimental results is validated with actual system measurements. The dynamic scheduling algorithm is the basis of a real-time multiprocessor operating system kernel developed in conjunction with this research. Specifically, this algorithm is used at the lowest, threads-based layer of the kernel whenever threads are created.Keywords
This publication has 17 references indexed in Scilit:
- On-line scheduling of real-time tasksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- The integration of deadline and criticalness in hard real-time schedulingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Experimental evaluation of a real-time scheduler for a multiprocessor systemIEEE Transactions on Software Engineering, 1991
- Scheduling processes with release times, deadlines, precedence and exclusion relationsIEEE Transactions on Software Engineering, 1990
- CHAOS-Kernel Support for Objects in the Real-Time DomainIEEE Transactions on Computers, 1987
- Preemptive Scheduling Under Time and Resource ConstraintsIEEE Transactions on Computers, 1987
- A configurable system for automation programming and controlPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Dynamic Configuration for Distributed SystemsIEEE Transactions on Software Engineering, 1985
- StarOS, a multiprocessor operating system for the support of task forcesPublished by Association for Computing Machinery (ACM) ,1979
- Some simple scheduling algorithmsNaval Research Logistics Quarterly, 1974