两种经典实时调度算法的研究与实现 被引量：19

1

作者 邢群科 郝红卫 温天江 《计算机工程与设计》 CSCD 北大核心 2006年第1期117-119,123,共4页

速率单调(RM)调度和最早截止期限优先(EDF)调度在实时调度领域占有重要低位。基于一个x86体系结构的小系统上设计实现RM和EDF调度算法,并在不同的工作负载下,以任务截止期错失率作为衡量不同任务调度算法性能优劣的指标,对两种算法进行... 速率单调(RM)调度和最早截止期限优先(EDF)调度在实时调度领域占有重要低位。基于一个x86体系结构的小系统上设计实现RM和EDF调度算法,并在不同的工作负载下,以任务截止期错失率作为衡量不同任务调度算法性能优劣的指标,对两种算法进行了性能分析和比较。在通常情况下,RM和EDF都可以保证任务成功调度,EDF算法可承受较多的工作负载。但是随着负载的增加,EDF算法性能急剧下降,到一定过载程度,EDF算法性能低于RM算法。 展开更多

关键词 实时调度 速率单调调度 最早截止期限优先调度 截止期限 截止期错失率

下载PDF 职称材料

嵌入式操作系统多策略调度模型

2

作者 罗君 陈双龙 《指挥控制与仿真》 2006年第6期63-66,共4页

分析了目前嵌入式操作系统调度策略的现状,指出了传统调度方法的不足之处,给出了多策略调度模型,该模型根据进程的属性参数决定采用哪种调度算法。多策略调度模型采用两级调度方案,即在原传统调度方法的基础上增加一级调度。一级调度确... 分析了目前嵌入式操作系统调度策略的现状,指出了传统调度方法的不足之处,给出了多策略调度模型,该模型根据进程的属性参数决定采用哪种调度算法。多策略调度模型采用两级调度方案,即在原传统调度方法的基础上增加一级调度。一级调度确定多个调度算法的优先顺序;二级调度确定同一种调度算法中,的进程优先顺序。该模型使进程调度更加灵活和高效,应用范围更广。 展开更多

关键词 嵌入式操作系统 进程 调度 速率单调算法 最早截止期限优先

下载PDF 职称材料

一种新的组优先级动态实时调度算法 被引量：2

3

作者 巴巍 张大波 +1 位作者 李琦 王伟 《计算机科学》 CSCD 北大核心 2009年第7期230-233,239,共5页

传统动态调度算法由于对优先级个数没有限制,在实际应用中往往受制约,达不到很好的调度性能。针对此问题,考虑硬实时抢占任务调度需要,提出一种新的组优先级动态实时调度算法。研究作业执行顺序改变对系统可调度性能的影响,给出作业分... 传统动态调度算法由于对优先级个数没有限制,在实际应用中往往受制约,达不到很好的调度性能。针对此问题,考虑硬实时抢占任务调度需要,提出一种新的组优先级动态实时调度算法。研究作业执行顺序改变对系统可调度性能的影响,给出作业分组可调度性能测试。新算法将满足分组可调度测试公式的作业作为一个任务组,各任务组之间按照最小截止期优先调度,任务组内按照最短作业优先的原则执行作业。仿真结果表明,与最小截止期优先等传统调度算法相比,新算法不仅能有效降低算法所需优先级个数,还能提高任务调度的成功率,缩短平均响应时间,减少任务切换次数。 展开更多

关键词 任务调度 最小截止期优先调度算法 成功率 切换次

下载PDF 职称材料

实时调度算法研究 被引量：36

4

作者 王志平 熊光泽 《电子科技大学学报》 EI CAS CSCD 北大核心 2000年第2期205-208,共4页

对实时调度进行了讨论：研究了单处理器下的经典调度算法：单调速率调度、最早死线调度和最短空闲时间优先调度；分析了多处理器系统中的典型调度算法：对分布式系统中的两种调度算法：广义单调速率调度和分布式风车调度做了简要论述；... 对实时调度进行了讨论：研究了单处理器下的经典调度算法：单调速率调度、最早死线调度和最短空闲时间优先调度；分析了多处理器系统中的典型调度算法：对分布式系统中的两种调度算法：广义单调速率调度和分布式风车调度做了简要论述；指出实时调度研究策略方向。 展开更多

