一种提高构件化嵌入式操作系统性能的方案

本文分析了现有构件化嵌入式操作系统所用调度算法存在的缺点,提出抢占阈值调度算法是更为合适的算法。通过仿真实验比较抢占阈值调度算法、非抢占式调度算法和FIFO(First-In-First-Out)调度算法的性能,证明了上述结论。通过分析现有嵌入式系统构件模型的特点,提出了一种构件模型以及将构件映射成任务的方式,还提出了一种设计方法。整个方案能提高构件化嵌入式操作系统的性能。     

抢占阈值调度算法的分析与研究

本文详细论述了应用于静态优先级实时系统的抢占阈值调度算法。描述了算法实现和任务集合可调度性判定公式的推导,分析了算法的性能特点,阐述了抢占阈值调度是静态优先级嵌入式实时系统开发中调度算法的合适选择。     

一种分布式实时系统任务调度算法的设计

结合分布式系统和实时系统的特点,分析了分布式系统任务调度算法和实时系统任务调度算法,为了能够较好地实现系统的并行性能、实时任务的调度性能以及网络的负载平衡,提出一种将分布式系统任务调度算法和实时系统任务调度算法想结合的算法,采用层次式调度算法以及动态权值的轮转调度算法和速率单调调度算法相结合,在队列权值固定的实验基础上,采用随机改变队列权值的算法,实验证明该随机改变队列权值的算法能够更好地调度任务.     

动态抢占阈值调度中的快速任务选择算法

基于动态抢占阈值的实时调度算法集非抢占调度和纯抢占调度的特点,既减少了由于过多的随意抢占造成的CPU资源浪费,又保证了较高的CPU资源利用率。然而,现有的任务选择算法运行时的额外代价严重影响了系统的整体性能。针对这个问题,本文提出一种使用“选择树”作为任务队列结构的、时间复杂度为O（｜log2n｜）的快速任务选择算法。本文从理论上证明该算法正确性的同时,在使用ARM9芯片的Nokia智能手机上验证了该算法在嵌入式实时系统中的有效性。实验表明,该算法在充分利用处理器的同时能够有效降低动态阈值调度算法的额外代价。     

基于EDF算法的可行性判定及实现

实时调度算法是实时系统中的关键技术。验证实时调度算法的可行性是在实时系统中实施某种调度算法的必经环节。在介绍实时系统中常用的各种实时调度算法,包括固定优先级调度算法和动态优先级调度算法基础上,详细分析了动态优先级调度算法EDF算法的运算过程和使用条件。提出了该算法在实际应用中存在的问题。针对该硬实时调度算法,提出了分别在简单模型上和复杂模型上如何判定实时任务的可行性。为实际应用中实现该实时调度算法确定了依据。     

基于EDF算法的可行性判定及实现

实时调度算法是实时系统中的关键技术。验证实时调度算法的可行性是在实时系统中实施某种调度算法的必经环节。在介绍实时系统中常用的各种实时调度算法．包括固定优先级调度算法和动态优先级调度算法基础上．详细分析了动态优先级调度算法EDF算法的运算过程和使用条件。提出了该算法在实际应用中存在的问题。针对该硬实时调度算法．提出了分别在简单模型上和复杂模型上如何判定实时任务的可行性。为实际应用中实现该实时调度算法确定了依据．     

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

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

NFRL:一种分布系统的实时容错调度算法

在硬实时系统的应用中,如果硬实时任务不能在规定的时限完成,将会产生人员伤亡, 失等严重后果,为了保证在系统出错的情况下,硬实时任务仍然在能戴止时限之前完成,必须研究实时容错技术。本文从实时容错调度算法的角度出发,提出一种基于分布式系统的实时容错调度算法,并研究了该算法的时间复杂度,同时给出一个实例说明该容错调度算法的调度过程。这种容错调算法称为“无容错需求后调度算法（ＮＦＲＬ）,该实时容错调度算法     

嵌入式系统的细粒度多处理器实时抢占式调度算法

现有的嵌入式实时系统调度算法一般以任务级为调度单位,对此提出一种细粒度的线程级多处理器实时调度算法。采用DAG图描述实时系统的任务,并采用任务分解法将其分解为线程形式;为任务级调度采用基于干扰的可调度性分析,为线程级调度采用基于工作负载的可调度性分析;将线程的偏移、截止期与优先级作为三个调度目标,设计混合线程级调度算法。仿真实验结果表明,算法对于多线程任务的实时系统具有较好的性能。     

