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

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

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

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

容错优先级混合式分配搜索算法

在实时系统中,由于任务未能及时产生正确结果将导致灾难性后果,容错对于实时系统的有效性及可靠性至关重要.基于最坏响应时间计算的可调度性分析,提出了一种容错优先级混合式分配搜索算法.这种算法通过允许替代任务既能运行在高优先级别上,又可运行在低优先级别上,有效地提高了系统的容错能力.通过实验测试,与目前所知的同类算法相比,在提高系统容错能力方面更为有效.     

多媒体网络中基于优先级调度的实时QoS研究

使用到达函数和服务函数描述不同优先级实时分组集的到达和处理,基于期望可调度性来刻画不同紧急程度的实时应用对延迟的要求。提出的方法能够实现实时QoS控制下的瞬时特性研究,判定某一时刻不同优先级分组集的可调度性。最后对指数分布服务时间下的不同优先级分组集的期望可调度性进行了研究,基于理论结论的数值结果和基于模型的模拟结果是一致的。     

一种实时任务可调度性预测研究

对于嵌入式系统来说，通过预测一个任务能否在绝对时限之前运行完成而决定是否调度执行是很有意义的。在ARMLinux上，为了对新任务的运行结束时间进行预测，对它的内核作了修改，按优先级排序就绪队列，每次时钟中断判断是否有优先级比当前任务更高的任务就绪，以决定是否调度，去掉了SCHED_RR调度策略，这样新任务的运行结束时间可以得到准确的计算，并根据任务的绝对时限来判断对新任务的接受和拒绝，对修改后的内核进行了试验验证。     

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

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

全局EDZL实时调度算法的可调度性判定

可调度性判定就是离线验证实时系统中所有任务是否可调度。通过可调度性判定,能够更好地保证实时系统的可靠性。有多种分析方法可用于可调度性判定,得到的结果有所不同。通过分析在多处理器实时系统中全局EDZL算法的任务需求,考虑带入作业和带出作业对处理器资源的需求。引入最大连续忙区间的概念,以确定带入作业的最大个数,得到了多处理器实时系统中全局EDZL算法的可调度性判定算法。实验结果说明了这种方法提高了通过可调度性判定的任务数量,是一种更紧密的可调度性判断方法。     

多处理器系统实时调度的可预测性

在多处理器实时系统中,由于调度的不规则性,系统的可预测性判定问题尤为重要。针对多处理器系统中实时任务调度的可预测性问题,给出了不可预测的实时任务集反例,证明了一种可预测的实时任务集合。对于多处理器实时系统中常用的最早截止期零松弛调度算法(earliest deadline zero laxity,EDZL)的可预测性,利用EDZL算法的基本性质,用一种简捷的方法证明了EDZL算法是可预测的。通过仿真系统验证了证明的正确性,该方法可用于多处理器及分布式实时系统的设计和验证。     

基于AADL的综合航电分区系统可调度性判定

综合模块化航电(IMA)系统中的分区系统提高了其可靠性和安全性,但在系统设计和实现过程中,应采用各种分析和验证方法确保系统的时间需求得到满足。为此,针对符合ARINC653规范的IMA系统,根据分区系统层级调度的特性,提出一种基于仿真的分区任务集可调度性判定方法。借助Cheddar工具及其自定义调度策略功能,使架构分析和设计语言(AADL)具有对分区系统进行建模的能力,并利用该工具对AADL模型进行仿真以判定系统的可调度性。实例分析结果表明,该方法能自动、准确、快速地进行可调度性判定,并以甘特图的方式绘制任务调度过程,得到直观、详细的结果。     

硬实时系统中基于软件容错模型的容错调度算法

在硬实时系统中,由于任务超时完成将会导致灾难性后果,因此硬实时系统必须具有实时性和可靠性保障.软件容错模型是提高硬实时系统容错能力的一种有效方法.针对硬实时系统中容错优先级两种分配策略存在的不足,基于软件容错模型提出了一种容错优先级可提升的双重优先级分配策略.该方法通过为替代版本分配双重优先级,不仅能够提高硬实时系统的容错能力,同时还能够显著减少任务间的抢占次数.为了获得双重优先级分配的最佳策略,基于任务最坏响应时间的可调度性分析,首先提出了一种最大的双重优先级配置搜索算法(MDPCSA).然后结合MDPCSA算法,提出了一种最优的双重优先级配置搜索算法（ODPCSA）.仿真实验表明,与两种分配策略相比,在提高系统容错能力和降低抢占开销方面更为有效.     

多路有序优先级和有序环形仲裁器设计

为解决传统仲裁器不能记忆请求顺序的问题,设计多路有序优先级仲裁器和有序环形仲裁器。通过先入先出(FIFO)电路来保存请求的先后顺序,将FIFO电路分别与优先级仲裁器和环形仲裁器组合,从而构成有序仲裁器。实验结果表明,该设计能简化复杂度,提高仲裁器处理请求能力,但延时和面积性能略有下降。     

缓冲区结构效率分析

I/O设备与CPU的速度不匹配,制约了计算机系统性能的进一步提高。为此,根据计算机体系结构,对缓冲区结构的效率进行分析,使用EDA计算机辅助设计软件QuartusII设计异步双时钟FIFO缓冲区,并对其进行仿真验证及数据记录,通过对数据的分析,证明系统整体效率与FIFO效率密切相关,只有实现FIFO效率的最大化,才能使系统整体效率最大化,同时FIFO效率最大化也只能在完成系统效率最大化的过程中得以实现。     

基于哈希算法的脏数据回写磁盘实时调优策略

针对传统数据库缓冲池脏数据回写磁盘策略实时性与安全性差的问题,提出基于Hash算法与先入先出(FIFO)双向链表的数据库缓冲池脏数据回写磁盘实时调优策略。利用基于负载的调优策略创建多个内存FIFO队列链表,通过Hash算法将数据库缓冲区内的脏数据块按最后修改时间随机分配到不同队列负载中,实现FIFO队列链表的负载均衡,并利用全局时序约束将链表队列中的脏数据块分批回写磁盘,以解决传统脏数据回写磁盘策略系统资源消耗大与宕机后数据丢失风险高的问题。实验结果证明,该策略能提高脏数据回写的实时性及安全性,降低数据丢失率。     

Model-level WCET analysis of real-time system based on FPN

Worst Case Execution Time （WCET） is the major characteristic which describes time predictability of the real-time system. A model-level WCET analysis method based on Fuzzy Petri Net （FPN） is presented to improve the accuracy of WCET analysis. The whole WCET analysis is divided into three phases, FPN modeling, flow analysis and low-level analysis. Since the low-level WCET analysis is performed on the generated FPN code, and global timing effects stretching across the borders of single blocks can be taken into account, so it can improve the accuracy of WCET analysis. Moreover, by using twice the WCET analysis method and the additional information through analyzing the possible behavior of the FPN model, a more precise WCET estimation is achieved than by just analyzing the generated source code alone.