首页 >  硕士论文 > 计算机硕士毕业论文 >   正文

计算机硕士毕业论文:并发缺陷的检测与规避研究

添加时间:2017-12-07 20:17:19   浏览:次   作者: www.dxlwwang.com
专业论文资料, 搜索论文发表论文代写论文网为你解忧愁!详情请咨询我们客服。
获取免费的论文资料? 欢迎您,提交你的论文要求,获取免费的帮助

第1章 绪论

 
1.1课题背景及研究目的与意义
过去几十年间,软件一直从处理器(CPU)性能的不断提升中获益。计算机工业界中存在一个有趣的现象:“安迪送,比尔取”。无论CPU性能提升多少,软件都有办法迅速吞噬。理想情况下,CPU性能十倍于前,软件就能在同样时间段内处理十倍于前的工作量(或者运行速度十倍于前)。实际情况中,软件受益于CPU和内存、硬盘等外围设备的持续不断升级,其不作任何改变就能免费获得性能提升。但是这种免费午餐已经结束。由于受制于一些物理学问题,如功耗、发热及电子泄露,CPU时钟频率的提升越来越难,已经达到极限。图1-1反映了Intel处理器的时钟频率与晶体管规模关系的演化历史。大约在2003年左右,一直快速攀升的时钟频率突然陷入了停滞。即使大幅增加晶体管数量,也无济于事:时钟频率仍旧不能提升,甚至会有所下降。最终Intel的单核CPU时钟频率止步于3.8GHz[3]。因此软件在保持单执行流的体系结构下,将再也不能从CPU性能提升中获益。Intel于2006年6月发布革命性的“酷睿”双核架构处理器[4]。4年后,Nvidia在2010年1月的国际消费类电子产品展览会(CES2010)上发布全球首款移动双核处理器Tegra2[5]。紧接着,LG Electronics基于Tegra2开发并于2010年12月率先发布全球首款双核智能手机Optimus 2X[6]。经过6-10年普及与发展,现在个人电脑和手机普遍配置一个或者多个2核、4核、6核甚至8核处理器。在当今多核并行时代,为提高运行速度,软件必须转向并发模式。然而相对于传统顺序程序设计,并发程序设计更加困难且容易出错。
............
 
1.2国内外研究现状及分析
 
1.2.1并发缺陷暴露
通过观察缺陷能否暴露,这些研究验证预测的缺陷是否是真正的缺陷。并发缺陷暴露技术考虑并发缺陷的共同特点,能暴露各类并发缺陷。传统内控测试中并发缺陷的暴露概率很低,这主要是由于:并发程序的执行交错空间庞大;并发缺陷只隐藏于某些罕见的的、特殊的执行交错;测试技术缺乏对底层调度器的控制,并发程序常常在多次不同执行中按照某些固定执行交错执行。针对这些问题,学者们提出各种各样的尽快暴露并发缺陷的方案,本文将其总结为3类。技术[13, 15, 32]在并发程序进行共享内存访问和同步控制时,插入随机延时。对于死锁,该技术在线程成功获取锁后插入延时,从而使得本线程挂起而其他线程得到执行机会,增大了其他线程获取锁的概率。对于原子性违背,该技术在两个本地操作之间插入延时,从而增大远程操作交错在2个本地操作之间的概率。对于数据竞争和顺序违背,在预知正确执行次序的前提下,该技术将试图执行错误的执行次序,从而使两者的暴露概率接近于1(限时等待),否则,两者暴露概率接近于0.5。
....
 
第2章 基于锁分配图的混合死锁动态检测方法
 
