基于组合优先级的自适应实时调度算法研究

在嵌入式实时操作系统中,由单个特征参数作为实时任务优先级的调度依据,并不能较好地描述系统中任务的关键性和紧迫性.提出一种基于组合优先级的自适应实时调度算法(SREDF),综合任务的截止期和CPU运行期设计任务的优先级,使截止期越早且CPU运行期越短的任务拥有最高优先级.处理器能有效地调度相同截止期的实时任务,并提前分析和预测任务能否完成.实验表明,该算法降低了任务调度的截止期错失率(MDP),并提高了任务调度的速度和效率.     

基于截止期错失率可预测的高利用率容错调度

现代导航与通信等实时系统经常面临着复杂的实时数字信号处理及信息交互需求,处理器处于高利用率状态.对于此类高利用率实时系统,传统的时间冗余容错通常会引发多个任务连续错失截止期的灾难性后果.针对高利用率情况,提出一种截止期错失率可预测的容错调度方法,截止期错失次数不大于出现错误的次数,消除了多个任务截止期连续错失的多米诺效应.进一步地在该方法中融合时间冗余方法的优点,提出了求解检测点上界位置的离线快速算法,有效地降低了截止期错失率.仿真实验表明,与目前已知的同类方法相比,该方法具有更低的截止期错失率.     

支持截止期敏感应用的数据流任务调度方法

当前,数据流上的实时处理系统大多关心平均元组延时最小化要求,而很少考虑每个元组的截止期要求.提出一种实时的自适应批任务调度策略--ATS(adaptive batch task scheduling),以支持时变突发的数据流上关键任务的严格截止期需求.ATS调度策略可以降低调度开销和过期处理开销,从而实现截止期错失率最小化和有效任务完成率最大化.提出了最优调度单位概念--批粒度,设计了闭环反馈控制机制,以在不可预测的数据流环境中自适应地动态选择最优批大小.理论分析和实验表明了ATS批调度策略的有效性和高效性.     

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

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

基于反馈控制的嵌入式实时系统调度算法设计

针对嵌入式实时系统在系统负载模型不确定的情况下系统的实时任务错过率过高以及调度稳定性差的问题,提出了一个基于反馈控制的调度模型.该模型主要由改进的多级队列调度器和3个控制器(准入控制器、执行等级控制器、比例积分微分(PID)控制器)组成.任务的错过率偏差反馈到PID控制器,产生相应的调整量并作用于其他两个控制器,对实时任务的执行等级进行调整, 经过调整的任务被调度器调度执行.在对模型中每个部件进行了一些结构调整和改进设计之后,将该调度模型应用于嵌入式可配置操作系统(eCos)中.实验结果表明,该模型降低了任务的时限错过率,同时解决了系统频频超载的问题.     

一种严格按比例派发服务的混合实时调度算法

在混合实时系统中,调度器必须既保证所有硬实时任务严格按照其时间约束在截止期内完成,又要尽可能地提高软实时任务和非实时任务的服务质量.提出了一种严格按比例派发服务器算法(RPDS),并以此为基础构建了一种层次式调度框架.RPDS将处理器时间流分成连续的小段,并在每一小段中强制为非硬实时任务分配一个时间片.实验结果表明,RPDS可以合理地为各种类型应用分配处理器时间,并且降低了实时任务的截止期错失率.     

一种任务优先级的综合设计方法

提出了一种基于优先级表设计的调度算法.将任务的相对截止期和空闲时间这两个特征参数结合起来,综合设计任务的优先级表,使得截止期越早或空闲时间越短,任务的优先级越高,而且任务的优先级由相对截止期和空闲时间惟一确定.对于任意一个任务,可通过对设计的优先级表进行二元多点插值获得相应任务的惟一优先级.与传统的EDF和LSF算法进行仿真比较,仿真结果表明,通过优先级表设计方法来确定任务的优先级,提高了任务调度的成功率,降低了任务截止期的错失率.该方法可应用于实时系统中实时任务的动态调度中.     

一种动态优先级实时任务调度算法

