Abstract: In the multi-processor system, task scheduling is one of the key factors which decide the performance of system. In order to optimize the task scheduling, this paper proposes a new task scheduling algorithm based on some typical algorithms（e.g., PPA, the algorithm which is put forward by XU Cheng etc.）. On the one hand, the algorithm establishes reasonable order to duplicate precursor task, and two stages of replication, which can duplicate more precursor task to reduce scheduling length and spare time. On the other hand, the algorithm removes redundant clusters which don’t affect the scheduling length of the task system, then carries on the merger between clusters to reduce the number of the processor and scheduling length. Simulation results show that   the improved algorithm on the performance of task scheduling is superior to the above typical algorithms.

Key words: multi-processor, task duplication, task scheduling, merger of clusters

摘要： 在多核系统中，任务调度是决定系统性能的关键因素之一。为优化任务调度，基于一些典型的任务调度算法（如PPA，徐成提出的算法等），提出了一种新的任务调度算法。该算法一方面合理确定前驱任务复制的先后顺序，而且进行两个阶段的复制，从而可以复制更多的前驱任务以减少调度长度和处理器上空余时间；另一方面，通过去除不影响任务系统调度长度的冗余簇，然后进行簇之间的合并，以减少处理机的数目和调度长度。实验表明，改进后的算法在任务调度的性能上优于典型算法。

关键词: 多核, 任务复制, 任务调度, 簇合并