EDF调度算法可调度性分析方法的改进研究

任务集的可调度性分析是实时系统研究和应用的关键问题。针对抢占式与不可抢占式EDF(earliest deadline first)调度算法, 分别给出了实时任务集新的可调度性测试条件, 针对任务集为可调度时可以实现快速判定。通过与已有的EDF算法的可调度性判定充要条件相结合, 提出了改进的抢占式与不可抢占式EDF算法的可调度性分析方法。仿真实验表明, 相对现有EDF算法的可调度性分析方法, 所提出的方法能有效提高算法性能。     

FPTS:一种任务间存在共享资源时的抢占阈值调度算法

受到广泛关注的抢占阈值调度算法能够有效减少现场切换次数,防止不必要的任务抢占,降低资源额外消耗,提高任务集合的可调度性.目前该调度算法的研究工作大多围绕独立任务集合展开,在实际实时系统中任务经常需要互斥访问共享资源,任务之间由于资源共享而导致的相关性对于任务集合的优先级分配和抢占阈值分配都有很大的影响.SRP协议是在实时系统中得到广泛应用的资源访问控制协议,具有死锁避免、提前阻塞、共享任务栈等一系列优良特性.将SRP和抢占阈值调度算法结合起来,提出FPTS调度模型,给出相应的可调度性判定公式,考虑在任务之间使用SRP协议时求解任务抢占阅值分配,最后给出计算抢占阈值分配的伪多项式时间算法.     

EPTS:一种实时动态电压调整的抢占阈值调度器

低功耗目前已成为嵌入式实时系统设计中非常重要的性能需求。动态电压调度DVS机制通过动态调整处理器电压进而有效降低系统功耗,正在逐渐得到广泛应用。抢占阈值调度策略实现双优先级系统,每个任务具有两个优先级,任务优先级被用于任务之间竞争处理器,而抢占阈值作为任务开始运行后实际使用的优先级,从而减少现场切换次数,降低系统功耗,同时也提高整个任务集合的可调度性。本文提出一种在线节能调度算法EPTS,拓展抢占阈值调度模型,在任务执行过程中动态调节处理器电压,力求在保证任务集合可调度性的前提下尽可能减少系统功耗,提高系统性能。而后在AMDAthlon4处理器和RT-Linux平台上实现了EPTS调度器,实验证明对于实际任务集合能够有效节能,提高了处理器的利用率,改善了RT-Linux的实时性能。     

基于最优虚拟截止日期多处理器混合时序调度

为提高混合临界系统实时调度有效性,提出基于最优虚拟截止日期的多处理器混合时序调度算法.将现有非抢占最早截止时间可调度性测试算法推广到混合临界多处理器系统,引入时序保证技术,确保系统在两个不同临界值间过渡;将所提可调度性测试扩展到混合临界系统,利用系统级截止期缩减参数控制,设计最优虚拟截止日期分配策略.仿真结果表明,采用最优虚拟截止时间分配策略可调度性测试可发现大量额外可调度任务集,实现混合临界多处理器非抢占调度性能提升.     

多处理器硬实时系统的抢占阈值调度研究

在实时系统中,抢占在提高系统灵活性的同时带来额外的系统开销,特别在多处理器平台上抢占导致的作业迁移会造成相当大的性能下降,减少不必要的抢占是硬实时系统研究的重要方向.抢占阈值调度是处于抢占调度和不可抢占调度之间的一种混合调度方法,在保持调度能力的基础上限制抢占.基于截止期分析建立了多处理器硬实时系统抢占阈值调度的可调度性判定条件,针对抢占阈值调度提出一种改进的优先级分配算法OPA-MLL,并建立了抢占阈值分配(preemption threshold assignment,PTA)算法.仿真结果表明,采用OPA-MLL算法和PTA算法分别给任务集分配优先级和抢占阈值时,可调度任务集比率明显提高,同时能最大程度限制抢占次数.     

容错优先级可提升的抢占阈值容错调度算法

基于软件容错模型,提出了允许容错优先级提升的抢占阈值容错调度算法(extended fault-tolerantfixed-priority with preemption threshold,简称FT-FPPT*).该算法能够在抢占式容错调度算法(fault-tolerantfixed-priority preemptive,简称FT-FPP)和抢占阈值容错调度算法(fault-tolerant fixed-priority with preemptionthreshold,简称FT-FPPT)无法提高系统容错能力的情况下,进一步提高系统的容错能力.为了获得系统中任务优先级分配的最佳策略,基于任务最坏响应时间的可调度性分析,提出了一种最优的优先级配置搜索算法(priorityassignment search algorithm,简称PASA).经过深入分析和实验证明,与FT-FPPT算法相比,FT-FPPT*算法能够有效地提高硬实时系统的容错能力.     

抢占阈值调度算法的分析与研究

本文详细论述了应用于静态优先级实时系统的抢占阈值调度算法。描述了算法实现和任务集合可调度性判定公式的推导,分析了算法的性能特点,阐述了抢占阈值调度是静态优先级嵌入式实时系统开发中调度算法的合适选择。     

改进的抢占阈值调度任务响应时间分析方法

