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

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

AADL分级调度模型的分析与验证

针对嵌入式系统体系结构分析设计语言(architecture analysis and design language,AADL)分级调度模型的分析问题,提出了基于模型检验的可调度性分析和验证方法.基于时间自动机理论,将AADL分级调度模型转换为时间自动机网络,将待验证性质描述为时序逻辑公式,通过模型检验工具对可调度性进行分析和验证.研究结果表明,使用模型检验方法来分析AADL分级调度模型的可调度性是可行的.相对其他方法而言,该方法利用了形式化方法的穷举性来分析系统的性质,分析结果更加精确.     

基于RM调度的任务抢占次数最多分析

传统的实时系统可调度性分析方法往往忽略任务抢占的时间开销,然而在重负载情况下,如果任务抢占次数很多,则由此带来的时间开销将不可忽略。该文分析基于单调速率调度算法的系统中任务抢占次数最多需要满足的条件,提出通过修改任务参数来减少抢占次数的方法,减少了系统在最坏情况下的任务响应时间。     

回卷恢复模型下容错实时系统的可调度性分析

实时任务的超时完成将会导致灾难性后果,因此实时系统必须具备严格的实时性及可靠性保障.考虑实时系统的容错需求,本文基于回卷恢复模型,对容错实时系统的可调度性分析进行研究.在基于任务最环响应时间的可调度性分析方法中,容错优先级配置是决定系统可调度性的关键.为了改进系统的可调度性,提出一种容错优先级可降低的配置策略,并推导出此策略下任务最坏响应时间的计算公式,以判断系统的可调度性.降低策略下低优先级任务可挪用高优先级任务的空闲时间来满足自身的截止时限要求.仿真实验表明,降低任务的容错优先级可以有效提升系统的容错能力.     

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

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

时间Petri网的可调度分析及在FMS中的应用

在实时系统中,检查任务执行的计划是否满足要求的时间约束称为可调度分析.通过把时间特性与其他行为特性分离,提出了一种以时间Petri网建模的实时系统调度分析方法.如果特定任务的执行是可调度的,则可以计算任务执行的时间跨度,否则确定出不可调度的变迁以便于调整时间约束和纠正设计错误.提出了一种通过把复杂的任务序列分解成一些子序列来进行可调度性分析的综合时序分析技术,它不仅提高了效率,也有助于关于调度的可达性问题的讨论.讨论了柔性制造系统FMS中的车间装配子系统的可调度性.     

实时系统最坏执行时间分析*

实时系统开发过程中必须强调时间的重要性和支持时间的可预报性。最坏执行时间分析与可调度性分析构成了实时系统时间方面操作可信的基础。最坏执行时间分析计算任务执行时间的上界,这些任务的上界用来分配正确的CPU时间给实时任务。最坏执行时间是可调度分析工具的输入,可调度分析决定了一组任务在一个给定的目标系统下是否可调度。对最坏执行时间分析方面的研究进行了综述,给出在这一领域所取得的进展。 还讨论了在最坏执行时间分析方面存在的问题,给出了将来的研究方向。     

针对AADL模型的可调度性分析方法研究

AADL(Architecture Analysis＆Design Language)语言是美国SAE(Society of AutomotiveEngineers)组织定义的一组满足航空电子综合化设计用的建模语言.它可以描述安全关键嵌入式实时系统功能和非功能性属性,非功能属性包括可靠性、安全性、可调度性等.通过对这些非功能属性进行分析,可以在设计阶段而不是实现阶段纠正系统设计缺陷,缩短系统开发周期和降低开发成本.总结了AADL语言对可调度性分析方面提供的支持,并分析比较了几种针对AADL模型的可调度性分析工具,在此分析和比较基础上,识别它们各自的优缺点,方便使用者根据需要选择合适的工具使用.     

容错优先级可提升的抢占阈值容错调度算法

基于软件容错模型,提出了允许容错优先级提升的抢占阈值容错调度算法(extended fault-tolerantfixed-priority with preemption threshold,简称FT-FPPT*).该算法能够在抢占式容错调度算法(fault-tolerantfixed-priority preemptive,简称FT-FPP)和抢占阈值容错调度算法(fault-tolerant fixed-priority with preemptionthreshold,简称FT-FPPT)无法提高系统容错能力的情况下,进一步提高系统的容错能力.为了获得系统中任务优先级分配的最佳策略,基于任务最坏响应时间的可调度性分析,提出了一种最优的优先级配置搜索算法(priorityassignment search algorithm,简称PASA).经过深入分析和实验证明,与FT-FPPT算法相比,FT-FPPT*算法能够有效地提高硬实时系统的容错能力.     

