基于抢占阈值调度的周期任务最小响应时间分析*

针对采用抢占阈值调度策略的系统,在假设任务对释放偏移没有特定要求的情况下,给出使得任务响应时间最小时应满足的条件,并根据该条件得到了任务最小响应时间的计算公式。该公式的一个重要应用是在分布式系统中分析后继子任务的最大释放抖动,有效降低端到端任务的最大响应时间的计算结果,从而有利于提高系统的可调度性。     

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

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

基于动态抢占阈值的实时调度

具有抢占阈值的调度算法集非抢占调度和纯抢占调度的特点,既减少了由于过多的随意抢占造成的CPU资源浪费,又保证了一定的任务截止期错失率及CPU资源利用率。已有的工作基本集中于讨论任务集完全给定,任务数、任务的优先级及任务的抢占阈值在调度前已完全确定,而且要求不同的任务具有不同的优先级,提出的具有抢占阈值的调度算法,完全放松了对这些条件的限制,即任务的个数不确定,任务的优先级及其抢占阈值在调度过程中可以动态地变化。最后以常用的LSF调度策略为例,结合动态的抢占阈值进行仿真,仿真结果表明,对于不确定的任务集、任务优先级和抢占阈值,利用具有抢占阈值的动态调度算法,降低了任务截止期错失率、提高了CPU的有效使用率。     

抢占阈值调度的功耗优化

DVS(Dynamic Voltage Scaling)技术的应用使得任务执行时间延长进而使得处理器的静态功耗(由CMOS电路的泄露电流引起)迅速增加.延迟调度(Procrastination Scheduling)算法是近年提出用于减少静态功耗的有效方法,它通过推迟任务的正常执行来尽可能长时间地让处理器处于睡眠或关闭状态,从而避免过多的静态功耗泄露.文中针对可变电压处理器上运用抢占阈值调度策略的周期性任务集合,将节能调度和延迟调度结合起来,提出一种两阶段节能调度算法,先使用离线算法来计算每个任务的最优处理器执行速度,而后使用在线模拟调度算法来计算每个任务的延迟时间,从而动态判定处理器开启/关闭时刻.实例研究和仿真实验表明,作者的方法能够进一步降低抢占阈值任务调度算法的功耗.     

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

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

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

