Abstract
The development of ubiquitous intelligent has increased the real-time requirements for computing system. If one real-time computation does not complete before its deadline, it is as worse as that the computation is never executed at all. Ineffective computation not only wastes computational resources, but also might bring system overload and collapse. Hence, a schedulability test is necessary to ensure the stability of ubiquitous system. The schedulability test is concerned with determining whether a set of tasks is schedulable on a cluster. Although a number of schedulability tests have been developed, they can not be compared due to distinct test principles. In this paper, we propose a reliability indicator, through which the probability that a random task set succeeds in schedulability test can be evaluated. The larger the probability is, the better the test is. The reliability of two sufficient deadline monotonic tests are compared, and the comparison result is further validated by detailed experiments. Both analysis and experimental results show that the performance discrepancy of schedulability test is determined by a prerequisite pattern. Since this pattern can be deduce by reliability indicator, it may help system designers choose a good schedulability test in advance.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Nguyen, T.-M.-H., Magoulès, F.: Autonomic data management system in grid environment. Journal of Algorithms and Computational Technologies 3, 155–178 (2009)
Yu, L., Magoulès, F.: Service scheduling and rescheduling in an applications integration framework. Advances in Engineering Software 40(9), 941–946 (2009)
Masrur, A., Chakraborty, S., Färber, G.: Constant-time admission control for deadline monotonic tasks. In: Proceedings of the Conference on Design, Automation and Test in Europe (DATE), pp. 220–225 (2010)
Liu, C.L., Layland, J.W.: Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the Association for Computing Machinery 20(1), 46–61 (1973)
Peng, D.-T., Shin, K.G.: A new performance measure for scheduling independent real-time tasks. Journal of Parallel Distributed Computing 19, 11–26 (1993)
Bini, E., Buttazzo, G.C., Buttazzo, G.: Rate monotonic analysis: The hyperbolic bound. IEEE Transactions on Computers 52(7), 933–942 (2003)
Abdelzaher, T.F., Sharma, V., Lu, C.: A utilization bound for aperiodic tasks and priority driven scheduling. IEEE Transactions on Computers 53(3), 334–350 (2004)
Leung, J.Y.T., Whitehead, J.: On the complexity of fixed-priority scheduling of periodic, real-time tasks. Performance Evaluation 2, 237–250 (1982)
Buttazzo, G.C.: Rate monotonic vs. edf: judgment day. Real-Time Systems 29, 5–26 (2005)
Joseph, M., Pandya, P.K.: Finding response times in a real-time system. The Computer Journal 29, 390–395 (1986)
Audsley, N., Burns, A., Richardson, M., Tindell, K., Wellings, A.J.: Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal 8, 284–292 (1993)
Lehoczky, J.P.: Fixed priority scheduling of periodic task sets with arbitrary deadlines. In: Proceedings of the 11th Real-Time Systems Symposium, pp. 201–209 (1990)
Sjodin, M., Hansson, H.: Improved response-time analysis calculations. In: Proceedings of IEEE Real-Time Systems Symposium, pp. 399–408 (1998)
Abdelzaher, T.F., Lu, C.: Schedulability analysis and utilization bounds for highly scalable real-time service. In: Proceedings of IEEE Real Time Technology and Applications Symposium, pp. 15–25 (2001)
Chen, D., Mok, A.K., Kuo, T.-W.: Utilization bound revisited. IEEE Transactions on Computers 52, 351–361 (2003)
Bini, E., Buttazzo, G.C.: Schedulability analysis of periodic fixed priority systems. IEEE Transactions on Computers 53(11), 1462–1473 (2004)
Fisher, N., Baruah, S.K.: A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with bounded relative deadlines. Journal of Embedded Computing 2(3-4), 291–299 (2006)
Teng, F., Yu, L., Magoules, F.: SimMapReduce: a simulator for modeling MapReduce framework. In: Proceedings of International Conference on Multimedia and Ubiquitous Engineering, Loutraki, Greece, pp. 277–282 (June 2011)
Bini, E., Buttazzo, G.C.: Measuring the performance of schedulability tests. Real-Time Systems 30(1-2), 129–154 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Teng, F., Yu, L., Magoulès, F. (2011). Reliability Comparison of Schedulability Test in Ubiquitous Computing. In: Hsu, CH., Yang, L.T., Ma, J., Zhu, C. (eds) Ubiquitous Intelligence and Computing. UIC 2011. Lecture Notes in Computer Science, vol 6905. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23641-9_44
Download citation
DOI: https://doi.org/10.1007/978-3-642-23641-9_44
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-23640-2
Online ISBN: 978-3-642-23641-9
eBook Packages: Computer ScienceComputer Science (R0)