一种基于EDF算法的多处理器实时调度算法

多处理器系统实时调度理论是目前实时系统研究的热点问题。EDF调度算法是目前流行的实时调度算法,有很多优点,但在多处理器系统应用中存在问题。论文研究了EDF调度算法在多处理器系统中的调度理论,在此基础上,提出了一种基于EDF算法的优先级驱动实时调度算法,算法充分利用了EDF调度算法的优点,较大程度地克服了EDF算法在多处理器系统中的调度缺点,并提供了较好的实时调度性能。     

片上多处理器系统的多线程调度策略

本文提出了一种多线程调度策略,解决片上多处理器系统的线程分配问题。实验证实,本文的线程调度策略有效地实现了系统的负载均衡。     

多媒体服务器混合磁盘调度策略

基于多媒体服务器的性能要求，提出了一种自适应的混合磁盘调度策略DRT-window．它既能满足实时请求对实时性的要求，根据实时请求的截止期动态选择窗口大小；又能在其松弛度内尽努力(best-effort)地服务非实时请求，从而减少非实时请求的响应时间。DRT-window采用了两级层次调度方案：第一层为不同类型的请求采用各自适合的调度策略；第二层为混合请求调度嚣，混合调度第一层中的不同类型的请求。通过性能比较和理论证明，表明此混合磁盘调度策略能在保证实时请求无抖动执行的同时，尽量地减少非实时请求的响应时间。     

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

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

多核片上系统的高效软硬件划分及调度算法

软硬件划分与调度是软硬件协同设计的关键环节,是经典的组合优化问题。本文针对调度与软硬件划分问题提出一种高效的启发式算法。调度算法根据任务的出度及软件计算时间对任务赋予不同的优先级,出度越大,优先级越高,出度相同的情况下,软件计算时间越大,优先级越高。划分算法首先寻找关键路径,然后将关键路径上具有最高受益面积比的任务交由硬件去实现。每次迭代更新当前关键路径的调度长度及剩余硬件面积。继续循环,直到剩余的硬件面积不再满足关键路径上的任何一个软件任务所需的硬件面积的要求为止,这样使得硬件面积的使用率比较高。实验表明,该算法对已有算法的改进可达到38%。     

多处理器系统的在线节能调度算法

随着多处理器系统计算性能的提高,能耗管理已变得越来越重要,如何满足实时约束并有效降低能耗成为实时调度中的一个重要问题。基于多处理器计算系统,针对随机到达的任务,提出一种在线节能调度算法(OLEAS)。该算法在满足任务截止期限的前提下,尽量将任务调度到产生能耗最少的处理器,当某个任务在所有处理器上都不能满足截止期限要求时,则调整处理器之间的部分任务,使之尽量满足截止期限要求。同时,OLEAS尽量使单个处理器上的任务按平均电压/频率执行,以降低能耗,只有当新到任务不满足截止期限要求时,才逐个调高前面任务的电压/频率。模拟实验比较了OLEAS、最早完成时间优先(EFF)、最高电压节能(HVEA)、最低电压节能(LVEA)、贪心最小能耗(MEG)和最小能耗最小完成时间(ME-MC)的性能,结果表明OLEAS在满足任务截止期限和节省能耗方面具有明显的综合优势     

多处理器系统的实时调度算法研究

调度算法是实时系统的关键技术,选取何种算法调度实时任务,这将直接影响着系统的实时响应能力。多处理器系统有局部调度和全局调度两类实时调度方法,以PFair公平调度为代表的全局调度是当前研究的热点。研究了典型局部调度EDF-FF算法和典型PFair公平调度PD^2算法,比较了多处理器系统采用PD^2算法相对于采用EDF-FF算法实现任务调度的优点,分析了由于任务频繁抢占和迁移,PD^2算法引起的时间消耗,估计并比较了PD2算法和EDF-FF算法的时间消耗,最后得出结论：在共享内存的多处理器系统中,公平调度算法是实时任务调度的比较理想的选择。     

混合关键性多核系统调度综述

