一种静态最少优先级分配算法

随着实时系统越来越多地应用于各种快速更新系统,尤其是各种片上系统,如PDA(personal digital assistant),PSP(play station portable)等,性价比已成为系统设计者的主要关注点.实际应用中,实时系统通常仅支持较少的优先级,常出现系统优先级数小于任务数的情况(称为有限优先级),此时,需将多个任务分配到同一系统优先级,RM(rate monotonic),DM(deadline monotonic)等静态优先级分配算法不再适用.为此,静态有限优先级分配是研究在任务集合静态优先级可调度的情况下,可否以及如何用较少或最少的系统优先级保持任务集合可调度.已有静态有限优先级分配可分为两类:固定数目优先级分配和最少优先级分配.给出了任意截止期模型下任务静态有限优先级可调度的充要条件以及不同静态有限优先级分配间转换时的几个重要性质,指出了系统优先级从低到高分配策略的优越性,定义了饱和任务组与饱和分配的概念,证明了在任务集合静态优先级可调度的情况下,最少优先级分配比固定数目优先级分配更具一般性.最后提出一种最少优先级分配算法LNPA(least-number priority assignment).与现有算法相比,LNPA适用范围更广,且复杂度较低.     

一种有限优先级的静态优先级分配算法

静态优先级调度在实时系统中得到了广泛应用.然而,静态优先级调度受到系统支持的优先级个数的限制.当任务的个数大于优先级个数时,需要将多个任务映射到同一个优先级.针对优先级个数有限的情况,给出了在截止期限大于周期时任务可调度的充分必要条件,并提出了基于有限优先级的静态优先级分配算法(AGP).AGP算法对于基本任务集合是最优的静态优先级分配算法.其最优性表现在,所需的优先级个数最小,并且若采用AGP算法不可调度某个任务集,则采用其他静态优先级分配算法也不可调度该任务集.模拟结果表明,AGP算法的可调度性要远远大于常量法.AGP算法对于解决在嵌入式实时系统中任务的优先级分配问题具有重要意义.     

静态实时中间件的优先级映射问题

使用截止期单调(DM)调度算法和分布式优先级冲顶资源访问控制协议(DPCP)的实时CORBA系统中,当节点的本地优先级个数不足时,必须将多个全局优先级映射成一个本地优先级.这需要:①判定映射后任务可调度性的充分必要条件;②减少时间复杂度的映射算法.为此,推导出判定条件,确定了DGPM映射算法.该算法在保证系统可调度的前提下分配任务,或者证明映射后系统不可调度.证明了DGPM算法能调度其他直序列优先级映射算法可调度的任务和GCS集合.判定条件和算法在实际项目中得到了应用.     

周期多帧任务的固定优先级调度算法的调度分析

实时操作系统的核心问题－－实时任务的调度是实时系统研究的重点之一。主要讨论了周期多帧任务的固定优先级调度算法的调度情况,证明了对于周期多帧任务DM算法不是最优的,同时也证明了对于累积单调周期多帧任务的DM算法是最优的。     

多处理器硬实时系统的抢占阈值调度研究

在实时系统中,抢占在提高系统灵活性的同时带来额外的系统开销,特别在多处理器平台上抢占导致的作业迁移会造成相当大的性能下降,减少不必要的抢占是硬实时系统研究的重要方向.抢占阈值调度是处于抢占调度和不可抢占调度之间的一种混合调度方法,在保持调度能力的基础上限制抢占.基于截止期分析建立了多处理器硬实时系统抢占阈值调度的可调度性判定条件,针对抢占阈值调度提出一种改进的优先级分配算法OPA-MLL,并建立了抢占阈值分配(preemption threshold assignment,PTA)算法.仿真结果表明,采用OPA-MLL算法和PTA算法分别给任务集分配优先级和抢占阈值时,可调度任务集比率明显提高,同时能最大程度限制抢占次数.     

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