关键词 实时调度算法 单调速率调试 分布式系统

下载PDF 职称材料

多功能一体化雷达任务调度算法研究 被引量：18

5

作者 綦文超 杨瑞娟 +2 位作者 李晓柏 陈新永 程伟 《雷达科学与技术》 2012年第2期150-155,共6页

雷达、电子战、通信等多功能电子系统一体化是雷达的发展方向之一,资源管理与调度技术是一体化雷达的关键技术。针对基于孔径分割实现雷达、电子对抗、通信等多种功能的一体化系统的任务调度问题,对系统任务建模、调度算法设计、算法评... 雷达、电子战、通信等多功能电子系统一体化是雷达的发展方向之一,资源管理与调度技术是一体化雷达的关键技术。针对基于孔径分割实现雷达、电子对抗、通信等多种功能的一体化系统的任务调度问题,对系统任务建模、调度算法设计、算法评价指标进行了探讨。在研究常规相控阵雷达调度策略的基础上,提出了采用多任务并行EDF(Earliest Deadline First)算法来实现系统的自适应调度。最后对比常规多功能雷达的自适应调度进行了仿真比较,且对仿真结果进行了定量分析,结果表明采用多任务并行EDF(MTPEDF)算法的基于孔径分割的一体化雷达系统具有一定的优越性。 展开更多

关键词 多功能雷达 孔径分割 任务调度 截止期最早最优先(EDF)

下载PDF 职称材料

容错最早时限优先调度 被引量：5

6

作者 陈宇 熊光泽 《计算机工程与科学》 CSCD 2001年第5期58-62,共5页

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

关键词 软件容错 最早时限优先调度算法 实时操作系统 计算机

下载PDF 职称材料

多处理器混合关键性系统中的划分调度策略 被引量：13

7

作者 谷传才 关楠 +2 位作者 于金铭 王义 邓庆绪 《软件学报》 EI CSCD 北大核心 2014年第2期284-297,共14页

多核处理器正越发广泛地应用到现代嵌入式系统的设计与实现当中,其强大的计算能力为将多个不同关键性级别的功能子系统集成到统一的共享资源平台提供了支持.混合关键性系统的调度问题即便在单处理器平台中都极具挑战性,在多处理器平台... 多核处理器正越发广泛地应用到现代嵌入式系统的设计与实现当中,其强大的计算能力为将多个不同关键性级别的功能子系统集成到统一的共享资源平台提供了支持.混合关键性系统的调度问题即便在单处理器平台中都极具挑战性,在多处理器平台则更为困难.将目前资源利用率最高的单处理器混合关键性调度算法EY-VD扩展到多处理器平台中.首先,结合传统的划分调度策略提出了适用于多处理器混合关键性系统的MC-PEDF(mixedcriticality partitioned earliest deadline first)划分调度算法.尽管比之前的算法有更好的可调度性能,但传统的划分策略不能有效地平衡不同关键性级别下的负载,故其不完全适用于混合关键性系统.为了克服传统策略的不足,提出了划分调度策略OCOP(one criticality one partition).OCOP允许系统在关键性模式切换时对实时任务集进行重新划分,进而更好地平衡各个处理器在不同关键性模式中的资源利用率.基于OCOP,提出了第2种划分调度算法MC-MP-EDF(mixed-criticality multi-partitioned EDF).基于随机生成任务集的仿真实验结果表明,与MC-PEDF和已有的算法相比,MC-MP-EDF能够显著地提高系统的可调度性,尤其是在处理器数量较多的系统中. 展开更多

关键词 混合关键性系统 多处理器 划分调度 EDF(earliest deadline first)

下载PDF 职称材料

最早截止期优先调度算法的改进 被引量：10

8

