分布式实时容错调度算法研究

摘要

随着高速网络和高性能PC/工作站的发展，实时系统越来越多的应用于各种分布环境而形成的分布式实时系统，如飞行控制系统等。在实时系统中，如果任务没有在期限前完成，往往会导致灾难性的后果。因此为了保证系统中的实时任务即使在系统出现故障后仍能在期限前完成，必须为系统提供一定的容错能力以提高系统的可靠性。 实时容错调度是实现分布式实时系统容错的主要方法之一。针对现代分布式实时系统的特点，从多种性能指标的角度出发，分别研究和设计基于同构和异构分布式系统中的实时容错调度算法，研究的目的是旨在通过高质量的调度算法来提高分布式实时系统的可调度性、系统可靠性，以及任务接收率等不同的性能指标。 现代分布式实时系统常用于空间或者能源受限的系统中(如航天卫星的控制系统)，增加处理机的个数意味着占用更多的空间和能源消耗，因此在同构分布式系统中，应重点研究实时容错调度算法的可调度性问题，即在保证系统容错能力的前提条件下，尽量减少系统为实现容错所需的冗余。 传统的实时容错调度算法FTRMFF（Fault-Tolerant Rate-Monotonic First-Fit）同时采用两种方式的副版本，通过首次适应算法尽量减少主版本的最坏响应时间，使更多的副版本以被动方式执行，从而达到减少系统冗余的目的。实例分析表明，在FTRMFF算法中，传统的主动副版本在系统无故障运行时，如果主动副版本的最坏响应时间大于主版本的最坏响应时间，系统会存在大量的冗余。为了克服FTRMFF的这个固有缺陷，提出终止主动副版本调度算法Tercos(terminates the execution ofactive backup copies)。Tercos算法在系统无故障时，如果主版本成功执行完毕则强制终止主动副版本的执行，以减少不必要的冗余。实验表明，Tercos 算法在主版本和主动副版本的最坏响应时间相差较大的情况下能显著的减少调度所需处理机的个数。尽管Tercos算法能在一定程度上减少冗余，提高可调度性。但是Tercos 算法采用的却是一种“消极”和”被动”的策略，在主版本和主动副版本的最坏响应时间相差不大时，效果并不明显。因此，通过对Tercos 算法的扩展，提出基于延迟主动副版本的调度算法Debus(deferred active backup scheme)，Debus利用双优先级调度算法来尽量推迟主动方式副版本的执行以最大程度减少主/副版本间的重叠长度，并在主版本执行成功时，终止副版本的执行，从而进一步减少为实现容错所需要的冗余度。 实验数据表明，相对于Tercos，Debus算法能在主版本和主动副版本的最坏响应时间相差不大的情况下进一步提高了系统的可调度性。 同构分布式系统要求系统中的每一个处理机完全相同，但是在实际应用中这个条件不易满足。因此，实际应用中更广泛被采用的是异构分布式系统。与同构分布式系统不同，在设计基于异构分布式系统的实时容错调度算法时，必须考虑调度算法的可靠性。现有的基于异构分布式系统的实时容错调度算法都要求任务是非抢占性的非周期任务，不适合于抢占性的周期任务，因此在实际应用中有很大的局限性。 针对抢占性周期任务的特点，提出可靠性模型RMNCF和基于此模型的两个调度算法NRFTAHS(non-reliability-driven fault-tolerant algorithm for heterogeneous distributedsystem)和RDFTAHS(reliability-driven fault-tolerant algorithm for heterogeneousdistributed system)。可靠性模型RMNCF 以所有任务集在一个超周期内的失效概率作为系统的可靠性。NRFTAHS 算法以提高系统的可调度性为目标来进行任务的分配，而RDFTAHS 算法的调度目标则是提高系统的可靠性。实验数据表明，RDFTAHS 在可靠性方面大大优于NRFTAHS，但是RDFTAHS 在可调度性方面略逊于NRFTAHS。虽然可靠性模型RMNCF 能够在一定程度上度量系统的可靠性，但是该模型并未考虑处理故障后的系统可靠性，针对这个问题，进一步提出一个改进的基于抢占性实时周期任务的可靠性模型RMCF和对应的调度算法IRDFTAHS(ImprovedReliability-Driven Fault-Tolerant Algorithm for Heterogeneous Distributed System)。可靠性模型RMCF和IRDFTAHS 算法充分考虑了单处理机故障容错情况下的系统可靠性，与基于可靠性模型RMNCF的算法相比，IRDFTAHS 算法更接近于实际和有效。实验数据也表明IRDFTAHS的综合性能优于RDFTAHS。 与实时任务的静态调度算法不同，动态调度算法的实现更加复杂，因为动态调度算法需要根据系统的当前状况对调度策略进行调整。提出一个基于异构分布式系统的可靠性驱动动态实时容错调度算法，该算法以可靠性代价为调度目标动态调度独立、不可抢占的非周期任务，从而在不增加系统硬件代价的前提下，通过调度增加了系统的可靠性。同时，算法充分考虑任务的调度时间和分派时间，使得算法更加接近现实和更加精确。为了克服传统动态调度算法中仅支持单一类型的副版本的不足，算法同时采用主动和被动两种方式的副版本来实现容错，以最大程度的减少副版本的冗余度。