基于任务复制的处理器预分配算法

基于任务复制的调度算法比无任务复制的调度算法具有较好的性能．文章在分析了基于任务复制的几个典型算法(如TDS，OSA等算法)及其假设条件后，提出了以使调度长度最短作为主要目标、减少处理机数目作为次要目标的处理器预分配算法PPA．该算法对任务计算时间与任务间通信时间未做任何限制(即不考虑任务粒度)．通过与相关工作的比较可以看出：PPA算法在调度长度与处理器使用数目上均优于其它算法或与其它算法相当，同时，该算法具有与TDS，OSA相同的时间复杂度．这对嵌入式实时分布系统具有重要的意义。

An Algorithm of Processor Pre-Allocation Based on Task Duplication

Scheduling algorithms based on task duplication are of better performance than non duplication ones.The paper analyzes typical scheduling algorithms based on task duplication(e.g. TDS, OSA algorithm) and their assumptions, then puts forward the algorithm of Processor Pre Allocation (PPA) based on task duplication, whose primary aim is to get the shortest scheduling length, and secondary aim to utilize less number of processors, without any restricted conditions of task computing time and communication time between tasks (namely task granularity is not taken into account). Compared with correlative algorithms, PPA algorithm has advantages in scheduling length and the number of processors over others, but has the same time complexity. That is important for embedded real time distributed systems.