作者 程禹 赵宏伟 +1 位作者 龙曼丽 李玉翠 《吉林大学学报（工学版）》 EI CAS CSCD 北大核心 2013年第5期1338-1342,共5页

在基于IEEE802.16d协议的服务流调度过程中,为了保证优先级较高的任务优先得到服务,并尽量将调度过程对系统资源的消耗控制在可承受的范围内,在分析已有的非抢占式及抢占式两种方案的最早截止期优先(EDF)算法优缺点的基础上,重点考虑时... 在基于IEEE802.16d协议的服务流调度过程中,为了保证优先级较高的任务优先得到服务,并尽量将调度过程对系统资源的消耗控制在可承受的范围内,在分析已有的非抢占式及抢占式两种方案的最早截止期优先(EDF)算法优缺点的基础上,重点考虑时间特性、重要性特性、顺序参考三方面作为调节参数,同时兼顾传输距离,对已有的EDF算法进行改进。提出了基于重要性因素抢占的半抢占式EDF算法。通过仿真实验,把改进后的EDF算法应用到IEEE802.16d协议的实时轮询业务(RTPS)服务流调度中。结果表明,改进后的EDF算法较好地平衡了抢占及非抢占式EDF算法的优缺点,具备较前两者更小且更稳定的延时。 展开更多

关键词 计算机应用 最早截止期优先算法 平均延时 截止时间 时间特性 抢占

下载PDF 职称材料

EDF实时调度算法中的关键问题求解 被引量：8

9

作者 张杰 阳富民 +1 位作者 卢炎生 涂刚 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2009年第10期1-4,共4页

针对截止期最早优先(EDF)调度算法存在的问题,通过分析和证明EDF调度算法中最大可挪用时间的性质,结合EDF的最优调度过程,提出一种可延迟时间逼近(DTA)算法,以快速准确地计算EDF算法调度周期任务的最大可挪用时间,并且证明了该算法的时... 针对截止期最早优先(EDF)调度算法存在的问题,通过分析和证明EDF调度算法中最大可挪用时间的性质,结合EDF的最优调度过程,提出一种可延迟时间逼近(DTA)算法,以快速准确地计算EDF算法调度周期任务的最大可挪用时间,并且证明了该算法的时间复杂度只和周期任务数、处理器的占用率之和有关.仿真实验验证了DTA算法的时间性能. 展开更多

关键词 实时调度算法 截止期最早优先 偶发任务 容错 挪用时间

原文传递

基于CAN总线实时应用的可靠调度性研究 被引量：6

10

作者 邓竹莎 雷航 +1 位作者 罗淳 康涌泉 《计算机应用》 CSCD 北大核心 2006年第6期1301-1303,共3页

CAN总线是一种高级的串行通信协议,适用于各种分布式控制系统。在实时应用中,标准的CAN协议使用静态优先级算法,对传输信道的利用率比较低。对基于CAN总线通信的动态优先级调度算法进行研究后,提出了一种基于指数分配方式的MTS算法,在... CAN总线是一种高级的串行通信协议,适用于各种分布式控制系统。在实时应用中,标准的CAN协议使用静态优先级算法,对传输信道的利用率比较低。对基于CAN总线通信的动态优先级调度算法进行研究后,提出了一种基于指数分配方式的MTS算法,在保证强实时性消息的同时兼顾了低优先级消息的公平性。 展开更多

关键词 标识符 单调时间限算法 单调速率算法 混合通行算法 最早时间限优先算法

下载PDF 职称材料

混合动力汽车CAN网络优先级动态分配方法 被引量：7

11

作者 张利 王跃飞 +2 位作者 严刚 韩江洪 张建军 《农业机械学报》 EI CAS CSCD 北大核心 2011年第5期20-23,78,共5页

