基于单调速率的可调度性判定改进算法

在单调速率调度策略的基础上,提出一种改进的任务集可调度性判定算法。该算法通过设定时钟变量模拟调度过程中的系统时钟,在时钟变量值增长过程中,根据任务优先级从高到低的顺序,分析各个任务的截止时间限的满足情况,判定任务的可调度性,从而确定任务集的可调度性。通过实例分析及与现有判定方法的比较,验证了该算法的正确性和高效性。     

改进的单调速率调度算法

实时系统中调度算法起着重要的作用.单调速率调度算法(rate monotonic algorithm,RM)是一种被 广泛使用的调度算法,并且已被证明是一种最佳的静态优先级算法.传统的RM算法忽略上下文切换需要消耗的时间,针对此问题,提出了一种延迟抢占的改进方法.该方法考虑了上下文切换消耗时间对调度算法的影响,可以减少...     

单调速率及其扩展算法的可调度性判定

任务可调度性判定是实时系统调度理论研究的核心问题.单调速率(RM)算法是实时调度的重要算法,自其提出以来已被广泛研究.然而到目前为止,尚缺乏专题性的文章来系统而深入地探讨RM及其扩展算法的可调度性判定,以及各种现实条件和实现方式(包括任务调度的时间开销和任务同步问题等)对可调度性的影响.围绕RM算法下的可调度性判定问题,由浅入深,系统性地讨论各种不同假设和实现方式对可调度性的影响,具体为下述3大类问题：（1）理想的RM算法下的可调度性判定的CPU利用率最小上界最小及可调度的充分必要条件;（2）考虑调度时间开销情况下的可调度性判定条件;（3）优先级反转协议及其对可调度性的影响.给除了具体实例来叙述上述问题,并从算法复杂度和可检测率两方面比较各种算法的优劣。     

混合实时事务的延期单调速率调度算法及其可调度性分析

对于含有实时和非实时两部分的混合实时应用,传统的单调速率调度算法(RM)已不再适用.为此,该文引入“混合实时事务”的概念,并针对这类事务提出一种延期单调速率调度算法(DRM);着重分析了DRM算法对混合实时事务的可调度性;进行了实验测试与性能分析比较．结果表明,事务集中混合实时事务占的比例越高,混合事务中非实时子事务占的比例越大,该算法的CPU使用率阈值就越高,且在各种情况下,DRM算法与RM算法相比性能都更优,最低情况也与之一样．     

基于单调速率调度算法的μC/OS-II多任务周期的设计

嵌入式实时操作系统μC/OS-II对于多任务调度采用让就绪表中优先级最高的任务总是处于运行状态,这种策略在周期性多任务的调度中存在着缺陷,可能使得任务的周期设计不当导致任务不能被调度。通过引入单调速率调度算法,在对多个任务设计任务周期时予以分析,确定每个任务都能被调度。     

单调速率任务分配算法利用率的界限分析

通过对单调速率任务分配算法调度策略和可调度条件的分析,在多处理器周期任务抢占调度模型基础上,细致刻画了任务分配算法如何分配任务的行为。依据Liu和Layland定理,给出多处理器下任务分配算法的最小RM利用率界的定理。仿真结果表明,分配算法的利用率界是不同特征任务集选择不同分配算法进行任务划分的关键,通过对任务集总利用率与算法利用率界的比较,判断使用该算法对任务集是否可以产生可行分配。     

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

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

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

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

多处理器全局单调比率的可调度性分析

针对全局单调比率(RM)调度的多处理器系统中最高优先级任务数量少于处理器数量时,Bertogna等给出的最坏情况计算任务受到的干涉过于悲观,证明了任务受到最高优先级任务的干涉不会出现最坏情况,它受到非最高优先级任务干涉仍可能出现最坏情况。分析得出了任务受到最高优先级任务干涉的最大可能值,由此得到了一个更紧的可调度性判断条件。实验结果表明,提出的方法提高了判为可调度的任务集数量。     

基于确定周期性任务的进程管理及可调度性分析

文中讨论了基于确定周期性任务的实时进程管理,对确定周期性任务采用调度器生成的管理方式,通过截止期递增分类法将非性任务分为两类,分别采用中断内抢占调度和信号调度,提出了改进的最大紧急度优先算法,分析了目标系统的可调度性,给出了春可调度的充要条件。     

