面向高速实时数据处理的无锁内存分配算法

Lock-free Memory Allocation Algorithm for High-speed Real-time Data Processing

为了提高高并发生产环境下内存分配的效率,针对高速实时数据处理程序的高并发、高频内存分配等特点,采用一种无锁内存分配算法(Lock Free Memory Allocation, LFMA)来提高并发度及内存分配效率。针对伙伴(Buddy)算法的不足,使用位图替代链表,并结合原子操作来达到线程间无锁并发访问,同时降低了缓存未命中的概率。引入多级位图来提高空闲内存块的搜索效率,通过渐进式重合并算法避免Buddy算法频繁拆合带来的效率问题,并降低了外部碎片。实验结果表明,相较于Buddy算法,新算法的分配效率在单线程下提升约31%,在多线程下提升约27%。

According to the high concurrency and high frequency memory allocation of high-speed real-time data processing programs, a lock-free memory allocation algorithm is proposed to improve the efficiency of concurrency and memory allocation. Aiming at the shortcomings of Buddy algorithm, it uses bitmap to replace linked list to achieve lock-free concurrent access between threads, and the external fragmentation is reduced. The efficiency problem caused by the frequent splitting and merging of memory blocks by the Buddy algorithm is improved by the progressive re-merge algorithm. Experimental results show that compared with the Buddy algorithm, the allocation efficiency of the new algorithm is improved by about 31% in a single thread and about 27% in a multi-threaded manner.