基于随机模型的软实时系统的任务期望可调度性

本文基于随机模型研究了软实时系统中任务的可调度性特征,提出了期望可调度性的概念. 期望可调度性是与实时任务到达时间t相关的, 因此, 提出的方法能研究任务子集在任意给定时间间隔的可调度性特征. 本文给出了期望可调度性的条件, 如果任务的持续时间满足该条件, 则实时任务具有期望可调度性. 基于理论结果的数值分析与模拟结果是一致的,这表明当软实时系统的负载率小于69%(某些确定性模型提供的)时, 实时任务总是期望可 调度的. 这一结果也表明基于随机模型的期望可调度性方法能为软实时系统的任务可调度性分析提供一个更大的阈值和更好的适应性.     

On Schedulability Analysis of AADL Architecture with Storage Resource Constraint

Embedded systems have been widely applied in real-time automatic control systems, and most of these systems are safety-critical, for example, the engine control systems in an automobile and the avionics in an airplane. It is very important to verify the schedulability of such a real-time embedded system in its early design stages, so as to avoid unexpected loss for the debugging of architecture design problems. However, it has been proved to be a tough challenge to evaluate the schedulability of a Preemptive-Scheduling Real-Time (PSRT) system, especially when the constraints of system resources are taken into consideration. The cache memory built inside the processor is an exclusive-accessing resource shared by all the tasks deployed on the processor. In addition, the Cache-Related Preemption Delay (CRPD) caused by preemptive task scheduling will bring extra time to the execution time for all the tasks. Thus, the CRPD should be taken into consideration when the Worst-Case Execution Time (WCET) of tasks is estimated in a real-time system. A model-based evaluation and verification method of architecture schedulability, which is designed for priority-based PSRT systems, is proposed in this study to make cache resource constrained and CRPD related schedulability evaluation based on the AADL system architecture model. In the first step, the study enhances the property set of AADL storage elements to make it compatible with cache memory properties in a system architecture model. Secondly, the study proposes a set of algorithms to estimate the CRPDs of a task before it is completed; run system schedule simulation and construct the schedule sequence with the constraint of cache resources and CRPDs involved; and make WCET estimation of the tasks in such a CRPD considered, preemptive-scheduling execution sequence. Finally, the methods mentioned above are implemented within a prototype software toolkit, which is designed to make evaluation and verification of system schedulability within CRPD constraints. The toolkit is tested with a use case of aircraft airborne open-architecture intelligent information system. The result shows that, compared with the schedule sequence constructed without cache memory resource constraints, the WCET estimated for most tasks is extended, and the sequence order is changed. In some extreme cases, when CRPD is taken into consideration, some tasks are evaluated to be incompletable. The test shows that the method and algorithms proposed in this study are feasible.     

一种面向实时系统的程序基本块指令预取技术

面向通用计算机系统的指令预取技术无法满足实时系统的应用需求,其中一个重要原因是：无效预取引起的指令Cache内容污染使得实时任务WCET评估值不够精确,导致系统可调度性下降,严重影响系统效率.以简化实时任务WCET分析、降低任务WCET评估值为目标,提出一种基于程序基本块的指令预取方法.该方法以基本块为粒度执行指令预取,避免了传统指令预取技术引入的无效预取;通过简化最坏情况下的指令访问命中/缺失情况判定,简化任务WCET分析过程并优化WCET评估值.实时基准测试程序评估结果表明：与常规无预取方法相比,该预取方法可使实时任务WCET评估值降低约20%,平均执行情况下的指令Cache访问性能提升约10%.     

Joint task assignment and cache partitioning with cache locking for WCET minimization on MPSoC

Cache locking technique is often utilized to guarantee a tighter prediction of Worst-Case Execution Time (WCET) which is one of the most important performance metrics for embedded systems. However, in Multi-Processor Systems-on-Chip (MPSoC) systems with multi-tasks, Level 2 (L2) cache is often shared among different tasks and cores, which leads to extended unpredictability of cache. Task assignment has inherent relevancy for cache behavior, while cache behavior also affects the efficiency of task assignment. Task assignment and cache behavior have dramatic influences on the overall WCET of MPSoC. This paper proposes joint task assignment and cache partitioning techniques to minimize the overall WCET for MPSoC systems. Cache locking is applied to each task to guarantee a precise WCET. We prove that the joint problem is NP-hard and propose several efficient algorithms. Experimental results show that the proposed algorithms can consistently reduce the overall WCET compared to previous techniques.     