单调时限调度算法的可调度分析

单调时限调度通过定义Di≤Ti放宽了单调比率调度对被调度任务集的限制,使之更加近似于工程实际,但现有的单调时限调度的可调度分析的充分条件十分复杂。文章提出并证明了基于最小处理器利用率上限的单调时限调度的充分可调度条件,大大简化了单调时限调度的调度分析。     

Utilization Bounds for Multiprocessor Rate-Monotonic Scheduling

In this paper, we extend Liu and Layland's utilization bound for fixed priority scheduling on uniprocessors to homogeneous multiprocessor systems under a partitioning strategy. Assuming that tasks are pre-emptively scheduled on each processor according to fixed priorities assigned by the Rate-Monotonic policy, and allocated to processors by the First Fit algorithm, we prove that the utilization bound is (n–1)(2^1/2–1)+(m–n+1)(2^1/(m–n+1)–1), where m and n are the number of tasks and processors, respectively. This bound is valid for arbitrary utilization factors. Moreover, if all the tasks have utilization factors under a value , the previous bound is raised and the new utilization bound considering is calculated. Finally, simulation provides the average-case behavior.     

基于嵌入式RTOS的闭环反馈调度算法的研究

分析了常见调度算法的特点，提出一种基于嵌入式实时操作系统的闭环反馈控制调度策略。针对任务的特点．从任务的周期与非周期性、I／O消耗和处理器消耗型两个方面对任务进行相应的反馈控制，使调度器具有一定程度上的自适应功能。并对实时操作系统μC／OS-Ⅱ的内核调度算法进行改进，同时与EDF算法进行对比测试，可以看出改进后的调度算法在系统负载较重或系统过载的情况下表现良好。     

实时事务调度及静态可调度性分析

在类似闭环控制的硬实时数据库应用环境,实时事务具有一定的静态可预报性,其中实时事务的可调度性分析是维护实时数据库时间正确性的基础.通过利用抢占阈值,提出了一种新的实时事务处理模型,它集成了CPU调度和数据调度,实现离线并发控制,具有单阻塞的特征与好的静态可预测性,并有利于降低事务系统的负载和改善可调度性.进一步由此建立了实时事务的静态可调度性分析模型以及求最优可行调度的整数规划模型,该模型有利于达到实时事务调度的整体优化.     

一种改进的RM可调度性判定算法

固定优先级任务可调度性判定是实时系统调度理论研究的核心问题之一.目前已有的各种判定方法可归结为两大类:多项式时间调度判定和确切性判定.多项式时间调度判定通常采用调度充分条件来进行,为此,许多理想条件下基于RM(rate monotonic)调度算法的CPU利用率最小上界被提了出来.确切性判定利用RM调度的充要条件,保证任何任务集均可被判定,并且判定结果是确切的.但是由于时间复杂度较差,确切性判定方法难以实现在线分析.提出了一种改进的RM可调度性判定方法(improved schedulability test algorithm,简称ISTA).首先介绍了任务调度空间这一概念,并提出了二叉树表示,然后进一步提出了相关的剪枝理论.在此基础上,研究了任务之间可调度性的相关性及其对判定任务集可调度性的影响,提出并证明了相关的定理.最后基于提出的定理,给出了一种改进的伪多项式时间可调度性判定算法,并与已有的判定方法进行了比较.仿真结果表明,该算法平均性能作为任务集内任务个数的函数具有显著提高.     

应用于实时系统的DMS算法可调度性分析

固定优先级任务的可调度性判定是实时系统调度理论研究的核心问题之一。本文提出了一种可行的DMS可调度性判定方法——确切性判定方法（precised schedulability test algorithln,简称PSTA）,利用DMS调度的充要条件,保证任何任务集均可被判定,并且判定结果是确切的。首先给出了DMS调度模型,介绍了可调度性判定的基本思想,然后进一步通过实验提出并证明了PSTA相关的定理。     

强实时系统静态优先级调度的可调度性分析

文章在系统阐述和借鉴经典的强实时系统静态优先级调度理论的基础上,通过引入忙周期的概念,分析了任务时限超过任务周期的实时系统任务集的可调度特性,拓宽了该理论的应用范围,更有利于实时系统的设计者对任务的运行时间行为进行事前分析与预测。