实时调度算法是实时系统中的关键技术.文章在研究单处理器系统中常用实时调度算法:固定优先级调度算法和动态优先级调度算法基础上,详细分析了常用固定优先级调度算法RM、DM算法和动态优先级调度算法EDF、LLF和MLLF算法的运算过程和使用条件,提出了各个算法在实际应用中存在的问题,为实际应用中选择何种实时调度算法确定了依据.     

实时控制系统中固定优先级调度的延迟与抖动控制

在基于固定优先级调度实时控制系统中,任务的延迟与抖动是影响系统稳定性的重要因素,提出一种基于可抢占时间阈值的延迟与抖动控制策略,给出一种保证系统可调度的最优闽值分配算法,并通过对任务延迟和抖动的分析量化出阀值分配后的争最大可能IO延迟及抖动.最后通过仿真实验验证了该策略的有效性.     

基于μC/OS_Ⅱ的优先级调度算法的改进

μC/OS_Ⅱ内核最多可以管理64个任务,当工程的复杂度增加时,必须改换其他的开发平台,导致了前期工作变为徒劳.通过简易可行的方法来增加任务管理数目很有必要.μC/OS_Ⅱ内核原来的优先级调度算法的优先级变量总共8位,只用了其中的低6位,高2位未被使用.在尽量不改变内核的数据结构的情况下,为了增加内核可以管理任务的数目...     

一种不影响任务集合可调度性的优先级映射算法

采用静态优先级调度的实时系统中,当任务个数多于优先级个数时,只能给多个任务分配相同的优先级·现有分配算法增大了高优先级任务的最坏情况响应时间,可能造成任务集合不可调度·利用抢占阈值的调度算法,能在提高任务集合可调度性的同时,使用较少的线程·但所用优先级个数没有减少·提出了一种优先级映射算法———阈值段间映射法(threshold segment mapping,TSM),以及与之配合的事件驱动线程框架·证明了TSM是严格排序的·仿真结果表明,在保证任务集合可调度的前提下,TSM使用了比现有映射算法更少的优先级·     

TD-SCDMA集群系统中优先级退避算法研究*

针对TD-SCDMA集群通信系统随机接入优先级用户快速建立呼叫响应的要求,提出了基于优先级退避算法的随机接入技术。该算法通过为各优先级用户分配相应的上行同步码资源,以及对不同优先级用户采用优先级退避处理来实现对其快速等级接入。MATLAB仿真结果表明,与优先级BEB退避算法相比,采用改进优先级指数退避算法的随机接入过程,在能保证高优先级用户成功接入的同时,还能明显提高中、低优先级用户的接入成功率,并且当用户接入压力较大时,该算法能有效地降低各优先级用户的平均接入时延。     

The Non-Optimality of the Monotonic Priority Assignments for Hard Real-Time Offset Free Systems

In this paper, we study the problem of scheduling hard real-time periodic tasks with static priority pre-emptive algorithms. We consider tasks which are characterized by a period, a hard deadline, a computation time and an offset (the time of the first request), where the offsets may be chosen by the scheduling algorithm, hence the denomination offset free systems.We study the rate monotonic and the deadline monotonic priority assignments for this kind of system and we compare the offset free systems and the asynchronous systems in terms of priority assignment. Hence, we show that the rate and the deadline monotonic priority assignments are not optimal for offset free systems.     

A Feasibility Decision Algorithm for Rate Monotonic and Deadline Monotonic Scheduling

Rate monotonic and deadline monotonic scheduling are commonly used for periodic real-time task systems. This paper discusses a feasibility decision for a given real-time task system when the system is scheduled by rate monotonic and deadline monotonic scheduling. The time complexity of existing feasibility decision algorithms depends on both the number of tasks and maximum periods or deadlines when the periods and deadlines are integers. This paper presents a new necessary and sufficient condition for a given task system to be feasible and proposes a new feasibility decision algorithm based on that condition. The time complexity of this algorithm depends solely on the number of tasks. This condition can also be applied as a sufficient condition for a task system using priority inheritance protocols to be feasible with rate monotonic and deadline monotonic scheduling.     

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

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

