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

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

混合关键性系统寿命优化的任务调度算法

为延长混合关键性系统的设备寿命,考虑瞬时性、永久性2种故障并采取容错方案满足安全需求,提出一种两阶段解决方案。利用动态电压频率调整技术为每个任务确定运行频率,确保热循环对设备寿命的损害最小。使用重执行技术,在可靠性约束和可调度性约束下对设备寿命进行分析,构建一个多目标非线性规划问题,从而得到最优解。仿真结果表明,与RAND、MFPR、MRPF、DPAS 4种算法相比,该算法在保证系统可调度与可靠性的前提下,可使系统寿命最多延长47%。     

实时调度EDZL算法的可调度性判定

针对多处理器实时调度中的EDZL调度算法,利用多任务之间的相互干涉关系,找出与多处理器之间的时间约束条件,提出了一种可调度性判定的方法,并对给出的判定方法进行了证明。给出了一种判定多处理器实时EDZL可调度性的算法,这种方法可在设计多处理器实时系统时使用。     

端到端时间约束的实时任务动态调度算法

在单处理机系统中,由于计算高优先级任务抢占的时间相对比较简单,所以单处理机调度理论取得了长足的进步.提出一个端到端时间约束的实时任务调度算法,当实时任务到达系统时,算法为任务的每个子任务在相应的处理机上预约一定的计算资源,把端到端的多处理机调度问题转换成单处理机调度问题,从而可以利用单处理机调度理论判定实时任务的可调度性.实验表明,该算法明显地提高了CPU利用率和任务接收率.     

实时系统中的非定期任务调度算法综述

非定期任务调度是实时系统中的一个重要研究内容,综述了实时系统中非定期任务调度算法的研究与进展,按照这些算法的特征分为基于服务器的算法与基于空闲时间的算法两大类别,并着重对每个类别中的不同算法的特征与性能进行了分析,通过对这些算法的比较与分析,希望为实时系统的研究与开发者提供有意义的参考,最后还给出了非定期任务调度进一步研究的思路与建议。     

多处理器EPDFPfair算法的可调度性判定

针对多处理器实时调度中的最早伪时限优先(EPDF)Pfair算法,分析了EPDF算法在M个处理器平台上的可调度利用率约束,根据基于利用率的充分可调度性判定,提出了一种改进的可调度性判定方法。这种方法可以得到更多的可调度任务集,从而使得满足判定的强实时系统和使用tie-breaking规则困难的动态任务系统的调度有较小的开销。实验结果表明,改进的可调度性判定方法增加了判为可调度的任务集数量,具有较好的性能。     

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

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

基于模糊理论的多媒体实时调度算法研究

多媒体系统中的任务调度采用的是实时调度算法。传统的实时调度总是假设任务的属性是精确确定的并能够提供令人满意的结果，但实际任务的属性总是存在一个模糊的范围。文中在传统实时EDF算法的基础上，提出了基于模糊理论的可抢占式的实时调度算法(FEDF算法)。此算法的主要设计目标是在实时任务属性模糊条件下尽可能地减少任务丢失率，提高保证比率，实验结果表明该算法达到了预定的目标。     

多处理器固定优先级算法的可调度性分析

针对多处理器实时调度中的固定优先级(FP)调度算法,提出了一种改进的可调度性判定方法。引入Baruah的最早截止期优先(EDF)窗口分析框架,将高优先级任务带入作业的最大数量限定为m-1(m为处理器个数),进而对任务的干涉上界进行重新界定,并由此得到一个更加紧密的可调度性判定充分条件。仿真实验结果表明,该方法增加了通过判定任务集的数量,体现出更优的可调度判定性能。     

基于动态优先级策略的最优软非周期任务调度算法

周期任务与非周期任务的混合调度是实时调度研究的一个重要方向 通过定义“调度”和“逆调度” ,对实时周期任务集在使用EDF算法调度时的可挪用时间进行分析 ,求出了周期任务集在使用EDF调度时的最大可挪用时间 在此基础上 ,提出用于缩短非周期任务响应时间和周转时间的调度算法———ISA(idlestealingalgorithm) ISA算法充分使用最大可挪用时间 ,在保证周期任务满足最后期限的同时能取得非周期任务的最优响应时间和周转时间 证明了ISA算法的最优性 ,并使用仿真实验进行了性能验证     

A non-preemptive scheduling algorithm for soft real-time systems

