TY - GEN

T1 - Testing interval trees for real-time scheduling systems

AU - Hu, Xinfa

AU - Leung, Joseph Y.T.

PY - 2008/10/15

Y1 - 2008/10/15

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

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

UR - http://www.scopus.com/inward/record.url?scp=53549120230&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=53549120230&partnerID=8YFLogxK

U2 - 10.1109/RTCSA.2008.35

DO - 10.1109/RTCSA.2008.35

M3 - Conference contribution

AN - SCOPUS:53549120230

SN - 9780769533490

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

SP - 327

EP - 336

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

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

Y2 - 25 August 2008 through 27 August 2008

ER -