混合关键性多核系统调度主要考虑划分任务到每个核和任务在核上的调度两个大方面,以满足嵌入式系统安全性和可靠性的需求.由于嵌入式系统在硬件等多方面的约束,混合关键性得到了学术界和企业界的广泛关注,在提高任务调度率和多核系统资源利用率方面展开了许多研究.而不同的任务调度方法和划分方法对提高利用率方面有不同的结果,为此从改善低关键任务的调度、提高每个核的资源利用率、任务执行时的干扰、多核的划分策略等方面,对近年来的混合关键性任务调度进行了详细的分析和总结,并指出了当前研究的不足和未来的研究方向.     

一种有到达时问的多处理器混合流水车间调度的遗传算法

有到达时间的多处理器混合流水车间调度问题在实时机器视觉系统等领域有广泛的应用.这一问题是NP-困难的.鉴于以上原因,给出一种遗传算法.对不同的交叉算子和变异算子以及涉及的参数的不同取值进行试验,并对试验的结果进行分析和讨论,从而给出最好的参数组合.     

一种有到达时间的多处理器混合流水车间调度的遗传算法

有到达时间的多处理器混合流水车间调度问题在实时机器视觉系统等领域有广泛的应用。这一问题是NP-困难的。鉴于以上原因,给出一种遗传算法。对不同的交叉算子和变异算子以及涉及的参数的不同取值进行试验,并对试验的结果进行分析和讨论,从而给出最好的参数组合。     

Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors

The scheduling of systems of periodic tasks upon multiprocessor platforms is considered. Utilization-based conditions are derived for determining whether a periodic task system meets all deadlines when scheduled using the earliest deadline first scheduling algorithm (EDF) upon a given multiprocessor platform. A new priority-driven algorithm is proposed for scheduling periodic task systems upon multiprocessor platforms: this algorithm is shown to successfully schedule some task systems for which EDF may fail to meet all deadlines.     

容错最早时限优先调度

最早时限优先调度（EDF）是最优的动态可抢占先级实时调度算法,具有灵活、简单和高效的特点,但并没有考虑实时系统的容错要求。本文提出一种容错EDF算法,实现在规定时间段内的单个错误容错。本文详细分析了该算法的容错机制,证明了该算法的正确性,并给出了算法的可调度条件。     

多特征协调的实时调度算法

目前大多数实时调度算法都依据单一的特征参数确定任务优先级,本文提出一种基于多特征协调的实时调度算法,对特定高优先级任务优先处理,并且对其他任务的调度不产生任何影响。同时,在系统超载的时候,有效避免了EDF算法性能的急剧下降。实验结果表明,该算法有效地保证了特定任务的调度优先级,相对于EDF算法性能有明显改进。     

通信竞争的混合关键级系统多DAG动态调度策略

以多DAG模型研究通信竞争的混合关键级系统(mixed-criticality systems)的调度问题是适应现代汽车电子系统异构化和分布式的需要.首先实现通信竞争环境下“向上排序值(upward rank value)”和“最早完成时间(earliest finish time)”中时间的精确分析,以适应系统中计算与网络均异构,且任务与消息的同步特征.接着提出公平策略的多DAG动态任务与消息调度F_MDDTMS算法,以降低系统的调度长度;提出关键级策略的多DAG动态任务与消息调度C_MDDTMS算法,以确保高关键级应用的实时性;结合F_MDDTMS算法和C_MDDTMS算法,提出混合关键级策略的多DAG动态任务与消息调度MC_MDDTMS算法,既确保混合关键级系统中高关键级应用的实时性,又使得低关键级应用得到积极的处理.实例分析和实验结果验证了提出的算法在调度长度、不公平性、最差响应时间和实时性上的优越性.     

Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems

