基于共享内存的多核时代数据结构研究

随着计算机硬件技术的发展,如今我们已经迈入了多核CPU时代.然而,作为软件核心的数据结构仍然是按照单核CPU和顺序型准则来设计的.在基于共享内存的多核时代,大量并发运行的线程会交替地修改数据,产生不可预期的结果,因而我们面临着严峻挑战.针对基于共享内存多核时代数据结构的相关研究进行综述.首先,对比了并发与并行的区别,归纳了基于演进条件(progress condition)的多核数据结构分类,对近年来学术界对各种类型并发数据结构的研究进行综述.在此基础上,剖析了并发数据结构设计和实现的关键技术,并从并发数据结构的开发流程、正确性验证等方面进行了归纳阐述.最后,基于这些讨论,对多核架构下并发数据结构未来的研究趋势和应用前景进行了展望.

Study on Multi-Core Data Structure in Shared-Memory

With the development of computer hardware technology, now we have entered into an era of multi-core CPU. However, the data structures, as the core of the software, are traditionally designed according to single-core CPU and ordered sequence principle. Based on the shared-memory multicore, a large number of concurrent running threads alternately modify the data structure, which brings big challenges. This paper surveys researches on multi-core data structure in shared-memory. First, this paper compares the differences between the concurrent and parallel data structures, and investigates the multicore structure classification characteristics based on progress condition. Then it reviews academic research on various types of concurrent data structures in recent years. Based on these, this paper summarizes the key technologies of concurrent data structure, and explains the designing, development process and correctness verification of the concurrent data structures. Finally, research prospects are given.