现有的基于抢占阈值调度的任务响应时间分析方法对实时任务系统进行可调度性判定时,对任务响应时间估计过低,造成任务错过期限的现象。针对上述缺点不足,该文提出改进的基于抢占阈值调度的任务响应时间分析方法,考虑了任务释放抖动和时钟嘀嗒调度的影响,使用改进的任务参数计算系统任务时间需求函数。仿真对比结果表明,改进后的方法较单纯固定优先级抢占阈值调度下的任务响应时间分析方法得到更加精确可调度性分析结果。     

不可抢占式EDF调度算法的可调度性分析

现有的不可抢占式EDF调度算法的可调度性分析判定条件限定实时任务的截止期必须等于其周期,限制了它的使用范围。论文突破这一限制,提出了更具一般性的可调度性分析判定充要条件。通过对可调度性判定充要条件的分析,提出了基于不可抢占式EDF调度算法的周期性实时系统可调度性分析算法。     

基于单调速率的可调度性判定改进算法

在单调速率调度策略的基础上,提出一种改进的任务集可调度性判定算法。该算法通过设定时钟变量模拟调度过程中的系统时钟,在时钟变量值增长过程中,根据任务优先级从高到低的顺序,分析各个任务的截止时间限的满足情况,判定任务的可调度性,从而确定任务集的可调度性。通过实例分析及与现有判定方法的比较,验证了该算法的正确性和高效性。     

一种不影响任务集合可调度性的优先级映射算法

采用静态优先级调度的实时系统中,当任务个数多于优先级个数时,只能给多个任务分配相同的优先级·现有分配算法增大了高优先级任务的最坏情况响应时间,可能造成任务集合不可调度·利用抢占阈值的调度算法,能在提高任务集合可调度性的同时,使用较少的线程·但所用优先级个数没有减少·提出了一种优先级映射算法———阈值段间映射法(threshold segment mapping,TSM),以及与之配合的事件驱动线程框架·证明了TSM是严格排序的·仿真结果表明,在保证任务集合可调度的前提下,TSM使用了比现有映射算法更少的优先级·     

改进的基于抢占阈值调度的任务响应时间分析方法

基于抢占阈值调度的任务响应时间分析方法是一种新型实时系统任务可调度性判定技术。然而已有的研究工作,有时对以前的任务请求检查过少,可能导致对响应时间估计过低。同时对任务响应时间的分析忽略了任务释放抖动和时钟嘀嗒调度对任务响应时间的影响,造成任务错过期限的现象,系统任务可调度性判定存在潜在的不精确因素。针对上述缺点不足,本文提出改进的基于抢占阈值调度的任务响应时间分析方法,在修正已有方法缺陷的同时,考虑任务释放抖动和时钟嘀嗒调度的影响,引入额外的时间需求,使用改进的任务参数计算系统任务时间需求函数。仿真对比结果表明,改进后的方法较单纯固定优先级抢占阈值调度下的任务响应时间分析方法得到更加精确可调度性分析结果。     

Feasibility analysis under fixed priority scheduling with limited preemptions

Preemptive scheduling often generates a significant runtime overhead that may increase task worst-case execution times up to 40%, with respect to a fully non-preemptive execution. In small embedded systems, such an extra cost results in longer and more variable response times that can significantly affect the overall energy consumption, as well as the system predictability. Limiting preemptions is often possible without jeopardizing schedulability. Although several authors addressed schedulability analysis under different forms of limited preemptive scheduling, current results exhibit two major deficiencies: (i) The maximum lengths of the non-preemptive regions for each task are still unknown under fixed priorities; (i) The exact response time analysis for tasks with fixed preemption points is too complex.     

一种新型实时调度算法研究

在许多片上特定应用系统中，任务多且切换频繁，任务切换开销大，有时甚至严重影响系统的可调度性．研究了动态可抢占门限调度算法，它通过初始门限值、动态门限值的计算和优化线程分配，实现了在处理器高利用率下，有效降低任务切换开销的目的，并相应地减少了对内存的需求．动态可抢占门限调度算法是将静态抢占门限算法与动态调度算法有机地结合在一起。完成了由静态到动态无缝转换．     

实时事务调度及静态可调度性分析

在类似闭环控制的硬实时数据库应用环境,实时事务具有一定的静态可预报性,其中实时事务的可调度性分析是维护实时数据库时间正确性的基础.通过利用抢占阈值,提出了一种新的实时事务处理模型,它集成了CPU调度和数据调度,实现离线并发控制,具有单阻塞的特征与好的静态可预测性,并有利于降低事务系统的负载和改善可调度性.进一步由此建立了实时事务的静态可调度性分析模型以及求最优可行调度的整数规划模型,该模型有利于达到实时事务调度的整体优化.     

An analysis of EDF schedulability on a multiprocessor

A new schedulability test is derived for preemptive deadline scheduling of periodic or sporadic real-time tasks on a single-queue m-server system. The new test allows the task deadline to be more or less than the task period, and is based on a new analysis concept, called a /spl mu/-busy interval. This generalizes a result of Goossens et al. [2003] that a system of periodic tasks with maximum individual task utilization u/sub max/ is EDF-schedulable on m processors if the total utilization does not exceed m(1 /sup max/)+u/sub max/. The new test allows the analysis of hybrid EDF-US [x] scheduling, and the conclusion that EDF-US[1/2] is optimal, with a guaranteed worst-case schedulable utilization of (m +1)/2.