非阻塞自组织链表的研究

《非阻塞自组织链表的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、非阻塞自组织链表的研究ResearchonNon--blockingSelf-organizedLinked-·lists学科专业：计算机应用技术研究生：吴宗远指导教师：张坤龙副教授天津大学计算机科学与技术学院二零一零年六月_一’^吣‘独创性声明口’7lllllIllfllfllrfllIIIIrFIIIIIlllrrIIIY1873813本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特另J}Dl：l以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得：墨鲞苤堂或其他教

2、育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：昊眷远签字日期：纱f。年易月，7日学位论文版权使用授权书本学位论文作者完全了解苤鲞盘堂有关保留、使用学位论文的规定。特授权苤鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。(保密的学位论文在解密后适用本授权说明)学位论文作者签名：昊。孝还导师签名：球坪嫁签字同期：矽l口年切月。7同签

3、字日期：砷I口年易月九日～t摘要自组织链表是针对搜索问题提出的，它能够在响应未知访问请求序列的过程中不断调整节点位置，使链表结构逐渐进入一个能充分利用访问请求序列特性的状态，从而降低总体访问代价，提高链表性能。随着计算机硬件技术的发展，为了充分利用多处理器的协同计算能力，需要设计一种有效的共享并发自组织链表。非阻塞数据结构使用非互斥方法，可以同时被多个并发线程访问，避免了互斥方法中一个位于临界区中的线程的延迟对其它线程产生的影响。它能够保证在有限步内至少有一个线程能够完成若干操作，具有更强的健壮性和更高的可依赖性。论文提出了两种非阻

4、塞自组织链表：只读型非阻塞自组织链表和读写型非阻塞自组织链表。两种新链表均满足可线性化条件。其中读写型非阻塞自组织链表采用MTF规则，是己知的第一个支持常见字典操作的非阻塞自组织链表。只读型非阻塞自组织链表中引入了“热点”元素的概念。它为每个线程分配一个热点数组，通过热点数组来指导链表的自组织行为。此外，热点数组还可以提高热点元素的查找效率，为充分利用高速缓存带来了契机。读写型非阻塞自组织链表在数据节点之外引入了操作节点。一方面，执行相关操作的线程之间通过操作节点相互通信、获取其它线程的执行结果、以及通知其它线程自身的执行结果，保证

5、了操作的非阻塞性和正确性。另一方面，通过让操作节点起到数据节点的作用，能够及时、准确地对访问元素执行MTF操作，从而实现链表的自组织行为。实验表明，当访问请求序列具有较强局部性时，两种新链表的性能超过了已有的无自组织行为的非阻塞链表和使用粗粒度加锁方式实现的阻塞自组织链表。关键词：自组织链表、并发、非阻塞数据结构ABSTRACTSelf-organizedlinkedlistisproposedforthesearchproblem，ithasaruleoralgorithmforchangingthepositionofnodes

6、whenrespondingtoanunknowninputrequestsequence．Theruleoralgorithmcangetthestructureofthelinkedlistintoastatethatwilltakeadvantageofthepropertiesoftheinputrequesetsequence，andreducetheoverallcostofoperations，improvetheperformanceofthelinkedlist．Asthedevelopmentofcomputer

7、hardwaretechnology,inordertoutilizethecomputingpowerofmulti-processorsefficiently,weneedtodesignaconcurrentandsharedself-organizedlinkedlist．Non-blockingdatastructuredonotusemutualexclusion．Itcanbeaccessedbymultiplethreadssimultaneously,andcanavoidperformanceproblemsdu

8、etounpredictabledelayswhilethreadsarewithincirticalsections．Non-blockingdatastructureguaranteesthatinfinitelyoftensom