基于模型的窗口限制实时系统的分析与研究

在研究基于（m，k）模型的窗口限制实时系统的基础上，提出了一种受（m，k）限制的窗口限制实时系统．首先对该实时系统的调度性进行了分析与研究，得出了一些结论．然后提出了一种新的动态窗口调度算法，该算法充分利用了（m，k）限制的特点来提高实时任务的可调度性，减少窗口限制违例．同时，还进行了大量的模拟研究，这些模拟以传统的动态窗口调度算法为基准，将其应用于受（m，k）限制的窗口限制实时系统时的窗口限制违例情况并与新算法进行比较．模拟结果表明，新算法的表现优于传统的动态窗口限制的调度算法．最后进行了总结与展望．     

嵌入式并行系统中基于任务优化的调度算法

在嵌入式并行计算系统中,任务调度是决定系统性能的关键。多任务调度中,启发式调度法是一种设计简单且性能良好的调度方法。目前的调度算法大多是基于任务复制的,没有充分考虑前驱任务与其后继任务间的相关性。该文提出了一种基于相关任务优化(DTO)的调度算法,通过分析已用处理机的负载和空闲时间,尽量减少系统的调度长度和处理机数目。算法分析结果表明,DTO算法在性能上优于其他算法,对嵌入式并行计算系统中的多任务调度是一个较好的选择。     

Partitioning and mapping in embedded multiprocessor architectures in the presence of constraints

The paper focuses on the problem of partitioning and mapping parallel programs onto heterogeneous embedded multiprocessor architectures for real-time applications. Such applications present unique constraints and challenges. In addition to heterogeneity, the proposed partitioning and mapping algorithms satisfy memory, task throughput, task placement, intertask communication bandwidth, and co-location constraints. They do so for architectures that utilize circuit-switched (rather than packet-switched) interprocessor communication and optimize latency and throughput in addition to load-balancing. Finally, these mapping algorithms make use of knowledge of the local scheduling discipline to accommodate real-time scheduling constraints. Our focus is on unstructured parallel programs that fall into one of two classes: (i) the class of computations characteristic of control applications in a real-time environment where tasks execute concurrently, periodically exchanging information, and (ii) pipelined computation graphs found in sensor data processing applications. The algorithms are implemented in a set of tools that operate with commercial CASE tools at one end, and present an interface to multiprocessor simulators at the other end. Collectively, the algorithms form a significant component of an interactive design environment for the development and mapping of real-time embedded parallel programs. The paper describes the algorithms, the encapsulating toolset, and presents an example of their application to an existing embedded application—an Autonomous Underwater Vehicle application.     

Analysis and Optimisation of Hierarchically Scheduled Multiprocessor Embedded Systems

We present an approach to the analysis and optimisation of heterogeneous multiprocessor embedded systems. The systems are heterogeneous not only in terms of hardware components, but also in terms of communication protocols and scheduling policies. When several scheduling policies share a resource, they are organised in a hierarchy. In this paper, we first develop a holistic scheduling and schedulability analysis that determines the timing properties of a hierarchically scheduled system. Second, we address design problems that are characteristic to such hierarchically scheduled systems: assignment of scheduling policies to tasks, mapping of tasks to hardware components, and the scheduling of the activities. We also present several algorithms for solving these problems. Our heuristics are able to find schedulable implementations under limited resources, achieving an efficient utilisation of the system. The developed algorithms are evaluated using extensive experiments and a real-life example.     

Scheduling image processing tasks in a multilayer system

Multilayer multiprocessor systems are generally employed in real-time applications such as robotics and computer vision. This paper introduces three heuristic algorithms for multiprocessor task scheduling in such systems. In our model, tasks with arbitrary processing times and arbitrary processor requirements are considered. The scheduling aims at minimising completion time of processes in a two-layer system. We employed an effective lower bound (LB) for the problem. Then, we analysed the average performance of the heuristic algorithms by computing the average percentage deviation of each heuristic solution from the LB on a set of randomly generated problems. We have also applied these algorithms for scheduling computer vision tasks running on prototype multilayer architecture. Our computational and empirical results showed that the proposed heuristic algorithms perform well.     