基于软件容错模型,提出了允许容错优先级提升的抢占阈值容错调度算法(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*算法能够有效地提高硬实时系统的容错能力.     

一种基于非抢占RM算法的可行性判决算法及应用

为中断服务例程建立了任务模型，在该模型的基础上给出了中断服务例程集使用非抢占RM调度的可行性的充分必要条件，并且基于该条件提出了一种新的非抢占RM算法的可行性判决算法。进一步地，给出了如何改进不可调度例程集的方法，并且将该方法应用到一个具体工程项目中，取得较好的效果。     

一类特殊的非抢占式周期任务的调度方法

现实世界中针对许多任务的资源调度分配和使用具有时效性,对该类任务的调度问题目前的研究还较少。针对此类调度问题,分析其特点,明确其与已有调度模型研究问题的区别,提出新的非抢占式周期任务调度模型,并证明了该类问题为NP完全问题。在此基础上,给出了一种求解最优解的模式剪枝算法,以及一种求解近似解的快速求解算法。相关实验表明,提出的两种算法能够针对不同的需求场景分别对调度问题进行高效求解。     

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

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

基于EDF抢占式调度的周期任务最小响应时间分析

针对采用EDF抢占式调度策略的系统,在假设任务对释放偏移没有特定要求的情况下,给出使得任务响应时间最小时应满足的条件,并根据该条件得到了任务最小响应时间的计算公式。该公式的一个重要应用是用于精确估计在分布式系统中后继子任务的最大释放抖动,从而精确计算出端到端任务的最大响应时间,以正确判断任务的可调度性。     

单调速率任务分配算法利用率的界限分析

通过对单调速率任务分配算法调度策略和可调度条件的分析,在多处理器周期任务抢占调度模型基础上,细致刻画了任务分配算法如何分配任务的行为。依据Liu和Layland定理,给出多处理器下任务分配算法的最小RM利用率界的定理。仿真结果表明,分配算法的利用率界是不同特征任务集选择不同分配算法进行任务划分的关键,通过对任务集总利用率与算法利用率界的比较,判断使用该算法对任务集是否可以产生可行分配。     

基于CPN的嵌入式RTOS任务调度建模

针对有色PetriN（CPN）在并行、并发、资源共享描述上的适用性,将其引入到嵌入式实时操作系统（RTOS）建模中,解决了RTOS任务调度模型中的CPU独占表述、优先级排序、抢占时间处理和周期任务实现问题。对一个优先级抢占式任务调度实例建立CPN模型,结果表明该模型能有效反映RTOS系统的动态特性,准确定量模拟出RTOS系统的效率、切换频率指标。     

实时操作系统内存分配性能检测

主要提出了一种检测实时操作系统内存分配性能的方法，利用概率统计的方法随机产生内存碎片，检测实时操作系统在不同条件下内存分配性能的变化，并采用符合正态分布的随机数产生内存碎片，对嵌入式操作系统VxWorks的内存分配性能进行检测，最后结合实际数据分析了VxWorks的内存分配性能符合实时操作系统的要求，同时验证了该检测方法的可行性和可信性。     

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

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

开源RTOS内存管理机制分析和改进

针对开源RTOS(FreeRTOS)内存分配时间不确定及内存利用率低、不能很好支持动态内存分配等不足,研究FreeRTOS的内存管理机制并比较几种典型动态内存管理算法的优缺点。移植修改过的TLSF算法对管理机制进行改进,较小的内存分成固定大小的内存块,用一级位图索引组织,较大的内存用二级间隔表组织。实验结果表明该方法能较好地提高内存分配速度和利用率。     

经典RM调度算法在无人机发动机试车台软件开发中的应用

现代无人机发动机测试项目多、实时性要求高,早期的基于非实时的片上系统不能很好地满足测试要求。本文以某型无人机发动机试车台软件系统实际开发为例,在软件开发中引入了经典RM调度算法,分析了经典RM算法的可调度性判定法则,描述了片上系统任务集设计过程,进行了RM可调度性理论判定。通过对任务集的实际可调度性测试表明：硬件利用率最大可达到93．8％,达到设计指标要求;系统运行稳定可靠,并取得预期效果。     

嵌入式实时操作系统在航天器软件中的应用研究

随着航天任务的日益复杂化,航天器软件中嵌入式实时操作系统的应用已经成为大势所趋。本文分析嵌入式实时操作系统应用的必要性,总结我国航天器软件中嵌入式实时操作系统的应用特点,并对以后发展趋势进行展望。     

基于OSEK/VDX的RTOS设计与实现

在分析OSEK/VDX规范的基础上,从任务调度、事件机制和资源管理等方面出发,研究8位嵌入式实时操作系统FDOSEK的设计,并在Freescale的MC9S08DZ60芯片上实现其内核。对FDOSEK的任务切换时间和存储需求进行测试,结果表明,FDOSEK具有较强的实时性和较低的存储需求,适用于汽车电子领域。     

微小卫星星务计算机任务调度算法

为了在有限的时间内尽可能多地安排具有时间约束的卫星任务,提出一种针对具有独占性、优先级相同的任务的先完成先调度算法EFFFS,对算法性能进行分析,将其与同类算法进行比较,结果表明,该算法具有较小的时间复杂度和较好的调度性能,适用于计算资源受限的环境。     

单调比率(RM)调度算法及应用

介绍了任务死线不大于其周期的任务集调度条件分析及算法实现。这种约束条件放松, 有利于周期与非周期任务混合模型调度。同时,分析了以往调度算法中单调比率调度算法约束条件, 并指明了计算时间复杂度的缺点。因而,在RM算法基础之上提出一种实时系统调度算法及实现流 程图,并对提出的现场级实时调度算法进行了对比测试。