摘要
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.
有保证的调度对硬实时系统是必须的 ,这是因为系统中每个进程必须满足它们的截止时间 ,否则后果不堪设想 .本文讨论了两种有保证的调度算法 ,它们是分支限界法和回溯法 ,给出了用这两种算法寻找最优解的过程 ,提出逻辑结点和物理结点的概念 .通过对多个进程集合寻找最优解的实验 ,对两种算法在产生的结点个数、比较次数。
