固定优先级调度的线性近似分析方法

通过线性逼近硬实时系统任务的工作负荷量的方法,一个更加接近精确响应时间的时间上限能有效地降低调度分析时间。同时该上限用于任务集的充分性可调度测试时具有线性时间的复杂度。这种线性上限的可调度性测试能够用于交互的系统工具设计、基于搜索的系统优化以及任务集的动态接纳新任务的设计中。并且新的调度系统模型无时间死线、抖动大小限制,适用范围更广。相关的实验也表明响应时间上限可调度性分析提高了准确调度测试的效率。     

静态优先级实时任务的多项式时间近似分析

经典的硬实时任务响应时间分析及其各种基于初始值的递归改进无法适用交互的实时设计环境.高效的近似分析方法是一种有效的选择,提出能高效计算任务最差响应时间上限的方法并给出与精确调度的误差量化分析,定义响应时间分析的线性近似请求约束函数并由此提出一个具有ε参数多项式时间复杂度的死线约束分析方法.针对死线约束分析方法本文将采用经典的近似比率技术和资源增值技术来分析该方法所提供的性能保证的程度.随机任务集的相关实验证明了所提出近似方法的有效性.     

基于裁剪的弱硬实时调度算法

针对当前弱硬实时调度算法无法保证超过窗口长度的执行序列的满足率达到一定比例的问题,基于(m~-,p)弱硬实时约束,提出了一种基于裁剪的调度算法(cut-down based scheduling,简称CDBS).由于判断(m~-,p)约束是否满足需要遍历任务的整个执行序列,因此判断复杂度很大.为此,提出一种高效的裁剪执行序列的算法,同时证明其正确性,并利用适当的数据结构,使得计算复杂度与序列长度无关,通过实验说明其降低计算复杂度的有效性.进一步与其他经典实时调度算法(EDF(earliest deadline first),DBP(distance-based priority),DWCS(dynamic window constraint schedule))进行比较,验证该算法与其他算法具有相当的性能.     

反馈控制实时调度中采样周期的研究

以CPU资源调度为典型应用背景，研究并分析了采样周期对反馈控制实时调度和一般数字控制系统性能影响的差异，通过仿真实验得出采样周期的选择对反馈控制实时调度性能影响规律，提出了采样周期的选择方法。对于平均执行时间难以预测的任务集，提出一种可变采样周期的有效解决方案。     

容错多处理机中一种高效的实时调度算法

针对基于主副版本容错的多处理机中独立的、抢占性的硬实时任务,提出了一种高效的调度算法——TPFTRM(task partition based fault tolerant rate-monotonic)算法.该算法将单机实时RM 算法扩展到容错多处理机上,并且调度过程中从不使用主动执行的任务副版本,而仅使用被动执行和主副重叠方式执行的任务副版本,从而最大限度地利用副版本重叠和分离技术提高了算法调度性能.此外,TPFTRM 根据任务负载不同将任务集合划分成两个不相交的子集进行分配;还根据处理机调度的任务版本不同,将处理机集合划分成3 个不相交的子集进行调度,从而使TPFTRM 调度算法便于理解、实现以及减少了调度所需要的运行时间.模拟实验对各种具有不同周期和任务负载的任务集合进行了调度测试.实验结果表明,TPFTRM与目前所知同类算法相比,在调度相同参数的任务集合时不仅明显减少了调度所需要的处理机数目,还减少了调度所需要的运行时间,从而证实了TPFTRM 算法的高效性.     

基于相似压缩的近似线性SVM

为了解决模式识别中的近似线性可分问题,提出了一种新的近似线性支持向量机(SVM).首先对近似线性分类中的训练集所形成的两类凸壳进行了相似压缩,使压缩后的凸壳线性可分;基于压缩后线性可分的凸壳,再用平分最近点和最大间隔法求出最优的分划超平面.然后再通过求解最大间隔法的对偶问题,得到基于相似压缩的近似线性SVM.最后,从理论和实证分析两个方面,将该方法与线性可分SVM及推广的平分最近点法进行了对比分析,说明了该方法的优越性与合理性.     