AUTOSAR可运行实体-任务自动映射方法研究

下一代汽车电子标准AUTOSAR定义汽车应用程序设计过程包括系统级设计和ECU级设计。系统级设计以软件构件为单位来设计应用,其中软件构件包含一组可运行实体。ECU级设计主要将可运行实体代码组织为嵌入式实时操作系统任务。因此,在将分配到ECU的软件构件集转换为实时系统任务集的过程中,需要有经验的嵌入式开发工程师进行可运行实体-任务的映射配置,以保证系统的实时性。鉴于可运行实体-任务的映射配置工作具有配置需求量大、复杂度高等特点,文中设计了一种可运行实体-任务自动映射方法。该方法综合考虑了可运行实体的触发关系、周期需求、数据共享等因素,对提高汽车软件开发效率具有非常重要的实用价值。最后,将该方法应用于AUTOSAR标准的汽车电子巡航控制系统实例中。实验结果显示,所提方法在抖动时间、阻塞时间、调度频繁度和数据通信量4个方面都具有良好的表现。     

Pre-run-time scheduling in real-time systems: Current researches and Artificial Intelligence perspectives

This paper presents the taxonomy of real-time systems with special emphasize on pre-run-time scheduling problem. Firstly, we present real-time systems, real-time tasks, timing, precedence and exclusion constraints. Then, we describe the problem of pre-run-time scheduling of tasks under constraints. After that, we present the most existing efficient techniques to deal with the latter problem. We summarize the discussion of existing techniques and possible research perspectives after surveying the Artificial Intelligence’s point of view about the problem of pre-run-time scheduling of real-time tasks. The Artificial Intelligence survey includes Constraint Satisfaction Problems class since pre-run-time scheduling belongs to the latter class. The Artificial Intelligence survey includes also Path-finding Problems from which intelligent algorithms could be observed such as Learning-Real-Time-A1(LRTA1) thanks to its important properties (optimality, linear space complexity and determinism). The development of an algorithm like LRTA1 to solve Constraints Satisfaction Problems and particularly the pre-run-time scheduling of real-time tasks problem is one clear research direction to deal with large-scale real-time systems. The overall objective of this paper is to show what are the perspectives to Artificial Intelligence literature that could be beneficial firstly to Artificial Intelligence community itself and secondly to real-time systems community.     

同构计算环境中一种快速有效的静态任务调度算法

快速有效的调度任务是多处理器计算环境中的一个关键问题．目前任务调度算法中刻画任务依赖关系最流行的模型是DAG,在以前的文献中,提出了一种新的更实际、更普遍的TTIG模型及其相应的MATE算法(基于同构计算环境)．延伸了TTIG模型,并提出基于同构系统的新的算法及两种启发式方法(GBHA1和GBHA2)．GBHA以组的形式尽量消除图中回路,因而能获得任务图的全局信息,具有更好的调度性能．在模拟实验中,将此算法与MATE和其他同构环境中基于DAG的有效调度算法,在不同测试条件下进行了比较,结果显示GBHA在性能上明显优于MATE,与基于DAG模型的调度算法比较而言,在性能方面各有千秋,但在算法时间复杂度方面具有显著的优势．     

开放式实时嵌入式系统自适应调度模型研究

开放式实时嵌入式系统中多类型实时任务并存和资源受限的情况给实时调度机制带来了新的需求和挑战。通过引入准入控制、资源管理、调度服务器、自适应调节机制等,提出了一个形式化的自适应调度模型。它能适应开放计算环境的不确定性,有控制地接受不同类型任务的运行;可根据系统资源和任务需求的最新变换情况计算带宽变化,自适应地调节任务的优先等级,使得系统运行在最优的实时性能上;该模型在某航空机载系统设计中得到了实际应用,同其它类似系统相比,该模型的应用提高了系统的调度性和系统稳定性。     

通用调度框架的改进及其在Linux中的实现

在嵌入式Linux实时系统中,要求内核对不同时问约束的任务采用不同的调度算法.但目前Linux内核采用单一的实时调度模式,不能灵活地执行多种调度算法,也就无法满足实时系统中实时任务的时间约束.引入了一种能够在Linux内核调度中执行多种调度算法的框架,即通用调度框架(GSF),并改进了其中的多算法调用机制,从而更好地在Linux内核中实现GSF.