一种改进的优先级继承协议及其算法研究

优先级反向是实时系统中由于任务间需要共享资源以及同步而引起的高优先级任务被低优先级任务阻塞的现象。优先级反向使得高优先级任务的执行时间无法预测，增加了实时系统的不确定性。早期的扩展协议较好地解决了优先级反转问题，但同时也存在着自身的不足。针对这些缺陷，在深入研究相关协议的基础上，该文提出了一种改进的优先级继承协议。该协议中信号量按预定义的非循环固定顺序获取，以防止死锁发生，设置超时保护机制，避免任务在获取信号量时长时间的阻塞，给出了关于该协议的分析，并在实时Linux上实现了基于该协议的算法。     

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

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

一种解决μC/OS中优先级反转问题的方案

针对实时系统中的优先级反转问题,提出了一种采用优先级继承机制来解决优先级反转问题的方案,并给出了在μC/OS中的实现。该方案基于互斥信号量,描述了相应的数据结构和主要算法并对算法作了简要的分析。     

Linux互斥锁机制的研究及改进

Applications with real-time constraints are not only growing in the field of embedded system, but gaining popularity in the desktop environment as well. At the same time, using an opened source system ,Linux, as the sup-ported OS is more and more appealing to many developers. So it is regarded as a potential aspect by many users to im-prove Linux performance to satisfy the real-time requirements. The article discusses the mutex implementation of Linux in depth and on the basis of that, gives rise to methods to improve the deficiency. An implementation underversion of 2.2 series is brought forward.     

Java线程在不同平台下的表现

论文在线程、多线程概念的基础上,通过对Java语言在多种不同平台环境下的不同表现进行阐述和分析,讨论了引起各种不同表现的根源本质。     

利用堆实现优先队列

利用堆实现的优先队列实质是一棵顺序存储的二叉树。所以具有很好的时间、空间性能。比传统的优先队列具有更广泛的应用前景。可在计算机的各种排队算法中推广应用。     

卫星全球普查任务规划系统预处理模块的开发

全球普查任务利用地球观测卫星季节性地动态监测地球表面变化，是遥感技术在全球变化监测中一种应用。卫星全球普查任务规划系统为全球普查任务的实施提供了技术和工具支持。该文介绍了卫星全球普查任务规划系统中预处理模块的设计和实现，分析了预处理模块的结构和功能，重点讨论了全球表面场景划分的可视化、时间窗口计算和分析、卫星日常图像采集活动中候选场景的确定和场景拍摄优先级的动态调整的关键技术。     

基于GA的网络最短路径多目标优化算法研究

针对现有基于遗传算法(GA)优化的网络最短路径算法存在优化目标单一、遗传编码质量低、搜索策略间平衡性差、适应度分配效率与灵活性较低等问题,建立一种多目标优化最短路径自适应GA模型,提出了优先级编码和优先级索引交叉算子,引入了遗传算子参数的模糊控制机制和基于自适应加权的适应度分配方法.实验结果表明,该算法的准确性和稳定性高、复杂度合理,实现了对网络设计优化中多目标最短路径问题的高质量求解.     

prialt in Handel-C: an operational semantics

We describe an operational semantics for the hardware compilation language Handel-C [7], which is a C-like language with channel communication and parallel constructs which compiles down to mainly synchronously clocked hardware. The work in this paper builds on previous work describing the semantics of the “prialt” construct within Handel-C [5] and a denotational semantics for part of the language [6]. We describe a key subset of the language and show how a design decision for the real language, namely that default guards in a prialt statement executed in “zero-time”, has consequences for the complexity of the operational semantics. We present the operational semantics, along with a revised and completed prialt semantics, indicating clearly the interface between them. We then describe a notion of observational equivalence and present an example illustrating how we handle the complexity of nested prialts in default guards.     

基于优先级考试自动编排的算法研究

利用计算机进行考试自动编排,涉及到的约束条件纷繁复杂,本文论及了一种基于优先级的考试编排算法,根据约束条件将教师,教室,课程各定义一个特征函数,来计算他们各自的优先级别,结合分治法、贪婪法等多种算法思想来排出无冲突的,人性化的考试编排表。     

实时通告服务设计与实现

OMG通告服务为对策之间提供强有力的解耦通信支持,是CORBA提供的重要服务之一,目前很多应用需要之间的通信具有实时性,而现有的通告服务规范已不能满足这种需求,为此,设计并实现了具有实时功能的通告服务,提出了一种实时通告服务的体系结构,讨论了实时通告服务系统的实现技术。     

渲染网格调度策略研究

针对渲染网格的特点提出了渲染网格的二个调度模型.模型一提出了在局部资源的计算结点内,采用基于用户优先级的CPU频度轮转调度方案,达到提高系统吞吐率的目的.模型二提出了适合市场机制的渲染网格调度模型,并给出了竞标的报价算法.该算法在公共网格开放软件Globus Toolkit4.0上实现,符合国际标准WSRF规范.实验结果表明本调度策略在处理渲染网格任务时性能得到了很好的体现.     

