iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/BF01553887
A new algorithm for scheduling periodic, real-time tasks | Algorithmica Skip to main content
Springer Nature Link
Log in

A new algorithm for scheduling periodic, real-time tasks

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We consider the problem of preemptively scheduling a set of periodic, real-time tasks on a multiprocessor computer system. We give a new scheduling algorithm, the so-called Slack-Time Algorithm, and show that it is more effective than the known Deadline Algorithm. We also give an (exponential-time) algorithm to decide if a task system is schedulable by the Slack-Time or the Deadline Algorithm. The same algorithm can also be used to decide if a task system is schedulable by any given fixed-priority scheduling algorithm. This resolves an open question posed by Leung and Whitehead. Finally, it is shown that the problem of deciding if a task system is schedulable by the Slack-Time, the Deadline, or any given fixed-priority scheduling algorithm is co-NP-hard for each fixedm≥.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

  1. E. G. Coffman, Jr. and P. J. Denning,Operating Systems Theory, Prentice-Hall, Englewood Cliffs, NJ, 1973.

    Google Scholar 

  2. S. K. Dhall and C. L. Liu, On a Real-Time Scheduling Problem,Operations Research, Vol. 26, No. 1, 1978, pp. 127–140.

    Article  MATH  MathSciNet  Google Scholar 

  3. J. Labetoulle, Some Theorems on Real Time Scheduling, inComputer Architecture and Networks, E. Gelenbe and R. Mahl (eds.), North-Holland, Amsterdam, 1974, pp. 285–293.

    Google Scholar 

  4. E. L. Lawler and C. U. Martel, Scheduling Periodically Occurring Tasks on Multiple Processors,Information Processing Letters, Vol. 12, No. 1, 1981, pp. 9–12.

    Article  MATH  MathSciNet  Google Scholar 

  5. J. Y.-T. Leung and M. L. Merrill, A Note on Preemptive Scheduling of Periodic, Real-Time Tasks,Information Processing Letters, Vol. 11, No. 3, 1980, pp. 115–118.

    Article  MATH  MathSciNet  Google Scholar 

  6. J. Y.-T. Leung and J. Whitehead, On the Complexity of Fixed-Priority Scheduling of Periodic, Real-Time Tasks,Performance Evaluation, Vol. 2, 1982, pp. 237–250.

    Article  MATH  MathSciNet  Google Scholar 

  7. C. L. Liu and J. W. Layland, Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment,Journal of the ACM, Vol. 20, No. 1, 1973, pp. 46–61.

    Article  MATH  MathSciNet  Google Scholar 

  8. O. Serlin, Scheduling of Time Critical Processes,Proceedings of the Spring Joint Computer Conference, 1972, pp. 925–932.

Download references

Author information

Authors and Affiliations

  1. Computer Science Program, University of Texas at Dallas, 75080, Richardson, TX, USA

    Joseph Y. -T. Leung

Authors
  1. Joseph Y. -T. Leung
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by C. L. Liu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Leung, J.Y.T. A new algorithm for scheduling periodic, real-time tasks. Algorithmica 4, 209–219 (1989). https://doi.org/10.1007/BF01553887

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Key words

Search

Navigation