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

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.

Authors:

• Vahid Salmani
• Saman Taghavi Zargar
• Mahmoud Naghibzadeh

Keywords:

• Modified maximum urgency first
• maximum urgency first
• real-time systems
• scheduling.

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.