基于多片FPGA的双优先级动态调度算法

针对单片现场可编程门阵列(FPGA)在处理高速网络中海量数据时存在效率低下的问题,结合多处理器的双优先级调度算法,在所构建的多片FPGA并行处理的高速数据采集和处理模型上,提出一种基于多片FPGA的双优先级动态调度算法,并对处于低优先级段的强实时周期任务提出一种最早截止期临界松弛调度(EDCL)算法。根据任务的松弛度确定任务的优先级,若提升时间到达时仍未完成,则将其提升到高优先级段; 对软实时周期任务,设置在中优先级段,通过延长当前任务截止期至动态模糊阈值进行调度。实验结果表明,该算法能很好地调度强实时周期任务,保证重要任务的优先执行,并能降低由于抢占造成的软实时周期任务错失率。     

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

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

μC/OS-II在应用系统中任务划分及优先级设置

利用实时内核开发嵌入式多任务系统程序,应该将系统功能合理分解,构造不同的任务,并根据任务相对于其他任务的重要性决定其优先级。主要介绍了在嵌入式操作系统μC/OS-II的开发过程中,如何在应用系统中进行任务的划分及其优先级的设置,并结合自己的开发项目给出实例。     

基于组合优先级的自适应实时调度算法研究

在嵌入式实时操作系统中,由单个特征参数作为实时任务优先级的调度依据,并不能较好地描述系统中任务的关键性和紧迫性.提出一种基于组合优先级的自适应实时调度算法(SREDF),综合任务的截止期和CPU运行期设计任务的优先级,使截止期越早且CPU运行期越短的任务拥有最高优先级.处理器能有效地调度相同截止期的实时任务,并提前分析和预测任务能否完成.实验表明,该算法降低了任务调度的截止期错失率(MDP),并提高了任务调度的速度和效率.     

固定优先级抢占调度算法下非周期任务实时性能研究

嵌入式实时系统不仅要在功能上满足需求,而且要在性能上满足实时性需求.给定调度算法,实时性取决于各个任务的到达特征和执行时间.任务的到达特征由应用环境决定.为此,本文研究任务执行时间对实时性能的影响,为嵌入式系统设计提供参考.针对固定优先级抢占调度算法,应用排队论,提出一种非周期实时任务的理论模型.该理论模型包含两个优先级不同的非周期实时任务,给出了任务的执行时间长短对时限错过率、任务响应时间、任务队列长度等实时性能的影响.给出一个应用实例,仿真结果验证了理论模型的正确性.     

分布式控制系统中多种混合任务的容错调度

分布式控制系统中存在有强实时、软实时和非实时等多种实时性的任务,其中强实时任务必须在其时限前完成,否则会出现灾难性后果,因此必须为分布式控制系统提供一定的容错能力。首先给出了用于调度多种实时性任务的单处理器调度算法——双优先级队列调度算法,并分析算法的可调度性条件。针对分布式控制系统,考虑基版本与副版本的执行时间不同时,结合版本复制技术和单处理器调度算法提出了一种新的容错调度算法。分析了算法的可调度行,给出了可任务集的可调度条件判断方法和基版本任务时限的设置方法。在此基础上,采用启发式静态任务分配算法,保证各处理器的负载均衡。本算法在保证任务容错可调度的条件下,可提高系统中各处理器的利用率,仿真结果表明该算法是有效的。     

μC/OS-Ⅱ在应用系统中任务划分及优先级设置

利用实时内核开发嵌入式多任务系统程序，应该将系统功能合理分解，构造不同的任务，并根据任务相对于其他任务的重要性决定其优先级。主要介绍了在嵌入式操作系统μC／OS—Ⅱ的开发过程中，如何在应用系统中进行任务的划分及其优先级的设置，并结合自己的开发项目给出实例。     

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

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

一种任务优先级的综合设计方法

提出了一种基于优先级表设计的调度算法.将任务的相对截止期和空闲时间这两个特征参数结合起来,综合设计任务的优先级表,使得截止期越早或空闲时间越短,任务的优先级越高,而且任务的优先级由相对截止期和空闲时间惟一确定.对于任意一个任务,可通过对设计的优先级表进行二元多点插值获得相应任务的惟一优先级.与传统的EDF和LSF算法进行仿真比较,仿真结果表明,通过优先级表设计方法来确定任务的优先级,提高了任务调度的成功率,降低了任务截止期的错失率.该方法可应用于实时系统中实时任务的动态调度中.     

