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

An Algorithm of Processor Pre-Allocation Based on Task Duplication

作　　者：周双娥 袁由光[2] 熊兵周[2] 欧中红 

机构地区：[1]哈尔滨工程大学计算机科学与技术学院,哈尔滨150001 [2]武汉数字工程研究所,武汉430074

出　　处：《计算机学报》2004年第2期216-223,共8页Chinese Journal of Computers

基　　金："十五"国家预研项目 (4 13 160 2 0 1)资助

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

关 键 词：任务复制 处理器 PPA算法 TDS算法 OSA算法 任务调度 任务分配 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]