A Study on Multi-Processor Scheduling Algorithm

A Study on Multi-Processor Scheduling Algorithm

Y. DuanW. Chen 

Dept of Basic Science Guangdong Univer sity of Science and T echnologyechnology, Dongguan, Guangdong,

Corresponding Author Email: 
dy_01155@126.com com
January 2017
| |
15 April 2017
| | Citation



This paper deals with task scheduling problem of multi-processors by using T-LET plane method, and proposes a new algorithm named BLREF based on flow scheduling model. And the optimality of this algorithm is also demonstrated. Finally, we verify the superiority of it through specific examples. This is a simple algorithm is designed for simulation scheduling project, improvement of simulation technology has important significance. BLREF algorithm can pass the execution time of appropriating makes full use of the processor, so as to realize the feasible scheduling, is a kind of optimal multiprocessor scheduling algorithm. In addition, the misappropriation of the execution time for the analysis has very important reference value for other algorithm, and the other is of great reference value for multiprocessor scheduling problem research.


Scheduling algorithm algorithm, multimulti-processorsprocessors, T-LET planeplane, event C, event B.

1. Introduction

Two main strategies for multi-processor task scheduling are global scheme and classification scheme [1]. In the global scheduling scheme, every new real time task is always executed in different processors, and all processors run the same scheduling algorithm. While, in the classification scheme, all emergences of a task are executed in the same processor, and tasks are assigned to different processors beforehand by a task assignment algorithm. Typical multi-processor scheduling algorithms have many drawback [2, 3]. For example, the minimum relaxation algorithm and the global EDF algorithm, etc. are not the optimal algorithms, since we can find task set whose cut-off time could not be fulfilled by both algorithms. Therefore, this paper proposes an optimal multi-processors scheduling algorithm named BLREF, can pass the execution time of appropriating makes full use of the processor, in order to realize the feasible scheduling, and gives proofs on its optimality.

2. T-LET Plane Based BLREF Scheduling Algorithm
3. Necessary and Sufficient Conditions of “Schedulability” in Blref Algorithm
4. Event C
5. Event B
6. Proof on the Current Feasibility of Blref Algorithm on the T-Let Plane
7. Comparison and Analysis of Algorithms
8. Conclusion

[1] J.Carpenter,S.Funk. A categorization of real-time multiprocessor scheduling problems and algorithms[A].Handbook on Scheduling Algorithms, Methods and Models[C].2004.Chapman and Hall/CRC

[2] KRamamritham, J.A. Stankovic.Scheduling Algorithms and Operating Systems Support for Real-time Systems. Proceeding of the IEEE, Vol 83(1):55-67,1994.

[3] Gao Li'e,A.L. Tong, F.T. Kang,W.D. Liu,N.N.Zhao, Application and Research of Dynamic Scheduling Algorithm for Multiprocessor[J], Computer Engineering and Applications,Vol.34,196-199,2005.

[4] L.M.Dertouzos. Multiprocessor On-LineScheduling of Hard-Real-Time Tasks[J]IEEE Transactions on Software Engineering,vol 15(12):1497-1506,1989.

[5] P.Holman, J.H. Anderson.Adapting Pair Scheduling forSymmetric Multiprocessors[J].Journal of Embedded Computing,Vol.1Number 4, 543-564,2005.

[6] C. Feng,J. Liang, Solve the more general travelling salesman problem [J]. AMSE Journals–2014-Series: Modelling D.Vol 35, Issue 1,9-23,2014.

[7] S. Lui . Real Time Scheduling Theory: A Historical Perspective[J].Real-Time Systems,2004,28:101-155.Kluwer AcademicPublishers.Manufactured in TheNetherlands.

[8] C. Feng,J. Liang.The solution of the more general traveling salesman [J]. AMSE Journals–2014-Series: Advances A,Vol 51, Issue1:27-40,2014

[9] Y. Duan., Optimization design of the single processor scheduling algorithm in real-time system research [J]. Journal ofoperational research,Vol 17, No.1,27-34,2013.

[10] Y. Duan.,Y. Xiang,Comparative study of different genetic operator combination to solve TSP problem [J]. Science and technology.Vol 28, No.5,27-31,2012.