A group priority earliest deadline first scheduling algorithm

doi:10.1007/s11704-012-1104-4

Front Comput Sci

0, Vol.

Issue () : 560-567 https://doi.org/10.1007/s11704-012-1104-4

A group priority earliest deadline first scheduling algorithm

Qi LI¹(

), Wei BA²

1. School of Control Science and Engineering, Dalian University of Technology, Dalian 116024, China; 2. Science and Technology on Underwater Test and Control Laboratory, Dalian 116013, China

Download: PDF(421 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

In most priority scheduling algorithms, the number of priority levels is assumed to be unlimited. However, if a task set requires more priority levels than the system can support, several jobs must in practice be assigned the same priority level. To solve this problem, a novel group priority earliest deadline first (GPEDF) scheduling algorithm is presented. In this algorithm, a schedulability test is given to form a job group, in which the jobs can arbitrarily change their order without reducing the schedulability. We consider jobs in the group having the same priority level and use shortest job first (SJF) to schedule the jobs in the group to improve the performance of the system. Compared with earliest deadline first (EDF), best effort (BE), and group-EDF (gEDF), simulation results show that the new algorithm exhibits the least switching, the shortest average response time, and the fewest required priority levels. It also has a higher success ratio than both EDF and gEDF.

Keywords real-time system group priority success ratio switching

Corresponding Author(s): LI Qi,Email:qili@dlut.edu.cn

Issue Date: 01 October 2012

Cite this article:

Qi LI,Wei BA. A group priority earliest deadline first scheduling algorithm[J]. Front Comput Sci, 0, (): 560-567.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-012-1104-4
https://academic.hep.com.cn/fcs/EN/Y0/V/I/560

1	Ba W, Zhang D B, Li Q, Wang W. The partitioned scheduling of sporadic task systems on heterogeneous multiprocessors. ICIC Express Letters , 2010, 4(4): 1325-1330
2	Li Y J, Yang Y H, Zhou L, Zhu R B. Observations on using problemspecific genetic algorithm for multiprocessor real-time task scheduling. International Journal of Innovative Computing, Information and Control , 2009, 5(9): 2531-2540
3	Lin J F. Performance analysis and discussion on a heuristic approach for scheduling multiprocessor tasks in a grid computing environment. International Journal of Innovative Computing, Information and Control , 2010, 6(12): 5451-5462
4	TimeSys Corporation. The concise handbook of Linux for embedded real-time systems version 1.1 . 2002, http://www.timesys.com
5	Bidoki A, Yazdani N, Azhari S V. A logarithmic scheduling algorithm for high speed input-queued switches. Computer Communications , 2008, 31(1): 5-18 doi: 10.1016/j.comcom.2007.09.015
6	Erbas C, Pimentel A D, Cerav-Erbas S. Static priority scheduling of event-triggered real-time embedded systems. Formal Methods in System Design , 2007, 30(1): 29-47 doi: 10.1007/s10703-006-0021-2
7	LamS S, Xie G G. Group priority scheduling. IEEE/ACMTransactions on Networking , 1997, 5(2): 205-218 doi: 10.1109/90.588083
8	Cayssials R, Orozco J, Santos J, Santos R. Rate monotonic scheduling of real-time control systems with the minimum number of priority levels. In: Proceedings of the 11th Euromicro Conference on Real Time Systems . 1999, 54-59 doi: 10.1109/EMRTS.1999.777450
9	Liu C L, Layland J W. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM , 1973, 20(1): 46-61 doi: 10.1145/321738.321743
10	Bin X L, Yang Y H, Jin S Y. Optimal fixed priority assignment with limited priority levels. In: Proceedings of the 5th International Workshop on Advanced Parallel Programming Technologies. 2003, 194-203
11	Katcher D I, Sathaye S S, Strosnider J K. Fixed priority scheduling with limited priority levels. IEEE Transactions on Computers , 1995, 44(9): 1140-1144 doi: 10.1109/12.464392
12	Cao H J, Jin H, Wu X X, Wu S, Shi X H. DAGMap: efficient and dependable scheduling of DAG workflow job in Grid. Journal of Supercomputing , 2010, 51(2): 201-223 doi: 10.1007/s11227-009-0284-7
13	Hansen J P, Zhu H, Lehoczky J P, Rajkumar R. Quantized EDF scheduling in a stochastic environment. In: Proceedings of the 16th International Parallel and Distributed Processing Symposium . 2002, 94-100 doi: 10.1109/IPDPS.2002.1016476
14	Shin C S, Kang M S, Jeong C W, Joo S C. TMO-based object group framework for supporting distributed object management and real-time services. In: Proceedings of the 5th International Workshop on Advanced Parallel Programming Technologies . 2003, 525-535
15	Li W M, Kavi K, Akl R. A non-preemptive scheduling algorithm for soft real-time systems. Computers & Electrical Engineering , 2007, 33(1): 12-29 doi: 10.1016/j.compeleceng.2006.04.002
16	Jeffay K, Stanat D F, Martel C U. On non-preemptive scheduling of periodic and sporadic tasks. In: Proceedings of the 12th IEEE Real-Time Systems Symposium . 1991, 129-139
17	Baker T P. Stack-based scheduling for realtime processes. Real-Time Systems , 1991, 3(1): 67-99 doi: 10.1007/BF00365393

[1]	Yuanrui ZHANG, Frédéric MALLET, Yixiang CHEN. A verification framework for spatio-temporal consistency language with CCSL as a specification language[J]. Front. Comput. Sci., 2020, 14(1): 105-129.
[2]	Kai HU, Zhangbo DUAN, Jiye WANG, Lingchao GAO, Lihong SHANG. Template-based AADL automatic code generation[J]. Front. Comput. Sci., 2019, 13(4): 698-714.
[3]	ZHANG Jian, ZHANG Wenhui, ZHAN Naijun, SHEN Yidong, CHEN Haiming, ZHANG Yunquan, WANG Yongji, WU Enhua, WANG Hongan, ZHU Xueyang. Basic research in computer science and software engineering at SKLCS[J]. Front. Comput. Sci., 2008, 2(1): 1-11.

Viewed

Full text

Abstract

Cited

Shared

Discussed