| 摘要: |
| 随着计算机硬件技术的发展,如今我们已经迈入了多核CPU时代.然而,作为软件核心的数据结构仍然是按照单核CPU和顺序型准则来设计的.在基于共享内存的多核时代,大量并发运行的线程会交替地修改数据,产生不可预期的结果,因而我们面临着严峻挑战.针对基于共享内存多核时代数据结构的相关研究进行综述.首先,对比了并发与并行的区别,归纳了基于演进条件(progress condition)的多核数据结构分类,对近年来学术界对各种类型并发数据结构的研究进行综述.在此基础上,剖析了并发数据结构设计和实现的关键技术,并从并发数据结构的开发流程、正确性验证等方面进行了归纳阐述.最后,基于这些讨论,对多核架构下并发数据结构未来的研究趋势和应用前景进行了展望. |
| 关键词: 多核处理器 并发数据结构 演进条件 |
| DOI：10.13328/j.cnki.jos.005021 |
| 分类号: |
| 基金项目:国家自然科学基金(61133004,61363021,61540061) |
|
| Study on Multi-Core Data Structure in Shared-Memory |
|
ZHOU Wei1, ZHOU Ke-Ren1, LUAN Zhong-Zhi2, YAO Shao-Wen1, QIAN De-Pei2
|
|
1.National Pilot School of Software, Yunnan University, Kunming 650091, China;2.School of Computer Science and Engineering, BeiHang University, Beijing 100191, China
|
| Abstract: |
| The development of computer hardware technology has led to an era of multi-core CPU. However, data structures, as the core of the software, are traditionally designed in line with single-core CPU and ordered sequence principle. Operating 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, the 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 the findings, this paper summarizes the key technologies of concurrent data structure, and explains the design and development process as well as correctness verification of concurrent data structures. Finally, it discusses research prospects. |
| Key words: multi-core CPU concurrent data structures progress condition |
