硬实时调度的线性近似分析方法

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

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

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

周期多帧任务的固定优先级调度算法的调度分析

实时操作系统的核心问题－－实时任务的调度是实时系统研究的重点之一。主要讨论了周期多帧任务的固定优先级调度算法的调度情况,证明了对于周期多帧任务DM算法不是最优的,同时也证明了对于累积单调周期多帧任务的DM算法是最优的。     

一种固定优先级实时调度算法的可行性测定

实时调度算法是实时系统的关键技术,验证实时调度算法的可行性是保证实时系统性能的必要手段。不同实时调度算法可行性测定方法不同。在简单实时模型上,针对固定优先级实时调度算法给出通过任务最坏响应时间来测定调度算法可行性的方法,分析了影响任务最坏响应时间的各种因素,修正了响应时间方程,将该方法运用在复杂实时模型中。     

一种固定优先级实时调度算法的可行性测定

实时调度算法是实时系统的关键技术,验证实时调度算法的可行性是保证实时系统性能的必要手段.不同实时调度算法可行性测定方法不同.在简单实时模型上,针对固定优先级实时调度算法给出通过任务最坏响应时间来测定调度算法可行性的方法,分析了影响任务最坏响应时间的各种因素,修正了响应时间方程,将该方法运用在复杂实时模型中.     

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

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

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

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

用PID控制近似线性自抗扰控制

线性自抗扰控制(LADRC)是结合PID和现代控制理论发展起来的新型控制方法,很多文献表明PID可以转化为LADRC,那么LADRC能否近似为PID,并且近似效果如何,目前没有确定的答案.本文首先证明LADRC的积分作用实际上包含在扰动的估计及补偿里,说明了二阶LADRC和PID的关系.然后根据LADRC阶数的不同,本文提出了实际PID+n阶超前环节的策略近似各阶LADRC.通过仿真实例,说明二阶和三阶LADRC和转化后的PID具有相似的抗干扰性能,但更高阶的LADRC转换得到的PID控制效果不如LADRC.因此,LADRC是PID控制在工业过程控制中的推广,具有更多的应用前景.     

2轮Trivium的线性逼近研究

Triviurn是国际重要的序列密码,贾艳艳等人曾提出对2轮Trivium进行单线性和多线性密码攻击（电子与信息学报,2011年第1期）。针对其中的线性近似方程个数少和偏差小问题,提出通过改变第1轮Trivium所占的时钟数和线性逼近式的方法对2轮进行线性逼近,给出一个偏差为2书的线性符合和8个偏差为2。。的线性符合,并利用贾艳艳文中算法对2轮Trivium进行单线性和多线性密码攻击。研究结果表明,在相同攻击成功概率的前提下,所需的数据量均为上文中所需数据量的1／16,即需要选择初始化向量的个数分别为258和257。     

Energy aware fixed priority scheduling in mixed-criticality systems

Most of studies about energy management for MC systems are based on dynamic priority scheme. The disadvantages of dynamic priority scheme are high system overhead and poor predictability. Unlike previous studies, we focus on the problem of scheduling mixed-criticality (MC) periodic tasks with minimizing energy consumption in MC systems based on fixed priority scheme. Firstly, we explain a criticality rate monotonic scheduling (CRMS) and propose the sufficient schedulability condition of CRMS. Secondly, we compute the energy minimization uniform scaled speed and present an optimal static solution algorithm based on CRMS. The extra workload of the high criticality level (HI) task executes with the maximum processor speed in the high criticality mode (HI-mode). But this algorithm does not exploit the slack time generated from the HI task in the low criticality mode (LO-mode). For energy efficiency, we propose a dynamic fixed priority energy minimization algorithm which exploits the slack time generated from the HI task in LO-mode to save energy. In addition, it combines a dynamic voltage and frequency scaling technique and a dynamic power management technique to reduce energy consumption. Finally, the experiments are applied to evaluate the performance of the proposed algorithm and the experimental results show that the proposed algorithm can save up 23.89% energy compared with other existing algorithms.     

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

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

一种基于任务响应时间预测的网格调度算法的研究

针对网格环境下计算节点的自治性、异构性、分布性等特征,提出了一种动态的基于任务响应时间预测的调度算法。该调度方法依据历史数据和最近访问过计算节点的任务请求提交时间、任务完成时间、网络通信延迟等信息,预测计算节点将来的任务响应时间,将任务提交给轻负载或性能较优的计算节点完成。实验结果表明,该方法不但可以有效减少不必要的延迟,而且在任务响应时间、任务的吞吐率及任务在调度器内等待被调度的时间方面比随机调度等传统算法要优。     

