×

On the competitiveness of on-line real-time task scheduling. (English) Zbl 0766.68011

Summary: With respect to on-line scheduling algorithms that must direct the service of sporadic task requests we quantify the benefit of clairvoyancy, i.e., the power of possessing knowledge of various task parameters of future events. Specifically, we consider the problem of preemptively scheduling sporadic task requests in both uni- and multi- processor environments. If a task request is successfully scheduled to completion, a value equal to the task’s execution time is obtained; otherwise no value is obtained. We prove that no on-line scheduling algorithm can guarantee a cumulative value greater than 1/4th the value obtainable by a clairvoyant scheduler; i.e., we prove a 1/4th upper bound on the competitive factor of on-line real-time schedulers. We present an online uniprocessor scheduling algorithm \(TD_ 1\) that actually has a competitive factor of 1/4; this bound is thus shown to ge tight. We further consider the effect of restricting the amount of overloading permitted (the loading factor), and quantify the relationship between the loading factor and the upper bound on the competitive factor. Other results of a similar nature deal with the effect of value densities (measuring the importance of type of a task). Generalizations to dual- processor on-line scheduling are also considered. For the dual-processor case, we prove an upper bound of 1/2 on the competitive factor. This bound is shown to be tight in the special case when all the tasks have the same density of zero laxity.

MSC:

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

References:

[1] Baruah, S., Koren, G., Mishra, B., Raghunathan, A., Rosier, L. and Shasha, D. 1991. On-line scheduling in the presence of overload. 1991 IEEE Symposium on Foundations of Computer Science. San Juan, Puerto Rico, October 2-4.
[2] Baruah, S., Mok, A. and Rosier, L. 1990. The preemptive scheduling of sporadic, real-time tasks on one processor. In Eleventh Real-Time Systems Symposium, pp. 182-190, Orlando, Florida.
[3] Dertouzos, M. 1974. Control robotics: the procedural control of physical processors. In Proceedings of the IFIP Congress, pp. 807-813.
[4] Koren, G. and Shasha, D. 1991. An Optimal Scheduling Algorithm with a Competitive Factor for Real-Time Systems. Technical Report 572, Computer Science Department, New York University. · Zbl 0834.68037
[5] Liu, C. and Laylan, J. 1973. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, vol. 20: 46-61. · Zbl 0265.68013
[6] Locke, C.D. 1986. Best-effort Decision Making for Real-Time Scheduling. PhD thesis, Computer Science Department, Carnegie-Mellon University.
[7] Sahni, S. 1985. Concepts in Discrete Mathematics. Fridley, Minnesota: Camelot Publishing. · Zbl 0606.65094
[8] Wang. F. and Mao, D. 1991. Worst Case Analysis for On-Line Scheduling in Real-Time Systems. Technical Report 91-54, Department of Computer and Information Science, University of Massachusetts at Amberst.
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.