Testing interval trees for real-time scheduling systems

Xinfa Hu, Joseph Y.T. Leung

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

1 Scopus citations

Abstract

In real-time systems, the efficiency of scheduling modules (SM) is of critical importance. While efficient algorithms result in efficient SMs, this will not occur without appropriate implementations of the algorithms. Moreover, an algorithm with good implementation could further improve the efficiency of the SM. Therefore, creative implementations of algorithms are well worthy of exploring. In this paper, we propose novel data structures (i.e., testing interval trees (TIT)) to help build efficient algorithms for schedulability test and admission control in some real-time SMs. With the testing interval tree for vacancy analysis (TIT-V), the complexities of the schedulability tests in a class of parallel/distributed real-time systems can be effectively reduced from O(m2nlogn) to O(mlogn+mlogm) (where m is the number of processors, and n is the number of tasks). Similarly, with the testing interval tree for release time and laxity analysis (TIT-RL), the complexity of the online admission control in a uni-processor based real-time system can be reduced from O(n2) to O(nlogn) (where n is the number of tasks). Furthermore, the TIT-RL tree can also be applied to a class of parallel/distributed real-time systems. Therefore, the TIT trees are effective approaches to building efficient real-time SMs.

Original languageEnglish (US)
Title of host publicationProceedings - 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2008
Pages327-336
Number of pages10
DOIs
StatePublished - Oct 15 2008
Event14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2008 - Kaohsiung, Taiwan, Province of China
Duration: Aug 25 2008Aug 27 2008

Publication series

NameProceedings - 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2008

Other

Other14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2008
CountryTaiwan, Province of China
CityKaohsiung
Period8/25/088/27/08

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Hardware and Architecture
  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Testing interval trees for real-time scheduling systems'. Together they form a unique fingerprint.

Cite this