Novel algorithms for open-loop and closed-loop scheduling of real-time tasks in multiprocessor systems based on execution time estimation

R. Al-Omari, G. Manimaran, M. V. Salapaka, Arun K. Somani

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

Most dynamic real-time scheduling algorithms are open-loop in nature meaning that they do not dynamically adjust their behavior using the performance at run-time. When accurate workload models are not available, such a scheduling can result in a highly underutilized system based on an extremely pessimistic estimation of workload. In recent years, "closed-loop" scheduling is gaining importance due to its applicability to many real-world problems wherein the feedback information can be exploited efficiently to adjust system parameters, thereby improving the performance. In this paper, we first propose an open-loop dynamic scheduling algorithm that employs overlap in order to provide flexibility in task execution times. Secondly, we propose a novel closed-loop approach for dynamically estimating the execution time of tasks based on both deadline miss ratio and task rejection ratio. This approach is highly preferable for firm real-time systems since it provides a firm performance guarantee. We evaluate the performance of the open-loop and the closed-loop approaches by simulation and modeling. Our studies show that the closed-loop scheduling offers a significantly better performance (20% gain) over the open-loop scheduling under all the relevant conditions we simulated.

Original languageEnglish (US)
Title of host publicationProceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)0769519261, 9780769519265
DOIs
StatePublished - Jan 1 2003
EventInternational Parallel and Distributed Processing Symposium, IPDPS 2003 - Nice, France
Duration: Apr 22 2003Apr 26 2003

Publication series

NameProceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003

Other

OtherInternational Parallel and Distributed Processing Symposium, IPDPS 2003
CountryFrance
CityNice
Period4/22/034/26/03

Keywords

  • Closed-loop scheduling
  • Feedback control
  • Modeling
  • Multiprocessor systems
  • Openloop scheduling
  • Real-time scheduling

Fingerprint Dive into the research topics of 'Novel algorithms for open-loop and closed-loop scheduling of real-time tasks in multiprocessor systems based on execution time estimation'. Together they form a unique fingerprint.

Cite this