在混合动力汽车网络结构和消息实时性分析的基础上,将最早截止期优先算法(EDF)引入到网络集成协议设计中,提出基于EDF调度的优先级分配策略,给出了实现该策略的非均匀分区编码方法及可调度判定条件,指出了该判定条件下的分区因子无关性... 在混合动力汽车网络结构和消息实时性分析的基础上,将最早截止期优先算法(EDF)引入到网络集成协议设计中,提出基于EDF调度的优先级分配策略,给出了实现该策略的非均匀分区编码方法及可调度判定条件,指出了该判定条件下的分区因子无关性。仿真结果表明该方法能够满足截止期变化范围较大的CAN消息集传输要求,使网络具有较高的利用率。 展开更多

关键词 混合动力汽车 CAN总线 动态优先级 最早截止期优先算法 截止期编码

下载PDF 职称材料

一种面向硬件线程的实时调度算法研究与设计 被引量：3

12

作者 尹震宇 赵海 +2 位作者 林恺 孙佩刚 王金英 《电子学报》 EI CAS CSCD 北大核心 2007年第8期1467-1471,共5页

本文根据硬件线程的特征,为硬件线程调度建立了一个周期与非周期混合线程集的调度模型.在数学层面描述了硬件多线程调度中每个线程被成功调度的条件判据.并在此基础之上,提出一种以截止时间与最坏执行时间差为基本因子的DR-EDF算法,提... 本文根据硬件线程的特征,为硬件线程调度建立了一个周期与非周期混合线程集的调度模型.在数学层面描述了硬件多线程调度中每个线程被成功调度的条件判据.并在此基础之上,提出一种以截止时间与最坏执行时间差为基本因子的DR-EDF算法,提供了一种实现这种DR-EDF算法的硬件多线程控制器的设计原理.最后用FPGA为载体,实现了一款硬件多线程处理器,通过实际测试的分析结果,得出这种面向硬件多线程的实时调度算法在不影响线程集错失率前提下,提高了嵌入式系统中紧急任务的可调度性. 展开更多

关键词 抢占模型 最早期限优先 变级最早期限优先 硬件线程 实时调度

下载PDF 职称材料

偶发实时系统可调度性分析问题的整数规划方法 被引量：6

13

作者 孙景昊 孙景昶 +1 位作者 关楠 邓庆绪 《软件学报》 EI CSCD 北大核心 2017年第2期411-428,共18页

偶发实时任务最早截止期优先(earliest deadline first,简称EDF)可调度分析是实时系统领域经典的NP困难问题.现有的伪多项式时间判定算法(pseudo-polynomail time decision algorithm,简称PTDA)均局限于利用率U严格小于1的同步任务系统... 偶发实时任务最早截止期优先(earliest deadline first,简称EDF)可调度分析是实时系统领域经典的NP困难问题.现有的伪多项式时间判定算法(pseudo-polynomail time decision algorithm,简称PTDA)均局限于利用率U严格小于1的同步任务系统.对于U≤1的同步系统或更加困难的异步系统,现有PTDA则不再适用.针对以上问题,为同步和异步两类实时系统建立了统一的整数规划模型,其规模并不依赖于利用率U的取值.基于多面体理论证明了模型维数和极大诱导不等式,进而提出了同/异步系统上EDF可调度性分析问题统一的多项式时间线性松弛求解方法.实验结果表明,该方法能够获得较紧的问题解下界,在异步和同步系统中,线性松弛解与最优解之间的平均百分界差gap分别为0.78%和1.27%.另外,随机生成了大量同步和异步系统的算例,用于该算法和传统算法进行性能比较.对于同步算例,实验结果表明,在U>0.99时,该算法能够对70%的算例给出判定结果,算法性能与QPA算法相比有指数级提升.对于异步算例,实验结果表明,该算法能够对近96%的算例给出可调度性判定.与传统算法相比,该方法将不能判定可调度性的算例比例平均降低了29.27%.对于剩余的4%的算例,该算法将可调度上界的值平均降低了近10~4倍. 展开更多

关键词 截止期优先 可调度性分析 整数规划 多面体分析 线性松弛

下载PDF 职称材料

异构云环境下基于分簇的云资源感知任务调度方案 被引量：6

