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

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

RM及其扩展可调度性判定算法性能分析

可调度性判定是实时调度算法的关键问题．单调速率算法RM（rate monotonic）及其扩展是应用广泛的实时调度算法，大量文献讨论了实时任务在这些算法下的可调度性判定，给出了相应的判定算法．但迄今为止，对这些判定算法的性能分析都是理论上的定性分析或者只是少数几种判定算法之间的简单比较，这不利于实时系统的开发．归纳了RM及其扩展的可调度性判定算法，通过测试平台，系统地测试和分析了各算法的性能和适用场合，讨论了各种条件和实现方式对算法性能和可调度性的影响．

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

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

基于逻辑"或"约束优化的实时系统设计

标准约束优化问题的等式或不等式约束之间是逻辑“与”关系，目前已经有很多高效、收敛的优化算法．但是，在实际应用中有很多更一般的约束优化问题，其等式或不等式约束之间不仅包含逻辑“与”关系，而且还包含逻辑“或”关系，现有的针对标准约束优化问题的各种算法不再适用，给出一种新的数学变换方法，把具有逻辑“或”关系的不等式约束转换为一组具有逻辑“与”关系的不等式，并应用到实时单调速率调度算法的可调度性判定充要条件中，把实时系统设计表示成混合布尔型整数规划问题，利用经典的分支定界法求解．实验部分指出了各种方法的优缺点．

单调速率及其扩展算法的可调度性判定

任务可调度性判定是实时系统调度理论研究的核心问题.单调速率(RM)算法是实时调度的重要算法,自其提出以来已被广泛研究.然而到目前为止,尚缺乏专题性的文章来系统而深入地探讨RM及其扩展算法的可调度性判定,以及各种现实条件和实现方式(包括任务调度的时间开销和任务同步问题等)对可调度性的影响.围绕RM算法下的可调度性判定问题,由浅入深,系统性地讨论各种不同假设和实现方式对可调度性的影响,具体分为下述3大类问题:(1)理想的RM算法下的可调度性判定的CPU利用率最小上界及可调度的充分必要条件;(2)考虑调度时间开销情况下的可调度性判定条件;(3)优先级反转协议及其对可调度性的影响.给出了具体实例来阐述上述问题,并从算法复杂度和可检测率两方面来比较各种算法的优劣.

Algorithm for simulating fracture processes in concrete by lattice modeling

To simulate fracture behaviors in concrete more realistically, a theoretical analysis on the potential question in the quasi-static method is presented, then a novel algorithm is proposed which takes into account the inertia effect due to unstable crack propagation and meanwhile requests much lower computational efforts than purely dynamic method. The inertia effect due to load increasing becomes less important and can be ignored with the loading rate decreasing, but the inertia effect due to unstable crack propagation remains considerable no matter how low the loading rate is. Therefore, results may become questionable if a fracture process including unstable cracking is simulated by the quasi-static procedure excluding completely inertia effects. However, it requires much higher computational effort to simulate experiments with not very high loading rates by the dynamic method. In this investigation which can be taken as a natural continuation, the potential question of quasi-static method is analyzed based on the dynamic equations of motion. One solution to this question is the new algorithm mentioned above. Numerical examples are provided by the generalized beam (GB) lattice model to show both fracture processes under different loading rates and capability of the new algorithm.

Iris recognition algorithm based on point covering of high-dimensional space and neural network

In this paper, we constructed a Iris recognition algorithm based on point covering of high-dimensional space and Multi-weighted neuron of point covering of high-dimensional space, and proposed a new method for iris recognition based on point covering theory of high-dimensional space. In this method, irises are trained as "cognition" one class by one class, and it doesn't influence the original recognition knowledge for samples of the new added class. The results of experiments show the rejection rate is 98.9%, the correct cognition rate and the error rate are 95.71% and 3.5% respectively. The experimental results demonstrate that the rejection rate of test samples excluded in the training samples class is very high. It proves the proposed method for iris recognition is effective.

An improved BP algorithm for pattern recognition

An improved BP algorithm for pattern recognition is proposed in this paper. By a function substitution for error measure, it resolves the inconsistency of BP algorithm for pattern recognition problems, i.e. the quadratic error is not sensitive to whether the training pattern is recognized correctly or not. Trained by this new method, the computer simulation result shows that the convergence speed is increased to treble and performance of the network is better than conventional BP algorithm with momentum and adaptive step size.

A nonmonotonic dependence of standard rate constant on reorganization energy for heterogeneous electron transfer processes on electrode surface

In the present work a nonmonotonic dependence of standard rate constant (k(0)) on reorganization energy (lambda) was discovered qualitatively from electron transfer (Marcus-Hush-Levich) theory for heterogeneous electron transfer processes on electrode surface. It was found that the nonmonotonic dependence of k(0) on lambda is another result, besides the disappearance of the famous Marcus inverted region, coming from the continuum of electronic states in electrode: with the increase of lambda, the states for both Process I and Process II ET processes all vary from nonadiabatic to adiabatic state continuously, and the lambda dependence of k(0) for Process I is monotonic thoroughly, while for Process II on electrode surface the lambda dependence of k(0) could show a nonmonotonicity.