×

Improved conditions for bounded tardiness underepdfpfair multiprocessor scheduling. (English) Zbl 1186.68061

Summary: The earliest-pseudo-deadline-first (EPDF) Pfair algorithm is more efficient than other known Pfair scheduling algorithms, but is not optimal for scheduling recurrent real-time task systems on more than two identical processors. Although not optimal, EPDF may be preferable for real-time systems instantiated on less-powerful platforms, those with soft timing constraints, or those whose task composition can change at run-time. In prior work, Srinivasan and Anderson established a sufficient per-task utilization restriction for ensuring a tardiness of at most \(q\) quanta, where \(q\geqslant 1\), under EPDF. They also conjectured that under this algorithm, a tardiness bound of one quantum applies to task systems that are not subject to any restriction other than the obvious restrictions, namely, that the total system utilization not exceed the available processing capacity and per-task utilizations not exceed 1.0. In this paper, we present counterexamples that show that their conjecture is false and present sufficient per-task utilization restrictions that are more liberal than theirs. For ensuring a tardiness bound of one quantum, our restriction presents an improvement of 50% over the previous one.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Anderson, A. Srinivasan, Early-release fair scheduling, in: Proceedings of the 12th Euromicro Conference on Real-Time Systems, June 2000, pp. 35-43; J. Anderson, A. Srinivasan, Early-release fair scheduling, in: Proceedings of the 12th Euromicro Conference on Real-Time Systems, June 2000, pp. 35-43
[2] J. Anderson, A. Srinivasan, Pfair scheduling: Beyond periodic task systems, in: Proceedings of the 7th International Conference on Real-Time Computing Systems and Applications, December 2000, pp. 297-306; J. Anderson, A. Srinivasan, Pfair scheduling: Beyond periodic task systems, in: Proceedings of the 7th International Conference on Real-Time Computing Systems and Applications, December 2000, pp. 297-306
[3] Anderson, J.; Srinivasan, A., Mixed Pfair/ERfair scheduling of asynchronous periodic tasks, J. Comput. System Sci., 68, 1, 157-204 (February 2004)
[4] Baruah, S.; Cohen, N.; Plaxton, C. G.; Varvel, D., Proportionate progress: A notion of fairness in resource allocation, Algorithmica, 15, 6, 600-625 (June 1996)
[5] U. Devi, J. Anderson, Improved conditions for bounded tardiness under EPDF fair multiprocessor scheduling, in: Proceedings of the 12th International Workshop on Parallel and Distributed Real-Time Systems, April 2004, 8 pages (on CD-ROM); U. Devi, J. Anderson, Improved conditions for bounded tardiness under EPDF fair multiprocessor scheduling, in: Proceedings of the 12th International Workshop on Parallel and Distributed Real-Time Systems, April 2004, 8 pages (on CD-ROM)
[6] Devi, U.; Anderson, J., A schedulable utilization bound for the multiprocessor EPDF Pfair algorithm, Real-Time Syst., 38, 3, 237-288 (February 2008)
[7] Jeffay, K.; Goddard, S., A theory of rate-based execution, (Proceedings of the Real-Time Systems Symposium. Proceedings of the Real-Time Systems Symposium, Phoenix, AZ (December 1999), IEEE Computer Society Press), 304-314
[8] Sha, L.; Abdelzaher, T.; Arzen, K.-E.; Cervin, A.; Baker, T.; Burns, A.; Buttazzo, G.; Caccamo, M.; Lehoczky, J.; Mok, A. K., Real time scheduling theory: A historical perspective, Real-Time Syst., 28, 2/3, 101-155 (November/December 2004)
[9] A. Srinivasan, Efficient and Flexible Fair Scheduling of Real-Time Tasks on Multiprocessors, PhD thesis, University of North Carolina at Chapel Hill, December 2003; A. Srinivasan, Efficient and Flexible Fair Scheduling of Real-Time Tasks on Multiprocessors, PhD thesis, University of North Carolina at Chapel Hill, December 2003
[10] A. Srinivasan, J. Anderson, Optimal rate-based scheduling on multiprocessors, in: Proceedings of the 34th ACM Symposium on Theory of Computing, May 2002, pp. 189-198; A. Srinivasan, J. Anderson, Optimal rate-based scheduling on multiprocessors, in: Proceedings of the 34th ACM Symposium on Theory of Computing, May 2002, pp. 189-198 · Zbl 1192.68109
[11] A. Srinivasan, J. Anderson, Efficient scheduling of soft real-time applications on multiprocessors, in: Proceedings of the 15th Euromicro Conference on Real-Time Systems, July 2003, pp. 51-59; A. Srinivasan, J. Anderson, Efficient scheduling of soft real-time applications on multiprocessors, in: Proceedings of the 15th Euromicro Conference on Real-Time Systems, July 2003, pp. 51-59
[12] Srinivasan, A.; Anderson, J., Fair scheduling of dynamic task systems on multiprocessors, J. Syst. Software, 77, 1, 67-80 (April 2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.