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

Authors: Yongxian Jin, Jingzhou Huang

Abstract:

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.

Keywords: Hard real-time, two-level scheduling profile, open real-time system, non-distinctive schedule, soft real-time

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1062298

References:

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