On-line schedule with precedence constraints satisfying

Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (12): 43-45.

• 研究、探讨 • Previous Articles Next Articles

On-line schedule with precedence constraints satisfying

ZHAO Ming1，2，ZHAO Hai1，ZHANG Haohua1，ZOU Yong1

1.School of Information Science & Engineering，Northeastern University，Shenyang 110004，China
2.School of Information & Control Engineering Faculty，Shenyang Jianzhu University，Shenyang 110168，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-04-21 Published:2011-04-21

满足偏序约束的在线调度

赵明1，2，赵海1，张浩华1，邹勇1

1.东北大学信息科学与工程学院，沈阳 110004
2.沈阳建筑大学信息与控制工程学院，沈阳 110168

Abstract

Abstract: Real-time scheduling with precedence constraints needs that scheduling sequence produced by algorithm satisfies not only real-time constraints of every task，but also precedence constraints between tasks.Based on parallel topological sort，this paper presents a new on-line scheduling algorithm wich can set priority of task considering serial property and parallel property of task execution.This algorithm can deal with tasks with random release time.The priciple and design of the algorithm are preseneted and example is shown to prove the algorithm.

Key words: real-time scheduling, precedence constraints, topological sort

摘要： 具备偏序关系的实时调度要求调度算法产生的执行序列既要满足任务的实时约束，又要满足任务间执行的偏序约束。基于并行拓扑排序，提出一种新的在线调度算法，该算法通过同时考察任务间执行的串行性和并行性来进行优先级设置，能够处理释放时间任意的任务集。给出该算法的原理和设计，并通过示例分析和比较对算法进行验证。

关键词: 实时调度, 偏序约束, 拓扑排序

ZHAO Ming1，2，ZHAO Hai1，ZHANG Haohua1，ZOU Yong1. On-line schedule with precedence constraints satisfying[J]. Computer Engineering and Applications, 2011, 47(12): 43-45.

赵明1，2，赵海1，张浩华1，邹勇1. 满足偏序约束的在线调度[J]. 计算机工程与应用, 2011, 47(12): 43-45.

[1]	WANG Jianhong, YAN Li. Schedulability test of EPDF Pfair algorithm on multiprocessor platforms [J]. Computer Engineering and Applications, 2013, 49(1): 43-45.
[2]	PENG Liqiang1，YIN Junwen2，WANG Fei1，3. Real-time scheduling model of fuzzy itemized tasks for non-traditional safety critical system [J]. Computer Engineering and Applications, 2011, 47(27): 55-59.
[3]	XIA Qiufen，LI Mingchu，XU Zichuan，WU Guowei. Research on thermal aware real-time scheduling [J]. Computer Engineering and Applications, 2011, 47(26): 27-31.
[4]	LIANG Hao，YAN Li. Schedulability test of real-time scheduling EDZL algorithm [J]. Computer Engineering and Applications, 2011, 47(2): 60-61.
[5]	LIU Chunfeng1，2，YANG Shanlin1. Study on algorithm for project scheduling with heterogeneous efficiency workforce [J]. Computer Engineering and Applications, 2011, 47(13): 18-21.
[6]	ZHOU Peng. Fuzzy scheduling design in computer on-line monitoring system based on pipeline flux leak [J]. Computer Engineering and Applications, 2009, 45(27): 231-236.
[7]	YAN Li,PENG Chen-hui. Real-time scheduling design of SCADA based on validity period of data [J]. Computer Engineering and Applications, 2009, 45(1): 92-95.
[8]	Zhuowei Shen. A Long-Release-Interval-First Scheduling Algorithm for Hybrid Real-time Systems [J]. Computer Engineering and Applications, 2007, 43(5期): 3-6.
[9]	Zhuowei Shen. Schedulability Analysis for Non-Preemptive EDF Scheduling Algorithm [J]. Computer Engineering and Applications, 2006, 42(9期): 10-.

On-line schedule with precedence constraints satisfying

满足偏序约束的在线调度

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 9

Recommended Articles

Metrics