|
|
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 |
|
|
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
|
|
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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|