论文部分内容阅读
实时分布系统的任务调度问题是一个富有挑战性的课题,也是当前的一个研究热点。由于任务调度是一个典型的NP 问题,同时它又是直接影响分布式系统性能的关键因素。因此,研究实时分布计算机系统的任务调度策略具有重要的理论意义和实际意义。本文以“十五”预研项目为背景,在与单处理器调度算法相结合的基础上,针对实际应用中大量的实时周期任务,以提高资源利用率为主要目标,对分布实时系统的调度理论与实现问题进行了深入的探索与研究。首先,给出与实时分布容错系统相关系统(包括实时系统、容错系统、分布式系统和实时分布系统)的模型和主要特点,分析了这些系统所涉及的调度理论。进一步指出,实时分布式系统由于自身具有冗余特性而使其实现容错可行。给出了任务可调度的证明和调度算法的评价指标。其次,根据分布系统容错调度原理,在单处理器实时调度采用EDF 算法的基础上,提出了采用不同容错技术的两种实时分布系统容错调度算法:PPB-MFT-EDF 算法和APB-MFT-EDF 算法。前者采用了常用的容错技术—被动备份容错技术,后者采用的则是主动备份容错技术。文中证明了两种算法的可调度条件和一些重要性质。证明和模拟结果显示:APB-MFT-EDF 的性能优于PPB-MFT-EDF 算法,并对这一结果进行了深入分析。第三,在以上算法的基础上,进一步提出了既可调度周期任务也可调度非周期任务的混合任务调度算法,它将所有非周期任务转化为周期任务进行调度,并有效地利用处理机无故障时的空闲资源。与其它同类算法相比,该算法简单实用,并可进一步扩大处理任务类型的范围。针对单处理器的实时容错调度,将单处理器容错与分布式容错相结合,提出了在一次备份的基础上同时实现多种类型错误的容错调度,有效地扩大了算法应用范围并进一步提高了资源利用率。最后,在一种实时分布容错系统的体系结构和三种容错方法的基础上,提出了针对单处理机实时调度算法的一种实时分布容错系统任务动态分配与调度结构图,详细描述了调度的策略、机制与算法。