Wait-Free Multi-Word Compare-and-Swap Using Greedy Helping and Grabbing

We present a new algorithm for implementing a multi-word compare-and-swap functionality supporting the Read and CASN operations. The algorithm is wait-free under reasonable assumptions on execution history and benefits from new techniques to resolve conflicts between operations by using greedy helping and grabbing. Although the deterministic scheme for enabling grabbing somewhat sacrifices fairness, the effects are insignificant in practice. Moreover, unlike most of the previous results, the CASN operation does not require the list of addresses to be sorted before the operation is invoked, and the Read operation can read the current value without applying helping when the word to be read is within an ongoing transaction. Experiments using micro-benchmarks varying important parameters in three dimensions have been performed on two multiprocessor platforms. The results show similar performance as the lock-free algorithm by Harris et al. for most scenarios, and significantly better performance on scenarios with very high contention. This is altogether extraordinary good performance considering that the new algorithm is wait-free.     

A Wait-Free Sorting Algorithm

Sorting is one of a set of fundamental problems in computer science. In this paper we present the first wait-free algorithm for sorting an input array of size N using P ≤ N processors to achieve optimal running time. We show two variants of the algorithm, one deterministic and one randomized, and prove that, with high probability, the latter suffers no more than contention when run synchronously. Known sorting algorithms, when made wait-free through previously established transformation techniques, have complexity O(log ³ N) . The algorithm we present here, when run in the CRCW PRAM model, executes with high probability in O(log N) time when P=N , and O((Nlog N)/P) otherwise, which is optimal amongst comparison-based sorting algorithms. The wait-free property guarantees that the sort will complete despite any delays or failures incurred by the processors. This is a very desirable property from an operating systems point of view, since it allows oblivious thread scheduling as well as thread creation and deletion, without fear of losing the algorithm's correctness. Received May 15, 1998, and in revised form November 17, 1999. Online publication November 19, 2001.     

Highly-Efficient Wait-Free Synchronization

We study a simple technique, originally presented by Herlihy (ACM Trans. Program. Lang. Syst. 15(5):745–770, 1993), for executing concurrently, in a wait-free manner, blocks of code that have been programmed for sequential execution and require significant synchronization in order to be performed in parallel. We first present an implementation of this technique, called Sim, which employs a collect object. We describe a simple implementation of a collect object from a single shared object that supports atomic Add (or XOR) in addition to read; this implementation has step complexity O(1). By plugging in to Sim this implementation, Sim exhibits constant step complexity as well. This allows us to derive lower bounds on the step complexity of implementations of several shared objects, like Add, XOR, collect, and snapshot objects, from LL/SC objects. We then present a practical version of Sim, called PSim, which is implemented in a real shared-memory machine. From a theoretical perspective, PSim has worse step complexity than Sim, its theoretical analog; in practice though, we experimentally show that PSim is highly-efficient: it outperforms several state-of-the-art lock-based and lock-free synchronization techniques, and this given that it is wait-free, i.e. that it satisfies a stronger progress condition than all the algorithms that it outperforms. We have used PSim to get highly-efficient wait-free implementations of stacks and queues.     

Wait-Free Clock Synchronization

Multiprocessor computer systems are becoming increasingly important as vehicles for solving computationally expensive problems. Synchronization among the processors is achieved with a variety of clock configurations. A new notion of fault-tolerance for clock synchronization algorithms is defined, tailored to the requirements and failure patterns of shared memory multiprocessors. Algorithms in this class can tolerate any number of napping processors, where a napping processor can fail by repeatedly ceasing operation for an arbitrary time interval and then resume operation without necessarily recognizing that a fault has occurred. These algorithms guarantee that, for some fixed k, once a processor P has been working correctly for at least k time, then as long as P continues to work correctly, (1) P does not adjust its clock, and (2) P's clock agrees with the clock of every other processor that has also been working correctly for at least k time. Because a working processor must synchronize in a fixed amount of time regardless of the actions of the other processors, these algorithms are called wait-free. Another useful type of fault-tolerance is called self-stabilization: starting with an arbitrary state of the system, a self-stabilizing algorithm eventually reaches a point after which it correctly performs its task. Two wait-free clock synchronization algorithms are presented for a model with global clock pulses. The first one is self-stabilizing; the second one is not but it converges more quickly than the first one. The self-stabilizing algorithm requires each processor's communication register contents to be a part of the processor's state. This last requirement is proven necessary. A wait-free clock synchronization algorithm is also presented for a model with local clock pulses. This algorithm is not self-stabilizing. Received December 20, 1993; revised January 1995.     

非法计算检测的通用模型

非法计算是导致系统崩溃的一个常见故障.文中总结了Java语言中可能产生非法计算的运算符和数学库函数;建立了一个通用模型,用以检测一般函数(包括系统函数和自定义函数)在使用时是否合法;基于该通用模型提出了非法计算检测算法,并在此算法中引入区间运算.实验结果表明,文中模型及算法可以在检测出更多的非法计算故障的同时降低误报率.     

模n的大整数幂乘的一种快速算法

在RSA公钥密码体制中，要提高模n的大整数幂乘的运算效率，主要是解决两个方面的问题：（1）大整数的算术运算，特别是大整数的乘除法；（2）降低幂模运算的实际次数。文章从这两个方面进行研究，实现了大整数幂乘的一种快速计算。并给出了关键部分的算法，分析了算法的效率。     