现有实时任务调度算法往往根据任务的时间属性或者价值确定任务优先级,较少同时兼顾任务的价值和执行紧迫性.文中根据任务的价值和剩余执行时间讨论任务的剩余价值密度,根据任务的截止期和空余执行时间分析任务的紧迫性;然后综合任务的剩余价值密度和执行紧迫性,提出了动态分派任务优先级的DPA策略;最后提出了基于DPA的抢占调度算法DRTP.DRTP算法分析了任务抢占调度的各种可能条件,分析了系统中可能出现的颠簸调度,并给出避免颠簸的条件.仿真实验结果显示,与其它同类算法相比,DRTP算法能够提高系统价值收益,降低任务截止期错失率,并大大减少任务抢占的次数.     

基于ISM的动态优先级调度算法

在嵌入式Linux操作系统的实时调度算法中,EDF调度算法不能解决负载过载问题。为此,引进对系统负载有着良好表现的SLAD算法和BACKSLASH算法。基于ISM算法思路,提出一种动态优先级调度算法。该算法能根据一段时间内负载过载的情况,灵活地调度EDF算法和SLAD算法,从而提高系统在正常负载和过载情况下的调度效率。对实时任务截止期错失率DMR指标的测试结果证明了其改进效果。     

基于多片FPGA的双优先级动态调度算法

针对单片现场可编程门阵列(FPGA)在处理高速网络中海量数据时存在效率低下的问题,结合多处理器的双优先级调度算法,在所构建的多片FPGA并行处理的高速数据采集和处理模型上,提出一种基于多片FPGA的双优先级动态调度算法,并对处于低优先级段的强实时周期任务提出一种最早截止期临界松弛调度(EDCL)算法。根据任务的松弛度确定任务的优先级,若提升时间到达时仍未完成,则将其提升到高优先级段; 对软实时周期任务,设置在中优先级段,通过延长当前任务截止期至动态模糊阈值进行调度。实验结果表明,该算法能很好地调度强实时周期任务,保证重要任务的优先执行,并能降低由于抢占造成的软实时周期任务错失率。     

Improving adaptivity and fairness of processing real-time tasks with QoS requirements on clusters through dynamic scheduling

In this paper, we consider the problem of scheduling a set of independent real-time tasks with QoS requirements on a cluster, in which the adaptivity and fairness are the two important performance metrics. Thereby, we propose a novel scheduling strategy named AFSS that can guarantee: 1) excellent adaptivity, i.e., more real-time tasks can be accepted when the system is in heavy workload, and real-time tasks have high QoS levels when the system is lightly loaded; 2) fairness, i.e., real-time tasks have fair QoS levels to hold smooth processing quality. The GS and LA algorithms in AFSS are discussed and analyzed. Further, several theorems are given to prove the effectiveness of AFSS.     

Multi-Dimensional Scheduling for Real-Time Tasks on Heterogeneous Clusters

Multiple performance requirements need to be guaranteed in some real-time applications such as multimedia data processing and real-time signal processing in addition to timing constraints.Unfortunately,most conventional scheduling algorithms only take one or two dimensions of them into account.Motivated by this fact,this paper investigates the problem of providing multiple performance guarantees including timeliness,QoS,throughput,QoS fairness and load balancing for a set of independent tasks by dynamic ...     

实时控制任务的模糊反馈调度系统研究

分析了实时控制任务的控制性能在不同控制阶段与处理器利用率需求间的关系,提出一种实时控制任务的模糊反馈调度系统.模糊控制器通过监测实时控制任务的误差及其变化率,查询模糊决策表,动态决定任务的优先级,反馈调度器根据优先级分配任务的利用率.仿真结果表明，在计算资源有限时，该方法能有效改善实时控制任务的控制性能.     

An intelligent scheduling system using fuzzy logic controller for management of services in WiMAX networks

