TY - GEN
T1 - Testing interval trees for real-time scheduling systems
AU - Hu, Xinfa
AU - Leung, Joseph Y.T.
PY - 2008
Y1 - 2008
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 -