论文摘要
随着计算技术的发展,实时应用种类日益增多,实时系统应用范围不断扩大,系统复杂性不断提高,特别是随着网络技术的发展而推动的网络实时应用,例如网络多媒体、远程教学、远程手术等,这些应用对任务的完成具有时间的约束,但是这类时间约束既不像硬实时那样严格,又不像弱实时那样定义不明确,而是基于一定的服务质量需求。为了更好地应对实时系统任务类型多种多样、约束复杂、具有瞬时超载等新特点,弱硬实时理论应运而生。弱硬实时理论作为一种规范,完善充实了实时系统理论,统一描述了原有各类实时系统,硬实时和弱实时实际上都是弱硬实时系统的一种特例。弱硬实时能够满足实时系统新特点的需要。由于其可以把硬实时、弱实时统一起来,因此更便于处理多种类型任务的综合调度;弱硬实时采用两个参数描述任务的服务质量需求,从而更明确地定义和区分了任务的服务质量;在系统过载时,可以通过弱硬实时调度算法提供服务质量的缓慢退化。为此,本文进一步丰富了弱硬实时的约束规范,并对弱硬实时调度算法进行了深入的研究,在以下几个方面做出了富有成效的工作并具有创新性:1)本文丰富了弱硬实时约束规范,提出（p,k）约束,并证明了其与（ m ,p）约束的等价性,进而可以导出与其它弱硬实时约束的关系。（ m ,p）约束和（p,k）约束的侧重点不同,前者突出连续丢失截止期的次数,后者突出用户考虑的最小窗口。进一步,定义了（p,k）丢失率,并通过（p,k）丢失率给出满足（p,k）约束的必要条件,为分类选择算法提供了理论基础。2)本文提出了一类基于裁剪的调度算法,基于（ m ,p）约束,提出了一类用于解决变长窗口约束违背判别的基于裁剪的弱硬实时调度（Cut-Down Based Scheduling, CDBS）算法。通过对任务的执行序列进行有效的裁剪,并引入转折点的概念,使得对（ m ,p）约束满足性判别的复杂度大幅度降低,而且与序列长度无关。文中给出了裁剪算法正确性的证明,并通过实验验证了其有效性。本文采用了一种简洁的优先级分配策略,即基于距离m次连续丢失截止期的距离分配任务的优先级,并结合任务可能出现的四种状态进行调度。最后,将算法与EDF、DWCS、DBP等算法进行比较,CDBS算法在动态失效率和最小成功率方面都提供了适当的折中,与其它算法相比具有相当的性能。3)本文提出了一种任意窗口约束调度算法,从变长窗口的丢失率保证问题出发,研究在过载情况下提供公平而有差别的服务。设计了基于（p,k）约束的任意窗口约束调度（Any Window Constraint Scheduling, AWCS）算法,分析了AWCS算法的复杂度,并根据其在重度过载情况下复杂度剧增而不适合调度的情况,提出简化算法K窗口约束调度（K-Window Constraint Scheduling, KWCS）算法。实验表明KWCS具有与AWCS相近的性能,且复杂度大幅降低,因此KWCS更适合实际系统应用。通过分析AWCS（KWCS）提供的公平性和差别性,进一步定义出成功率偏离度,并给出调度算法时延上界的通用表示方法。最后,将算法与其它弱硬实时调度算法进行比较,结果表明AWCS（KWCS）在重度过载情况下优于其它算法,能够使任务的QoS缓慢地退化,提供了一种既公平又有差别的服务。4)本文对K窗口约束调度算法的实践应用进行了丰富的扩展。提出KWCS与DBP的混合算法,将系统过载情况分为轻度过载、临界过载和重度过载,动态监控系统的状态,并根据不同的过载情况采取不同的调度策略,进而解决了KWCS在轻度过载情况下性能欠佳的问题;针对KWCS算法需要保存历史状态而不利于扩展的问题,提出分类选择算法,根据（p,k）丢失率,对（p,k）流进行分类,从而提高了算法的可扩展性;提出多跳K窗口约束调度（Multihop KWCS, M-KWCS）算法,解决了KWCS在端到端系统中的应用。5)本文对弱硬实时调度算法在新应用领域的探索进行了尝试。提出多处理器弱硬实时调度算法,解决多处理器中多类任务的综合调度,并考虑了资源的共享/独占访问方式;提出基于简单反馈的混合静态/动态节能弱硬实时调度算法,针对任务的实际执行时间通常远小于最坏情况执行时间的实际情况,对混合静态/动态节能弱硬实时调度算法加以改进,引入任务划分,通过反馈机制估计任务的实际执行时间,以获取更低的执行速度,达到更好的节能效果。实验表明,当平均情况执行时间低于最坏情况执行时间较多时,新算法优于原始算法,最多可节能60%到70%,最少可节能约10%。算法的不足之处在于当平均情况执行时间接近最坏情况执行时间时,新算法比原算法更耗能。最后,对全文进行了概括性总结,并指出了有待进一步研究和完善的问题。
论文目录
相关论文文献
标签：实时系统论文; 弱硬实时论文; 调度算法论文; 动态失效论文; 服务质量论文; 定长窗口约束论文; 变长窗口约束论文; 反馈机制论文;