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.     

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.     

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

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

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

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

多处理器EPDFPfair算法的可调度性判定

针对多处理器实时调度中的最早伪时限优先(EPDF)Pfair算法,分析了EPDF算法在M个处理器平台上的可调度利用率约束,根据基于利用率的充分可调度性判定,提出了一种改进的可调度性判定方法。这种方法可以得到更多的可调度任务集,从而使得满足判定的强实时系统和使用tie-breaking规则困难的动态任务系统的调度有较小的开销。实验结果表明,改进的可调度性判定方法增加了判为可调度的任务集数量,具有较好的性能。     

基于双曲线边界的多处理器实时任务可调度性判定

Lopez等学者求解出基于单调速率算法和首次适应分派策略的多处理器实时任务可调度性判定边界.该边界在所有O(m)复杂度的判定边界中是最优的.基于Bini等学者针对单处理器提出的双曲线可调度性判定方法,给出了一种多处理器实时任务可调度性判定边界.新边界在相当数量的利用率分布下明显优于已有边界.新边界与已有边界具有相容性,所以虽然新边界无法在所有情况下超越已有边界,但在实际应用中可联合两种边界进行判定,在不增加计算复杂度的同时全面提高可调度任务集的数量.     

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.     

一种改进的分布强实时系统可调度性分析算法

Holistic算法是用于预测分布强实时系统可调度性的一种有用的方法.对该算法进行改进,扩展了原算法,使其更具普遍性.并且以一种高可靠、强实时、分布信息处理系统为研究背景,对有关应用实例进行了测试和分析.实验结果说明,改进后的算法更加准确、有效.     

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

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

Improved Blocking Time Analysis and Evaluation for the Multiprocessor Priority Ceiling Protocol

The Multiprocessor Priority Ceiling Protocol （MPCP） is a classic suspension-based real-time locking protocol for partitioned fixed-priority （P-FP） scheduling. However, existing blocking time analysis is pessimistic under the P-FP ＋ MPCP scheduling, which negatively impacts the schedulability for real-time tasks. In this paper, we model each task as an alternating sequence of normal and critical sections, and use both the best-case execution time （BCET） and the worst-case execution time （WCET） to describe the execution requirement for each section. Based on this model, a novel analysis is proposed to bound shared resource requests. This analysis uses BCET to derive the lower bound on the inter-arrival time for shared resource requests, and uses WCET to obtain the upper bound on the execution time of a task on critical sections during an arbitrary time interval of △t. Based on this analysis, improved blocking analysis and its associated worst-case response time （WCRT） analysis are proposed for P-FP ＋ MPCP scheduling. Schedulability experiments indicate that the proposed method outperforms the existing methods and improves the schedulability significantly.     

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

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

多处理机容错系统中实时任务的轮转式调度算法

基于多处理机实时系统的“主从备份技术”,文章提出一种采用轮转式调度策略实现容错调度的算法。模拟结果表明,该算法可达到较均衡的任务分布,提高了CPU利用率。     

端到端实时CORBA系统调度模型及其可调度性研究

实时CORBA系统中的基本问题是如何合理分配有限的计算资源和通信资源以保证各个实时任务的时间需求。该文以固定优先级方式调度的、周期性任务的硬实时系统为研究对象，提出了端到端实时CORBA系统调度模型，该模型综合考虑了客户端系统的处理、服务对象处理、网络传输等几大主要因素，而且可以描述服务对象间的嵌套调用关系，因而能全面描述实时CORBA系统中客户调用过程。在此基础上，该文基于非连续工作型同步协议，应用时间需求分析方法，研究并提出了该模型的可调度性分析算法。     

单调速率调度算法的可调度性分析与仿真

单调速率调度算法是一种经典的周期任务调度算法,在采用单调速率调度算法调度周期任务前对算法的可调度性进行分析和仿真是十分必要的。该文介绍了单调速率调度算法的基本调度规则和可调度的充分必要条件,分别基于Windows平台的多线程机制和实时操作系统SACOS的RMS管理器对单调速率调度算法的可调度性进行仿真,并对仿真结：果进行了评价与分析。仿真结果表明,这两种方法可为单调速率调度算法的可调度性分析提供有益的指导。     

