Study on multi-core data structure in shared-memory

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.