The utilization bound for earliest deadline first (EDF) scheduling is extended from uniprocessors to homogeneous multiprocessor systems with partitioning strategies. First results are provided for a basic task model, which includes periodic and independent tasks with deadlines equal to periods. Since the multiprocessor utilization bounds depend on the allocation algorithm, different allocation algorithms have been considered, ranging from simple heuristics to optimal allocation algorithms. As multiprocessor utilization bounds for EDF scheduling depend strongly on task sizes, all these bounds have been obtained as a function of a parameter which takes task sizes into account. Theoretically, the utilization bounds for multiprocessor EDF scheduling can be considered a partial solution to the bin-packing problem, which is known to be NP-complete. The basic task model is extended to include resource sharing, release jitter, deadlines less than periods, aperiodic tasks, non-preemptive sections, context switches, and mode changes.     

A Scheduling Extension Scheme of the Earliest Deadline First Policy for Hard Real-Time Uniprocessor Systems Integrated on Posix Threads Based on Linux

The Linux operating system has been employed to execute numerous real-time applications. However, it is limited to support soft real-time systems by two scheduling policies: First-In-First-Out and Round Robin. For real-time systems with critical constraints, the soft real-time support and these scheduling policies are still insufficient. In this work, the Earliest Deadline First scheduling policy, which has been shown in theory to be an optimal one in uniprocessor systems, is introduced as an extension of the Linux kernel. This policy is implemented into the real-time class, without the necessity of defining an additional class. The Linux kernel affords capabilities of a hard real-time operating system by an RT-Preempt patch, enabling the use of Linux to implement hard realtime systems. The integration is compliant with the POSIX real-time and thread standards, ensuring applications portability, employing the GLIBC library. In order to validate the proposed implementation, a set of experiments is conducted, showing that a real-time system that cannot be feasibly scheduled using existing policies, attains feasibility when it is scheduled using the integrated Earliest Deadline First policy.     

基于总线的开放式控制系统调度策略

提出“基于改进EDF的模糊反馈调度策略”,并应用于基于总线的开放式控制系统。设计了一个适用于此类总线控制架构的任务调度方案,由任务截止期、任务重要性以及传输误差和响应时间的综合影响来动态调节任务优先级,用以解决由引入总线而导致的响应速度慢、总线阻塞时的丢包问题。通过对机器人的控制实验验证了所提出调度策略的可行性。实验结果表明,加入调度模块后控制系统的响应时间和丢包率都有显著改善,系统的实时性得到了提高。     

TinyOS中DSA调度策略的研究

针对TinyOS任务调度采用非剥夺的先来先服务调度策略,而产生的系统紧急任务不能及时得到响应及节点吞吐量下降情况,该文提出一种新的可抢占时限短作业调度策略——DSA。在绝对时限前执行硬实时任务,满足了系统对实时任务的响应要求,提高处理器的响应速度,对软实时任务实行短作业优先调度策略,提高系统的吞吐量。在TinyOS上测试表明,DSA策略在不影响TinyOS原有性能的情况下,改进了传感器网络承担实时性任务的运行效果。     

队头阻塞优化的EDF可重构任务调度算法

针对最早截止时刻优先(earliest deadline first,EDF)调度算法队头阻塞任务导致资源利用率和配置端口复用率低下的问题,提出一种队头阻塞优化的EDF实时调度算法.通过定义无效阻塞任务并引入无效阻塞任务丢弃策略,提前判定和丢弃无法调度成功的任务,以利于后续任务调度;通过定义队头阻塞任务最早布局成功时刻...     

Scheduling Messages with Earliest Deadline Techniques

Thispaper discusses the applicability of earliest deadline schedulingtechniques to local area networks. The focus is on controllerarea networks (the only standard that allows direct implementation)although a comparison is tried with other possible implementationson different network topologies (and contention resolution methods).Message scheduling follows the well-known EDF algorithm. Thepaper discusses the limitations and the problems in the implementationof the algorithm on standard controller area network protocols.Then, it presents a short study on the comparative effectivenessof other contention resolution methods modeled on the standardsToken-ring and Carrier Sense Multiple Access-Collision DetectionCSMA-CD (all implementing the earliest deadline scheduling policy.)Finally, the paper shows how to compute an optimal packet sizewith respect to the guaranteeability of the real-time properties,exploiting the trade-off between preemptability and efficiency.