Robust priority assignment for messages on Controller Area Network (CAN)

This paper addresses the problem of determining the most robust priority assignment for CAN messages that are subject to transmission errors due to Electromagnetic Interference. In the presence of errors on the bus, CAN messages have a non-zero probability of missing their deadlines. An appropriate choice of priority ordering can minimise the overall worst-case deadline failure probability resulting in a more robust system. This paper shows that “deadline minus jitter” monotonic priority assignment, commonly used for priority assignment in commercial CAN systems, does not always result in the most robust priority ordering. A Robust Priority Assignment algorithm is presented that computes the most robust priority ordering for CAN messages subject to bit errors on the bus. This algorithm is optimal in the sense that it can be used to (i) maximise the number of errors tolerated, (ii) maximise the delay tolerated by any message, or (iii) minimise the probability of any message failing to meet its deadline. This algorithm is efficient and appropriate for use in an engineering context.

优先级有限时的单处理器静态优先级调度

静态优先级调度在实际应用中经常受到系统支持的优先级个数的影响,当任务个数多于系统优先级个数时,需要将几个任务优先级映射成一个系统优先级.这可能引起优先级映射问题,使映射前可调度的系统(任务集合)在映射后变得不可调度.解决这一问题需要减少时间复杂度的映射算法和判定映射后任务可调度性的充分必要条件主要存在3种映射算法:(1)按照任务优先级递减顺序进行映射的DPA(decreasing priority assignment)算法;(2)按照优先级递增顺序进行映射的IPA(Increasing priority assignment)算法;(3)阈值段间映射法(thresh01d segment mapping,简称TSM).描述了3种算法的实现和判定条件,论述并证明了算法特性,分析并通过仿真实验比较了算法的性能,最后总结了3种算法各自的适用场合.比较结果和结论对实时嵌入式系统的设计和实现具有一定的参考价值.     

面向抖动优化的任务静态优先级指派算法

对任务相对截止时限进行优化设置是一种减少输出抖动的有效方法,但现有方法均是针对最早时限优先调度算法,不能适用于任务集采用静态优先级调度算法的场合.为此,提出通过优化优先级指派实现任务集的整体抖动最小化,并给出一种启发式的优先级指派算法.根据单调速率调度算法确定任务的初始优先级,以最小化局部抖动方式依次对任务的优先级进行再调整,从而得到近似最优的优先级指派.仿真实验结果表明,该算法能有效减少任务集的整体输出抖动.     

Exact speedup factors and sub-optimality for non-preemptive scheduling

Fixed priority scheduling is used in many real-time systems; however, both preemptive and non-preemptive variants (FP-P and FP-NP) are known to be sub-optimal when compared to an optimal uniprocessor scheduling algorithm such as preemptive earliest deadline first (EDF-P). In this paper, we investigate the sub-optimality of fixed priority non-preemptive scheduling. Specifically, we derive the exact processor speed-up factor required to guarantee the feasibility under FP-NP (i.e. schedulability assuming an optimal priority assignment) of any task set that is feasible under EDF-P. As a consequence of this work, we also derive a lower bound on the sub-optimality of non-preemptive EDF (EDF-NP). As this lower bound matches a recently published upper bound for the same quantity, it closes the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive fixed priority scheduling dominates the other, in other words, there are task sets that are feasible on a processor of unit speed under FP-P that are not feasible under FP-NP and vice-versa. Hence comparing these two algorithms, there are non-trivial speedup factors in both directions. We derive the exact speed-up factor required to guarantee the FP-NP feasibility of any FP-P feasible task set. Further, we derive the exact speed-up factor required to guarantee FP-P feasibility of any constrained-deadline FP-NP feasible task set.