一个基于多线程的优先级继承协议锁的算法研究

实时线程库对构造实时中间件和开发具有良好可移植性，有实时要求的分布式应用具有重要意义，防止优先级翻转的线程互斥和同步机制是实现实时线库的核心，目前多数的线程库都缺乏这种机制，基于优先级继承协议，提出了一个防止优先级反转的互斥算法，算法能够保证操作的原子性，可以避免发生死锁，且能够有效地防优先级翻转，在Windows和Solaris平台上对性能进行了分析，并将算法应用到了实时CORBA工程实践之中。     

飞机电气负载管理中心软件实时调度算法的分析与实现

实时性是飞机电源控制与管理系统的一项基本要求,它由构成系统的网络的实时性和终端的实时性共同保证.为了满足该系统的整体实时性要求,分析了其中一类终端--负载管理中心所应具有的实时性,并进一步列出了该终端各个任务所应满足的实时性要求,提出了采用单调速率调度算法来调度该任务集的想法,讨论了任务的临界区对任务执行时间的影响及相应的处理办法,并对所有任务的可调度性作出了判定.该终端最终采用了这种调度算法,实现结果能够满足系统对该终端的实时性要求.     

Multicycle Polling Scheduling Algorithms for FieldBus Networks

The paper deals with the scheduling of periodic information flow in a FieldBus environment. The scheduling problem is defined from an analytical point of view, giving a brief survey of the most well-known solutions. One of these is called multicycle polling scheduling, which is based on the hypothesis that all the production periods of the periodic processes to be scheduled are harmonic. Although in some process control or manufacturing scenarios, this hypothesis may be acceptable, there are many real industrial processes to which it cannot be applied. The aim of the paper is to make a contribution towards solving the scheduling problem. It essentially concerns extension of the theory on which multicycle polling scheduling is based to a much more realistic and general scenario, where the periods of all the processes to be scheduled have arbitrary values. The authors present a new formulation of multicycle polling scheduling, called extended multicycle polling scheduling, and demonstrate that it comprises the scenario currently considered in the literature. Two algorithmic solutions for extended multicycle polling scheduling are then proposed, giving a computational complexity analysis which will highlight the capability of the algorithmic scheduling solutions to be performed on-line. The paper concludes by comparing the multicycle polling scheduling approach known in literature and the one presented in the paper. Comparison is performed by evaluating the use of available bandwidth to serve both periodic and asynchronous traffic in the two approaches.     

提高软非周期任务响应性能的调度算法

实时环境中常常既包含硬周期任务,又包含软非周期任务,引入一种改进软非周期实时任务响应时间的算法.已有的解决混合任务调度问题的方法都是基于速率单调（Rate Monotonic）策略的,其中从周期任务“挪用时间”的算法被证明优于其他所有算法.但是,速率单调算法限制了处理器的使用率,从而使周期任务的可“挪用”时间受到限制.最后期限驱动（Deadline Driven）策略DD可使潜在的处理器利用率达到100%.新算法正是在周期任务的调度中适当加入了DD策略,从而使非周期任务的响应时间得以缩短.仿真实验的结果表明,这种算法的性能优于已有的所有算法,而由它所带来的额外开销却不算很高.     

Analysis of Worst Case DMA Response Time in a Fixed-Priority Bus Arbitration Protocol

We propose a technique for finding the worst case response time (WCRT) of a DMA request that is needed in the schedulability analysis of a whole real-time system. The technique consists of three steps. In the first step, we find the worst case bus usage pattern of each CPU task. Then in the second step, we combine the worst case bus usage patterns of CPU tasks to construct the worst case bus usage pattern of the CPU. This second step considers not only the bus requests made by CPU tasks individually but also those due to preemptions among the CPU tasks. Finally, in the third step, we use the worst case bus usage pattern of the CPU to derive the WCRT of DMA requests assuming the fixed-priority bus arbitration protocol. Experimental results show that overestimation of the DMA response time by the proposed technique is within 20% for most DMA request sizes and that the percentage overestimation decreases as the DMA request size increases.