改进的最小空闲时间优先调度算法

最小空闲时间优先(least slack first,简称LSF)算法结合任务执行的缓急程度来给任务分配优先级.任务所剩的空闲时间越少,就越需要尽快执行.然而,LSF算法造成任务之间的频繁切换或严重的颠簸现象,增大了系统开销,并限制了其应用.在调度策略中设置抢占阈值可以减少任务之间的切换,但现有的抢占阈值设置方法因受到固定优先级的限制而不适用于LSF算法.为了减轻LSF算法的颠簸现象,基于抢占阈值的思想,提出适用于LSF算法的抢占阈值分配方法,动态地给每个任务配置抢占阈值.任务的抢占阈值是随着任务执行的缓急程度不同而动态地变化的,而且不受任务个数的限制.仿真结果表明,通过对LSF算法的改进,任务之间的切换大大减少,同时降低了任务截止期错失率.该改进型算法对设计和实现实时操作系统具有一定的参考价值.

基于动态抢占阈值的实时调度

具有抢占阈值的调度算法集非抢占调度和纯抢占调度的特点 ,既减少了由于过多的随意抢占造成的CPU资源浪费 ,又保证了一定的任务截止期错失率及CPU资源利用率 已有的工作基本集中于讨论任务集完全给定 ,任务数、任务的优先级及任务的抢占阈值在调度前已完全确定 ,而且要求不同的任务具有不同的优先级 提出的具有抢占阈值的调度算法 ,完全放松了对这些条件的限制 ,即任务的个数不确定 ,任务的优先级及其抢占阈值在调度过程中可以动态地变化 最后以常用的LSF调度策略为例 ,结合动态的抢占阈值进行仿真 仿真结果表明 ,对于不确定的任务集、任务优先级和抢占阈值 ,利用具有抢占阈值的动态调度算法 ,降低了任务截止期错失率。

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

在实时系统中,抢占在提高系统灵活性的同时带来额外的系统开销,特别在多处理器平台上抢占导致的作业迁移会造成相当大的性能下降,减少不必要的抢占是硬实时系统研究的重要方向.抢占阈值调度是处于抢占调度和不可抢占调度之间的一种混合调度方法,在保持调度能力的基础上限制抢占.基于截止期分析建立了多处理器硬实时系统抢占阈值调度的可调度性判定条件,针对抢占阈值调度提出一种改进的优先级分配算法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*算法能够有效地提高硬实时系统的容错能力.

Linux中一种改进的实时调度算法及其应用

在实时操作系统中,调度算法起着关键性的作用,然而调度算法的开销与系统的调度性能之间经常是一对矛盾。就此问题,结合最新版Linux2.6内核任务调度的特点,提出了一种改进的最小裕度优先(LSF)算法。针对LSF算法中因任务间的频繁切换造成系统开销增大的缺点,通过采用适当的抢占阈值策略减少"颠簸"现象,提高了Linux2.6内核的实时性。

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

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

一种采用抢占阈值的软实时动态调度策略PT-STDS

抢占式实时任务调度,其任意抢占会浪费系统资源而影响调度性能;有必要尽量减少任务间的无效抢占.针对软实时任务的特点,提出一种基于抢占阈值的动态调度策略PT-STDS.首先,PT-STDS策略考虑软实时任务的空闲时间和价值密度,提出综合两者的优先级构造函数.其次,PT-STDS策略根据任务的响应时间和任务间的抢占关系,确定任务的抢占阈值.通过设置任务抢占阈值减少较低优先级任务被抢占的机率,以提高整个系统任务间的有效抢占和执行完成率.实验证明,在软实时系统环境下,PT-STDS策略能够有效提高任务成功率、减少软实时任务的延迟时间,并提高系统总收益.

基于动态抢占阈值的LSF调度算法

在最小空闲时间优先(LSF)调度算法中,当任务集中有多个任务的优先级相同或相近时,过多的上下文切换会产生"颠簸"现象,从而大幅增加系统开销。为此,结合LSF算法的特点,通过设计合理的动态抢占阈值,提出一种改进的调度算法DPTLSF。仿真结果表明,改进的算法能够大幅减少"颠簸"现象的发生,降低任务集的截止期错失率。

抢占阈值调度的功耗优化

DVS(Dynamic Voltage Scaling)技术的应用使得任务执行时间延长进而使得处理器的静态功耗(由CMOS电路的泄露电流引起)迅速增加.延迟调度(Procrastination Scheduling)算法是近年提出用于减少静态功耗的有效方法,它通过推迟任务的正常执行来尽可能长时间地让处理器处于睡眠或关闭状态,从而避免过多的静态功耗泄露.文中针对可变电压处理器上运用抢占阈值调度策略的周期性任务集合,将节能调度和延迟调度结合起来,提出一种两阶段节能调度算法,先使用离线算法来计算每个任务的最优处理器执行速度,而后使用在线模拟调度算法来计算每个任务的延迟时间,从而动态判定处理器开启/关闭时刻.实例研究和仿真实验表明,作者的方法能够进一步降低抢占阈值任务调度算法的功耗.

优先级有限时的单处理器静态优先级调度