On implicit data structures for priority queues

Certain implicit data structures for priority queues are implemented and compared with a simple linked structure. Timing experiments show that implicit structures are rather slow.     

一种改进的基于样本块的目标移除方法

图像修补的目的是对指定的区域进行修补,填补该区域的信息,并且要求最终图像的原有区域与填补区域间的过渡自然,尽量减少人工痕迹。Criminisi曾提出一种基于样本块的图像修补方法,这种方法不仅适用于对数字图像中的大面积破损区域进行修补,而且可以用于移除图像中不想要的目标物。对Criminisi的方法进行改进,在计算优先权时增加多个已知像素的梯度信息,并且用加法代替乘法防止了快速衰减,对于一些比较特殊的图像,通过改变修补顺序提高修补效果。大量实验结果表明,与Crimini-si的方法相比,该方法能够取得更好的视觉效果。     

Dual ceiling protocol for real-time synchronization under preemption threshold scheduling

The application of object-oriented design methods to real-time embedded systems is seriously hindered by the lack of existing real-time scheduling techniques that can be seamlessly integrated into these methods. Preemption threshold scheduling (PTS) enables a scalable real-time system design and thus has been suggested as a solution to this problem. However, direct adoption of PTS may lead to long priority inversion since object-oriented real-time systems require synchronization considerations in order to maintain consistent object states. In this paper, we propose the dual ceiling protocol (DCP) in order to solve this problem. While DCP exploits both priority ceilings and preemption threshold ceilings, this is not a straightforward integration of existing real-time synchronization protocols for PTS. We present the rationale for the locking conditions of DCP and show that it leads to the least blocking and response times by comparison with other real-time synchronization protocols. We also present its blocking properties and schedulability analyses. We implemented PTS and DCP in a real-time object-oriented CASE tool and present the associated experimental results, which show that the proposed protocol is a viable solution that is superior to other real-time synchronization protocols for PTS.     

基于门限优先级的业务模型及性能仿真分析

随着网络访问用户的增加，如何合理分配网络资源，减少网络通信阻塞具有十分重要的意义。该文运用了排队理论对门限优先的业务进行了分析，建立了数学模型。利用排队模型，通过计算机仿真对门限优先业务中门限不同对两类信元的平均逗留时间、信元丢失率的影响进行了分析。结果表明如果门限值选取适当，门限优先级策略降低了高优先级信元的丢失率，同时使低优先级信元的丢失率尽量减小，从而提高了对高优先级信元的服务质量。     

(Incremental) Priority Algorithms

We study the question of which optimization problems can be optimally or approximately solved by greedy or greedy-like algorithms. For definiteness, we limit the present discussion to some well-studied scheduling problems although the underlying issues apply in a much more general setting. Of course, the main benefit of greedy algorithms lies in both their conceptual simplicity and their computational efficiency. Based on the experience from online competitive analysis, it seems plausible that we should be able to derive approximation bounds for greedy-like algorithms exploiting only the conceptual simplicity of these algorithms. To this end, we need (and will provide) a precise definition of what we mean by greedy and greedy-like.     

The pairing heap: A new form of self-adjusting heap

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue) called theFibonacci heap. Although theoretically efficient, Fibonacci heaps are complicated to implement and not as fast in practice as other kinds of heaps. In this paper we describe a new form of heap, called thepairing heap, intended to be competitive with the Fibonacci heap in theory and easy to implement and fast in practice. We provide a partial complexity analysis of pairing heaps. Complete analysis remains an open problem.Research partially supported by National Science Foundation Grant MCS 82-04031 and by Bell Communications ResearchResearch partially supported by National Science Foundation Grant DCR 85-14922     

Scheduling for a share of the machine

This paper describes the mechanism used to schedule jobs and control machine use on the IBM 370/165 at Cambridge University, England. The same algorithm is currently being used in part at the University of Bradford, and implementations are in progress at the Universities of Leeds, Salford and Liverpool for the ICL 1900 series machines. The mechanism relies on allocating a share of the machine to each user (or project), and then varying the turnround time for jobs according to whether the project in question is over- or under-using its share of the machine. The approach is believed to be an original one, having a number of advantages over more conventional scheduling and control algorithms.     

门限优先级系统的费用优化问题

在排队系统的设计或运营管理中，需要考虑顾客和服务双方的利益，以便在某种合理指标上使系统达到最优。陔文以此作为理论依据，建立了门限优先级系统的费用模型。运用排队理论建立的仿真模型对门限优先级系统的费用问题进行了量化分析。结果表明：随着服务率的增加，由于信元的逗留时间及丢失率减小，与之对应的排队损失费也随之减小，但同时服务费在增加；系统总费用有它的最小值，这时对应的服务率是最优值。这种分析方法在排队系统的设计中具有重要的参考价值。