Full Text:   <1641>

CLC number: TP316

On-line Access: 2008-05-05

Received: 2007-07-26

Revision Accepted: 2008-01-30

Crosschecked: 0000-00-00

Cited: 1

Clicked: 3320

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2008 Vol.9 No.6 P.776~785


Schedulability analysis for linear transactions under fixed priority hybrid scheduling

Author(s):  Zhi-gang GAO, Zhao-hui WU

Affiliation(s):  School of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China

Corresponding email(s):   gaozhigang@zju.edu.cn

Key Words:  Real-time systems, Hybrid scheduling, Linear transactions, Worst-case response time (WCRT), Schedulability analysis

Zhi-gang GAO, Zhao-hui WU. Schedulability analysis for linear transactions under fixed priority hybrid scheduling[J]. Journal of Zhejiang University Science A, 2008, 9(6): 776~785.

@article{title="Schedulability analysis for linear transactions under fixed priority hybrid scheduling",
author="Zhi-gang GAO, Zhao-hui WU",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Schedulability analysis for linear transactions under fixed priority hybrid scheduling
%A Zhi-gang GAO
%A Zhao-hui WU
%J Journal of Zhejiang University SCIENCE A
%V 9
%N 6
%P 776~785
%@ 1673-565X
%D 2008
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.A071411

T1 - Schedulability analysis for linear transactions under fixed priority hybrid scheduling
A1 - Zhi-gang GAO
A1 - Zhao-hui WU
J0 - Journal of Zhejiang University Science A
VL - 9
IS - 6
SP - 776
EP - 785
%@ 1673-565X
Y1 - 2008
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.A071411

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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[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.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE