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

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

强实时系统静态优先级调度的可调度性分析

文章在系统阐述和借鉴经典的强实时系统静态优先级调度理论的基础上，通过引入忙周期的概念，分析了任务时限超过任务周期的实时系统任务集的可调度特性，拓宽了该理论的应用范围，更有利于实时系统的设计者对任务的运行时间行为进行事前分析与预测。

面向抖动优化的任务静态优先级指派算法

对任务相对截止时限进行优化设置是一种减少输出抖动的有效方法,但现有方法均是针对最早时限优先调度算法,不能适用于任务集采用静态优先级调度算法的场合。为此,提出通过优化优先级指派实现任务集的整体抖动最小化,并给出一种启发式的优先级指派算法。根据单调速率调度算法确定任务的初始优先级,以最小化局部抖动方式依次对任务的优先级进行再调整,从而得到近似最优的优先级指派。仿真实验结果表明,该算法能有效减少任务集的整体输出抖动。

一种新的静态优先级在线节能调度算法

合理运用动态电压调整技术可有效降低嵌入式实时系统能耗.针对静态优先级实时调度,提出了一种能够有效分析松弛时间并尽可能平衡分配松弛时间的在线节能调度算法TPSRM.设计了一种两段式频率执行策略来改变任务执行时间的分配,能充分在线分析各种形式的松弛时间.通过尽可能合理降低高优先级任务的处理器执行频率来实现有效的在线频率调整.实验结果表明TPSRM算法可实现较好的节能效果.

基于静态优先级的ATM网延迟算法

利用到达和服务与时间的反函数 ,获得了一种计算与ATM交换连接的最坏情况延迟的直接算法 .在借鉴经典的强实时系统静态优先级调度理论的基础上 ,通过引入分区算法来计算ATM交换的延迟 ,在指定的时限内传送完所有的信息 .仿真实验结果表明 ,基于静态优先级的分区算法明显优于直接算法 ,ATM交换网连接的允许可能性平均提高 10 % .

一种静态最少优先级分配算法

随着实时系统越来越多地应用于各种快速更新系统,尤其是各种片上系统,如PDA(personal digital assistant),PSP(play station portable)等,性价比已成为系统设计者的主要关注点.实际应用中,实时系统通常仅支持较少的优先级,常出现系统优先级数小于任务数的情况(称为有限优先级),此时,需将多个任务分配到同一系统优先级,RM(rate monotonic),DM(deadline monotonic)等静态优先级分配算法不再适用.为此,静态有限优先级分配是研究在任务集合静态优先级可调度的情况下,可否以及如何用较少或最少的系统优先级保持任务集合可调度.已有静态有限优先级分配可分为两类:固定数目优先级分配和最少优先级分配.给出了任意截止期模型下任务静态有限优先级可调度的充要条件以及不同静态有限优先级分配间转换时的几个重要性质,指出了系统优先级从低到高分配策略的优越性,定义了饱和任务组与饱和分配的概念,证明了在任务集合静态优先级可调度的情况下,最少优先级分配比固定数目优先级分配更具一般性.最后提出一种最少优先级分配算法LNPA(least-number priority assignment).与现有算法相比,LNPA适用范围更广,且复杂度较低.

基于矿井下含分支节点的CAN总线优先权分配

为了解决CAN总线在矿井下覆盖面积和实时通信的问题,对CAN总线的协议进行了修改,采用了节点分支的方法,扩大了覆盖面积;在传输的帧中加入体现优先权的仲裁字段,根据煤矿监控节点的多少采用静态或动态优先权分配机制,解决了冲突问题。实践证明,该种方法在保证了实时通信的同时,覆盖面积扩大了10倍以上。因此,该系统能够适用不同类型煤矿的井下监控任务。

优先级受限系统中可调度判定方法

在通信、雷达、导航以及各种消费类电子产品等民用和军事领域,嵌入式实时调度已逐渐成为电子电气系统的控制核心。针对同优先级任务使用FIFO调度的静态优先级系统,使用反例指出给定同优先级任务初始执行顺序的前提下,Katcher可调度判定条件的必要性不成立,提出并解析证明了FP可调度的充要条件。随机实验表明,对于高利用率下任务间执行时间差异较大的情况,约有15%的可调度任务集会被Katcher条件错判为不可调度。进一步的仿真和实例分析表明,Liu、Lehoczky、Bini等提出的条件不能判定相同优先级的情况,Katcher条件的必要性不成立,论文提到的条件能够正确判定任务集的可调度性。提出方法为实时系统调度的顶层设计提供了快速离线工具。

基于矿井下CAN总线的优先权分配及延时分析

针对煤矿监控安全现状,提出了以CAN总线为网络总线的矿井监控系统,并对CAN总线的协议进行了修改,在传输的帧中加入体现优先权的仲裁字段,根据煤矿监控节点的多少采用静态或动态优先权分配机制,并对CAN总线延时进行了分析,有效地解决了矿井下信息实时传输的问题。

公交信号优先控制的应用研究

公交信号优先以公交车流为控制目标,通过选择交通控制策略和设置相关参数,控制交通信号灯,减少公交车辆在路口的等待时间,提高公交车辆的运行优先级。详细介绍了公共交通信息与优先系统PTIPS的系统框架、通讯方式、主要功能、控制策略,并且分两类:基于信息反馈的动态优先;基于历史数据调查研究以及各种算法、理论推导的静态优先。详细阐述了各种控制策略的原理和适用情况。最后采用浦东张江有轨电车工程的实际应用情况作为示例,以动态优先策略为基点,各种检测设备的信息反馈为基础,较好地实现针对单辆有轨电车的优先放行。

