基于副本非阻塞自组织链表 (1)

《基于副本非阻塞自组织链表 (1)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得天津大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：签字日期：年月日学位论文版权使用授权书本学位论文作者完全了解天津大学有关保留、使用学位论文的规定。特授权天津大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学

2、校向国家有关部门或机构送交论文的复印件和磁盘。（保密的学位论文在解密后适用本授权说明）学位论文作者签名：导师签名：签字日期：年月日签字日期：年月日摘要自组织链表是一种具有启发意义和实用价值的数据结构，它能够响应访问模式的变化，调节链表结构以改善链表的性能，并已经被成功应用到数据压缩算法、凸包算法和计算最大值点。随着计算机多核技术的发展，为了充分利用多核的协同计算能力，需要设计一种高效的并发自组织链表结构。非阻塞数据结构使用非互斥的方法实现并发，使互斥资源能够被多于一个线程同时访问，避免了互斥方法中的死锁、优先级反转和护航问题。它能保证至少有一个线程能

3、够在有限时间内完成操作，具有更好的健壮性和可靠性，并可以获得比互斥方法更好的性能。因此，提出了实现非阻塞自组织链表的设想。本文提出了基于副本的非阻塞自组织链表。为链表中的结点维护一个副本结点，通过移动副本结点实现对链表的自组织。链表分为无序的副本结点和有序的数据结点两部分，通过副本结点能快速访问数据结点，数据结点部分采用的是Michael的算法，副本结点部分应用的是MTF规则。链表结构简单，能保证可线性化的正确性和非阻塞的演进性。实验表明，在高读操作比例、长链表的情况下，本文的非阻塞自组织链表能获得很好的性能和可扩展性。在实验的测试数据序列情况下，9

4、0%读操作比例、键值范围4096时，新链表的性能超过了所有已知的阻塞的和非阻塞的链表。关键词：并发，非阻塞，自组织，链表ABSTRACTSelf-organizedlinkedlistisdatastructure,whichhasedificationsignificanceandpracticalvalue.Itcanrespondtochangesinaccessmode,andadjustitsstructuretoimproveperformance.Andithasbeensuccessfullyappliedtodatacompress

5、ionalgorithm,theconvexhullalgorithmandcalculatethemaximumpoint.Asthedevelopmentofcomputermulti-coretechnology,inordertoutilizethecomputingpowerofthemulti-coresefficiently,weneedtodesignanefficientconcurrencyself-organizedlinkedlist.Non-blockingdatastructuredonotusemutualexclusi

6、ontoachieveconcurrent,makingtheexclusiveresourcecanbeaccessedbymultiplethreadssimultaneously.Anditcanvoidtheproblemscausebymutualexclusionsuchasdeadlock,priorityinversionandconvoy.Non-blockingdatastructureguaranteesthatsomethreadswillcompletewithininfinitenumberofstepsregardles

7、sofotherthreads’actions,andoffersbetterrobustness,reliable,andperformance.Soweproposetoachievenon-blockingself-organizedlinkedlist.Thispaperpresentsacopy-basednon-blockingself-organizedlinked-list.Wemaintainacopynodeforthenodesinthelist,andbymovingthecopynodetoachieveself-organ

8、izationofthelinkedlist.Thelistisdividedintotwoparts:di