A Review of Sufficient Schedulability Analysis for Fixed Priority Scheduling Systems

Abstract:

This papercarries out a survey of sufficient schedulability analysis forfixed priority (FP) scheduling. The most common used fixed priority assignment is the rate monotonic (RM) algorithm, according to its policy, the task priorities are ordered based on their activation rates, so that the task with the shortest period is assigned the highest priority. However, when each task’s relative deadline is not equal to its period, the RM algorithm is not suitable to assign the task priorities. When relative deadlines are less than or equal to periods,the deadline monotonic (DM) algorithm can be deployed to schedule the tasks. The utilization based schedulability analysis has the advantage of simple implementation, and manyexisting schedulability analyses on uniprocessor are covered.

• Periodical: Applied Mechanics and Materials (Volume 741)
• Pages: 856-859
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.741.856
• Online since: March 2015
• Authors: Yan Feng Zhai*, Feng Xiang Zhang
• Keywords: Deadline Monotonic, Fixed Priority, Rate Monotonic, Schedulability Analysis, Scheduling

References

[1] C. L. Liu and J. W. Layland, Scheduling algorithms for multiprogramming in a hard real-time environment, Journal of the ACM, vo l. 20, no. 1, p.40–61, (1973).

DOI: 10.1145/321738.321743

[2] D. Chen, A. K. Mok, and T. -W. Kuo, Utilization bound re-visited, in Proceedings of the 6th Real-Time Computing Systems and Applications, 1999, p.295–302.

DOI: 10.1109/rtcsa.1999.811259

[3] D. Park, S. Natarajan, and M. J. Kim, A generalized utilization bound test for fixed-priority real-time scheduling, in Proceedings of the 2nd International Workshop on Real-Time Systems and Applications, October 1995, p.73–76.

DOI: 10.1109/rtcsa.1995.528754

[4] E. Bini, G. C. Buttazzo, and G. M. Buttazzo, A hyperbolic bound for the rate monotonic algorithm, in IEEE Proc. of the 13th Euromicro Conf. on Real-Time Systems, June (2001).

DOI: 10.1109/emrts.2001.934000

[5] E. Bini, G. C. Buttazzo, and G. M. Buttazzo, Rate monotonic scheduling: The hyperbolic bound, IEEE Transactions on Computers, vol. 52, no. 7, p.933–942, July (2003).

DOI: 10.1109/tc.2003.1214341

[6] H. Liu and X. Hu, Efficient performance estimation for general realtime task systems, in IEEE/ACM International Conference on Computer Aided Design, 2001, p.464–471.

DOI: 10.1109/iccad.2001.968681

[7] J. P. Lehoczky, L. Sha, and Y. Ding, The rate-monotonic scheduling algorithm: Exact characterization and average case behavior, in Proceedings of the 10th IEEE Real-Time Systems Symposium, 1989, p.166–172.

DOI: 10.1109/real.1989.63567

[8] J. W. S. Liu, Real-Time Systems. Prentice Hall, (2000).

[9] J. Y. -T. Leung and J. Whitehead, On the complexity of fixed-priority scheduling of periodic, real-time tasks, Performance Evaluation, vol. 2, p.237–250, (1982).

DOI: 10.1016/0166-5316(82)90024-4

[10] L. Sha, R. Rajkumar, and J. P. Lehoczky, Priority inheritance protocols: An approach to real-time synchronization, IEEE Transactions on Computers, vol. 39, no. 9, p.1175–1185, (1990).

DOI: 10.1109/12.57058

[11] T. -W. Kuo and A. K. Mok, Load adjustment in adaptive real-time systems, in Proceedings of the IEEE Real-Time Systems Symposium, December (1991).

DOI: 10.1109/real.1991.160369