14

作者 江务学 魏文国 +1 位作者 丁度坤 李菲 《计算机应用研究》 CSCD 北大核心 2016年第11期3422-3425,共4页

针对提高异构云平台中资源调度的效率,提出了一种基于任务和资源分簇的异构云计算平台任务调度方案。利用K-means算法,根据任务的CPU和I/O处理时间对任务分簇,根据资源的计算能力对资源分簇;然后,将任务簇对应到合适的资源簇,并利用最... 针对提高异构云平台中资源调度的效率,提出了一种基于任务和资源分簇的异构云计算平台任务调度方案。利用K-means算法,根据任务的CPU和I/O处理时间对任务分簇,根据资源的计算能力对资源分簇;然后,将任务簇对应到合适的资源簇,并利用最早截止时间优先(EDF)算法对任务簇中的独立任务进行调度,利用提出的改进型最小关键路径(MCP)算法对依赖性任务进行调度。实验结果表明,在资源异构的云计算环境中,该方案执行任务时间短、能耗低。 展开更多

关键词 异构云计算平台 任务调度 分簇 K-MEANS算法 最早截止时间优先 最小关键路径

下载PDF 职称材料

反馈调度减少实时控制任务的输出抖动 被引量：3

15

作者 周平方 谢剑英 刘俊 《上海交通大学学报》 EI CAS CSCD 北大核心 2005年第12期2052-2056,共5页

提出一种反馈调度的方法在线调节控制任务的截止时限,从而减少输出抖动.反馈控制器采用比例算法,通过对其参数的自调整以动态满足整个任务集的可调度性.控制算法被公式化为一个截止时限分配表达式.仿真结果验证了该方法的有效性.

关键词 实时控制系统 反馈调度 抖动 最早截止时限优先

下载PDF 职称材料

基于缓存区段的P2P流媒体调度算法 被引量：4

16

作者 刘永卫 唐新春 +1 位作者 刘戊开 陈谦 《计算机工程与科学》 CSCD 2008年第6期66-68,94,共4页

由于P2P环境的高度动态性和异构性,以及流媒体服务的高宽带和连续性强的特征,P2P流媒体系统中数据块和发送节点的调度便显得尤为重要。本文针对数据驱动的P2P流媒体系统提出了基于缓存区段的调度算法,即根据时间线将缓存划分为反映不同... 由于P2P环境的高度动态性和异构性,以及流媒体服务的高宽带和连续性强的特征,P2P流媒体系统中数据块和发送节点的调度便显得尤为重要。本文针对数据驱动的P2P流媒体系统提出了基于缓存区段的调度算法,即根据时间线将缓存划分为反映不同紧急程度的若干区段,以便节点根据资源副本数和紧急程度作出合理调度。模拟实验表明,在高动态性的网络情况下,基于缓存区段的调度算法仍然能够很好地保证媒体流的连续性以及节点间的协作。 展开更多

关键词 对等网 流媒体 缓存区段 局部最少优先 最早时限优先

下载PDF 职称材料

嵌入式多核操作系统关键技术 被引量：4

17

作者 姜春茂 倪蕴涛 黄春梅 《科技导报》 CAS CSCD 北大核心 2012年第11期69-75,共7页

分析了目前多核操作系统的现状,多核芯片的出现导致了相应操作系统的改变,嵌入式操作系统的一些关键问题被提出。通过研究多核操作系统在实时性调度算法、负载平衡、同步机制中的现状及其存在的问题,提出未来的研究方向。并辅之以分析... 分析了目前多核操作系统的现状,多核芯片的出现导致了相应操作系统的改变,嵌入式操作系统的一些关键问题被提出。通过研究多核操作系统在实时性调度算法、负载平衡、同步机制中的现状及其存在的问题,提出未来的研究方向。并辅之以分析一个软实时多核操作系统LITMUS,对其基于多核体系结构的嵌入式多核平台的应用给出了基本的研究设想。 展开更多

关键词 多核操作系统 全局实时调度算法 最早截止时间优先调度