嵌入式实时调度框架研究

嵌入式实时操作系统环境中的多类型实时任务并存的情况给实时调度机制带来了新的需求和挑战。提出了一种适用于嵌入式实时环境的调度框架,可以调度多类型实时和非实时任务,且可通过自适应控制来调节软实时任务带宽,使系统实时性最优化。它引入了两个层次的任务准入控制,解决了任务相关性和资源等约束问题,保证了进入系统的任务独立性和可调度性。它具有良好的可扩展性和可配置性,适用于分布式实时环境。     

Modeling Control Speculation for Timing Analysis

The schedulability analysis of real-time embedded systems requires worst case execution time (WCET) analysis for the individual tasks. Bounding WCET involves not only language-level program path analysis, but also modeling the performance impact of complex micro-architectural features present in modern processors. In this paper, we statically analyze the execution time of embedded software on processors with speculative execution. The speculation of conditional branch outcomes (branch prediction) significantly improves a program's execution time. Thus, accurate modeling of control speculation is important for calculating tight WCET estimates. We present a parameterized framework to model the different branch prediction schemes. We further consider the complex interaction between speculative execution and instruction cache performance, that is, the fact that speculatively executed blocks can generate additional cache hits/misses. We extend our modeling to capture this effect of branch prediction on cache performance. Starting with the control flow graph of a program, our technique uses integer linear programming to estimate the program's WCET. The accuracy of our method is demonstrated by tight estimates obtained on realistic benchmarks.     

Techniques to increase the schedulable utilization of cache-based preemptive real-time systems

Nowadays, cache memories are applicable to real-time systems with the help of tools that obtain the worst-case execution time (WCET) of cached programs. However, these tools do not allow preemption, because from the point of view of program analysis, the number of preemptions is unknown. To face this problem, the cache-related preemption cost can be considered in the schedulability analysis, or annulled by the use of private cache partitions. This paper comprises a number of techniques using the first or both solutions. This paper also explores the harmonic relationships among tasks to improve the estimation of the cache interference in the analysis.     

面向WCET估计的Cache分析研究综述

实时系统时间分析的首要任务是估计程序的最坏情况执行时间(worst-case execution time,简称WCET).程序的WCET 通常受到硬件体系结构的影响,Cache则是其中最为突出的因素之一.对面向WCET计算的Cache分析研究进行了综述,介绍了经典Cache分析框架与Cache分析核心技术,并从循环结构分析、数据Cache分析、多级Cache分析、多核共享Cache分析、非LRU替换策略分析等角度介绍了Cache分析在不同维度上的研究问题与主要挑战,总结了现有技术的优缺点,展望了Cache分析研究的未来发展方向.     

Hardware-software co-synthesis of hard real-time systems with reconfigurable FPGAs

Real-time systems cover a wide application domain. This paper presents an efficient heuristic algorithm for enforcing the schedulability of aperiodic hard real-time tasks arriving simultaneously with precedence constraints and individual deadlines. The proposed co-synthesis algorithm integrates partitioning and non-preemptive scheduling. Reconfigurable FPGAs are incrementally added when schedulability suffers in a uniprocessor system. Initially, a schedule that minimizes the maximum lateness and satisfies the precedence constraints is made. If individual timing constraints are not met in this schedule, some tasks are selected and transferred to dynamically reconfigured FPGAs. The proposed algorithm was implemented and tested with a large number of task graphs with task size as high as 700 nodes. The algorithm could not only achieve schedulability but also could reduce the total completion time of the task graph. Moreover, incremental addition of reconfigurable FPGAs yielded a cost effective solution.     

一种改进的自适应多媒体任务调度算法

支持多媒体任务调度以满足其性能需求，是一项重要而富有挑战性的工作，一直备受关注，并出现了一些实时任务模型。它们都需要任务提供最坏执行时间（Worst Case Execution Time，WCET），以方便准入控制机制的实现，但这正是多媒体任务难以提供的。那么在WCET未知的前提下，如何实现多媒体任务的调度，而且必须支持准入控制和动态QoS控制机制，支持尽可能多任务的执行，使CPU资源的利用最大化？本文首先提出了一种改进的基于速率的自适应（Adaptive Rate-Based，ARB）任务模型。然后通过理论分析和实验证明了：在WCET未知的情况下，基于ARB任务模型的多媒体任务调度算法、准入控制和自适应QoS控制机制是可行的、有效的，而且可以支持尽可能多任务的执行，达到了预期的目标。