Research on Guaranteed Scheduling Algorithms  

有保证调度算法的研究(英文)

作　　者：张凤芝[1] 张红线[1] 宗润宽[2] 任长明[1] 

机构地区：[1]天津大学电子信息工程学院,天津300072 [2]天津大学化工学院,天津300072

出　　处：《Transactions of Tianjin University》2002年第1期48-51,共4页天津大学学报（英文版）

摘　　要：Guaranteed scheduling is necessary for hard real time systems, because each process of them must meet their deadline, or a serious consequence will result.In this paper we discuss two guaranteed schedule algorithms:backtracking and branch and bound,introduce the process to find the optimal solution by both methods,propose the concept of logical node and physical node.Through some experiments for different process sets,we have made comparisons between the two algorithms in branch nodes,comparing time,topology of the search tree,memory size needed,etc.有保证的调度对硬实时系统是必须的 ,这是因为系统中每个进程必须满足它们的截止时间 ,否则后果不堪设想 .本文讨论了两种有保证的调度算法 ,它们是分支限界法和回溯法 ,给出了用这两种算法寻找最优解的过程 ,提出逻辑结点和物理结点的概念 .通过对多个进程集合寻找最优解的实验 ,对两种算法在产生的结点个数、比较次数。

关 键 词：hard real time systems branch and bound BACKTRACKING guaranteed scheduling 

分 类 号：TP316.2[自动化与计算机技术—计算机软件与理论]