Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

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 LI1(), Wei BA2
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