一种带融合操作的实数多种群遗传算法

提出了一种带融合操作的实数多种群遗传算法。该算法由多个种群组成,根据各个种群中最优个体的适应值及其成长性优化计算资源分配;引入融合操作,利用各种群中的最优个体产生新个体,取代各种群中的最差个体,改善种群的遗传进程。实例计算表明该算法是有效的。     

作战文书关键信息抽取方法*

作战文书关键信息抽取是实现自动标图系统的关键。现有研究多以文书处理流程设计为主,未深入分析军标用法,信息抽取不完整。为完整提取信息,提出了基于分词处理与语义角色标注（SRL）相结合的文书关键信息抽取方法,实验证明方法有效、可行。基于文中方法所设计的信息抽取系统,已在某集团军内推广、应用。     

作战行动建模资源库系统研究

该文分析了作战行动建模资源库的特点,确定了基于WEB的分布式作战行动建模资源库系统的体系结构和功能,选取了XML描述资源元数据信息,并提出了基于本体的智能搜索引擎。     

模n的大整数幂乘的一种快速算法

在RSA公钥密码体制中,要提高模n的大整数幂乘的运算效率,主要是解决两个方面的问题:⑴大整数的算术运算,特别是大整数的乘除法;⑵降低幂模运算的实际次数。文章从这两个方面进行研究,实现了大整数幂乘的一种快速计算,并给出了关键部分的算法,分析了算法的效率。     

一种面向可离线业务的移动办公系统设计方案

无线计算设备正在迅速增生,要求软件应用能够处理移动计算这样一种方式.不论用户与网络保持连接还是离线,它们都期望从运行在它们的移动设备上的应用那里得到相同的功能.它们期望本地应用能够很好的处理间歇的网络连接和带宽变化问题,所有这些期望对应用开发提出了一套新挑战.该移动应用设计把便携式计算设备和无线网络合并为一个计算环境,在这个环境中,一个用户可以忽视网络连接的状态而有效的工作.     

移动作业系统的客户端解决方案

移动作业往往发生在用户无法在一个固定位置完成工作，而必须经常地改变工作的方位以适应工作的需要。国内很多公司提出了自己的移动作业系统的解决方案，但基本上基于服务端的模式，本文提出一种客户端的解决方案，试图达到既能有效减少系统维护和升级成本，又能使用户界面富于变化的目标。     

基于饱和度运算的快速图像去雾算法

在雾、霾等恶劣天气条件下,大气介质中悬浮粒子的散射和吸收作用会严重退化户外拍摄的图像,造成图像识别率降低.从单色大气散射模型出发,提出面向视觉感知的HSV颜色模型定义饱和度的新算法,估计大气光亮度A;利用饱和度运算估计透射率函数进而恢复场景反照率;最后经直方图拉伸得到最终的复原图像.实验结果表明,改进算法能有效地复原场景的对比度和颜色,提高图像的视觉度和计算效率.     

一种基于GA-PSO算法的列车运行调整模型

本文针对列车运行时刻调整问题进行建模分析。首先,本文对该问题建立数学模型,并运用PSO算法对模型进行计算求解。在初步的求解过程中,针对PSO算法的收敛速度较慢等不利因素对其进行优化,提出了GA-PSO算法。最后,通过模拟实验得出GA-PSO在调度过程中能达到较高的准点率。     

定点DSPs的定标及其运算方法

分析了定点DSPs的定标问题，讨论了定点运算中的Qs值选择和解决数值超范围的方法，提出了定点DSPs加法的通用处理方法，并就定点运算程序设计中的一些具体问题进行了讨论。     

操作系统日志的行为挖掘与模式识别

文章提出了对操作系统日志进行用户行为挖掘和系统状态模式识别的设计策略,该设计能够准确细腻的分析Audit二进制日志,对用户的行为包括用户的登录登出,用户身份切换,命令操作等进行高精度挖掘,以及对系统的服务启动与关闭,关键文件状态变化等系统状态进行识别。从而为操作系统的安全、补救、恢复提供有效的支持保障。该系统基于面向对象设计,有良好的扩展性和易部署性,具有广阔的市场应用前景。     

WDM网络中考虑Qos约束的动态业务路由算法

路由问题是WDM网络中的一个核心问题。该文研究了WDM网络中受瓶颈带宽Qos和时延Qos约束的动态业务路由算法。算法以链路的延时值作为链路的权值,为网络中所有节点对计算所有代价有限的路由,作为备用路由。当一个连接请求到达时,考察其瓶颈带宽Qos指标与时延Qos指标,在备用路由集中选择满足Qos指标的路由;对所选路由综合考察其跳数、成本以及链路瓶颈带宽,计算目标函数,选择目标函数值最优的路由建立连接。     

基于检查点和Rejuvenation的软件运行模型分析

近来的研究表明,长时间运行的通信软件往往存在老化现象。为防止软件老化引起的突发性系统停机,提高系统的可靠性,人们提出了一种预防性的软件容错策略,称为rejuvenation。由于它的过程复杂,总的停机成本仍然是可观的。检查点是一种轻量级的软件容错策略,其成本远小于rejuvenation的成本。该文通过合理结合rejuvenation和检查点技术,实现了降低总的系统停机成本的目的。文中给出了系统的Petri网模型,并结合实例进行了分析。