Behaviors of real-time schedulers under resource modification and a steady scheme with bounded utilization

In this article we present an analysis for task models having random resource needs and different arrival patterns. In hard real-time environments like avionic systems or nuclear reactors, the inputs to the system are obtained from real world by using sensors. And it is highly possible for a task to have different resource needs for each period according to these changing conditions of real world. We made an analysis of schedulers for task models having random resources in each period. Since feasibility tests for usual task models are just limited to some specific schedulers and arrival patterns, we made our analysis using different preemptive schedulers with different arrival patterns. Another issue that this paper presents is that for task sets having processor utilization factors of below 100%, a new scheduler assigns more resource values to the tasks than they originally have by extending and shrinking the resource values. This provides a better utilization of the resources as well as providing all the tasks to finish in their timing constraints and never assigning lower resource values than the initial resources for all tasks. We exposed a dynamic priority driven scheduling scheme that implements the newly developed Steady Scheme with Bounded Utilization for changing resources and simulated to reach the results depicted.

Anahtar Kelimeler:

Scheduling, real-time scheduler, task arrival patterns, simulation, dynamic priority, random resource, resource modification

Behaviors of real-time schedulers under resource modification and a steady scheme with bounded utilization

Keywords:

Scheduling, real-time scheduler, task arrival patterns, simulation, dynamic priority, random resource, resource modification,

PDF

___

D. Stewart, P. Khosla, Real-Time Scheduling of Sensor-Based Control Systems in Real-Time Programming, Ed. by W. Halang and K. Ramamritham, Tarrytown, New York, Pergamon Press Inc., 1992.
P. Marti, R. Villa, J. M. Fuertes, G.. Fohler, “On real-time control tasks schedulability”, 2001.
E. Bini, G. C. Buttazzo, “Schedulability analysis of periodic Şxed priority systems”, IEEE Transact ı ons on Computers, Vol. 53, No. 11, pp. 1462–1473, 2004.
K. Albers, F. Slomka, “Eﬃcient feasibility analysis for real-time systems with EDF scheduling”, Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE’05), IEEE Computer Society, 2005.
P. M. Alvarez, H. Aydin, D. Mosse, R. Melhem, “Scheduling optional computations in fault-tolerant real-time systems”, Proceedings of the Seventh International Conference on Real-Time Computing Systems and Applications, pp. 323, 2000.
R. Samet, “Fault-tolerant procedures for redundant computer systems”. Int. J. Quality and Reliability Engineering International, Vol. 25, pp. 41–69, 2009.
C. Han, K. G. Shin, J. Wu, “A fault-tolerant scheduling algorithm for real-time periodic tasks with possible software faults”, IEEE Transactions on Computers, Vol. 52, No. 3, pp. 362–372, 2003. [8] G. Manimaran, C. S. R. Murthy, “A fault-tolerant dynamic scheduling algorithm for multiprocessor real-time systems and its analysis,” IEEE Transactions on Parallel and Distributed Systems, Vol. 9, No. 11, pp. 1137–1152, 1998.
G. M. A. Lima, A. Burns, “An optimal Şxed-priority assignment algorithm for supporting fault-tolerant hard real-time systems,” IEEE Transactions on Computers, Vol. 52, No. 10, pp.1332–1346, 2003.
J. Locke, “Designing real-time systems,” In IEEE International Conference of Real-Time Computing Systems and Applications (RTCSA ’97), Taiwan (Invited talk), 1997.
C. L. Liu, J. W. Layland, “Scheduling algorithms for multiprogramming in a hard real-time environment”, Journal of the association for computing machinery, Vol. 20, No. 1, pp. 46–61, 1973. [12] J. L. Lehoczky, et al. “The rate monotonic scheduling algorithm: Exact characterization and average case behavior,” In Proceedings 10thIEEE Real-Time Systems Symposium, Santa Monica, CA, pp. 166–171, 1989.
S. Lauzac, R. Melhem, D. Mosse, “An improved rate-monotonic admission control and its applications”. IEEE Transactions on Computers, Vol. 52 (3), 2003.
Y. Chen, G. Xiong, “Imprecise computation fault-tolerant rate-monotonic scheduling”. Computer Science and Engineering College Proceedings of the Fifth International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP’02) IEEE, 2002.
S. H. Oh, S. M. Yang, “A modiŞed least-laxity-Şrst scheduling algorithm for real-time tasks,” Proceedings of the Fifth International Conference on Real-Time Computing Systems and Applications, pp. 31–36, 1998.
W. Zhang, S. Teng, Z. Zhu, X. Fu, H. Zhu, “An improved least-laxity-Şrst scheduling algorithm of variable time slice for periodic tasks”, Proc. 6th IEEE Int. Conf. on Cognitive Informatics (ICCIO07), IEEE, 2007.
J. Y. T. Leung, M. L. Merril, “A note on preemptive scheduling of periodic”, Real-Time Tasks Information processing Letters, Vol. 11, 1980.
S. K. Baruah, A. K. Mok, A. K. Rosier, “Preemptively scheduling hard real-time sporadic tasks on one processor”, Proceedings of the 11th Real-Time Systems Symposium, pp. 182–190, 1990. [19] J. Goossens, C. Macq, “Limitation of the hyper-period in real-time periodic task set generation,” 9th Conference RTS embedded systems, pp. 133-148, 2001.
G. Buttazzo, “Rate monotonic vs. EDF: Judgment day real-time systems,” Vol. 29, pp. 5–26, 2005.
L. George, N. Rivierre, M. Spuri, “Preemptive and non-preemptive real-time uniprocessor scheduling,” INRIA Research Report, 2966, 1996.