CAJ | 학술논문

针对基于主副版本容错的多处理机中独立的、抢占性的硬实时任务,提出了一种高效的调度算法--TPFTRM(task partition based fault tolerant rate-monotonic)算法.该算法将单机实时RM算法扩展到容错多处理机上,并且调度过程中从不使用主动执行的任务副版本,而仅使用被动执行和主副重叠方式执行的任务副版本,从而最大限度地利用副版本重叠和分离技术提高了算法调度性能.此外,TPFTRM根据任务负载不同将任务集合划分成两个不相交的子集进行分配;还根据处理机调度的任务版本不同,将处理机集合划分成3个不相交的子集进行调度,从而使TPFTRM调度算法便于理解、实现以及减少了调度所需要的运行时间.模拟实验对各种具有不同周期和任务负载的任务集合进行了调度测试.实验结果表明,TPFTRM与目前所知同类算法相比,在调度相同参数的任务集合时不仅明显减少了调度所需要的处理机数目,还减少了调度所需要的运行时间,从而证实了TPFTRM算法的高效性.
침대기우주부판본용착적다처리궤중독립적、창점성적경실시임무,제출료일충고효적조도산법--TPFTRM(task partition based fault tolerant rate-monotonic)산법.해산법장단궤실시RM산법확전도용착다처리궤상,병차조도과정중종불사용주동집행적임무부판본,이부사용피동집행화주부중첩방식집행적임무부판본,종이최대한도지이용부판본중첩화분리기술제고료산법조도성능.차외,TPFTRM근거임무부재불동장임무집합화분성량개불상교적자집진행분배;환근거처리궤조도적임무판본불동,장처리궤집합화분성3개불상교적자집진행조도,종이사TPFTRM조도산법편우리해、실현이급감소료조도소수요적운행시간.모의실험대각충구유불동주기화임무부재적임무집합진행료조도측시.실험결과표명,TPFTRM여목전소지동류산법상비,재조도상동삼수적임무집합시불부명현감소료조도소수요적처리궤수목,환감소료조도소수요적운행시간,종이증실료TPFTRM산법적고효성.
This paper has considered the problem of preemptively scheduling a set of independent periodic hard real-time tasks in primary-backup based multiprocessor systems. An efficient scheduling algorithm-Task Partition based Fault Tolerant Rate-Monotonic (TPFTRM) is proposed which extends RM algorithm to primary-backup based multiprocessor to provide fault tolerance. Compared with previous scheduling algorithms in this area, TPFTRM abandons active backup copies and only uses passive and overlapping backup copies to maximize the backup over-booking and deallocation, thus improves the scheduling performance. Moreover, TPFTRM proposes the task partitioning and processors grouping technique, which reduce the scheduling computation time and also make an easy way to understand and implement it. Extensive simulations experiments are also carried out based on task sets with different parameters. And the simulation result shows a remarkable saving of processors as well as scheduling computation time compared with previous algorithms, which proves the feasibility and effectiveness of the proposed TPFTRM algorithm.