原文传递

基于CAN的电动汽车控制系统动态调度算法研究 被引量：2

18

作者 王书举 张天侠 张国胜 《机械与电子》 2010年第6期42-45,共4页

针对在控制器局域网(CAN)总线中应用最早截止期优先(EDF)调度时,CAN帧用有限的标识符位难以实现信息截止期编码,以及各节点同时更新截止期需要严格的时间同步等问题,提出了基于总线仲裁的EDF调度算法,介绍了EDF调度算法原理及可调度性... 针对在控制器局域网(CAN)总线中应用最早截止期优先(EDF)调度时,CAN帧用有限的标识符位难以实现信息截止期编码,以及各节点同时更新截止期需要严格的时间同步等问题,提出了基于总线仲裁的EDF调度算法,介绍了EDF调度算法原理及可调度性分析方法,最后将该调度算法应用于电动汽车控制系统信息的调度,验证了调度算法的可行性. 展开更多

关键词 控制器局域网 最早截止期优先 动态调度 可调度性分析

下载PDF 职称材料

带宽约束下舰艇编队网络的跨平台任务调度算法 被引量：3

19

作者 武树斌 温玉屏 +2 位作者 夏洋 汪慧君 李含辉 《中国舰船研究》 CSCD 北大核心 2020年第6期170-175,共6页

[目的]舰艇编队无线IP网络的带宽有限且具有时变性,故为满足编队作战应用对跨平台任务运行的时限要求,需研究网络带宽约束下的跨平台任务调度算法。[方法]提出舰艇编队无线IP网络任务调度模型,运用"任务发起方"和"任务... [目的]舰艇编队无线IP网络的带宽有限且具有时变性,故为满足编队作战应用对跨平台任务运行的时限要求,需研究网络带宽约束下的跨平台任务调度算法。[方法]提出舰艇编队无线IP网络任务调度模型,运用"任务发起方"和"任务响应方"的通信模式,实现"最早时限优先+先来先服务"两级任务调度。采用所提的最早时限优先(EDF)扩展算法,在传统的单平台单处理机实时调度算法基础上,将任务执行时间的计算由处理机占用时间转换为网络占用时间,以适用于舰艇编队需要,进而推导出任务可调度性的判定条件,并对此进行试验验证。[结果]试验结果表明,在所构建的测试网络环境下,可计算得到舰艇编队跨平台任务集合的可调度性。[结论]所提理论模型及算法具有较强的可实施性,对于指导舰艇编队无线IP网络的任务规划和任务调度具有重要价值。 展开更多

关键词 舰艇编队网络 无线网络 网络带宽约束 任务调度模型 最早时限优先算法

下载PDF 职称材料

基于希尔排序的动态优先级调度算法 被引量：3

20

作者 王瑞奇 赵菊敏 李灯熬 《电视技术》 2018年第5期57-59,共3页

实时调度策略中,EDF算法应用最为广泛,但其在系统过载的情况下,仅由任务截止期决定任务执行顺序,使得截止期错失率非常高,且系统收益小。近年来,出现了一些改进的EDF算法,综合考虑了时间和执行价值,但未加入能量因素,对于能量有限的系统... 实时调度策略中,EDF算法应用最为广泛,但其在系统过载的情况下,仅由任务截止期决定任务执行顺序,使得截止期错失率非常高,且系统收益小。近年来,出现了一些改进的EDF算法,综合考虑了时间和执行价值,但未加入能量因素,对于能量有限的系统,充分利用能量是极其重要的。针对这一问题,提出一种基于希尔排序的动态优先级调度算法,在系统过载时,综合考虑任务截止时间、执行价值、消耗能量三种因素确定任务优先级,通过希尔排序算法选出优先级高的任务加入优先调度子集,进行率先调度。实验结果表明,该算法不仅能降低任务截止期错失率,还能提高系统执行收益。 展开更多

关键词 实时系统 任务调度 最早截止期优先调度 希尔排序 动态优先级

下载PDF 职称材料