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

来源：软件学报杂志2016年第4期北京时间：

作者：周维,周可人,栾钟治,姚绍文,钱德沛

单位：周维，云南大学 软件学院, 云南 昆明 65009111,周可人，云南大学 软件学院, 云南 昆明 65009102,栾钟治，北京航空航天大学 计算机学院, 北京 10019103,姚绍文，云南大学 软件学院, 云南 昆明 65009104,钱德沛，北京航空航天大学 计算机学院, 北京 10019105

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

关键词：多核处理器;并发数据结构;演进条件

基金资助：国家自然科学基金(61133004,61363021,61540061)