实时人工智能的研究

1 引言随着实时技术的发展,实时系统对制造、控制、运输、太空、机器人和军事系统起着越来越关键性的作用。实时系统是工作在时间约束下的系统,它与一般的计算机系统有本质的区别。实时系统不但要保证计算结果的逻辑正确性,而且必需在截止期内完成任务。在硬实时系统中,如果实时任务没有在规定的截止期内     

近似线性时间的社团结构动态演化挖掘算法

探测网络社团结构对于分析、设计复杂的自然或工程网络至关重要,然而现有的探测技术主要依托于最优化和启发式算法,不能兼顾计算效率和准确性。因此提出了一种基于演化迭代技术的动态社团探测算法,它能准确高效地发现网络中的社团结构。首先引入了一个离散时间的动态系统,通过描述社团划分收敛到特定指标最优的演化轨迹来确定社团划分。接着提出了一个一般化的指标函数,以确定网络中最优的社团数量及最稳定的社团结构。该指标函数极具概括性,改变相应的参数即可引申到各种已广泛应用的指标函数。针对参数选择的困难,利用图生成模型自动确定社团划分的指标函数。此算法效率很高,计算复杂度与稀疏网络中的节点数量呈近似线性关系。最后,在人工和真实网络中进行了大量的仿真实验来测试算法表现,结果显示所提算法能够揭示很多有价值的信息。     

基于有限的共享资源模型实现嵌入式硬实时Linux

首先分析了采用双核方案实现硬实时Linux存在的问题,然后基于有限的共享资源模型提出了一种在单Linux内核上实现嵌入式硬实时Linux的新思路,并在Linux 2.6内核上予以完整实现。在目标平台上实测结果表明,从硬实时任务中断产生到硬实时任务得到调度执行的最大延迟小于100μs,可以满足绝大多数嵌入式硬实时系统的要求。     

Scheduling algorithms based on weakly hard real-time constraints

The problem of scheduling weakly hard real-time tasks is addressed in this paper.The paper first analyzes the characters of μ-pattern and weakly hard real-time constraints,then,presents two scheduling algorithms,Meet Any Algorithm and Meet Row Algorithm,for weakly hard real-time systems.Different from traditional algorithms used to guarantee deadlines,MeetAny Algorithm and Meet Row Algorithm can guarantee both deadlines and constraints.Meet Any Algorithm and Meet Row Algorithm try to find out the probabilities of tasks breaking constraints and increase task‘s priority in advance,but not till the last moment.Simulation results show that these two algorithms are better than other scheduling algorithms dealing with constraints and can largely decrease worst-case computation time of real-time tasks.     

嵌入式操作系统的硬实时微内核设计

目前的嵌入式实时操作系统存在着内核结构较为复杂、臃肿、稳定性不高、对硬实时应用支持不足等问题.针对这些问题,结合现有的操作系统内核理论及嵌入式实时系统的特殊需求,通过组件化的设计,将内核划分为核心态基本模块及用户态扩展模块,提供多种进程间通讯(IPC)方式,并引入独特的硬实时抢占式调度机制,设计出一种精炼、稳定的硬实时微内核.通过这种设计思路成功开发出了昊鹏(Hopen)操作系统新版内核,应用于最新的3G手机产品上,取得了非常好的效果.     

开放式实时系统双层调度框架的一种改进方案

分析了开放式实时系统双层调度框架的调度特点,指出了其仅适用于硬实时环境的缺陷。在保证硬实时应用可调度性的基础上,针对硬实时和软实时应用的不同特点提出了一种改进方案,增加了软实时应用的处理,拓展了原方案的适用范围,完善了开放式实时系统的双层调度框架,最后用理论证明与仿真实验验证了改进方案的有效性。     

基于双层调度框架的开放式实时系统非实时应用调度

