具备约束的实时调度关键问题的研究

发布时间：2020-05-06 07:07

【摘要】：随着嵌入式技术的迅猛发展以及嵌入式应用复杂性的不断攀升,当今嵌入式系统的应用环境通常包含多种类型的应用需求,而对于系统进行满足实时约束的服务不再是实时调度的唯一目标。为了能够正确的执行系统功能,在系统调度的过程中,还需要考虑任务间的偏序约束、任务间的资源共享约束以及为任务提供满足QoS要求的服务等问题。虽然传统的实时调度理论及其相关模型仍是目前实时系统中实时调度的理论基础,但仅仅使用任务的基本时间特征来作出系统的调度决策并不能充分满足多种类型的应用需求,而且单一的调度目标往往不能够满足具备其他约束的实时系统需要。因此在确保满足实时任务可调度性这一根本需求的前提下,如何根据具体应用的实际约束需求进行正确有效的调度,是目前实时调度研究领域需要解决的关键问题。本文主要对具备约束的实时调度问题进行研究,主要包括具备偏序约束的实时调度问题和具备QoS约束的实时调度问题。具备偏序约束的实时调度问题源于实际应用中特定功能的设计要求,这样的实时应用通常被设计为在计算资源上调度运行的交互任务,由于这些并行任务要实现整体计算,因此任务间需要满足执行的优先顺序关系来确保整体功能的正确性。为了解决在线调度算法无法处理释放时间任意的任务集的问题,本文以并行拓扑排序原理为基础,通过任务间的并行性和串行性分析来在线确定不可抢占调度序列,可证明该方法在任务按偏序约束层次释放时最优。离线调度是解决具备偏序约束调度问题的另一个手段,本文通过对具备偏序约束的实时任务集的不可抢占调度的分析,将调度约束总结为任务的实时约束、任务间的偏序约束以及调度序列中不可抢占的序列约束,将这三种约束转换为线性规划求解问题的标准约束形式,采用分支检测策略,不断修正调度序列约束来进行规划,以求解满足偏序和实时约束的可行调度序列。具备QoS约束的实时调度问题来自嵌入式实时系统在控制系统、网络通信系统、工业网络系统等领域中的应用,在这类应用中,在有限时间区间内部分任务截止期的错过不会影响整个应用的性能,但这种截止期不满足的情况需要在QOS约束允许的范围内。本文提出满足QoS约束的在线调度算法,基于任务周期和实时QoS约束采用RM调度策略进行任务固定优先级设置,根据当前实时约束参数满足情况的统计将任务在抢占和可选间进行调整,以时刻反映任务当前的QoS服务等级需求,同时为了满足系统对高负载的适应性,该算法可以结合QoS适度退化机制,在保证为紧要任务提供满足最低QoS的服务的前提下,最大限度的为所有任务提供有效的服务。该算法即具备了静态调度算法可以进行可调度判定的优点,又能够像动态调度算法那样根据系统负载动态设定任务的执行模式。本文还针对具备QoS约束的实时系统在能耗约束系统中的应用,基于遗传算法提出最小化能耗的任务执行模式的离线优化方案,并针对于采用标准遗产算法求解任务的最佳执行模式出现“早熟”等问题,将模拟退火算法引入到遗传算法变异过程形成混合遗传算法,提高最优解的搜索性能。在对两个约束调度目标、四种调度策略的论述过程中,本文分别使用算例分析、仿真实验等手段验证了所提出调度算法的正确性和有效性。
【图文】：

最小上界,CPU利用率,可调度,物理意义

则可由RM调度。以L(N)表示N个任务的CPU利用率的最小上界。L(N)与君无关，，以N)随着N单调递减，当N峥co，定的物理意义如图2.1所示。L(N)=0.693。利用CPU利用率作为可调度判 u................麟黔撇黝 0Boundl图2.1利用CPU利用率最小上界进行可调度判定的物理意义 Fig.2.1PhysiealmeaningofsehedulablitytestwithCPUutilizationleastuPbounds图2.1中三种情况所代表的物理意义如下:(l)整个CPu利用率小于L(N)，任务集是RM可调度的;(2)整个CPU利用率大于1，任务集是RM不可调度的;(3)整个CPu利用率介于L(N)和1之间，无法判定。可见，对于图中处于灰色区域内的任务集，有可能可调度，但利用CPU利用率最小上界来判定却无能为力。可见，定理2.1是RM调度的充分条件。实际上，不满足上述定理的实时任务集也可能由RM调度。RM算法是一种静态优先级调度算法。它在运行前确定任务的执行顺序，运行调度开销小

序列,示例图,示例,超周期

图5.1示例1的R五1一RTO调度序列 Fig.5.1SchedulingsequeneebyRM一RTOofExamPlel从图5.1可以看出，采用RM一Rl，O的固定优先级设置方法，在一个超周期内，所有周期任务的强制任务都能够满足截至期的要求，从而达到了实时Qos约束参数的要求。若采用本调度算法对该任务集进行调度，由于尸，欠介z<pZ厂k2<P3欠儿，因此分别设置:，，:2和:。抢占任务的优先级为1
【学位授予单位】：东北大学
【学位级别】：博士
【学位授予年份】：2010
【分类号】：TP368.1

【参考文献】