静态优先级调度在实际应用中经常受到系统支持的优先级个数的影响,当任务个数多于系统优先级个数时,需要将几个任务优先级映射成一个系统优先级.这可能引起优先级映射问题,使映射前可调度的系统(任务集合)在映射后变得不可调度.解决这一问题需要减少时间复杂度的映射算法和判定映射后任务可调度性的充分必要条件主要存在3种映射算法:(1)按照任务优先级递减顺序进行映射的DPA(decreasingpriorityassignment)算法;(2)按照优先级递增顺序进行映射的IPA(Increasingpriorityassignment)算法;(3)阈值段间映射法(thresholdsegmentmapping,简称TSM).描述了3种算法的实现和判定条件,论述并证明了算法特性,分析并通过仿真实验比较了算法的性能,最后总结了3种算法各自的适用场合.比较结果和结论对实时嵌入式系统的设计和实现具有一定的参考价值.

基于软件容错的抢占阈值调度算法设计与仿真

为了提高硬实时系统的容错能力,同时减少任务间的抢占次数,基于软件容错模型提出了抢占阈值容错调度算法(FT-FPPT).为了获得系统中任务抢占阈值分配的最佳策略,基于任务最坏响应时间的可调度性分析,提出了一种最优的抢占阈值配置搜索算法(PTCSA).PTCSA算法能够将搜索空间由O(n!)减少到O(n 2),其中n为任务的个数.最后给出了该算法的最优性证明.仿真实验表明,抢占阈值容错调度算法能够在抢占式容错调度算法的基础上,进一步提高系统的容错能力。

云模型优化LSF调度算法的研究

为了解决LSF调度算法在实时调度中由颠簸现象引起的调度实时性差、浪费系统资源的问题,在LSF算法中引入一个任务重要度系数,采用云模型对任务重要度系数和裕度进行定量表示,并通过由重要度系数云和裕度云两个任务特征参数云模型共同确定的二维云模型,为每个任务设定一个抢占阈值,当某一就绪任务要抢占当前任务时,必须要满足它的优先级高于当前任务的抢占阈值。仿真结果表明,采用云模型优化后的LSF算法不仅有效解决了颠簸现象,而且能使紧急且重要的任务优先运行。

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

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

两种改进的EDF软实时动态调度算法

软实时系统中,任务的随意抢占浪费了CPU资源,过多的任务丢失降低了系统的调度性能.文章引入"动态模糊阈值"概念,提出了两种新的类似EDF调度的模糊阈值调度算法.两种算法在任务执行过程中,分别通过缩短和延长当前任务截止期至动态模糊阈值的方法节约资源、提高任务完成率.给出模糊阈值的临界值计算公式,分析算法的可调度性,进行仿真与性能分析比较.结果表明,与EDF调度算法比较,两种算法有效地提高了重要任务的完成率,当截止期被延长时,任务的错失率明显降低,当截止期被缩短时,任务间的切换次数大大减少.因此,新算法提高了CPU的利用率,改善了系统的实时性能.

能量收集信息物理融合系统抢占阈值调度

在能量收集信息物理融合系统(energy harvesting based cyber-physical systems,EHCPS)中,其能量管理体系结构不同于传统电池供电嵌入式系统,任务调度策略需要考虑能量收集单元的能量输出、电池的能量存储和计算任务的能量消耗.实时任务在满足能量约束的情况下,才能满足时间约束.传统抢占阈值调度的可调度性分析没有考虑任务的能量属性,其阈值分配算法也不适用于EHCPS.针对此问题,提出了一种能量相关抢占阈值调度策略(energy related preemption threshold scheduling,ERPT),在可调度性分析中融入任务能耗属性和能量补充能力,并给出了阈值分配算法,为抢占阈值调度在EHCPS中的应用提供了一种解决方法.通过与目前现有的2个经典调度策略进行比较,验证了ERPT策略能够有效减少任务抢占.

基于负载执行紧迫度的实时补偿任务调度策略TSCTTL

针对支持补偿性的实时任务模型,分析实时任务的系统负载执行紧迫度,进而提出基于负载执行紧迫度的实时补偿任务调度策略TSCTTL;通过实验仿真表明,依据实时任务的负载执行紧迫度来调度补偿任务,降低了系统任务的截止期错失率,并提高了系统收益。

面向对象实时多任务系统的优化实现模型

论文提出了一种基于抢占门限的实时多任务系统的优化实现模型,它同时具有低开销与高可调度性。该模型扩展了固定优先级调度模型,同时通过实现模型中线程数的减少实现了运行时的低开销。文中同时也讨论了互不抢占分组的实现算法及每个任务最大抢占门限的分配算法。

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

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

基于抢占阈值的嵌入式实时数据库事务调度

提出了一种嵌入式实时数据库事务处理模型 ,把抢占阈值应用到固定优先级可抢占的实时事务调度之中 ,并提出了一种冲突避免的实时事务并发控制协议 ,使实时事务调度和并发控制高度集成 ,降低了系统的事务管理开销 .通过事务的可调度性分析 。

一种提高构件化嵌入式操作系统性能的方案

本文分析了现有构件化嵌入式操作系统所用调度算法存在的缺点,提出抢占阈值调度算法是更为合适的算法。通过仿真实验比较抢占阈值调度算法、非抢占式调度算法和FIFO(First-In-First-Out)调度算法的性能,证明了上述结论。通过分析现有嵌入式系统构件模型的特点,提出了一种构件模型以及将构件映射成任务的方式,还提出了一种设计方法。整个方案能提高构件化嵌入式操作系统的性能。