The appearance of media applications with high bandwidth and quality of service requirements has made a significant impact in telecommunications technology. In this direction, the IEEE802.16 has defined wireless access systems called WiMAX. These systems provide high-speed communications over a long distance. For this purpose some service classes with QoS requirements are defined; but the QoS scheduler is not standardized in IEEE802.16. The scheduling mechanism has a significant effect on the performance of WiMAX systems for use of bandwidth and radio resources. Some scheduling algorithms have been introduced by researchers; but they only provide some limited aspects of QoS. An intelligent decision support system is therefore necessary for scheduling. In this paper a fuzzy based scheduling system is proposed for compounds of real-time and non-real-time polling services which provide QoS requirements and fairness in dynamic conditions. A series of simulation experiments have been carried out to evaluate the performance of the proposed scheduling algorithm in terms of latency and throughput QoS parameters. The results show that the proposed method performs effectively regarding both of these criteria and achieves proportional system performance and fairness among different types of traffic.     

基于多参数的μC/OS-Ⅱ任务优先级和调度方法

在μC/OS-Ⅱ进行实时任务调度时,可以使用单一的调度算法分配任务优先级。优先级判定标准的片面性、“错过率”较高的截止期,影响了μC/OS-Ⅱ的实时调度性能。该文提出了多参数任务优先级分配策略和μC/OS-Ⅱ任务的调度方法,实验证明,该方法截止期的平均错过率为60.1%,有效地改善了μC/OS-Ⅱ的实时调度性能。     

Job scheduling algorithm based on Berger model in cloud environment

Considered the commercialization and the virtualization characteristics of cloud computing, the paper proposed for the first time an algorithm of job scheduling based on Berger model. In the job scheduling process, the algorithm establishes dual fairness constraint. The first constraint is to classify user tasks by QoS preferences, and establish the general expectation function in accordance with the classification of tasks to restrain the fairness of the resources in selection process. The second constraint is to define resource fairness justice function to judge the fairness of the resources allocation. We have expanded simulation platform CloudSim, and have implemented the job scheduling algorithm proposed in this paper. The experimental results show that the algorithm can effectively execute the user tasks and manifests better fairness.     

Event-Triggered Real-Time Scheduling of Stabilizing Control Tasks

In this note, we revisit the problem of scheduling stabilizing control tasks on embedded processors. We start from the paradigm that a real-time scheduler could be regarded as a feedback controller that decides which task is executed at any given instant. This controller has for objective guaranteeing that (control unrelated) software tasks meet their deadlines and that stabilizing control tasks asymptotically stabilize the plant. We investigate a simple event-triggered scheduler based on this feedback paradigm and show how it leads to guaranteed performance thus relaxing the more traditional periodic execution requirements.     

基于中间件的实时内存调度

在数据密集型实时监测系统中,任务需要通过分配内存来存储和处理动态变化的信息。该文提出了一种基于中间件的新型内存调度器,通过反馈驱动来调节实时任务的内存分配,与受控任务保持平滑的连接,开放结构允许系统设计人员增加或修改内存管理策略。测试结果表明,内存调度器引起的开销较小,能有效地协调资源共享冲突。     

异构集群系统中具有QoS 需求的实时任务容错调度

容错调度是调度问题中一个重要的研究内容,是提高系统可靠性的有效手段.目前已有很多集群系统中实时任务的容错调度算法,但是这些算法都没有考虑到任务的QoS需求问题.提出了一种异构集群系统中具有QoS需求的实时任务容错调度算法FTQ(fault-tolerant QoS-based scheduling).该算法采用主版本/副版本(primary/backup,简称PB)技术,综合考虑了任务的时间限制、任务的QoS需求、系统的可靠性和系统资源的利用率,能够自适应地根据系统负载情况动态地调整任务的QoS级别和副版本的执行模式,从而提高了系统的灵活性、可靠性、可调度性和资源的利用率.对系统的可靠性进行了定量分析,并将其引入到容错调度算法中,提高了系统的可靠性.同时,在调度过程中尽量提前主版本的开始时间,推迟副版本的开始时间,以使任务的副版本采用被动执行模式或者使任务主版本和副版本的重叠部分尽量少,提高了资源的利用率.此外,采用了副版本重叠技术,并分析了副版本的最晚开始时间及其约束条件,提高了任务的调度成功率.通过大量的模拟实验,对FTQ,NOFTQ和DYFARS算法进行了比较.实验结果表明,FTQ算法的性能优于其他方法,具有更好的调度质量.