多线程应用中的定时器管理算法

针对高性能电信系统中软定时器效率低下的问题,提出一系列优化方案,采用二次散列的时间轮,并结合免锁算法的低粒度互斥锁,从理论上把定时器查询和定时器插入等常用操作的复杂度从O(n)降至最优情况的O(1)。通过真实高负荷进行测试,采用SunStudio11性能分析工具对优化前后的性能进行定量分析。实验结果表明,该优化方案能够有效提高系统效率。     

一种采用消隐技术的锁无关栈算法

随着对实时系统的实时性和系统服务要求的不断提高,基于多核/多处理器硬件平台的实时系统成为发展趋势.相应的高性能实时操作系统需具有更高的硬实时性和可靠性,并避免优先级逆转、死锁.相比阻塞同步,非阻塞同步在提高实时系统性能、确定性和容错性等方面具有优势,有利于实现上述要求.设计锁无关数据结构是实现非阻塞同步的方法之一.文章介绍了锁无关算法的基本结构,提出一种采用消隐技术的锁无关栈算法及证明锁无关算法正确性的理论方法,并证明了该锁无关栈算法的正确性.实验结果表明,该算法提高了访问共享数据的执行速度,并避免了死锁、优先级逆转、低容错性等缺点.     

供动态无锁数据结构使用的资源窃取型无锁内存池

动态内存管理的问题对无锁动态数据结构的性能尤为关键,因为多线程环境下的动态内存管理涉及开销较高的同步操作。提出一种构建用于动态无锁数据结构的内存池的方法来减少动态内存使用和与之相伴的动态内存管理开销。该方法通过平衡线程的动态内存消耗来减小内存开销,利用本方法构建的内存池基于线程私有的支持节点窃取的无锁循环队列。本方法具有以下优点:a)用本方法构建的内存池是无锁的;b)能够平衡线程的堆内存消耗;c)可以方便地与动态无锁数据结构集成。实验结果显示,用该方法构造的资源窃取型内存池扩展性较强,且能够在高负载下有效降低无锁数据结构的堆内存消耗和操作执行时间;平衡算法在很大程度上决定内存消耗量,内存池在高负载下的扩展性也受到它所用的数据结构自身多线程访问性能的影响。     

Cache-aware design of general-purpose Single-Producer–Single-Consumer queues

Data processing pipelines normally use lockless Single-Producer–Single-Consumer (SPSC) queues to efficiently decouple their processing threads and achieve high throughput, minimizing the cost of synchronization. SPSC queues have been widely studied, mostly for applications such as streaming data or network monitoring, where the main goal is maximizing throughput. There are now many applications, such as virtual-machine–virtual-machine communication, software-defined networking, and message-based kernels, where low latency is also important, and the tradeoffs between high-throughput and low-latency algorithms have not been studied equally well. Furthermore, at high or variable transaction rates, the effect of memory hierarchies and cache coherence subsystems may be dominant and yield surprising results. In this paper, we make two contributions. First, we provide a comprehensive study of the two main families of SPSC queues, namely, “Lamport” and “FastForward” queues, with a detailed analytical and experimental characterization of their behavior in terms of operating regimes, throughput, latency, and cache misses. Second, we propose two new queue variants, namely, improved FastForward and batched improved FastForward, which have better worst-case behavior than other variants in terms of cache misses, which is an important feature for a number of applications. Together, these two contributions provide practical guidelines to choose the best solution depending on the application requirements.     

改进型锁无关双端队列的设计与实现

高性能实时系统对系统性能、确定性和容错性有着更高的要求。非阻塞同步在任务同步方面满足要求,实现方法之一就是设计锁无关数据结构。介绍了设计锁无关数据结构算法的关键技术,通过对已有算法不足的分析提出了一种改进型的锁无关双端队列算法,介绍了对该算法的实验分析和实际应用。实验结果表明,该算法提高了访问双端队列的执行速度,并避免了多任务间同步引发的死锁、优先级逆转、低容错性等缺点。     

基于多核处理器的无锁零拷贝数据包转发框架

为突破高速软件路由器转发路径中存储访问方面的性能瓶颈,分析PacketShader和Netmap2个软件路由器的转发结构和存在的问题,设计一个基于多核处理器的零拷贝包转发框架MapRouter。采用零拷贝技术去除包转发路径中的包拷贝,并借助并发无锁队列设计一个适合多端口间数据包零拷贝转发的包缓冲区管理方案。将高度优化的包I／O驱动、包缓冲区回收机制、无锁队列实现等一系列优化措施相结合,以提高转发速度。实验结果表明,对于不包括IP路由表查找的最小转发,MapRouter在模拟的两端VI路由器上可以达到i0Gb／s的转发速度,与PacketShader和Netmap相比,其转发速度更高、CPU利用率更低。     

Compiler-driven approach for automating nonblocking synchronization in concurrent data abstractions

This paper presents an extended version of our previous work on using compiler technology to automatically convert sequential C++ data abstractions, for example, queues, stacks, maps, and trees, to concurrent lock-free implementations. A key difference between our work and existing research in software transactional memory (STM) is that our compiler-based approach automatically selects the best state-of-the-practice nonblocking synchronization method for the underlying sequential implementation of the data structure. The extended material includes a broader collection of the state-of-the-practice lock-free synchronization techniques, additional formal correctness proofs of the overall integration of the different synchronizations in our system, and a more comprehensive experimental study of the integrated techniques. We evaluate our compiler-generated nonblocking data structures both by using a collection of micro-benchmarks, including the Synchrobench suite, and by using a multi-threaded application Dedup from PARSEC. Our automatically synchronized code attains performance competitive to that of concurrent data structures manually-written by experts and much better performance than heavier-weight support by STM.     

基于硬件CAS原语的高效多字无锁同步算法

共享内存体系结构下,为解决锁同步导致的并发性能瓶颈,本文提出了一种基于硬件CAS（比较交换）原语的无锁同步算法.该算法利用底层处理器提供的比较交换指令,实现了在多核多线程环境下对共享变量的非阻塞同步操作,通过采用全局标记值的方式,避免了传统设计中由于使用内存字标记导致的性能开销,同时确保数据在并发访问中的一致性.实验结果表明,本文算法可以高效地支持任意多字的CAS同步,提高了对共享数据的并发访问性能,具有较好的可扩展性.     

无锁并发二叉搜索树的实现

针对异步共享内存模型下的并发搜索二叉树（BST）数据结构,提出了一种新的无锁实现方法。通过一种有效的节点重用策略,使得删除操作是无等待的,插入操作是无锁的。实验数据表明,该数据结构是高度可扩展的而且在高负载下能提供很高的吞吐量。