A Modified Maximum Urgency First Scheduling Algorithm for Real-Time Tasks

Authors: Vahid Salmani, Saman Taghavi Zargar, Mahmoud Naghibzadeh

Abstract:

This paper presents a modified version of the maximum urgency first scheduling algorithm. The maximum urgency algorithm combines the advantages of fixed and dynamic scheduling to provide the dynamically changing systems with flexible scheduling. This algorithm, however, has a major shortcoming due to its scheduling mechanism which may cause a critical task to fail. The modified maximum urgency first scheduling algorithm resolves the mentioned problem. In this paper, we propose two possible implementations for this algorithm by using either earliest deadline first or modified least laxity first algorithms for calculating the dynamic priorities. These two approaches are compared together by simulating the two algorithms. The earliest deadline first algorithm as the preferred implementation is then recommended. Afterwards, we make a comparison between our proposed algorithm and maximum urgency first algorithm using simulation and results are presented. It is shown that modified maximum urgency first is superior to maximum urgency first, since it usually has less task preemption and hence, less related overhead. It also leads to less failed non-critical tasks in overloaded situations.

Keywords: Modified maximum urgency first, maximum urgency first, real-time systems, scheduling.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1070399

References:

[1] C. L. Liu, and 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. 44-61, January 1973.
[2] D. B. Stewart, and P. k. Khosla, "Real-Time Scheduling of Dynamically Reconfigurable Systems," in Proc. IEEE International Conference on Systems Engineering, Dayton Ohio, August 1991, pp. 139-142.
[3] A. Mok. "Fundamental Design Problems of Distributed Systems for Hard Real-time Environments". PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, 1983.
[4] S. H. Oh, and S. M. Yang, "A Modified Least-Laxity-First Scheduling Algorithm for Real-Time Tasks", in Proc. Fifth International Conference on Real-Time Computing Systems and Applications, October 1998, pp. 31-36
[5] D. B. Stewart, D. E. Schmitz, and P. K. Khosla, "Implementing Real- Time Robotic Systems using CHIMERA II," in Proc. IEEE International Conference on Robotics and Automation, Cincinnati, OH, May 1990, pp. 598-603.
[6] D. B. Stewart, and P. k. Khosla , "Real-Time Scheduling of Sensor- Based Control Systems", in Proc. Eighth IEEE Workshop on Real-Time Operating Systems and Software, in conjunction with 17th IFAC/IFIP Workshop on Real-Time Programming, Atlanta, GA, May 1991, pp. 144-150.
[7] J. Goossens, and P. Richard, "Overview of real-time scheduling problems", in Proc. the ninth international workshop on project management and scheduling, Nancy, France, April 2004.
[8] L. Sha, J. P. Lehoczky, and R. Rajkumar, "Solutions for Some Practical Problems in Prioritized Preemtive Scheduling," in Proc. 10th IEEE Real-Time Systems Symposium, Santa Monica, CA, December 1989.
[9] M. Naghibzadeh, M. Fathi, "Intelligent Rate-Monotonic Scheduling Algorithm for Real-Time Systems", Kuwait Journal of Science and Engineering, vol. 30, no. 2, pp. 197-210, 2003.
[10] M. L. Dertouzos. "Control robotics: The procedural control of physical processes", in Proc. the IFIP Congress, 1974, pp. 807-813.
[11] M. Naghibzadeh, "A modified Version of Rate-Monotonic Scheduling Algorithm and its efficiency Assessment", in Proc. Seventh IEEE International Workshop on Object-Oriented Real-time Dependable Systems, San Diego, January 2002.