2.1引言
本章研究由互斥锁和读写锁造成的混合死锁的动态检测方法,解决现有死锁检测方法检测能力弱、只能检测由互斥锁造成的死锁的问题。我们通过分析互斥锁和读写锁的不同加锁语义,发现了新的死锁类型,在此基础上提出混合死锁的概念以概括由互斥锁和读写锁造成的所有5类死锁,接着给出混合锁分配图的定义以表征多线程程序相对于互斥锁和读写锁的同步状态,最后利用混合锁分配图上的环给出5类死锁的严格定义也即其判定方法。互斥锁与读写锁加锁语义的区别是:互斥锁在任何时刻只能被至多一个线程占据,因此任何线程对互斥锁的占据和请求都是互斥占据和互斥请求;读写锁在任何时刻可被多个线程同时共享占据,但只能被至多一个线程互斥占据,因此对读写锁的占据和请求各自分为2类,即共享占据与互斥占据和共享请求与互斥请求。根据它们的语义,不仅互斥锁可能造成互斥锁死锁和互斥锁自锁,读写锁也可能造成读写锁死锁和读写锁自锁,甚至互斥锁和读写锁还能造成杂交死锁,如图2-1所示。然而如1.2.2.1节所述,现有方法[41, 44, 46–56]只能检测互斥锁死锁。本章统称这5类死锁为混合死锁(Mixed Deadlocks),并将对锁(不论互斥锁还是读写锁)的互斥占据和互斥请求称为写占据和写请求,将对锁的共享占据和共享请求称为读占据和读请求。在图2-1中,我们分别用不同的线型和标签来表示这4种操作。
...........
 
2.2混合锁分配图与5类死锁定义
本章定义混合锁分配图(Multiple-Type Lock Allocation Graph, MLAG)来表征多线程程序相对于互斥锁和读写锁的同步状态,并在此基础上给出5类死锁的严格定义也即其判定方法。Monitor在劫持互斥锁的加锁解锁操作时,需要知道正被加锁或者解锁的互斥锁的类型,以根据不同的类型做出不同的反应。然而在pthread库中,互斥锁的类型一旦被设置后就无法仅仅从该互斥锁获知其实何种类型。为绕开这个限制,我们参考了互斥锁的内部定义,并依据定义取互斥锁的第4个域的值为互斥锁的类型。这种方法在Linux系统上是可行的,然而可能不具有可移植性。我们建议pthread在其下一版中,应增加一个获取已初始化的互斥锁的类型属性的函数。互斥锁lock和unlock操作的劫持算法分别如算法2-1和算法2-2所示。在这2个算法中,“gettype”负责如前所述地检索互斥锁类型的任务。在对互斥锁加锁操作的劫持算法2-1中,如果线程t当前没有占据互斥锁v,则Monitor将生成一个写请求事件并将其插入到线程t的事件队列t.eq(第10行)。劫持算法接着对v调用真正的加锁操作并检查它是否成功。如果成功,则t已成功占据v,此时检测算法将v加入到线程t的已占据锁集合t.held locks中,然后生成一个写占据事件并将其插入到t.eq。在此过程中,如果v是递归互斥锁,则将其锁计数增加1(第11-16行)。
........
 
第3章 动静结合的数据竞争检测方法.......... 50
3.1引言....... 50
3.1.1现有研究存在的问题....... 50
3.1.2本文的解决思路.... 52
3.2静态数据竞争检测...... 52
3.2.1静态竞争检测工具RELAY......... 52
3.2.2静态竞争访问对生成....... 53
3.3静态自旋读循环定位............. 55
3.4动态数据竞争验证与检测...... 62
3.5自定义同步原语动态确认与误检竞争剔除........... 77
3.6实验与分析...... 82
3.7本章小结.......... 94
第4章 基于未来锁集的动静结合死锁规避方法....... 96
4.1引言....... 96
4.1.1现有研究存在的问题....... 96
4.1.2本文的解决思路.... 96
4.2规避对象、锁效应与未来锁集......... 97
4.3规避逻辑.......... 101
4.4死锁规避方法的具体实现...... 104
4.5实验与分析...... 112
4.6本章小结.......... 120
第5章 基于软件事务内存的并发缺陷规避方法.......122
5.1引言....... 122
5.2可回滚内存...... 130
5.3可回滚执行...... 133
5.4可回滚I/O ........ 135
 
第5章 基于软件事务内存的并发缺陷规避方法
 
