Analysis and Research of Two-Level Scheduling Profile for Open Real-Time System

In an open real-time system environment, the coexistence of different kinds of real-time and non real-time applications makes the system scheduling mechanism face new requirements and challenges. One two-level scheduling scheme of the open real-time systems is introduced, and points out that hard and soft real-time applications are scheduled non-distinctively as the same type real-time applications, the Quality of Service (QoS) cannot be guaranteed. It has two flaws: The first, it can not differentiate scheduling priorities of hard and soft real-time applications, that is to say, it neglects characteristic differences between hard real-time applications and soft ones, so it does not suit a more complex real-time environment. The second, the worst case execution time of soft real-time applications cannot be predicted exactly, so it is not worth while to cost much spending in order to assure all soft real-time applications not to miss their deadlines, and doing that may cause resource wasting. In order to solve this problem, a novel two-level real-time scheduling mechanism (including scheduling profile and scheduling algorithm) which adds the process of dealing with soft real-time applications is proposed. Finally, we verify real-time scheduling mechanism from two aspects of theory and experiment. The results indicate that our scheduling mechanism can achieve the following objectives. (1) It can reflect the difference of priority when scheduling hard and soft real-time applications. (2) It can ensure schedulability of hard real-time applications, that is, their rate of missing deadline is 0. (3) The overall rate of missing deadline of soft real-time applications can be less than 1. (4) The deadline of a non-real-time application is not set, whereas the scheduling algorithm that server 0 S uses can avoid the “starvation" of jobs and increase QOS. By doing that, our scheduling mechanism is more compatible with different types of applications and it will be applied more widely.

• Yongxian Jin
• Jingzhou Huang

• Hard real-time
• two-level scheduling profile
• open real-time system
• non-distinctive schedule
• soft real-time

[1] Z.Deng, J.W.S. Liu. Scheduling Real-Time Applications in an Open
Environment. In: Proc. of the 18th IEEE Real-Time Systems
Symposium. IEEE Computer Society, 1997, pp.308-319.
[2] Y.C .Wang, K.J. Lin. Implementing a General Real-Time Scheduling
Framework in the RED-Linux Real-Time Kernel. In: Proc. of the 20th
IEEE Real-Time Systems Symposium. IEEE Computer Society, 1999,
pp. 246-255.
[3] A.K. Parekh. A generalized processor sharing approach to flow control
in integrated services networks [Ph.D. Thesis]. Massachusetts Institute
of Technology,1992.
[4] T.W. Kuo, W.R. Yang, K.J. Lin. EGPS: a class of real-time scheduling
algorithms based on processor sharing. In: Proc. of the 10th Euromicro
Workshop on Real Time Systems. IEEE Computer Society, 1998,
pp.27-34.
[5] L.Abeni, G.Buttazzo. Integrating Multimedia Applications in Hard
Real-Time Systems. In: Proc. of the 19th IEEE Real-Time Systems
Symposium(RTSS-98). IEEE Computer Society,1998, pp. 4-13.
[6] L.Abeni, G.Buttazzo. Resource Reservation in Dynamic Real-Time
Systems. Real-Time Systems,2004,27: pp.123-167.
[7] G.Lipari, S.Baruah. A Hierarchical Extension to the Constant
Bandwidth Server Framework. In: Proc. of the 7th IEEE Real Time
Technology and Applications Symposium.IEEE Computer Society,
2001, pp. 26-35.
[8] A. Marchand, M. Silly-Chetto. Dynamic Real-time Scheduling of Firm
Periodic Tasks with Hard and Soft Aperiodic Tasks. Real-Time
Systems,2006,32(1-2): pp.21-47.
[9] W.Li, K.Kavi,R.Akl. A non-preemptive scheduling algorithm for soft
real-time systems. Computers and Electrical Engineering,2007,33(1):
pp.12-29.
[10] U.C. Devi, J.H.Anderson. Tardiness bounds under global EDF
scheduling on a multiprocessor. Real-Time System,2008,38(2):
pp.133-189.
[11] G.Lipai, J.Carpenter, S.Baruah. A Framework for Achieving
Inter-Application Isolation in Multiprogrammed Hard Real-Time
Environments. In: Proc. of the 21st IEEE Real-Time Systems
Symposium. IEEE Computer Society, 2000, pp. 217-226.
[12] Y.C. Gong, L.G. Wang, et al. A Hybrid Real-Time Scheduling
Algorithm Based on Rigorously Proportional Dispatching of Serving.
Journal of Software, 2006,17(3): pp. 611-619. (in Chinese)
[13] X.Y.Huai, Y.Zou, M.S.Li. An Open Adaptive Scheduling Algorithm
for Open Hybrid Real-Time Systems. Journal of Software, 2004,15(4):
pp. 487-496. (in Chinese)
[14] P.L. Tan, H.Jin, M.H. Zhang. Two-Dimensional Priority Real-Time
Scheduling for Open Systems. Acta Electronica Sinica, 2006, 34(1): pp.
1773-1777. (in Chinese)
[15] B.B. Brandenburg, J.H. Anderson. Integrating Hard/Soft Real-Time
Tasks and Best-Effort Jobs on Multiprocessors. In: Proceedings of the
19th Euromicro Conference on Real-Time Systems. IEEE Computer
Society,2007, pp. 61-70.
[16] Y.Zou, M.S. Li, Q.Wang. Analysis for Scheduling Theory and
Approach of Open Real-Time System. Journal of Software, 2003,14(1):
pp. 83-90. (in Chinese)
[17] Z.Deng, J.W.S. Liu, J.Sun. A Scheme for Scheduling Hard-Real-Time
Applications in Open Environment. In: Proc. of the 9th Euromicro
Workshop on Real-Time Systems. IEEE Computer Society Press, 1997,
pp.191-199.
[18] Y.X.Jin, J.Z.Huang, J.G.Wang. Scheduling for Non-Real Time
Applications of ORTS Based on Two-Level Scheduling Scheme. To
appear in: International Journal of Computer Theory and Engineering,
2009, 1(2): pp.170-180.
[19] C.L.Liu, J.W.Layland. Scheduling Algorithms for Multiprogramming
in a Hard Real-Time Environment. Journal of the ACM, 1973, 20(11):
pp. 46-61.