基于无锁数据结构的FIFO队列算法

现代商用多核处理器缺少硬件支持的处理核间通信机制,多个处理核间必须通过加锁保护的共享内存传递数据。为此,设计一种基于软件的无锁队列作为核间通信机制,通过无锁数据结构提高软件队列的性能。当数据到达速率较低时,队列自适应地减小队列长度,从而占用较小的内存空间,进而更好地利用处理器高速缓存;当数据到达速率较高时,队列自适应地增加队列长度,以避免数据丢失。实验结果表明,在数据到达速率变化较大的实际应用场景中,该队列较FastForward、MCRingBuffer和B-Queue队列具有更高的数据处理性能。

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

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

并行计算机系统中的计数算法研究

计数算法是计算机程序设计中的基础算法。然而,传统计数算法在新兴的多核并行计算机系统中存在计数效率低下以及计数不准确的问题。文中首先对这些问题进行深入量化分析,之后提出了一种适用于并行计算机系统的确定性高速计数算法。该算法采用对计数器数据先进行快照再进行统计计数的方法,有效避免了计数算法中读者线程与写者线程之间的相互干扰,保证了计数数据的准确性;同时,通过采用无锁链表队列存储计数数据快照,实现了并发读取情况下的无阻塞计数统计,保证了计数算法的效率。实验论证和性能分析结果表明:在新一代的多核并行计算机中,本计数算法计数效率高且计数准确,综合性能优于现有算法。

面向多线程程序的内存安全运行时验证

Linux操作系统、嵌入式系统、航电系统、通信系统等一般都是用C/C++语言进行编写。因为C语言具有偏底层硬件、移植性强、执行效率高等优秀特性。但是随着多核并行机的出现,许多语言也开始支持多线程编程。由于C语言本身存在着对内存访问时,不对内存边界进行检查的问题,从而造成软件系统相关的可靠性和安全性问题。对多线程C语言程序来说,由于多线程程序的不确定性,使得运行时验证多线程C程序的内存安全问题变得更加困难。通过使用基于改进的指针运行时验证技术、多核多线程技术、并行计算、无锁数据结构技术、源代码插桩技术方法,并结合开源工具Clang编译器实现原型工具Movec对多线程C程序的支持。该工具实现了对多线程C程序内存安全问题的运行时验证。然后通过Mibench和SARD测试用例进行实验,验证了该工具对多线程C程序进行运行时验证的有效性。