5.1引言
本章研究一种基于软件事务内存(Software Transactional Memory, STM)的并发缺陷规避方法,解决现有通用并发缺陷规避技术规避能力弱和人工参与度高的问题。重点研究4个问题:自动事务化目标程序、有效规避多种类型并发缺陷、支持事务I/O 和合理处理条件变量。通过替代线程以进程、利用进程间虚拟内存保护机制并定制内存分配回收逻辑,实现内存事务化。通过劫持每个线程的线程间操作并将它们之间的代码划分为事务,实现对目标程序的自动事务划分。通过在开始/结束事务时保存/恢复当前线程的栈帧和 CPU 寄存器,实现执行流可回滚化。通过建立和维护虚拟文件系统,并将I/O 操作重定向到它们上,实现I/O 事务化。通过置空加锁解锁操作、定制条件变量操作和事务性地提交内存与I/O 变更,实现对死锁、数据竞争、原子性违背和顺序违背的有效规避。软件事务内存STM是事务内存(Transactional Memory, TM)的一种软件实现。TM是一种并发控制机制,程序员可以使用它将代码段划分为事务并保证事务的原子性和隔离性执行:一个事务要么顺利地执行到提交点然后成功提交,要么与其他事务存在冲突而撤销在执行期间所作的所有更改然后回滚并重新执行。STM用事务代替锁,通过简化数据保护、允许事务间的顺序推理、消除死锁风险和支持事务可组合性来降低并发程序设计的难度,通过乐观执行机制来提升(某些)并发程序的并发度与执行效率。
\
.........
 
结 论
 
并发程序具有并发性和不确定性的特点,易于遭遇并发缺陷,而并发缺陷难以暴露、检测、调试和修复。为消除并发缺陷对程序正确性的威胁,可以设法尽快暴露和准确检测并发缺陷,识别其构成要素以辅助调试和修复,或者容忍并发缺陷存在,通过有意识地控制执行调度,避免并发缺陷发生。因此本文研究如何准确检测和有效规避并发缺陷,以提高并发程序质量和增强其运行可靠性。本文将并发缺陷分为死锁、数据竞争、原子性违背和顺序违背4类,针对如何增加死锁检测能力、如何降低数据竞争检测误报率和漏报率、如何增强死锁规避能力并提高死锁规避效率和如何增强通用并发缺陷规避能力并降低其人工参与度等4个问题进行了深入研究,取得了如下创新性成果:
(1)针对现有死锁检测技术检测能力弱,只能检测互斥锁死锁的问题,研究并提出一种基于锁分配图的混合死锁动态检测方法Docklinter,以检测由互斥锁和读写锁造成的所有5种死锁。首先提出混合死锁的概念,以概括互斥锁和读写锁可能造成的5种死锁。接着提出混合锁分配图的概念,并给出其定义和构建方法。然后在目标程序运行时劫持所有互斥锁和读写锁的加锁解锁操作,动态构建和实时更新一个反映目标程序同步状态的混合锁分配图。最后在锁分配图上检测环并通过判定该环是否是死锁环来检测死锁。当检测到死锁时,输出相关信息以辅助调试。评测和对比实验表明Docklinter能成功检测分属5种死锁类型的所有13个死锁缺陷,检测能力强于Dimmunix;Docklinter造成的最大性能下降为10.15%,对目标程序的性能影响较小且可扩展性良好。
(2)针对现有竞争检测方法无法调和误检率与漏检率的矛盾的问题,研究并提出一种动静结合的竞争检测方法Dacelinter,重点研究2个问题:研究用户自定义同步原语的准确识别问题,并剔除其造成的良性和虚假数据竞争,降低误检率;研究触发条件互斥的多个静态竞争对的同时验证问题,提高检测效率并降低竞争检测的漏检率。首先静态分析找到所有可能的竞争访问对,定位所有可能构成自定义同步原语的自旋读循环。然后动态分析监视程序在竞争访问点的行为,控制线程调度以尽量暴露数据竞争,同时记录共享访问的锁集信息和时钟信息,并综合使用锁集算法和先发生于算法来检测因触发条件与当前所要暴露的数据竞争互斥而被遮蔽的数据竞争。最后通过动态监视远程写是否能交错到静态期间识别的自旋读循环并导致循环退出来确认自定义同步原语,一旦自定义同步原语得到确认,则剔除由其造成的虚假和良性数据竞争,得到一份包含尽可能少的误检和漏检的竞争检测结果。评测和对比实验表明,相对于现有检测方法,Dacelinter能够同时降低竞争检测的误检率和漏检率(误检率0%和漏检率8.64%),验证和检测效率较高,可扩展性优于传统的串行验证方法。
..........
参考文献(略)

提供海量毕业论文,论文格式,论文格式范文,留学生论文,商务报告相关资料检索服务。
本论文由代写论文网整理提供 http://www.dxlwwang.com/
需要专业的学术论文资料,请联系我们客服
本文地址:http://www.dxlwwang.com/jsj/6372.html
论文关键字:计算机硕士毕业论文 并发缺陷 检测 规避