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

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

Resource stealing lock-free memory pool for dynamic-sizedlock-free data structures

Dynamic memory management in a multi-threaded environment involes expensive synchronization cost, making it a vital issue for the performance of dynamic lock-free data structures. This paper proposed a scheme for the lock-free implementation of a memory pool suited to dynamic-sized lock-free data structures to reduce the associated dynamic memory consumption and dynamic memory management cost. This scheme reduced dynamic memory consumption associated with the shared lock-free data structures by balancing threads dynamic memory consumption, it was based on thread local lock-free circular queue that supported node stealing method. This scheme possesses three outstanding advantages: athe memory is wait-free, bit can balance the threads' consumption of dynamic memory, cits integration with existing dynamic-sized lock-free data strucutures is extremely easy. Experimental results show that this scheme is highly scalable and can effectively reduce the average execution time of dynamic-sized lock-free data structures' operations under heavy load. The amount of dynamic memory consumption is mostly affected by the balancing strategy and the scalability of the memory pool under high load is also affected by the underlying data structures.