Convergence of perturbation analysis based optimization algorithm with fixed number of customers period

In this paper we show that an optimization algorithm using infinitesimal perturbation analysis converges to the minimum of the performance measure. The algorithm is updated every fixed number of customers period rather than every one or two busy periods. The key step of the proof is to verify that the observation noises satisfy the strong law of large numbers. Then applying a stochastic approximation theorem leads to the desired results.     

Power-aware fixed priority scheduling for sporadic tasks in hard real-time systems

In this paper, we consider the generalized power model in which the focus is the dynamic power and the static power, and we study the problem of the canonical sporadic task scheduling based on the rate-monotonic (RM) scheme. Moreover, we combine with the dynamic voltage scaling (DVS) and dynamic power management (DPM). We present a static low power sporadic tasks scheduling algorithm (SSTLPSA), assuming that each task presents its worst-case work-load to the processor at every instance. In addition, a more energy efficient approach called a dynamic low power sporadic tasks scheduling algorithm (DSTLPSA) is proposed, based on reclaiming the dynamic slack and adjusting the speed of other tasks on-the-fly in order to reduce energy consumption while still meeting the deadlines. The experimental results show that the SSTLPSA algorithm consumes 26.55–38.67% less energy than that of the RM algorithm and the DSTLPSA algorithm reduces the energy consumption up to 18.38–30.51% over the existing DVS algorithm.     

Engineering and analysis of fixed priority schedulers

Scheduling theory holds great promise as a means to a priori validate timing correctness of real-time applications. However, there currently exists a wide gap between scheduling theory and its implementation in operating system kernels running on specific hardware platforms. The implementation of any particular scheduling algorithm introduces overhead and blocking components which must be accounted for in the timing correctness validation process. This paper presents a methodology for incorporating the costs of scheduler implementation within the context of fixed priority scheduling algorithms. Both event-driven and timer-driven scheduling implementations are analyzed. We show that for the timer-driven scheduling implementations the selection of the timer interrupt rate can dramatically affect the schedulability of a task set, and we present a method for determining the optimal timer rate. We analyzed both randomly generated and two well-defined task sets and found that their schedulability can be significantly degraded by the implementation costs. Task sets that have ideal breakdown utilization over 90% may not even be schedulable when the implementation costs are considered. This work provides a first step toward bridging the gap between real-time scheduling theory and implementation realities. This gap must be bridged for any meaningful validation of timing correctness properties of real-time applications     

Linear cryptanalysis of NUSH block cipher

NUSH is a block cipher as a candidate for NESSIE. NUSH is analyzed by linear crypt-analysis . The complexity δ = (ε , η) of the attack consists of data complexity ε and time complexity η. Three linear approximations are used to analyze NUSH with 64-bit block. When |K| = 128 bits, the complexities of three attacks are (258, 2124), (260, 278) and (262, 255) respectively. When |K| = 192 bits, the complexities of three attacks are (258, 2157) (260, 2%) and (262, 258) respectively. When |K| = 256 bits, the complexities of three attacks are (258, 2125), (260, 278) and (262, 253) respectively. Three linear approximations are used to analyze NUSH with 128-bit block. When |K|= 128 bits, the complexities of three attacks are (2122, 295), (2124, 257) and (2126, 252) respectively. When |K| = 192 bits, the complexities of three attacks are (2122, 2142), (2124, 275) and (2126, 258) respectively. When |K|= 256 bits, the complexities of three attacks are (2122, 2168), (2124, 281) and (2126, 264) respectively. Two l     

An efficient response-time analysis for real-time transactions with fixed priority assignment

In the general context of tasks with offsets (general transactions), only exponential methods are known to calculate the exact worst-case response time (WCRT) of a task. The known pseudo-polynomial techniques give an upper bound of the WCRT. In this paper, we present a new worst-case response-time analysis technique (mixed method) for transactions scheduled by fixed priorities, and executing on a uniprocessor system. This new analysis technique gives a better (i.e. lower) pseudo-polynomial upper bound of the WCRT. The main idea is to combine the principle of exact calculation and the principle of approximation calculation, in order to decrease the pessimism of WCRT analysis, thus allowing improving the upper bound of the response time provided while preserving a pseudo-polynomial complexity. Then we define the Accumulative Monotonic property on which a necessary condition of feasibility is discussed. We also propose, to speed up the exact and mixed analysis, the dominated candidate task concept that allows reducing significantly the number of critical instants to study in an analysis.