Similar articles

Abstract: In hard real-time systems, schedulability analysis is not only one of the important means of guaranteeing the timelines of embedded software but also one of the fundamental theories of applying other new techniques, such as energy savings and fault tolerance. However, most of the existing schedulability analysis methods assume that schedulers use preemptive scheduling or non-preemptive scheduling. In this paper, we present a schedulability analysis method, i.e., the worst-case hybrid scheduling (WCHS) algorithm, which considers the influence of release jitters of transactions and extends schedulability analysis theory to timing analysis of linear transactions under fixed priority hybrid scheduling. To the best of our knowledge, this method is the first one on timing analysis of linear transactions under hybrid scheduling. An example is employed to demonstrate the use of this method. Experiments show that this method has lower computational complexity while keeping correctness, and that hybrid scheduling has little influence on the average worst-case response time (WCRT), but a negative impact on the schedulability of systems.

[1] ARTIST2, 2005. ARTIST2 Roadmap on Real-Time Techniques in Control. Http://www.artist-embedded.org/artist/ARTIST-2-Roadmap-on-Real-Time.html

[2] Audsley, N., Burns, A., Richardson, M., Tindell, K., Wellings, A.J., 1993. Applying new scheduling theory to static priority pre-emptive scheduling. Software Eng. J., 8(5):284-292.

[3] Baruah, S.K., Chakraborty, S., 2006. Schedulability Analysis of Non-Preemptive Recurring Real-Time Tasks. Proc. 20th Int. Parallel and Distributed Processing Symp., p.1-8.

[4] Buttazzo, G.C., 1995. Hard Real-Time Computing Systems. Kluwer, Boston, MA.

[5] Damm, A., Reisinger, W., Schwabl, W., Kopetz, H., 1989. The real-time operating system of MARS. ACM SIGOPS Oper. Syst. Rev., 23(3):141-151.

[6] Dolev, S., Keizelman, A., 1999. Non-preemptive real-time scheduling of multimedia tasks. Real-Time Syst., 17(1):23-39.

[7] Fisher, N., Nguyen, T.H.C., Goossens, J., Richard, P., 2007. Parametric Polynomial-Time Algorithms for Computing Response-Time Bounds for Static-Priority Tasks with Release Jitters. Proc. 13th IEEE Int. Conf. on Embedded and Real-Time Computing Systems and Applications, p.377-385.

[8] Gonzalez Harbour, M., Klein, M.H., Lehoczky, J.P., 1994. Timing analysis for fixed-priority scheduling of hard real-time systems. IEEE Trans. on Software Eng., 20(1):13-28.

[9] Henia, R., Ernst, R., 2005. Context-Aware Scheduling Analysis of Distributed Systems with Tree-Shaped Task-Dependencies. Proc. Design, Automation and Test in Europe, 1:480-485.

[10] Jeffay, K., Stanat, D.F., Martel, C.U., 1991. On Non-Preemptive Scheduling of Periodic and Sporadic Tasks. Proc. IEEE Real-Time Systems Symp., p.129-139.

[11] Jiang, S., 2006. A Decoupled Scheduling Approach for Distributed Real-Time Embedded Automotive Systems. Proc. 12th IEEE Real-Time and Embedded Technology and Applications Symp. p.191-198.

[12] Khil, A., Maeng, S., Cho, J., 1997. Non-preemptive scheduling of real-time periodic tasks with specied release times. IEICE Trans. on Inf. Syst., E80-D(5):562-572.

[13] Lehoczky, J.P., 1990. Fixed Priority Scheduling of Periodic Task Sets with Arbitrary Deadline. Proc. 11th Real-Time Systems Symp., p.201-209.

[14] Liu, C.L., Layland, J., 1973. Scheduling algorithms for multiprogramming in a hard real-time environment. J. ACM, 20(1):46-61.

[15] OSEK, 2003. OSEK/VDX Operating System, Version 2.2.1. Http://www.osek-vdx.org/mirror/os221.pdf

[16] Palencia, J.C., Gonzalez Harbour, M., 1998. Schedulability Analysis for Tasks with Static and Dynamic Offsets. Proc. 19th IEEE Real-Time Systems Symp., p.26-37.

[17] Palencia, J.C., Gonzalez Harbour, M., 1999. Exploiting Precedence Relations in the Schedulability Analysis of Distributed Real-Time Systems. Proc. 20th IEEE Real-Time Systems Symp., p.328-339.

[18] Pillai, P., Shin, K.G., 2001. Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems. Proc. 18th ACM Symp. on Operating Systems Principles, p.89-102.

[19] Redell, O., 2004. Analysis of Tree-Shaped Transactions in Distributed Real Time Systems. Proc. 16th Euromicro Conf. on Real-Time Systems, p.239-248.

[20] Tindell, K.W., 1994. Adding Time-Offsets to Schedulability Analysis. Technical Report YCS 221, Univ. of York.

[21] Wang, L., Wu, Z.H., 2004. Schedulability Test for Fault-Tolerant Hybrid Real-Time Systems with Preemptive and Non-Preemptive Tasks. Proc. 4th Int. Conf. on Computer and Information Technology, p.1169-1174.

[22] Yomsi, P.M., Sorel, Y., 2007. Extending Rate Monotonic Analysis with Exact Cost of Preemptions for Hard Real-Time Systems. Proc. 19th Euromicro Conf. on Real-Time Systems, p.280-290.