Real-time systems are often designed using preemptive scheduling and worst-case execution time estimates to guarantee the execution of high priority tasks. There is, however, an interest in exploring non-preemptive scheduling models for real-time systems, particularly for soft real-time multimedia applications. In this paper, we propose a new algorithm that uses multiple scheduling strategies for efficient non-preemptive scheduling of tasks. Our goal is to improve the success ratio of the well-known Earliest Deadline First (EDF) approach when the load on the system is very high and to improve the overall performance in both underloaded and overloaded conditions. Our approach, known as group-EDF (gEDF) is based on dynamic grouping of tasks with deadlines that are very close to each other, and using Shortest Job First (SJF) technique to schedule tasks within the group. We will present results comparing gEDF with other real-time algorithms including, EDF, Best-effort, and Guarantee, by using randomly generated tasks with varying execution times, release times, deadlines and tolerance to missing deadlines, under varying workloads. We believe that grouping tasks dynamically with similar deadlines and utilizing a secondary criteria, such as minimizing the total execution time (or other metrics such as power or resource availability) for scheduling tasks within a group, can lead to new and more efficient real-time scheduling algorithms.     

基于RM与EDF的实时混合调度算法研究

通过对实时系统中静态调度算法RM和动态调度算法EDF的研究与分析,针对两种调度算法在实际应用中的问题,提出了一种基于阈值δ的混合调度算法,将RM与EDF调度算法相结合,并从数学角度描述了混合调度算法的可调度性与实时任务的周期、执行时间等属性之间的关系,给出了混合调度算法可调度性的充分必要条件。最后用实验验证了混合调度算法的有效性。     

Schedulability issues for EDZL scheduling on real-time multiprocessor systems

EDZL (Earliest Deadline first until Zero Laxity) is an efficient and practical scheduling algorithm on multiprocessor systems. It has a comparable number of context switch to EDF (Earliest Deadline First) and its schedulable utilization seems to be higher than that of EDF. Previously, there was a conjecture that the utilization bound of EDZL is 3m/4=0.75m for m processors. In this paper, we disprove this conjecture and show that the utilization bound of EDZL is no greater than m(1−1/e)≈0.6321m, where e≈2.718 is the Euler's number.     

开放式实时系统双层调度框架的一种改进方案

分析了开放式实时系统双层调度框架的调度特点,指出了其仅适用于硬实时环境的缺陷。在保证硬实时应用可调度性的基础上,针对硬实时和软实时应用的不同特点提出了一种改进方案,增加了软实时应用的处理,拓展了原方案的适用范围,完善了开放式实时系统的双层调度框架,最后用理论证明与仿真实验验证了改进方案的有效性。     

多处理器系统实时调度的可预测性

在多处理器实时系统中,由于调度的不规则性,系统的可预测性判定问题尤为重要。针对多处理器系统中实时任务调度的可预测性问题,给出了不可预测的实时任务集反例,证明了一种可预测的实时任务集合。对于多处理器实时系统中常用的最早截止期零松弛调度算法(earliest deadline zero laxity,EDZL)的可预测性,利用EDZL算法的基本性质,用一种简捷的方法证明了EDZL算法是可预测的。通过仿真系统验证了证明的正确性,该方法可用于多处理器及分布式实时系统的设计和验证。     

面向分布式实时系统的安全驱动调度算法研究

针对现有实时调度算法无法适应动态安全需求的问题,构建了一种安全驱动调度模型,该模型从系统安全级别、系统安全服务和任务安全策略三个方面描述了实时系统的动态安全需求,并设计了一种基于安全驱动的实时任务调度器框架。以该模型和框架为基础,提出了一种安全驱动调度算法(Security Driven Scheduling Algorithm,SDSA)。从全局角度对新到达任务进行可调度性检查,并将可调度任务分配到合适的处理机上运行。按照系统安全级别来动态调整已分配到各处理机上实时任务的安全策略,使其达到安全性和可调度性的最优平衡。采用优先级抢占式策略对各实时任务进行调度。仿真结果表明,SDSA算法与其他同类算法相比,在系统动态安全需求的适应性、关键任务的可调度性以及安全防危能力等方面具有较好的表现。     

多处理器系统动态调度负载均衡节约算法

将任务集与处理器处理能力之间的匹配关系作为研究调度算法性能的重要因素,建立了相应的任务-处理器模型,以描述多处理器系统的负载状况.描述了多处理器系统任务可调度的必要条件,设计实现了任务集的生成方法.对节约算法进行改进,提出了负载均衡的节约算法.所提出的算法可在保证调度成功率的前提下,缩短任务的平均响应时间和调度长度,并均衡地提高处理器的利用率.     

基于信道状态的WiMAX系统实时调度算法

介绍了M-LWDF、EXP和CD-EDD三种经典的实时调度算法,并在此基础上提出一种基于信道状态的WiMAX系统的实时调度算法CBRTS(channel-based real-time scheduling)。该算法核心思想是在数据链路层中考察物理层信道的传输条件,从而进一步将有限的无线资源更加合理地分配给用户。仿真结果表明,提出的算法具有更高的吞吐量、更小的时延和丢包率,能满足实时业务的QoS要求。