计算机工程 ›› 2008, Vol. 34 ›› Issue (2): 11-13.doi: 10.3969/j.issn.1000-3428.2008.02.004

• 博士论文 • 上一篇    下一篇

嵌入式并行系统中基于任务优化的调度算法

刘 勇1,尹增山2,杨根庆1,2   

  1. (1. 上海微小卫星工程中心,上海 200050;2. 中国科学院上海微系统与信息技术研究所,上海 200050)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-01-20 发布日期:2008-01-20

Scheduling Algorithm Based on Tasks Optimization for Embedded Parallel System

LIU Yong1, YIN Zeng-shan2, YANG Gen-qing1,2   

  1. (1. Shanghai Engineering Center for Microsatellites, Shanghai 200050;2. Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences, Shanghai 200050)
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-01-20 Published:2008-01-20

摘要: 在嵌入式并行计算系统中,任务调度是决定系统性能的关键。多任务调度中,启发式调度法是一种设计简单且性能良好的调度方法。目前的调度算法大多是基于任务复制的,没有充分考虑前驱任务与其后继任务间的相关性。该文提出了一种基于相关任务优化(DTO)的调度算法,通过分析已用处理机的负载和空闲时间,尽量减少系统的调度长度和处理机数目。算法分析结果表明,DTO算法在性能上优于其他算法,对嵌入式并行计算系统中的多任务调度是一个较好的选择。

关键词: 嵌入式系统, 任务调度, 调度长度, 相关任务

Abstract: The tasks scheduling algorithm is the key factor to the performance of the embedded parallel computing system. Heuristic scheduling algorithm is a simple multi-task scheduling algorithm with good performance in embedded distributed system. The present scheduling algorithms are mostly based on task duplication, and the dependence between the predecessor tasks and successor tasks is not well taken into account. In this paper, a new scheduling algorithm based on Dependent Tasks Optimization(DTO) is presented. For the algorithm, the scheduling length and the number of the processing units are decreased by analyzing the load and the idle time of the processor. The result of algorithm analysis shows that the performance of the DTO algorithm is better than other scheduling algorithms, it is a better choice for tasks scheduling in the embedded parallel computing systems.

Key words: embedded system, task scheduling, scheduling length, dependent tasks

中图分类号: