多处理器硬实时系统的调度算法研究

发布时间：2018-04-19 01:27

本文选题：硬实时系统 + 全局调度　；参考：《合肥工业大学》2015年博士论文

【摘要】：硬实时系统要求系统中的每个实时任务都能够在截止期之前正确响应,否则会带来难以承受的严重后果。硬实时调度算法构造确定性的任务运行秩序,并从理论上证明该运行秩序的可行性,确保任务不会错失截止期。随着硬实时系统对计算能力需求的不断增长,越来越多的复杂硬实时系统开始采用多处理器芯片。和单处理器实时系统相比,多处理器系统由于任务的并行运行,在调度方面的分析、设计难度较大。因此,高效率的多处理器实时调度算法是硬实时系统研究的核心内容之一抢占在提高调度能力和灵活性的同时会带来额外的系统开销。特别在多处理器平台上,抢占带来的作业迁移会造成不可忽视的性能下降。以减少不必要抢占为目标,提出多处理器实时系统的全局抢占阈值调度算法GPTS。GPTS是处于抢占调度和不可抢占调度之间的一种混合调度算法。该算法在作业开始运行时提升其优先级,从而降低了该作业被抢占的可能性,在保持系统可调度的基础上,可以有效减少系统运行过程中的抢占次数。限制不必要的抢占不仅可以减少资源损耗,还能够提高调度能力。将任务整体提升优先级会给高优先级任务带来过高的额外干扰,影响高优先级任务的实时性。以提高调度能力为目标,提出多处理器硬实时系统的限制抢占调度算法FPLPS.该算法在任务的末尾设置一段有较高优先级的区域,减少任务在该区域内运行时被抢占的次数,同时避免给资源压力很大的高优先级任务带来过多的额外干扰,从而提高了实时任务集的可调度性。硬实时系统在运行过程中,不可避免的会出现故障,在出现故障时依然可以正确运行是硬实时系统必须满足的要求。主副版本机制是硬实时调度中广泛采用的容错方法。在主副版本机制的容错调度算法中,主版本出现故障之后对应的副版本才会进入就绪状态,可供副版本运行的时间区间短,容易错失截止期。针对副版本实时性较差的问题,提出副版本不可抢占的全局容错调度算法FTGS-NPB。该算法通过赋予副版本最高优先级,使副版本在运行过程中不受干扰并在最短时间内响应,改善了副版本的实时性,从而减少了实现容错所需的额外处理器资源。副版本根据进入就绪状态的时间分为主动副版本和被动副版本。主动副版本在无故障时会消耗大量的额外资源,被动副版本不消耗额外资源,但是实时性较差,并且不适用于主副版本总使用率超过1的任务。同时考虑两种副版本的优缺点,提出副版本延迟的全局容错调度算法FTGS-BD。该算法根据资源使用情况将副版本的就绪时间尽量推迟,同时在不需要副版本响应时及时回收分配给副版本的资源,在保证副版本能够在对应主版本出现故障的情况下正确响应的同时,减少了副版本在主版本无故障时浪费的处理器资源,从而以较少的代价实现容错调度。同时,FTGS-BD可以应用于存在主副版本总使用率超过1的任务的实时任务集。
[Abstract]:This algorithm is a kind of hybrid scheduling algorithm in hard real - time system .

【学位授予单位】：合肥工业大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP332

【相似文献】