到达时间服从泊松分布的平行机队列的最优随机排序问题

论文考虑多个分布下,根据每类加工时间函数最小化目标函数的不同类别的随机排序问题。这个问题常出现在分布式系统、网络和应用程序方面。模型中,最优排序策略在每台机器上是一个简单的静态优先策略。在这种排序策略下,排序问题可以寻找到最佳路径矩阵。考虑一个非线性规划问题,证明了任何局部最优即为全局最优,大大简化了,优化问题的解决方案。在到达时间为泊松分布的情形下,论文提供了一个最佳的排序策略,能够最小化每类时间函数。对一般各种静态实例应用此方法,可得到简单的近似算法。

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

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

基于时限单调算法的混合任务实时调度算法的研究与设计

周期任务与非周期任务的混合调度是实时调度研究的一个重要方向。针对现代嵌入式实时系统的任务特性,和经典实时调度算法只调度周期任务的特点,提出一种新的静态优先级调度算法——混合任务时限单调算法(Periodic and Aperiodic Deadline Monotonic,PADM)。该方法结合时限单调(DM)算法和先来先服务(FCFS)算法,将非周期任务量化为周期任务,且非周期任务在其裕度为零时优先级最高。通过理论分析和具体实验比较,在任务集轻载情况下,PADM算法尽可能地保证周期任务的完成率和非周期任务的时限,同时所带来的额外开销小,计算复杂度低,实现方便,是一种有效的混合任务调度算法。

Lottery Bus的设计与实现

为了提高SoC内部总线的性能,优化总线架构。文章提出了一种新颖的LotteryBus总线机制。通过将其与静态优先级及时分复用总线进行比较,介绍了它的特点及其仲裁机制。并且设计和实现了一个4-Masters的Lot-teryBus用于龙芯SoC内部高速总线的改进,功能仿真和FPGA验证证明这一总线机制的可行性和正确性。

伪造对区分服务的影响

在提供区分服务的定价方法中,Marbach提出的静态定价方法假设各个优先级的价格事先确定,如果ISP诚实,在用户进入市场后I,SP无法影响用户的服务选择来增加效用。如果ISP不诚实,通过伪造用户使用网络,从而影响用户的服务选择,由此增加效用。用户意识到ISP可能伪造,会采取检查网络市场的对策来确保ISP诚实。对于伪造的经济分析以及用博弈论方法进行的分析都表明ISP有可能伪造。毫无疑问I,SP伪造改变了用户和ISP的行为与效用,具体例子也说明了伪造的影响。

带有无限到达源的Re-entrant Line的稳定性(英文)

用Foster判别准则,Weiss[13]给出了带有无限到达源的两站三步re-entrant line的稳定性的充分条件．本文用两种不同的方法得到了其稳定性的充分必要条件,即: 二维随机游动方法和Foster判别准则．同时,我们又用流体模型方法得到了系统稳定的充分条件,大大地简化了Weiss[13]的证明．

Hadoop集群环境下本地性调度算法改进

Hadoop集群环境下本地性调度算法是提高数据本地性的算法。算法本质是提高数据本地性,减少数据传输时间,减少集群的网络I/O,提高资源利用率。由于调度算法采用FIFO方式,当前作业数据量大时将影响其他紧急性高的作业响应时间,降低系统性能。本文提出一种新的调度策略,即在保证原算法数据本地性的前提下,集成静态优先级的抢占调度策略。实验结果表明,在相同的数据集上,采用集成静态优先级抢占的调度策略,优先级高的作业响应时间较优先级低的作业响应时间减少。

空间站电源系统信息管理软件重构方案

针对空间站电源系统内部多个单机与其他系统进行多总线通信,实现系统内外之间数据交换的复杂信息管理需求,同时考虑到软件的可靠性和继承性,设计采用架构重构和代码重构的空间站电源系统信息管理软件,具有多任务处理实时性高的特征,能实现传统电源下位机软件代码复用,提高代码复用率。另外,通过设计基于多级静态优先级的任务调度模块,实现多总线数据流的合理通信和多任务的有效处理。文章提出的软件重构方案在空间站电源系统信息管理软件中进行应用,实现了38.47%的软件代码复用率,实时性任务的响应率提高了44.48%,可有效满足空间站电源系统的信息管理任务需求。

UIQ 手机操作界面的常青树

Symbian是由手机界的诺基亚、爱立信、索尼爱立信、松下、三星、西门子等六大巨头与Psion联合起来为了抵挡微软的进攻而成立的一个公司，专门开发属于自己的智能手机操作系统（Operation System）。Symbian OS由此诞生，它是一个开放的操作系统。采用基于静态优先级、多任务机制构成简捷、高效的内核，具有模块化的系统结构，提供了良好的扩充空间，支持强大的通信及多媒体功能。Symbian OS的最大优点是有诺基亚的鼎立支持，且对手机的硬件要求不高，而且注重用户体验。因此，在短短的四五年时间里，Symbian OS就已经占据了将近70％的智能手机市场份额。

机载惯导系统的EDF算法优化研究

文章针对机载惯导系统软件的通信模块中出现多任务同时争夺处理机的过载情况,提出一种改进的最早截止时间优先算法(DPEDF),以最大化完成任务的静态优先级之和为目标,引入动态规划的方法建立调度模型,计算近似最优调度序列,实现了导致过载发生的各个任务优先级的动态划分。通过示例展示了如何化解过载,保证实时系统正常运行。