Skip to main content
Log in

On the competitiveness of on-line real-time task scheduling

  • Published:
Real-Time Systems Aims and scope Submit manuscript

Abstract

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 sheduling sporadic task requests in both uni- and multi-processor environments. If a task request is successfuly 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 be 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 and zero laxity.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • 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.

  • 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.

  • Dertouzos, M. 1974. Control robotics: the procedural control of physical processors. In Proceedings of the IFIP Congress, pp. 807–813.

  • 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.

  • Liu, C. and Laylan, J. 1973. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, vol. 20: 46–61.

    Google Scholar 

  • Locke, C.D. 1986. Best-effort Decision Making for Real-Time Scheduling. PhD thesis, Computer Science Department, Carnegie-Mellon University.

  • Sahni, S. 1985. Concepts in Discrete Mathematics. Fridley, Minnesota: Camelot Publishing.

    Google Scholar 

  • 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.

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Baruah, S., Koren, G., Mao, D. et al. On the competitiveness of on-line real-time task scheduling. The Journal of Real-Time Systems 4, 125–144 (1992). https://doi.org/10.1007/BF00365406

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00365406

Keywords

Navigation