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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:57256", author = "Vahid Salmani and Saman Taghavi Zargar and Mahmoud Naghibzadeh", title = "A Modified Maximum Urgency First Scheduling Algorithm for Real-Time Tasks", 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.", volume = "1", number = "9", pages = "2746-5", }