在开放式实时系统中,多类型实时和非实时应用同时并存,这给系统调度机制带来了新的需求和挑战。对一种开放式实时系统调度机制进行了简单的介绍,指出了非实时应用调度时不可抢占区可能影响系统可调度性,并提出了一种解决方案,弥补了原有调度机制的缺点,完善了开放式实时系统的双层调度框架,保证了开放式实时系统并存多类型实时及非实时应用的可调度性。     

硬实时混合任务在线节能调度技术分析

对混合实时任务节能调度技术进行了分析,深入探讨了目前优秀的硬实时系统在线节能调度算法(OLDVS),指出其存在不足的原因 ,即松弛时间丢失和松弛时间转移。为了提高其节能效果,给出了多种改进思路,为进一步研究工作做出有益的探索。     

Engineering a hard real-time system: From theory to practice

More and more programmers find their software being used in performance critical applications. Unfortunately, they have limited techniques at their disposal to help guarantee this particular aspect of their programs. There has been considerable activity in recent years on developing analysis techniques for hard real-time systems. Inevitably these techniques make simplifying assumptions so as to reduce the complexity of the problem to be solved. For example hard real-time schedulability analysis techniques often assume that the timing properties of the underlying kernel can be accounted for by incorporating extra execution time into the application tasks. Furthermore, they assume that the application task structure is very simple and uniform. This paper considers the implications of using these techniques in the analysis of a typical single processor application, the attitude and orbital control system (AOCS) for the Olympus satellite. The paper outlines a common approach for estimating the response times for tasks, and then extends the scheduling equations so that they can be used in the engineering of realistic real-time systems.     

A hardware supported operating system kernel for embedded hard real-time applications

The concept of the kernel, i.e. the time critical part of a real-time operating system, and its dedicated co-processor, especially tailored for embedded applications, are presented. The co-processor acts as a system controller and operates in conjunction with one or more conventional processors in hard real-time environments. It is composed of three physically and clearly separated layers which vary with regard to implementation, speed and complexity. Correspondingly, the model of the operating system kernel is hierarchically structured, and functions are mapped to these layers, observing the inherent parallelism of recognition and handling of different kinds of events expected in such environments and higher level kernel functions such as tasking operations. The operating system functions are supported by the high level real-time programming language constructs. Since many embedded systems are safety related, the software employed must be highly dependable. Therefore, the kernel was proven correct with formal methods, which represents a major innovation in software technology.     

基于杂交遗传算法的多处理器硬实时容错调度算法

传统的硬实时容错调度算法获得了较好的容错性能,但其任务拒绝率、处理器分配偏差比例以及最早完成时间等性能参数不佳,对此提出一种基于杂交遗传算法的优化方案,并对传统的硬实时容错算法进行优化。采用了中心型调度模型,并采用了任务备份方案来实现容错能力。将任务拒绝率、处理器分配偏差比例以及最早完成时间三个优化参数作为遗传算法适应度目标函数的三个带权分量,对其进行优化,通过遗传算法的杂交与迭代计算获得了优化的结果。最终使用不同的任务数量与处理器数量的组合对本算法与传统算法进行对比试验,结果可看出本算法的3个优化参数明显优于传统算法,且总适应度值亦比传统算法有明显改进。     

应用于实时控制系统的线程池调度策略设计

在进行多任务实时控制系统设计时,采用线程池技术是一种有效的解决方法,但必须首先避免超时的发生。为了降低线程完成的超时发生率,采用Half-Sync/Half-Async线程池架构建立实时控制系统的线程池,利用最小二乘支持向量回归机（LSSVR）对线程执行时间进行预测估计,再基于估计结果对线程池线程的分配调度优先级别算法进行设计。性能测试以无线图像传感器网络节点为对象对所设计的LSSVR线程池及其他线程池在不同状态下的超时发生率做了比较,结果表明在大多数应用情况下LSSVR线程池在抑制超时方面具有明显的优越性。