一种固定优先级实时调度算法的可行性测定

实时调度算法是实时系统的关键技术,验证实时调度算法的可行性是保证实时系统性能的必要手段.不同实时调度算法可行性测定方法不同.在简单实时模型上,针对固定优先级实时调度算法给出通过任务最坏响应时间来测定调度算法可行性的方法,分析了影响任务最坏响应时间的各种因素,修正了响应时间方程,将该方法运用在复杂实时模型中.     

Schedulability analysis and task mapping for real-time on-chip communication

Priority-based wormhole switching with a priority share policy has been proposed as a possible solution for real-time on-chip communication. However, the blocking introduced by priority share complicates the analysis process. In this paper, we propose a new “per-priority” basis analysis scheme which computes the total time window at each priority level instead of each traffic-flow. By checking the release instance of each flow at the corresponding priority window, we can determine schedulability efficiently. Building on this static analysis, for a given set of tasks and network topology, we further propose a task mapping and priority assignment algorithm, in such a way that the hard time bounds are met with a reduced hardware overhead. Experiment results show that significant resource saving can be achieved with no performance degradation in terms of missed deadlines. By using this approach, a broad class of real-time communications with different QoS requirements can be explored and developed in a SoC/NoC communication platform.     

基于OSEK的任务调度算法改进及实现

针对嵌入式操作系统中的任务调度算法不能保证临近时限的低优先级任务得以运行的情况,提出一种任务管理机制和任务调度算法。该算法通过一种链表结构来解决任务调度时系统开销大的问题,并在任务建立时确定任务的时限。当任务的时限临近时提高其优先级,使其得以运行,使系统在保证高优先级任务得以运行的同时,确保低优先级任务得以运行,从而保证了系统的实时性。     

Timing analysis for fixed-priority scheduling of hard real-timesystems

This paper presents a timing analysis for a quite general hard real-time periodic task set on a uniprocessor using fixed-priority methods. Periodic tasks are composed of serially executed subtasks, where each subtask is characterized by an execution time, a fixed priority and a deadline. A method for determining the schedulability of each task and subtask is presented along with its theoretical underpinnings. This method can be used to analyze the schedulability of any task set on a uniprocessor whose priority structure can be modeled as serially executed subtasks, which can lead to a very complex priority structure. Important examples include task sets that involve interrupts, certain synchronization protocols, certain precedence constraints, nonpreemptible sections, and some message-passing systems. The method is illustrated by a robotics example     

Software architecture for hard real-time applications: Cyclic executives vs. fixed priority executives

We contrast the software architecture of a hard real-time application using a fixed priority task structure against the software architecture of the same system using a cyclic executive structure to satisfy hard real-time deadlines in response to a set of embedded system requirements. We identify the perceived and actual advantages and disadvantages of both approaches, consider the types of applications which can take advantage of these approaches, and make recommendations related to the attributes of such applications that might be needed with both approaches. We conclude that the fixed priority approach, when priorities are assigned using rate monotonic priorities, generally dominates the cyclic executive approach for hard real-time systems.     

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

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

TinyOS中DSA调度策略的研究

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

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

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

Memory-centric scheduling for multicore hard real-time systems

Memory resources are a serious bottleneck in many real-time multicore systems. Previous work has shown that, in the worst case, execution time of memory intensive tasks can grow linearly with the number of cores in the system. To improve hard real-time utilization, a real-time multicore system should be scheduled according to a memory-centric scheduling approach if its workload is dominated by memory intensive tasks. In this work, a memory-centric scheduling technique is proposed where (a)?core isolation is provided through a coarse-grained (high-level) Time Division Multiple Access (TDMA) memory schedule; and (b)?the scheduling policy of each core ??promotes?? the priority of its memory intensive computations above CPU-only computation when memory access is permitted by the high-level schedule. Our evaluation reveals that under high memory demand, our scheduling approach can improve hard real-time task utilization significantly compared to traditional multicore scheduling.     

Real-time executives for microprocessors

Principles of real-time executives for microcomputer systems are discussed, together with some secondary functions. Salient features and limitations of three commercially available executives for 8080/5 and Z80 systems are described. An example is given illustrating the use of an executive in a multitasking application involving a simple data logger with a high priority data acquisition task, a low priority data converting task and storage task.