依赖缓存设置

研究生毕业论文(申请博士学位)论文题目并发程序共享内存访问依赖研究作者姓名蒋炎岩学科、专业名称计算机软件与理论研究方向并发程序的测试与分析指导教师吕建马晓星许畅教授2017年11月学号:DG1333011论文答辩日期:指导教师:(签字)UnderstandingSharedMemoryDependencesinConcurrentProgramsbyYanyanJiangSupervisedbyProfessorJianLu,XiaoxingMa,andChangXuAdissertationsubmittedtothegraduateschoolofNanjingUniversityinpartialfulfillmentoftherequirementsforthedegreeofDoctorofPhilosophyinComputerSoftwareandTheoryDepartmentofComputerScienceandTechnologyNanjingUniversityNovember,2017南京大学研究生毕业论文中文摘要首页用纸毕业论文题目:并发程序共享内存访问依赖研究计算机软件与理论专业2013级博士生姓名:蒋炎岩指导教师(姓名、职称):吕建马晓星许畅教授摘要随着多核处理器的普及和编程语言的发展,并发程序在近年来得到了迅速的普及.
由于并发程序中的线程访问共享资源的顺序并不确定,导致并发缺陷难触发、难复现、难检测,给并发程序的质量保障带来了重大挑战.
本文关注实现并发程序动态分析的基础技术.
并发程序的动态分析技术具有代价相对较低、正确性(soundness)容易保证等优点,是目前最有效的并发程序质量保障手段之一,也是工业实践中应用最广泛的一类技术.
为实现并发程序的动态分析,就必须在运行时观测并发程序的行为.
不同于串行程序,并发程序执行包含线程间的共享资源依赖关系,这导致应用于串行程序的动态分析技术无法直接在并发程序中应用.
这些依赖关系必须在运行时予以捕获或记录,才能实现对并发程序执行轨迹的分析和调控.
本文关注并发程序共享内存访问的数据依赖(共享内存访问依赖,简称访存依赖)相关的研究问题.
由于共享内存是并发程序中最常见的共享资源也是实现其他类型共享资源的基础,因此实现访存依赖的高效观测和有效使用是实现并发程序动态分析的基本问题之一.
也因并发程序执行中共享内存访问数量众多,使用朴素方法获取访存依赖将导致数千倍的运行时开销和海量的事件日志.
如何设计、实现并发程序动态分析技术和与之适应的访存依赖的获取技术是十分具有挑战性的难题.
本文完成了对访存依赖相关的研究框架、获取技术和基于访存依赖的动态分析三方面的研究工作:1.
针对目前对访存依赖研究缺乏系统性的现状,本文首先提出了访存依赖的理论框架与技术框架.
理论框架帮助我们系统性地理解访存依赖获取这一问题,其中包括系统模型和访存依赖的形式化定义、访存依赖获取的问题空间.
理论框架还提出了并发程序共享内存访问的局部性理论,刻画了现实程序访问共享内存的特征,为后续深入研究奠定了基础;技术框架帮助我们在统一的视角下研究来自体系结构、计算机系统、程序设计语言和软件工程四个研究领域的相关工作.
技术框架包含三个要素:访存依赖获取技术的四个评价指标、获取访存依赖的两类技术、访存依赖在并发程序动态分析中的两类应用.
在技术框架下实现了对现有访存依赖相关技术所作出的权衡的全面综述,为进一步研究奠定了基础.
2.
在理论框架和技术框架的共同指导下,提出了利用线程和空间-线程局部性的高效访存依赖获取技术.
基于乐观锁的高效访存依赖获取技术RWTrace在不引入额外同步/原子操作的前提下,能实现O(1)时间对读操作的线程局部性检测,从而实现高效的访存依赖在线追踪,相比于朴素的互斥锁在访存密集型的程序上实现多达数百倍的性能提升;基于二分组(bisectionalcoordination)协议的高效访存依赖约减技术在运行时动态维护地址空间的区间划分,使得区间中的变量具有空间-线程局部性并被视作一个整体处理从而实现访存依赖约减,相比于高度优化的RWTrace,在仅付出0–54.
7%运行时开销的前提下实现多达97%的依赖减少.
3.
基于在访存依赖获取问题研究中的经验,提出基于访存依赖的动态分析技术:基于缓存的高效执行重放技术CARE,其通过数值预测缓存实现近似的检测线程局部性检测,通过启发式算法离线合成访存依赖,实现高效、简洁的运行时记录;基于二分组协议的高效数据竞争检测和假共享检测算法,通过避免对整个变量组进行不必要的检测,能大幅减少检测开销和元数据维护的数量;基于依赖反转技术的应用程序崩溃一致性自动检测技术C3和移动应用的并发测试技术AATT,在知名开源软件中找到了前所未知的缺陷.
最后,基于二十多年来的研究都未能找到只进行wait-free修改实现准确访存依赖追踪的事实,本文提出没有免费(只进行wait-free的修改)午餐(在多项式时间内获得满足顺序一致性的访存依赖)的猜想.
在复杂性探讨中,我们给出顺序一致性判定(VSC)问题的一个新证明,并据此证明了"没有免费午餐"猜想的特殊情形.
关键词:访存依赖;并发;并发程序;动态分析南京大学研究生毕业论文英文摘要首页用纸Thesis:UnderstandingSharedMemoryDependencesinConcurrentProgramsMajorin:ComputerSoftwareandTheoryAuthor:YanyanJiangSupervisor:ProfessorJianLu,XiaoxingMa,andChangXuAbstractConcurrentprogramminghasbeenpopularsincethewidespreadofmulti-coreprocessorsandincreasedsupportinprogramminglanguages.
However,thenon-deterministicnatureofconcurrentprogramsbringsnewchallenges:concur-rencybugsarenotoriouslydifficulttotrigger,reproduce,anddetect.
Improvingthequalityofconcurrentprogramshasbecomeamajorchallenge.
Thispaperfocusesonthedynamicanalysisofconcurrentprogramsinwhichaconcurrentprogram'sexecutionisobservedandanalyzed.
Dynamicanalysisisoneofthemosteffectiveandefficienttechniquestowardsqualityconcurrentprogramsbecauseitstrikesagoodbalancepointbetweenefficiencyandcom-pleteness.
Sincedynamicanalysesarebasedonexecutiontracesandconcurrentprogramshavedata/resourcedependencesacrossthreads,thecharacteristicsofsuchdependencesmustbeunderstoodtorealizeeffectiveandefficientdynamicanalysesofconcurrentprograms.
Thispaperparticularlyfocusesonacommonproblemfacedbyalldynamicanalysesofconcurrentprograms:obtainingsharedmemorydependences,theorderofsharedmemoryaccesses.
Sincethenon-determinismofaconcurrentpro-gramismainlyattributedtonon-deterministicaccessestosharedresources(inparticular,thesharedmemory),thedependences(ordering)betweentheseac-cessesmustbefaithfullyloggedandanalyzed.
However,duetothehugeamountofsharedmemoryaccesses,howtoeffectivelyandefficientlyobtainsuchdepen-dencesisacentralproblemthatservesasthecornerstoneofdynamicanalysesofconcurrentprograms.
Thispaperstudiesthreeaspectsofsharedmemorydependences:theresearchframework,obtainingsharedmemorydependences,anddynamicanalysesbasedonsharedmemorydependences:1.
Realizingthattherelacksasystematicunderstandingofsharedmemoryde-pendences,wefirstproposedatheoreticalframeworkofmodelingsharedmemorydependencesandatechnicalframeworkofstudyingrelatedwork.
Thetheoreticalframeworkcontainstheformalizationofconcurrentsystem,sharedmemorydependences,andtheirbasicproperties.
Furthermore,italsoincludesthetheoryoflocalityinwhichcharacteristicsofsharedmemoryac-cessesinreal-worldconcurrentprogramexecutionsarestudied.
Thetechni-calframework,underwhichwesurveyedexistingworkacrossseveralresearchdomains,containsthreekeyelementsofsharedmemorydependences:thecriteriaofmeasuringtheeffectivenessandefficiencyofatechniquethatob-tainsthem;twocategoriesofapproachestoobtainingthem;anddynamicanalysistechniquesbasedonthem.
2.
Basedonthesetwoframeworks,wedevelopedtwonoveltechniquesthatcaneffectivelyandefficientlycapturesharedmemorydependences.
OptimisticsharedmemorydependencetracingtechniqueRWTraceexploitsthreadlo-calityofconcurrentprograms.
Itcandetectthread-localreadsinO(1)timewithoutsynchronization.
Bynotkeepinglogforsuchevents,itachievedhundredsoftimesofspeed-upcomparedwithamutex-basedimplementa-tion;Onlinesharedmemorydependencereductionviabisectionalcoordina-tionexploitsspatial-threadlocalityofconcurrentprograms.
Itmaintainsanintervalpartitionoftheaddressspacesuchthatvariablesineachintervalexhibitspatial-threadlocality,yieldingupto97%reducedsharedmemorydependencesbypayingonly0–54.
7%ofruntimeoverheaduponthehighlyoptimizedRWTrace.
3.
Wealsostudiedhowtousesharedmemorydependencesinrealizingsoftwaretestinganddebuggingtechniques.
DeterministicreplaytechniqueCAREleveragesthevaluepredictioncachetoguideanefficientrecord-replayofconcurrentJavaprograms.
Dynamicanalyses(dataracedetectionandfalsesharingdetection)basedonbisectionalcoordinationcangreatlyreducerun-timeoverheadandmetadatamaintenancecost.
Softwaretestingtechniquesbasedonreversingdependencesfoundpreviouslyunknownbugsinpopularopen-sourcesoftware.
Finally,summarizingthepastresearch,wefoundthatnobodyeverachievedaprecisesharedmemorydependencetracingusingonlywait-freechangestotheprogramorconcurrentsystem.
Therefore,thispaperalsoraisesanegativecon-jecture:thereisnofree(wait-freemodification)lunch(sequentiallyconsistenttrace).
WeprovideaprooftoamorerestrictedcaseoftheVSC(verifyingse-quentialconsistency)problem,anduseasimilartechniquetoproveaspecialcaseoftheno-free-lunchconjecture.
Keywords:SharedMemoryDependence,Concurrency,ConcurrentProgram,DynamicAnalysisvii目录目录vii插图清单xi附表清单xiii1绪论11.
1研究背景21.
1.
1并发程序21.
1.
2并发程序的质量保障31.
1.
3并发程序的动态分析51.
2访存依赖与并发程序的动态分析61.
2.
1访存依赖61.
2.
2访存依赖与动态分析71.
2.
3访存依赖的获取问题81.
3本文工作101.
3.
1研究挑战101.
3.
2研究思路111.
3.
3研究贡献121.
4论文组织结构142理论框架152.
1问题定义152.
1.
1系统模型162.
1.
2访存依赖的定义182.
1.
3访存依赖获取的问题空间212.
2共享内存访问的局部性理论222.
2.
1局部性理论概述232.
2.
2局部性的三要素242.
2.
3线程局部性、空间-线程局部性与同步局部性272.
3小结33viii目录3技术框架与相关工作综述353.
1技术框架概述353.
1.
1访存依赖获取技术的评价指标363.
1.
2访存依赖获取的两类技术373.
1.
3访存依赖的两类应用393.
2获取访存依赖的技术403.
2.
1在线追踪403.
2.
2离线合成433.
3访存依赖的应用453.
3.
1轨迹分析453.
3.
2并发控制473.
4研究契机494高效的访存依赖获取514.
1基于乐观锁的访存依赖追踪514.
1.
1问题定义与解决思路514.
1.
2基于乐观锁的访存依赖追踪544.
1.
3正确性讨论594.
2基于二分组协议的在线访存依赖数量约减644.
2.
1问题定义与解决思路644.
2.
2二分组协议684.
3系统实现与实验评估734.
3.
1系统实现734.
3.
2实验评估774.
4小结815基于访存依赖的动态分析835.
1并发程序的动态分析835.
1.
1基于缓存和依赖推导的执行重放835.
1.
2基于二分组协议的动态分析935.
2基于依赖反转的软件测试985.
2.
1应用程序崩溃一致性的全自动检测985.
2.
2移动应用的并发缺陷暴露1075.
3小结113ix6访存依赖获取复杂性的讨论1156.
1No-Free-Lunch(NFL)猜想1156.
1.
1问题定义1156.
1.
2NFL猜想1196.
2NFL猜想特殊情形的证明1226.
2.
1VSC问题的新证明1226.
2.
2NFL猜想的特殊情形及其证明1256.
3复杂性结果的启示1287总结与展望1317.
1工作总结1317.
2研究展望132参考文献135简历与科研成果151致谢155x目录xi插图清单1.
1串行程序与并发程序区别示意图.
21.
2访存依赖示意图.
图(a)为数据依赖,图(b),(c)为访存依赖.
·61.
3本文研究贡献总结.
122.
1讨论访存依赖相关理论所用的并发系统模型.
162.
2准确/一致/不一致的访存依赖.
192.
3对读写操作予以包装以获取访存依赖(为全局锁变量)212.
4对不同的变量使用不同的锁和日志,实现更高效的访存依赖获取.
222.
5局部性理论的三要素:定义、量化、应用.
232.
6定义局部性的投影函数φ和特征函数χ.
252.
7区间大小k对具有空间-线程局部性共享内存访问数量的影响.
·313.
1技术框架的三要素:评价指标、技术、应用之间的关系.
363.
2访存依赖获取的两类技术:在线追踪、离线合成.
373.
3访存依赖应用与评价指标之间的关系.
393.
4访存依赖追踪技术的关键问题:指派变量对应的锁及高效地实现锁机制.
403.
5访存依赖合成技术的关键问题:权衡高效性/简化性与合成代价.
434.
1乐观锁对读指令作出的修改,下划线为被修改的读指令.
534.
2乐观锁对写指令作出的修改,下划线为被修改的写指令.
544.
3检测读事件e是否具有线程局部性的算法.
554.
4读事件集合rx的维护算法.
584.
5访存依赖的约减:(a)传递约减(TR),(b)正则传递约减(RTR).
虚线为被约减的依赖,双线为添加的依赖.
654.
6将变量x,y,z组合为变量组{x,y,z}以实现访存依赖约减.
··674.
7不合适的变量分组{x,y}导致冗余的依赖.
704.
8二分组的历史构成一棵二叉树.
714.
9二分组协议相对RWTrace的运行时开销.
804.
10二分组协议实现依赖约减和运行时开销之间的权衡.
805.
1使用变量数值进行线程行为的重放.
85xii插图清单5.
2CARE在数值预测缓存缺失时再次执行读操作并用锁保护以实现访存依赖记录.
875.
3基于缓存的执行重放对读/写指令作出的修改,下划线为被修改的指令.
885.
4CARE在不同缓存设置下的时间开销和记录数量对比.
925.
5存在假共享缺陷的代码片段.
965.
6文本编辑器Ted中具有崩溃一致性缺陷的代码.
1005.
7基于依赖反转的崩溃现场生成算法.
1035.
8GigaGet中包含并发缺陷的代码.
1085.
9GigaGet中并发缺陷的暴露.
1085.
10实现移动应用并发缺陷暴露的SO-DFS算法.
1106.
1复杂性讨论中对并发程序的修改示意图.
1166.
2VSC问题:根据E,po恢复满足顺序一致性的访存依赖.
··1206.
3最短超序列问题(SCS):给定01字符串si∈S和k,判定是否存在长度为k的字符串s满足si是s的子序列.
1226.
4将LSCS实例归约到VSC所构造的E,po1246.
5实现对ML,MR"信息屏蔽"的调度.
126xiii附表清单2.
1Smile程序P在状态σ=V,PC,E时选中线程t执行的语义.
172.
2用于局部性实证量化研究的实验对象.
302.
3线程、空间-线程和同步局部性的量化对比.
314.
1评估RWTrace和二分组协议所用基准程序及其设置.
774.
2RWTrace与MutexLock和CREWLock对比实验结果.
784.
3二分组协议实现的依赖约减与RWTrace和MutexLock的对比实验结果.
795.
1用于评估基于缓存Java程序执行重放技术CARE的实验对象.
·915.
2CARE和LEAP的运行时开销和日志数量对比.
925.
3C3在14个应用中检出的崩溃一致性缺陷.
粗体为开发者前所未知的缺陷.
1065.
4评估AATT所用的两组实验对象:有已知并发缺陷的应用、随机选取的应用.
1115.
5AATT在两组实验对象上的评估结果.
1126.
1同步操作的一致性范数层次结构.
129xiv附表清单1第一章绪论由于多核处理器的广泛部署和编程语言中并发特性的发展,并发程序在近年来得到了迅速的普及.
并发程序中的多个线程访问共享资源的顺序不确定性使得并发程序具有巨大的调度空间,导致了由并发性引起的缺陷难触发、难复现、难检测,给并发程序的质量保障带来了重大挑战.
为应对这一挑战,并发程序的动态分析技术由于其基于准确的执行轨迹,从而代价较低且正确性(soundness)容易保证,是目前最有效的并发程序质量保障手段之一,也是工业实践中应用最广泛的一类技术.
为实现并发程序的动态分析,就必须实现在运行时观测并发程序的行为.
并发程序相较串行程序的主要区别是其具有线程之间的数据依赖(即访存依赖),而获取访存依赖则是并发程序动态分析的基本问题.
虽然目前有众多关于并发程序动态分析的研究,但对"访存依赖"这一基本概念的理解仍是不足的,表现为如下两点:1.
缺乏对访存依赖的系统性认识.
现有技术通常基于"需求驱动→经验性质→实验验证"的研究思路,使用直觉或经验性质,从某一侧面研究访存依赖相关的某一个具体问题(如特定场景下的某类缺陷检测技术),对宏观的问题空间理解不足,研究进展缓慢.
2.
缺乏统一的技术框架以系统化地研究现有技术的优势与不足.
由于并发性存在于计算机系统栈的各个层次,因而来自体系结构、计算机系统、程序设计语言、软件工程等多个领域的研究者均在不同侧面研究过访存依赖相关的问题.
缺乏统一的技术框架使得相关研究之间的内在关系未被揭示,阻碍了新技术的发现.
立足于这两个问题,本文开展了对访存依赖相关问题的研究:提出研究访存依赖的理论模型和技术框架,并在此基础上研究访存依赖的高效获取技术和基于访存依赖的动态分析.
最后,我们还用"没有免费午餐"的猜想讨论访存依赖获取中的"难"和"易",为未来的研究奠定了坚实的基础.
本章对全文关注的研究问题、研究挑战、研究思路、研究贡献予以了概括.
首先介绍必要的背景知识:并发程序(第1.
1.
1节)、并发程序的质量保障(第1.
1.
2节)和并发程序的动态分析(第1.
1.
3节),然后引入访存依赖的概念(第1.
2.
1节)并讨论其与并发程序动态分析的关系(第1.
2.
2节),提出访存依赖获取问题(第1.
2.
3节).
之后,我们介绍目前的研究挑战(第1.
3.
1节)以及针对研究挑战制定的研究思路(第1.
3.
2节),并总结全文的研究贡献(第1.
3.
3节).
2第一章绪论1.
1研究背景1.
1.
1并发程序并发程序通过在程序中引入多个串行的指令执行流,以通过共享资源的方式通信协作来完成计算任务[18].
本文讨论的范畴限定为运行在单处理器或多处理器的共享内存计算机系统1上的并发程序.
如图1.
1所示,区别于串行程序(左),并发程序(右)的数据依赖可能来自其他线程2.
图1.
1串行程序与并发程序区别示意图.
在程序中引入并发性主要目的如下[14]:1.
实现多任务处理:在单处理器或多处理器系统上通过分时和调度使得计算机系统呈现同时执行多个任务的能力.
这一能力大幅降低了需要同时服务多个目标对象的服务器程序的编程难度,同时也是有效利用多处理器系统并行计算资源的必要基础;2.
提高单处理器计算资源的利用率:在处理器需要等待外部资源(如I/O或套接字数据)时能调度同一计算任务中的其他部分而不必将计算资源浪费在等待外部资源上;3.
有效利用多处理器系统中的并行计算资源:并发程序能在处理器数量增加时将计算任务分派到多个处理器上同时执行,从而实现相对于串行程序(同一时刻只能运行在一个处理器上)的计算加速.
1常见的单结点计算设备(如嵌入式设备、移动智能设备、个人电脑、工作站和服务器)均是此类计算机系统.
由网络连接、以消息传递进行通信的分布式计算机系统(包括具有分布式共享内存的系统)不在本文讨论之列.
2如文中如不作特别说明,执行轨迹中的每一方框代表一个共享内存访问事件,其中R(x)表示对变量x的读事件,W(x)表示对变量x的写事件,事件按照从上到下的顺序发生.
1.
1研究背景3并发程序在近年来迅速普及,其原因有二:(1)在硬件方面,随着摩尔定律在单处理器上的终结,单个处理器性能提升遇到瓶颈,处理器进入"横向发展"时代,共享内存多处理器系统迅速普及[65],必须使用并发程序才能有效利用多处理器的并行计算资源;(2)在软件方面,现代程序设计语言对并发性的支持越来越好.
不同于早期程序设计语言(如C语言)对并发性的支持很少而必须通过外部库(如pthreads)实现,现代程序设计语言(如Java,Go等)则对并发性有了原生支持,更进一步促进了并发程序的普及.
并发程序由多个线程组成,其中每个线程都可以看作是一个串行程序.
并发程序中的线程可以访问共享资源(资源包括内存变量、操作系统资源如描述符和句柄等)以实现线程间通信,协作完成计算任务.
并发程序运行时的软件平台和硬件系统称为并发系统.
并发系统在运行时维护各个线程的状态、调度线程执行并确定共享资源访问的规约.
例如,基于POSIX线程库[6]编写的C语言并发程序,其中的线程执行其被pthread_create函数创建时所指定的入口函数代码,并且可以访问共享内存或通过系统调用访问操作系统中的共享资源.
同一个基于POSIX线程库编写的C语言并发程序在不同并发系统上(处理器和操作系统)的运行时行为可能具有一定差异(如不同处理器具有不同的内存模型);再如,Java语言在语言级上支持线程,并发程序中的每个线程均对应一个java.
lang.
Thread类型对象,且该对象包含此线程的元数据和代码.
Java虚拟机中的所有线程拥有一个共享的堆区,其运行时行为则符合JSR-133标准[7]的规定.
1.
1.
2并发程序的质量保障并发程序的执行具有不确定性(non-determinism),其原因是并发系统通常对线程访问共享资源的顺序不做任何限制.
由于各个线程在多次执行中所处的环境不同1,因而其中指令执行的相对速度不同,多次运行同一并发程序可能获得截然不同的指令执行顺序、程序运行时状态和输出结果.
由于并发程序执行的不确定性,在包含t个线程、每个线程访问n次共享资源的并发程序中,不同的调度数量达到指数级的O(tn).
由于现实程序中的n通常非常大(取决于程序执行的长度,甚至远大于输入的数量),并发程序通常具有巨大的调度空间(interleavingspace).
并发程序的不确定性导致了并发缺陷难触发、难复现、难检测.
首先,有些并发缺陷必须由特定的线程调度才能触发.
其次,并发程序有指数级的输入空间(输入长度为k的程序有2O(k)种合法的输入).
若并发程序中的缺陷必须1线程的运行受到系统设置、处理器内部状态(如缓存)、外部输入、中断、系统中其他线程等的影响.
4第一章绪论在指定的输入和特定的线程调度下才能触发,在有限的测试资源约束下找到包含缺陷的输入和调度就更加困难.
而即便在运行时触发了并发缺陷(如导致程序崩溃),程序员仅根据错误的现场信息(如崩溃时的寄存器、栈区和堆区的快照)有时也难以在测试环境中重现错误和诊断出错的原因.
并发程序不确定性致使并发缺陷具有难触发、难复现、难检测的特点,而使得并发缺陷成为软件系统中的"定时炸弹",随时威胁软件系统的可靠性.
以下列举一些由并发缺陷而引发重大损失的案例:1.
1985至1987年Therac-25放射性治疗仪的软件缺陷导致了6起患者接受过量辐射的人员伤亡事件,是迄今为止最严重的放射性治疗仪引起的医疗事故.
事故的原因是Therac-25软件在某种特定的并发事件调度下触发了非预期的竞争条件(racecondition),违反了程序员假设的原子性,造成了治疗仪反馈给操作员的状态与治疗仪实际状态之间的不一致,最终使患者接受过量的辐射[88].
2.
2003年8月北美洲东北部的大停电波及了加拿大和美国的逾五千万人口,造成了数百亿美元的经济损失.
引发事故的原因之一是XA/21电网管理系统中的一个竞争条件使得电网的自动警报系统无法正常工作,最终令操作员对情况误判而未能及时调配电网负载,致使本可控制在局部地区的小规模停电演变为大范围的电网过载瘫痪[39].
在并发程序广泛普及的今天,并发程序的数量和规模日益增长、用户不断增加,如何在测试阶段暴露缺陷、在调试阶段诊断缺陷、在运行阶段避免缺陷从而提高并发程序的质量是十分具有挑战性的难题.
近二十年来,来自计算机体系结构、计算机系统、程序设计语言、软件工程等领域的研究者向这一问题发起了挑战,并提出了多种并发程序质量保障技术,取得了卓有成效的研究成果.
目前,并发程序的质量保障技术根据其作用的对象大体可以分为三类:1.
语言级技术在并发程序编写之前即对其行为进行约束,在语言层面(或库函数层面)对共享资源的访问进行限制,以从源头避免一些程序员在程序中引入并发缺陷的可能性.
例如Scala语言[9]提倡使用ActorModel[11]在多个动作者之间发送同步或异步的消息、使用Future处理异步事件.
这一模型倡导"仅使用消息传递进行线程间通信"的并发编程模式,在具有足够强表达能力的同时彻底消除一些由资源竞争引起的并发缺陷.
2.
代码级技术在并发程序编写完成后对其代码进行静态分析或验证,在程序被运行前即可发现其中潜在的缺陷或缺陷模式并报告给程序员复审.
对于规模较小但运行在安全性攸关场景下的并发程序,可以通过模型检验技术1.
1研究背景5[58]枚举其所有可能的执行,并证明其满足某些安全性质(例如不会发生死锁或活锁)或符合程序规约;对于规模更大的复杂程序,我们也可以对其中的一些常见并发缺陷模式进行静态检测,如检测程序中可能存在数据竞争的共享内存访问[125].
3.
执行级技术在有测试用例时或在生产环境中实际运行程序,并通过修改并发程序或运行时系统实现对程序运行时状态的监控,在并发缺陷发生前予以预测或规避、发生时予以检测、发生后予以修复.
例如,通过修改运行时系统约束并发程序的调度空间,可以避免运行时与测试环境中差异较大的调度而触发缺陷[40].
在程序运行时记录的信息还可用于重现并发缺陷的触发过程[51]、预测并发程序中的缺陷[55]或生成更多的测试用例[102].
对比在三方面展开的并发程序质量保障技术,语言级技术能从根本上避免一部分并发缺陷的发生,但同时也可能引入新类型的并发缺陷,且无法适用于已用现有编程语言和库函数编写的代码,并在某些场合(如需要高并发性能的数据库或服务器应用)下使用受限的并发模式致使无法达到既定的目标.
代码级技术原则上能应用于任何程序,直接根据程序代码产生缺陷报告,但由于程序设计语言的Turing完备性、输入空间的隐含规约等问题,模型检验和静态代码分析在大规模现实程序上的实用性仍面临重大挑战,为实用化而作出的近似处理(如不准确的别名分析、无法建模隐式控制流等)也导致了误报、漏报等问题.
执行级技术具有最佳的可用性,只要程序能够执行,其执行轨迹就能用于分析,但其分析结果仅限于一次执行,无法推广到并发程序的其他输入和调度.
1.
1.
3并发程序的动态分析本文关注执行级的并发程序质量保障技术.
在执行级对程序运行时状态予以监测和调控的技术又称为动态分析技术(dynamicanalysis)[54].
动态分析最早被用于串行程序的测试、调试和分析,之后则在并发程序中被广泛研究.
并发程序的动态分析技术通过对程序进行插装或对运行系统进行修改,而后观测/调控并发程序的运行时行为,从而实现各类并发程序的质量保障技术——缺陷检测、缺陷诊断、并发控制等.
这类动态分析技术已在并发程序质量保障方面成效卓著,研究成果主要体现在轨迹分析和运行时并发控制两个方面.
轨迹分析包括动态数据流分析[59]、并发缺陷检测[95,116]、轨迹重放调试[84]等技术;运行时并发控制包括事务内存[47,63,120]、数据竞争避免[46,117]和确定多线程[40,45]等技术.
相比于语言级的技术(如使用特定的并发模型),动态分析不需要其使用者(并发程序的开发者或测试人员)付出额外的学习成本和项目重构代价,只要有6第一章绪论图1.
2访存依赖示意图.
图(a)为数据依赖,图(b),(c)为访存依赖.
并发程序的对应测试用例即可开展动态分析,动态分析工具通常是全自动的.
相比于代码级的技术(如静态代码分析器),动态分析基于一次确定的程序执行,因此无需考虑代码级的分支、循环、调度的多种不确定性可能,通常效率较高,能支持大规模的实际程序,且分析的结果通常是准确(sound)的,产生误报的情形较少.
动态分析是目前最有效的并发程序质量保障手段之一,也是工业实践中应用最广泛的一类技术,因此本文关注于并发程序动态分析的相关技术.
1.
2访存依赖与并发程序的动态分析1.
2.
1访存依赖区别于串行程序在给定输入的情况下具有完全确定的控制流和数据流,并发程序中的线程通过共享资源实现线程间通信,合作完成计算任务,因此线程访问资源的先后次序会对程序行为有重大影响.
这使得并发程序拥有巨大的调度空间而难测试、难调试、质量难以保障.
观测并发程序执行中线程访问共享资源的顺序是理解并发程序执行的必要条件,也是并发程序动态分析的基础(将在下节中讨论).
在本文讨论范围的单/多处理器共享内存计算机系统中,线程间通信主要由共享内存实现.
此类系统中,共享内存是访问延迟最小(纳秒级)、代价最低(仅需一条或几条机器指令)、数量最大(多达数十GB)的共享资源,且其他类型的资源(如锁、消息机制、并发数据结构等)均可基于共享内存实现.
因此对并发程序共享内存访问顺序进行观测能够代表对并发程序共享资源的观测.
本文的研究对象是访存依赖(sharedmemorydependence),即并发程序访问共享内存的顺序.
非形式地说,访存依赖指程序执行轨迹中可能产生数据依赖1.
2访存依赖与并发程序的动态分析7的共享内存访问事件之间的顺序关系[28].
即访存依赖是定义在所有共享内存访问事件E上的一个二元关系,由其确定任何一对有可能产生线程间数据依赖的共享内存访问事件1在执行中实际发生的先后关系.
图1.
2a中蓝色曲线箭头所示为读/写操作之间的数据依赖.
图1.
2b和图1.
2c中的红色曲线箭头分别描述了两个访存依赖关系,均能代表图1.
2a中的数据依赖.
访存依赖及其相关概念将在第2章中进行形式化定义.
访存依赖包含了具有潜在数据依赖事件之间的顺序关系.
因此根据访存依赖可以对并发程序的执行轨迹进行串行化.
在外部输入确定的前提下,任意多次按照访存依赖的规定顺序执行并发程序,都将得到完全相同的执行结果(包括输出、程序状态等).
早期的研究已观测到访存依赖的这一性质,并将其用于实现并发程序的执行重放[112].
获取访存依赖是实现并发程序动态分析的基石.
1.
2.
2访存依赖与动态分析Lu等人调研了开源软件中的并发缺陷模式[94],除较为容易检测的死锁缺陷(deadlockbug)外,剩余缺陷的97%可归结为原子性违反(atomicityviolation,占67%)和顺序违反(orderviolation,占33%).
因此这两类缺陷的检测、复现、诊断、避免即成为并发程序动态分析的主要目标.
这两类问题均是由于对共享资源(本文中研究共享内存)的访问顺序不当导致的,因此获得共享资源的访问顺序(即访存依赖)是并发程序动态分析中的重要问题.
并发程序的动态分析根据其产生作用的时间点可以分为两类:运行后(post-mortem)的轨迹(trace)分析技术对程序执行轨迹中的各类特征进行分析,从而实现并发缺陷的检测、复现和诊断等功能;运行时的并发控制技术在运行时检测程序的执行,并在必要时改变线程访问内存的顺序,从而实现事务语义、缺陷避免、消除不确定性等质量保障技术.
对于这两类动态分析技术,获取访存依赖都是其基础问题和先决条件:1.
对于轨迹分析技术,重点是得到执行轨迹.
为实现并发程序的执行重放调试,首先需要保证能够重现并发程序的执行结果,即按照与执行轨迹一致的访存依赖顺序执行程序[84].
在执行重放的基础上,我们还可以从执行轨迹中推断可能存在的并发缺陷(轨迹预测分析).
例如,未被同步操作约束的两个冲突访存事件即构成一个数据竞争[49,115],使用与数据依赖完全一致的访存依赖即可对执行轨迹中的数据竞争予以检测.
基于同一执行轨迹,研究者还提出了其他定义共享内存访问操作之间因果性的因果模型1仅当以下三个条件满足时,一对事件可能产生线程间数据依赖:(1)访问同一内存地址;(2)发生在不同线程;(3)至少有一个是写操作.
此定义与数据竞争(datarace)的定义类似.
8第一章绪论(causalmodel)[118,122],并将因果模型实现为预测能力更强的并发程序缺陷检测技术[71].
此外,执行轨迹中的访存依赖信息还能指导如原子性违反[95]等其他类型缺陷的发现,或为后续主动测试提供目标[116].
2.
对于并发控制技术,需要在程序运行时观测程序的状态并对其行为进行调整.
并发控制实现的关键技术是在共享内存访问发生前即获得访存依赖信息,从而对访存顺序进行调控(如检测到冲突事务时进行回滚).
由于并发控制技术往往运行在生产环境中并要求在线获取准确的访存依赖,因此其设计通常也是最具挑战的.
并发控制技术通过调整并发程序的执行轨迹以实现开发者预期的功能或避免并发缺陷,以提高并发程序的质量.
软件/硬件事务内存相关研究近年来已取得一定的进展[50,61],Intel已开始尝试在商业处理器中集成事务内存支持并在一些应用场景取得了显著的性能提升[133];为了进一步避免并发缺陷,运行时系统还可以主动对程序行为在运行时予以修正,例如Zhang等人将基本块构成的极大无环子图作为事务处理[137],从而避免有害数据竞争引发的并发缺陷;减少并发缺陷的终极目标是确定多线程[40,45]:采取确定的规则对系统内的共享资源进行调度,从而尽可能降低不确定性带来并发缺陷的可能.
综上所述,获取访存依赖是对并发程序进行动态分析的基础.
由于现代多处理器系统访问共享内存的代价很低,并发程序的共享内存访问通常数量大、频率高.
故如何在获取访存依赖的同时不对程序执行的速度、内存使用、语义等产生过多负面影响,是实现高效动态分析技术的一大挑战.
1.
2.
3访存依赖的获取问题朴素的访存依赖获取技术只需修改运行时系统或对共享内存访问进行插装,在共享内存访问前后插入同步操作将所有对共享内存的访问串行化,并在同时记录全局的时间戳,即可得到所有共享内存访问的全序,满足动态分析的需求.
然而,朴素的访存依赖获取可能带来巨大的开销[22],而其串行化内存访问与并发程序利用多处理器并行计算资源的初衷亦背道而驰.
为了实现更高效的并发程序动态分析来提高并发程序的质量,针对其具体应用场景设计高效的访存依赖获取技术是一个具有挑战性的难题.
访存依赖的获取技术在近年来受到越来越多研究者的关注.
鉴于并发性存在于计算机系统栈的各个层次,根据研究对象和研究手段的不同,现有的研究工作横跨体系结构、计算机系统、程序设计语言和软件工程等领域.
访存依赖的获取是通过程序插装(编译时插装[69]、二进制改写[22])、修改运行时系统(虚拟机[28]或定制硬件[17]),在程序执行的过程中记录直接或间1.
2访存依赖与并发程序的动态分析9接信息后,在线或离线推导得到.
根据动态分析技术的需求,高效的访存依赖获取技术应当具有以下特点:1.
在访存事件发生前就能获得依赖关系,从而能实现对程序行为的及时控制以避免并发缺陷的触发;2.
对运行时系统造成的时间开销和语义影响尽可能小,从而能降低在开发环境下的开销并且能够应用于生产系统;3.
能在满足动态分析需求的前提下记录数量尽可能的少,从而减少动态分析技术需要分析的访存依赖数量、提高其效率.
显然,"获取及时"、"开销小"、"数量少"的目标是难以同时实现的.
加之访存依赖的获取技术与其支持的动态分析技术相关,此即定义了一个问题空间.
目前,根据访存依赖获取技术是否能在访存事件发生前即得到依赖,主要分为直接获取(在线追踪)和间接获取(离线合成)两类.
在线追踪技术能即时得到准确的访存依赖,但通常对运行系统需要作出较大修改,高效性和简化性不足.
访存依赖追踪技术直接在内存访问发生前即得到.
目前,这类工作均是通过对共享内存访问予以同步或互斥实现的:为共享变量x分配锁x,并用x保护对变量x的访问.
此时记录解锁和上锁之间的依赖关系,即能获得访存依赖.
这类访存依赖追踪技术实现简单、准确性容易保证,是最早研究的一类技术[84],且已得到广泛的应用.
然而,在程序运行时增加额外锁是与共享内存并发程序设计初衷背道而驰的.
共享内存被定义为轻量级的通信方式,线程访问共享内存无需任何同步操作,从而最大程度发挥线程之间的并行性.
另一方面,为了保证访存依赖的正确获取,依赖信息更新和访存需为原子操作,而对于实现互斥来说,锁或与之等价的同步手段是无法避免的[15].
为实现高效性和简化性,访存依赖追踪技术的两个关键问题是如何将变量指派到其对应的锁,及如何实现锁机制从而降低其在运行时开销.
锁的指派分为静态指派(在程序运行前确定指派方式,如按照硬件缓存线指派[129]、按对象指派[124]等)和动态指派(在运行时动态根据程序运行时的访存情况进行指派[80]).
锁的实现可以借助定制硬件[129]、存储保护[52],也可使用软件实现,其中具有代表性的技术是利用访存局部性实现的偏向锁[28,79].
离线合成技术由于间接记录的灵活性,能够在高效、简化和合成代价之间进行权衡,缺点是无法即时得到访存依赖.
应用需根据其场景(对评价指标的需求)选择合适的访存依赖获取技术.
除直接追踪外,访存依赖的另一获取方法是在运行时记录间接信息,在程序结束(或运行到检查点)后根据间接记录合成访存依赖.
间接获取法适用于事后分析型的应用,如缺陷定位[136]和轨迹预测分10第一章绪论析[71].
由于不需在运行时立即得到依赖,依赖合成允许消耗更多计算资源甚至使用约束求解器[87],因此间接记录也更加灵活,也通常更加高效、简化.
因此,合成访存依赖的核心问题是通过选取记录不同的间接信息以实现对准确性、高效性、简化性和合成时间开销的权衡.
如只记录少量框架性的信息,则合成的代价极大或无法提供准确性保障,但因为其开销小,适用于生产应用场景[109,136].
若在每个线程本地记录读写事件数值或执行路径(此记录无需额外线程间通信),则可以使用约束求解器合成与在每个线程执行效果等价的依赖,但依赖合成是目前技术难以求解的NP-完全问题.
若允许进一步增加记录信息的数量(同时记录的高效性和简化性降低),推导出的访存依赖能够提供保证重现等价执行的准确性[144].
1.
3本文工作1.
3.
1研究挑战访存依赖是实现并发程序动态分析的基础.
目前尚无一项单一的访存依赖获取技术能满足所有动态分析技术的需求.
针对动态分析对即时性、数量、开销等的要求,访存依赖获取技术在各方面的指标之间进行权衡.
然而,"访存依赖"及其相关问题仍然主要是作为其应用的附属技术研究,缺乏系统化的研究和理解,目前的研究主要有两点局限:首先,缺乏对访存依赖这一事物的理论认识及量化研究.
因此,现有研究工作的基本思路通常是"需求驱动→经验性质→实验验证".
为了实现高效的动态分析,现有研究通常从一些实际观察出发,使用并发程序的一些经验性质(如线程局部性[144]、读/写不对称性[28]、同步局部性[34]),依靠启发式优化[90]或约束求解[87]实现,然后再以现实中的基准程序或并发缺陷予以验证.
这一流程确实促进了并发程序质量保障技术的发展,但与此同时,由于缺少对访存依赖自身性质的认识,基于"试错"的研究效率有待提高且研究进展缓慢,现有的技术仍然难以满足很多动态分析对性能等指标的要求.
其次,缺乏统一的技术框架用以研究现有技术的优势与不足,无法系统化地指导新的访存依赖相关技术的发展.
由于并发性存在于计算机系统栈的各个层次,体系结构、计算机系统、程序设计语言和软件工程等领域均展开了对并发程序动态分析的相关研究.
由于未曾意识到获取访存依赖是这些技术的基础,虽然这些研究具有内在关联,研究技术也相互重叠,但技术体系尚未打通,阻碍了技术的进一步发展.
例如在体系结构领域使用全局时钟为访存事件定序的技术[34]在软件工程领域也得到了应用[135].
1.
3本文工作11由于存在这两点局限,目前很多并发程序的动态分析技术开销巨大,仍然只能停留在实验室或测试阶段:执行重放、数据竞争检测等技术在共享内存访问密集型的应用中可能带来数百或数千倍的时间开销,而使其实用化受到较大阻碍.
受限于目前研究方法落后的原因,相关研究进展较为缓慢.
另一方面,尽管现有动态分析技术在缺陷检测方面取得了卓著的成效,大型软件、新兴软件(如移动应用)中依然包含很多缺陷,如何将访存依赖(及其推广)用于缺陷检测实现软件质量的提升,也是具有挑战性的研究问题.
1.
3.
2研究思路本文认为,访存依赖获取研究的最大挑战即在于针对目前研究的两点局限,全面地理解访存依赖的定义和性质,并系统化地分析现有技术,以找出其中的研究契机.
只有突破这两项挑战,才能指导系统化的访存依赖获取技术研究,并将它们应用到并发程序的动态分析中去.
针对缺乏访存依赖获取问题理论认识的研究现状,首先应明确问题的定义和范围,即形式化地定义访存依赖及其获取问题.
在此基础上,我们注意到现实中的程序访问共享内存的模式既非随机亦非固定,因而在形式化的框架下研究访存依赖所具有的性质,即访存依赖的理论建模,对设计高效的访存依赖获取技术有重要指导意义.
最后,我们还希望能从理论研究中认识到现有工作的固有局限性,即在何种条件下,获取访存依赖具有怎样的难度.
而针对缺乏统一框架研究现有技术的优势与不足的研究现状,本文在理论部分的指导下提出能容纳现有访存依赖获取技术的框架,并在框架中寻找实现高效访存依赖获取技术的研究契机.
获取访存依赖技术本身的挑战是在即时性(在访存事件发生前就能获得依赖关系)、准确性(能获得每个变量准确的数据依赖)、高效性(不引起额外开销和调度变化)和简化性(数量少)之间作出权衡.
技术部分的研究主要关注于寻找这些技术指标中的新平衡点.
应用上述理论模型和技术框架,我们根据并发程序访问共享内存的特征,吸取技术框架中已有技术的长处、弥补现有技术的缺点,特别关注局部性理论在访存依赖获取技术中的应用,提出了能取得数量级提升的高效访存依赖获取技术,从而实现高效的并发程序动态分析.
此外,我们还注意到"反转"访存依赖将导致新的、不同的执行而触发并发程序中潜在的缺陷.
本文还根据反转数据依赖关系这一思想,提出一系列软件质量保障技术,寻找开源软件中的前所未知缺陷,以提高其质量.
12第一章绪论图1.
3本文研究贡献总结.
1.
3.
3研究贡献基于上述研究思路开展研究,本文的主要工作总结如图1.
3所示,现概述研究贡献如下:首先,针对访存依赖相关问题缺乏理论、技术框架的现状,我们对来自体系结构、计算机系统、程序设计语言、软件工程四个领域的相关工作进行了归纳总结,在此基础上提出访存依赖的理论框架与技术框架:1.
理论框架对访存依赖、访存依赖获取问题进行了形式化定义和建模.
针对"共享内存访问具有局部性"这一传统认识,对线程、空间-线程、同步局部性进行了形式化定义,提出了现实程序具有的局部性模型,并针对现实程序进行了局部性的量化研究;2.
技术框架则对访存依赖相关的研究工作进行了理解和探讨.
技术框架包含三个要素:访存依赖获取技术的评价指标(即时性、准确性、高效性、简化性)、两类访存依赖获取技术(在线追踪、离线合成)、两类基于访存依赖的并发程序动态分析(轨迹分析、并发控制).
这一技术框架成功统一了来自多个领域的研究工作,深化了我们对访存依赖获取技术研究进展、研究挑战和研究机遇的理解.
1.
3本文工作13其次,在理论框架、技术框架的共同指导下,我们发现利用并发程序具有的各类局部性是改善现有访存依赖获取技术运行时开销大、日志数量多的有效手段.
据此,我们提出两项访存依赖获取的新技术:1.
基于访存依赖具有的线程局部性,提出基于乐观锁的访存依赖追踪技术RWTrace.
其能在不引入额外同步操作的前提下在O(1)的时间内有效检测读操作是否具有线程局部性,以实现高效的访存依赖获取.
相比于朴素的互斥锁,在访存密集型的程序上能实现多达数百倍的性能提升;2.
基于访存依赖具有的空间-线程局部性,提出二分组(bisectionalcoordina-tion)协议实现在线访存依赖约减.
其能在运行时维护地址空间的区间划分,使得区间中的共享内存地址具有空间-线程局部性,并可整体化处理,从而实现访存依赖的约减.
相比于高度优化的RWTrace,在仅付出0–54.
7%运行时开销的前提下,实现多达97%的访存依赖数量约减.
再次,基于上述两个框架和设计高效访存依赖获取算法的经验,我们进一步研究了访存依赖在动态分析中的应用,提出了以下可针对实际程序使用的具体动态分析技术:1.
基于访存依赖的并发程序动态分析技术.
其中包括两份研究工作:基于缓存的执行重放技术CARE和基于二分组协议的缺陷检测算法.
CARE使用数值预测缓存检测读事件的线程局部性以减少记录数量,并使用离线合成技术实现高效的Java程序执行重放调试,相比于使用互斥锁的技术减少多达数十倍的运行时开销和数百倍的访存依赖数量;基于二分组协议的高效数据竞争检测和假共享检测算法则利用二分组协议高效维护具有空间-线程局部性地址空间划分的特性,实现检测调用数量和元数据维护开销的大幅减少;2.
基于依赖反转(在多次执行中将依赖顺序进行调换)技术实现的各类软件测试和分析技术.
其中包括两份研究工作:应用程序的崩溃一致性检测技术C3和移动应用并发缺陷暴露技术AATT.
C3实现了软件中由于文件系统操作顺序反转引起的原子性违反缺陷的全自动检测.
其检出了知名开源软件(如GNUcoreutils,GNUzip等)中的前所未知的崩溃一致性缺陷;AATT通过同时探索移动应用的输入空间和调度空间,实现了高效的并发缺陷的暴露.
其自动检出了流行开源移动应用中前所未知的并发缺陷.
最后,纵观二十多年来访存依赖相关问题的研究成果和本文的研究经验,在仅对并发程序进行wait-free修改的前提下,获取准确的访存依赖是这一研究领域的终极理想之一.
我们对这一目标提出否定的猜想:"天下没有免费的午餐(NoFreeLunch,NFL)",即在合理的前提假设下,通过对共享内存访问操作进14第一章绪论行wait-free修改,则总存在一个程序,使得推导其满足顺序一致性的访存依赖时间复杂度是NP-完全的.
我们对这一猜想的证明作出了一些尝试,证明了顺序一致性验证(VSC)问题的一个更受限情况,用类似的技术进一步证明了NFL猜想的一个特殊情形,并根据这些理论结论对现有的技术进行总结和展望.
1.
4论文组织结构本文依据研究贡献的逻辑顺序组织如下:第2章给出全文的理论框架,包括形式化的系统模型和问题定义,以及并发程序共享内存访问所具有的局部性特征理论.
基于此,第3章提出"四个指标、两类技术、两类应用"的技术框架,对访存依赖相关的研究工作进行综述并讨论研究契机.
第4章提出我们在理论框架和技术框架指导下设计、实现的访存依赖获取技术:基于乐观锁的访存依赖追踪(第4.
1节)、基于二分组协议的访存依赖数量约减(第4.
2节),及其实现技术和实验评估(第4.
3节).
第5章描述基于访存依赖的动态分析技术,包括基于缓存和依赖推导的执行重放(第5.
1.
1节)、基于二分组协议的动态分析(第5.
1.
2节)、应用程序的崩溃一致性自动检测(第5.
2.
1节)和移动应用的并发缺陷暴露(第5.
2.
2节).
第6章提出"没有免费午餐"的猜想及其形式化定义,并给出其特殊情况的证明,探讨这一理论结果对访存依赖获取问题未来工作的启示.
最后,第7章对全文工作予以总结并提出未来可能的研究方向.
15第二章理论框架对并发程序进行动态分析(观测或调整并发程序的执行轨迹以实现缺陷的检测、诊断或避免)是保障并发程序质量的重要手段.
然而,由于并发程序不同于串行程序,其存在线程间的数据依赖,无法从单个线程的执行路径中推导出满足全局一致性的执行轨迹,因此获得这些线程间的数据依赖关系(访存依赖)是进行并发程序动态分析的先决条件.
因并发程序执行中通常包含海量的共享内存访问,若使用朴素的算法将共享内存访问串行化来实现访存依赖的获取,则会带来巨大的运行时时间开销和海量的依赖日志,无法满足对现实程序实现并发程序动态分析的需求.
为了更好地理解访存依赖,摆脱现有研究工作"需求驱动→经验性质→实验验证"思路的局限,本章提出了访存依赖获取问题的理论框架,对访存依赖进行形式化定义、提出访存依赖的问题空间、理解访存依赖所具有的性质.
理论框架包含以下两部分:1.
第2.
1节明确本文的研究对象.
具体而言,我们给出一个字节码语言Smile语言及其运行的并发系统、执行轨迹、访存依赖等概念的形式化定义,并在这一简化的系统模型上定义访存依赖获取的问题空间.
2.
第2.
2节提出本文研究对象所具有的性质.
具体而言,我们提出并发程序共享内存访问具有的局部性理论,提出了一个用来形式化和量化"局部性"这一非形式化概念的框架,并用这一框架实现了线程局部性、空间-线程局部性和同步局部性的形式化定义,在现实程序中量化验证了这些局部性的存在.
局部性是本文实现高效访存依赖获取的重要技术基础.
2.
1问题定义给予研究问题一个明确的定义是对其进行系统化研究的先决条件,故本节给出访存依赖的形式化定义:"访存依赖获取"是通过对运行时系统的修改或程序插装,得到访存依赖的过程.
我们首先在第2.
1.
1节定义了并发系统的模型,包括Smile字节码语言、Smile程序执行的语义及其内存模型.
基于这一模型,我们在第2.
1.
2节给出访存依赖的定义和性质,并在第2.
1.
3节讨论访存依赖获取的两个朴素算法,而由此引发对这一问题空间的初步讨论.
16第二章理论框架图2.
1讨论访存依赖相关理论所用的并发系统模型.
2.
1.
1系统模型2.
1.
1.
1Smile语言首先在一个简化的并发系统(图2.
1)上给出基于字节码的程序语言Smile.
本文后续讨论均基于此语言.
定义Smile程序P为三元组P=T,X,I,其中:1.
T为线程集合,T={t1,t2,t|T|},ti代表编号为i线程的标识符.
2.
X=Xs∪Xt为变量集合,由共享变量集合Xs={x1,x2,x|Xs|}及每个线程的局部变量集合Xt={xt11,xt22xt|Xt||Xt|}构成.
Xs中的共享变量任意线程均可访问,xti则仅限线程t访问.
3.
指令序列I={i1,i2,i|I|},其中指令包括(a)根据局部变量数值xti跳转:if(xtk)gotoij;(b)读取共享内存变量:xtk=R(xk′);(c)写入共享内存变量:W(xk,xtk′);(d)线程本地的局部变量运算:xtk=op(xtk,xtk′).
Smile语言包含了共享内存的读/写操作和线程本地的Turing-Complete计算,既能反映并发程序访问共享内存的复杂性,亦较为简洁,易于研究其性质.
2.
1.
1.
2Smile程序语义定义并发系统在运行时的状态σ=V,PC,E,其中:1.
V:X→Z将每个变量映射到其当前数值;2.
PC:T→N将每个线程标识符映射到其下条指令的编号;2.
1问题定义17表2.
1Smile程序P在状态σ=V,PC,E时选中线程t执行的语义.
名称PC(t)处指令条件新状态σ′分支(真)if(xtk)gotoijV(xtk)=0V,PC[t→j],E分支(假)if(xtk)gotoijV(xtk)=0V,PC[t→PC(t)+1],E读共享内存xtk=R(xk′)V[xtk→V(xk′)],PC[t→PC(t)+1],E∪{R(t,xk′,V(xk′)}写共享内存W(xk,xtk′)V[xk→V(xtk′)],PC[t→PC(t)+1],E∪{W(t,xk,V(xtk′)}局部运算xtk=op(xtk,xtk′)V[xtk→op(xtk,xtk′)],PC[t→PC(t)+1],E3.
E={e1,e2,是访存事件日志的集合,包含执行历史中所有的访存事件.
其中e=W(t,x,v)代表线程t向变量x写入值v,e=R(t,x,v)代表线程t从变量x读出值v.
我们e.
rw∈{r,w}表示事件e的类型(r代表读事件、w代表写事件),用e.
t,e.
x和e.
v分别表示事件e发生的线程、访问的变量和读/写的数值1.
并发系统的初始状态σ0=V0,PC0,E0,其中x∈X.
V0(x)=0,t∈T.
PC0(t)=1,E0=.
在任意时刻,假设并发系统处于状态σ=V,PC,E,其可以任意选择一个线程t∈T并执行一条指令.
表2.
1定义了所有指令的语义,在状态为σ时,若线程t被选中,则取出PC(t)处的指令iPC(t)执行,根据表中语义得到新状态σ′.
如此往复,当t执行指令后PC(t)不再为合法指令(PC(t)|I|)时程序结束.
因此,一次程序执行可以看作是形如τ=[σ0t1→σ1t2→.
.
.
tn→σn]的执行轨迹,其中σi=Vi,PCi,Ei,ti为在第i步时选择的线程.
E=En即为本次执行的访存事件集合.
在此模型中,每一线程都按顺序依次执行指令,故存在指令执行的全序,亦存在E中事件的全序tot.
定义程序顺序(programorder,po)为E上的最小偏序集使得对于任意线程t,所有发生在线程t中的事件(W(t,x,y)∈E或R(t,x,y)∈E)在po中被排序.
易见偏序关系po是存在且是唯一的,满足eipoej当且仅当(i99.
99%99.
80%water99.
77%99.
95%99.
99%99.
99%fft80.
71%98.
27%>99.
99%99.
32%radix72.
19%97.
30%99.
70%98.
61%fluid99.
44%99.
91%99.
91%99.
99%qsort76.
47%99.
42%99.
79%99.
56%x26496.
09%99.
90%>99.
99%99.
99%2223242526272829210211212213214215220100101102103分组大小(2k)归一化χ(ei1)=χ(ei)数量oceanwaterfftradixfluidqsortx264图2.
7区间大小k对具有空间-线程局部性共享内存访问数量的影响.
其中代价函数c定义如下:若存在同步变量xs能推导出{ei,.
.
.
ej}的数据依赖,则ci,j=1,否则ci,j=∞.
χSynL(e)定义为fm取最优解时e所对应的同步变量,并据此计算出同步局部性的量化统计L(E).
我们使用LLVM工具对其共享内存访问进行插装并获得所有对静态数据区和堆区的内存访问,以实现执行轨迹的获取.
所有实验结果均在一台有4个6核心IntelXeonX7460处理器(共24个处理器核心)和64GB内存的服务器上运行得到.
每个实验对象均运行10次,并取统计数据的平均值予以展示.
对线程、空间-线程、同步局部性的实证量化研究结果如表2.
3和图2.
7所示.
表2.
3展示了线程、空间-线程和同步局部性的量化研究结果(对空间-线程局部性,我们展示k=6的情形和对任意k∈N的最优值).
图2.
7包含了划分区间大小k对具有空间-线程局部性事件数量的影响.
根据L(E)的统计结果,可总结得出以下结论:32第二章理论框架1.
现实中并发程序对共享内存的访问确实具有相当程度的局部性,即便考虑L(E)数量最小的一列(线程局部性),也有72.
19–99.
77%(中位数96.
09%)的共享内存访问是"局部"事件.
2.
空间-线程局部性具有优秀的应用潜力.
假如我们能在程序运行前就知道其局部性最优的k,即便使用简单的静态空间分组(区间长度为2k),具有空间局部性的事件仍然达到了99.
70–99.
99%(中位数99.
99%),即如能充分利用空间-线程局部性,平均意义上仅有万分之一的共享内存访问是"非局部"事件.
3.
对于同步局部性与空间-线程局部性之间正交属性的同时利用可展现出更优秀的应用潜力.
在使用与空间-线程局部性同等长度的区间分组(k=6)时,具有同步局部性的事件数量(98.
61–99.
99%,中位数99.
80%)显著多于空间-线程局部性的事件数量(97.
30–99.
95%中位数99.
73%).
我们将在未来工作中对并发程序共享内存访问的局部性进行更深入的量化研究,以实现更高效的访存依赖获取技术.
2.
2.
3.
5局部性与访存依赖获取局部性,作为现实中并发程序共享内存访问的固有特性,可以用于指导高效访存依赖获取技术.
易见,获取访存依赖的算法在不同的访问模式下有不同的表现.
例如若整个程序中只有一个共享变量,图2.
3与图2.
4中的算法就是等价的.
但在实际系统中,由于大量共享变量的存在,图2.
4的算法即因使用细粒度锁(对不同共享变量使用不同的锁和时间戳),性能会显著优于图2.
3[69].
因此,利用现实并发程序访问共享内存的特性,有助于实现更高效的访存依赖获取技术,进而实现高效的并发程序动态分析技术.
局部性的动态应用可用于实现高效的访存依赖获取技术:1.
如果事件e∈E具有线程局部性或空间-线程局部性,则在记录所有不具有局部性事件的数据依赖关系的前提下,省略对局部事件的记录,也能推导出一致的访存依赖[28].
由于绝大部分内存访问都有线程局部性或空间-线程局部性,因而对其高效的检测亦为减少访存依赖获取事件开销和日志数量的重要手段.
这两类局部性也是目前研究工作关注的焦点[80].
2.
如果变量x在一段时间内具有同步局部性,则仅记录同步事件发生的顺序,就能够推导出这段时间内x的数据依赖关系.
多份研究工作[80,109]均表明,并发程序中的同步事件数量远少于访存事件,且记录同步事件发生的顺序不会引入额外的同步.
若能有效地利用变量的同步局部性,将能在获得一致访存依赖的前提下大幅降低其运行时开销.
2.
3小结33对局部性进行动态利用的典型技术是访存依赖追踪技术Octet[28],利用局部性提高访存依赖获取的效率.
其在运行时利用乐观锁快速检测内存访问事件是否具有线程局部性,并在具有线程局部性的事件上忽略访存依赖的记录.
此项技术能高效实现如执行重放[27]、事务内存[137]、数据竞争避免[117]等并发程序的动态分析技术.
局部性的静态应用可以指导访存依赖的合成.
有文献[57]证明,如果只在线程本地记录读写事件的数值,得到任一满足顺序一致性的访存依赖是NP-完全问题.
但由于现实程序同时具有线程局部性和同步局部性,在现实程序的执行轨迹中,大部分事件的时序关系是能够确定的,因而约束求解器通常可以在较短的时间内找到一组可行解,以实现现实程序的执行重放[87].
利用局部性实现的高效访存依赖获取技术将在第3章提出的技术框架中与其他访存依赖获取技术共同探讨.
2.
3小结在本章中,我们首先对本文的研究对象访存依赖及其相关概念(如并发系统、执行轨迹等)进行了形式化定义,探讨了访存依赖与并发程序动态分析技术之间的关系.
这一模型为我们后续的技术框架(第3章)对来自多个研究领域的研究工作进行系统化地总结奠定了基础.
其次,本章还提出了并发程序共享内存访问的局部性理论.
针对现有技术对"局部性"这一概念缺乏系统性认识的现状,我们提出了局部性所具有的三要素:定义、量化、应用,并基于这一框架总结了已被广泛应用的线程局部性和空间-线程局部性,在此基础上又提出了全新的同步局部性,其量化结果显示出巨大的应用潜力.
此外,对局部性的应用是实现高效访存依赖获取乃至并发程序动态分析的重要手段.
利用局部性实现高效访存依赖获取是本文主要技术贡献[78,79,80]的基石.
34第二章理论框架35第三章技术框架与相关工作综述近年来,来自体系结构、计算机系统、程序设计语言和软件工程等多个领域的研究者都对并发程序的动态分析技术进行了探讨.
然而,目前这些工作并非围绕"访存依赖"这一核心概念展开,缺乏统一的技术框架以系统性地总结和探讨现有技术的优势与不足,无法系统化地指导新的访存依赖相关技术的发展.
第2章提出的理论框架明确了访存依赖及其获取问题,并提出了并发程序共享内存访问的局部性理论.
在理论框架的指导下,我们已经具备了提出具有指导意义的技术框架的条件,其帮助我们系统性地理解了现有工作如何获取访存依赖、在哪些方面作出了权衡、实现了怎样的动态分析、解决了何种并发程序质量保障的挑战,从而指导我们更好地认识现有研究工作的不足和空白.
本章提出访存依赖相关研究的技术框架,该框架由三要素构成:评价指标、实现技术和技术应用.
这一技术框架成功地容纳了来自多个研究领域对访存依赖获取和应用的探讨,从更高层次上阐明了现有技术在各个方面作出的不同权衡及其原因,以全新的角度更好地认识现有技术的优势与不足,进而提出未来可行的研究方向.
第3.
1节首先讨论贯穿技术框架的访存依赖获取技术评价指标,然后对技术框架进行概述.
第3.
2节对获取访存依赖的两类技术:在线追踪(第3.
2.
1节)、离线合成(第3.
2.
2节)中的关键问题和解决手段进行综述;第3.
3节探讨两类并发程序的动态分析技术——轨迹分析(第3.
3.
1节)和并发控制(第3.
3.
2节)与访存依赖之间的关系.
最后,第3.
4节总结技术框架并讨论其中的研究契机.
3.
1技术框架概述针对访存依赖相关研究,我们提出包含三要素的技术框架:1.
四个评价指标:即时性、准确性、高效性和简化性.
即时性要求能在访存发生前即获得依赖;准确性要求获得的访存依赖能尽可能真实地反应实际程序执行的访存顺序;高效性要求其获取开销尽可能小;简化性要求获得的日志尽可能精简.
2.
两类现有访存依赖获取技术:在线追踪和离线合成.
在线追踪技术在程序运行时即时捕获访存依赖,而离线合成技术则通过记录间接信息,使用推导或搜索算法合成过去执行中的访存依赖.
36第三章技术框架与相关工作综述图3.
1技术框架的三要素:评价指标、技术、应用之间的关系.
3.
两类访存依赖的应用:轨迹分析和并发控制.
轨迹分析技术利用在线记录或离线合成的访存依赖实现测试、调试等功效;并发控制技术则依靠实时获得的访存依赖约束程序行为,以在运行时避免并发缺陷.
技术框架总结如图3.
1所示:获取访存依赖的技术在评价指标的指导下,对即时、准确、高效、简化四个特性进行权衡,并最终实现为高效的并发程序动态分析技术.
3.
1.
1访存依赖获取技术的评价指标我们首先对四个评价指标予以定义:1.
即时性反映是否在访存事件e发生前即获得与之相关的访存依赖.
即时性对实施运行时并发控制(如事务内存[120])是至关重要的,而轨迹分析类的应用(如测试、调试[84])则通常对即时性没有要求.
2.
准确性反映获取的d是否正确反映执行中的实际数据依赖.
获取完全准确访存依赖的代价通常是较高的,但在有些应用(如基于因果关系的数据竞争检测[55])中又是不可避免的;对于调试、执行重放类的应用,只要求获取一致的访存依赖(即对于一对冲突的访存事件eiej,eidej当且仅当eitotej),此时按d执行程序后每一线程的执行路径与tot相同(从而足以诊断轨迹中的缺陷),再次执行即可推导出准确的访存依赖;对性能极为敏感的应用[134]甚至允许与tot不一致.
3.
1技术框架概述37图3.
2访存依赖获取的两类技术:在线追踪、离线合成.
3.
高效性反映获取访存依赖时由于程序插装或修改并发系统导致的程序运行性能降低的程度.
在生产环境中,高效性至关重要,直接决定了一项技术能否在真实环境中部署.
即便测试、调试环境能一定程度容忍运行时开销,随着软件系统规模的增长、执行轨迹长度的增大,运行时开销也会逐渐成为动态分析技术的瓶颈[127].
4.
简化性反映访存依赖获取过程中所做的直接或间接记录的数量.
因访存依赖只需确定冲突事件e1e2发生的顺序,所以并不是唯一的.
即便对于同一个d也有多种等价的d表示.
访存依赖最终为并发程序的动态分析所使用,获取访存依赖所产生的日志记录数量会直接影响动态分析的性能.
若动态分析无需满足一致性的访存依赖,d和满足其需求的最简记录数量可相差数个数量级[72].
研究者已对运行时[105]或运行后[76]简化访存依赖作出了尝试,同时也证明了获取最简的访存依赖是NP-完全的[76].
尽管在理想情况下,我们希望能在访存事件发生前即获得准确或一致的访存依赖(即时、准确),同时不引起任何额外开销和记录(高效、简化),但现实中同时满足这些性质的技术是不存在的:获取即时、准确的访存依赖意味着需要更大的运行时开销和更多的依赖数量.
并发程序的动态分析技术通常需要根据应用场景的特点而对这些评价指标加以权衡.
3.
1.
2访存依赖获取的两类技术获取访存依赖的方法是插装程序(编译时插装[69]或二进制改写[22])或修改运行系统(虚拟机[28]或定制硬件[17]),以在程序执行时获得与其执行轨迹38第三章技术框架与相关工作综述相关的记录信息.
根据是否在访存事件发生前即得到其访存依赖,其获取技术主要分为直接获取(追踪)和间接获取(合成)两类(图3.
2).
概言之,在线追踪技术能即时得到准确或一致的访存依赖,但通常对运行系统需要作出较大修改,高效性和简化性不足;离线合成技术由于间接记录的灵活性,能够在高效、简化和合成代价之间进行权衡,但无法即时得到访存依赖.
访存依赖追踪技术直接在内存访问事件e发生前即得到e相关的访存依赖.
目前,这类工作均是通过对共享内存访问予以同步或互斥实现的:为共享变量x分配锁x,并用x保护所有对x的访问.
此时记录解锁和上锁之间的依赖关系,即能获得满足一致性的访存依赖.
这类访存依赖追踪技术实现简单、准确性容易保证,是最早被研究的一类技术[84],且已得到广泛应用.
然而,在程序运行时增加额外的同步操作是与共享内存并发程序设计初衷背道而驰的.
共享内存被定义为轻量级的线程间通信方式,线程访问共享内存无需任何同步操作,从而可最大程度利用多核处理器的并行计算资源.
而为了获取准确的访存依赖,信息更新(如时间戳更新)和共享内存读写需要封装为原子操作.
分布式理论已经证明,如需实现互斥,锁或与之等价的同步手段是无法避免的[15].
因而高效、简化地获取访存依赖是在线追踪技术的最大挑战.
为实现高效性和简化性,依赖追踪技术的两个关键问题是如何将变量指派到其对应的锁及如何实现锁机制降低其运行时开销.
锁的指派分为静态指派(在程序运行前确定指派方式,如按照硬件缓存线指派[129]、按对象指派[124]等)和动态指派(在运行时动态根据程序运行时的访存情况进行指派[127]).
锁可以借助定制硬件[129]、存储保护[52]实现,也可以使用软件实现,其中具有代表性的技术是利用共享内存访问局部性实现的偏向锁[28].
此外,静态线程逃逸分析[37]、数据竞争分析[125]等技术可以过滤不共享或无数据竞争的变量从而降低上锁的开销;获取的依赖可以通过离线方式实现简化[72,76].
由于这两类技术与访存依赖获取完全正交,本文不再赘述.
除在运行时追踪外,访存依赖的另一获取方法是在运行时记录间接信息,在程序结束(或运行到检查点)后根据间接记录予以离线合成.
间接获取法适用于事后分析型的应用,如调试[136]和轨迹预测分析[71].
由于不需在运行时立即得到依赖,依赖合成允许消耗更多计算资源甚至使用约束求解器,因而间接记录也更加灵活且通常更加高效和简化.
因此,合成访存依赖的核心问题是记录何种间接信息以权衡准确性、高效性、简化性和合成的时间开销.
如只记录少量框架性的信息,则合成d的代价极大或无法提供准确性保障,但因其开销小,适用于生产应用场景[136,109].
若在每个线程本地记录读写事件数值或执行路径(此记录无需额外线程间通信),3.
1技术框架概述39图3.
3访存依赖应用与评价指标之间的关系.
则可以使用约束求解器合成与tot在每个线程执行效果等价的d,但依赖合成是NP-完全问题.
若允许进一步增加记录信息的数量(同时记录的高效性和简化性降低),推导出的d能够提供保证重现等价执行的准确性[144].
3.
1.
3访存依赖的两类应用我们将访存依赖的应用分为两类:轨迹分析和并发控制.
为实现并发程序的测试、调试和质量保障,轨迹分析技术依托访存依赖对过往执行进行重放、诊断或缺陷预测,亦是众多并发程序测试技术的基础;并发控制技术则在开发者指导下或全自动地对程序运行时可能出现的缺陷予以规避.
访存依赖应用须根据其自身对访存依赖获取技术评价指标的需求选择或设计相应的技术(图3.
3).
轨迹分析技术在程序运行时或运行后对程序执行轨迹中的各类特征进行分析,以实现测试、调试等功能,是目前并发程序质量保障的主流技术和研究热点.
因共享内存是并发程序不确定性的主要来源,获取访存依赖便成为这类技术的核心组成部分.
为实现并发程序调试相关的缺陷诊断技术,首先需要保证能够重现并发程序的执行结果,其充分条件是记录满足一致性的d并严格按照d=tr(d∪po)的顺序执行程序[84].
在执行重放的基础上,我们还可以从执行轨迹中推断可能存在的并发缺陷(轨迹预测分析).
例如,未被同步操作约束的两个冲突访存事件即构成一个数据竞争[115,49],使用准确的d即可在运行时或运行后预40第三章技术框架与相关工作综述图3.
4访存依赖追踪技术的关键问题:指派变量对应的锁及高效地实现锁机制.
测此类缺陷.
基于同一执行轨迹,研究者还提出了其他定义两个操作是否存在因果顺序约束的因果性模型[118,122],并将该模型实现为预测能力更强的并发程序缺陷检测技术[71].
此外,执行轨迹中的访存依赖信息还能指导如原子性违反[95]等其他类型的缺陷发现,或为后续主动测试提供目标[116].
并发控制技术通过改变程序运行时的访存顺序,达到事务处理、缺陷避免、消除不确定性等功效.
并发控制技术实现的关键是在访存发生前即获得依赖信息(此时必须使用在线访存依赖追踪技术),从而对访存顺序进行调控(如检测到冲突事务时进行回滚).
由于并发控制技术往往运行在生产环境中且要求在线获取一致的访存依赖,因而是最具挑战性的一类技术.
并发控制为开发者提供系统级的支持,以提高并发软件的质量、减少并发缺陷.
软件/硬件事务内存相关研究近年来已取得一定的进展[50,60],Intel已开始尝试在商业处理器中集成事务支持并在一些应用场景中取得了显著的性能提升[133];为进一步避免并发缺陷的发生,系统还可以主动对程序行为在运行时予以修正,例如TXRace[137]技术将基本块构成的极大无环子图作为事务处理,从而避免了有害数据竞争导致的并发缺陷.
消灭并发缺陷的终极目标是将具有不确定性的并发程序确定化,又称确定多线程(deterministicmulti-threading)技术[45,40]——采取确定的规则对系统内的共享资源进行调度,从而尽可能降低不确定性带来并发错误的可能.
3.
2获取访存依赖的技术3.
2.
1在线追踪为在运行时即时、准确地获得访存依赖,最直接的手段是为每一共享变量x分配其对应的锁x并用lock(x)和unlock(x)包裹所有对x的读/写操作.
记录每个锁上锁、解锁之间的依赖关系所得的d保证能推导出tot中的所有数据依赖.
注意此处的锁不仅仅局限于互斥锁.
广义来说,任何实现同步和互3.
2获取访存依赖的技术41斥的机制都能作为锁在访存依赖中实现.
追踪访存依赖的关键问题是锁的指派(即如何进行变量到锁的映射)以及锁的实现(即如何实现互斥),如图3.
4所示.
锁的指派和实现决定了访存依赖获取技术的准确性、高效性和简化性.
3.
2.
1.
1锁的指派锁的指派指定共享内存变量x对应的锁x.
为每个变量分配其单独的锁(变量指派)能够获得准确的d.
然而,变量锁的开销通常是较大的.
若实现在硬件层面,将大幅增加电路实现的复杂性;若使用软件实现,则不仅增加了大量的锁操作,还可能降低缓存的使用率而大幅降低高效性.
解决此问题的途径是进行锁的指派,即将多个变量指派到同一个锁.
锁指派不仅能减少锁的数量以更好地利用现有硬件和访存局部性(并发程序共享内存访问的线程、空间-线程和同步局部性已在第2.
2节证实),还能将同时具有线程和空间局部性的访存事件作为一个单元事件,在准确性(使用锁指派获取访存依赖仍满足一致性)和高效性/简化性(使用锁指派能减少元数据维护的开销和访存依赖数量)之间进行权衡[28].
静态指派的一类代表方式是将地址空间上连续的变量指派为同一锁,以实现空间-线程局部性的利用.
在硬件实现的锁中,最常见的指派方式是将同一硬件缓存线指派为同一锁(缓存指派)[13,67,96,100,101,129].
在此基础上可以借助(或扩展)缓存一致性协议实现同步和依赖检测,且依赖信息可以在缓存一致性协议中捎带.
软件实现的锁从实现简便的角度可在静态时将连续的内存地址指派为同一锁(区间指派),Dunlap等人提出按虚拟内存页进行指派[52],或根据静态时的访问名称进行指派[69,144],但也存在其他指派方式.
在面向对象程序设计语言中,同一对象内变量的并发访问模式通常是类似的.
文献[124]最早提出了按对象粒度进行依赖追踪,即将同一对象内的内存指派为同一锁.
对象指派在面向对象程序设计语言中被广泛采纳[28,132].
锁也可以在运行时动态指派.
Ceze等人基于硬件的锁实现[31,32]将连续的内存访问打包,使用Bloomfilter近似地确定其读/写变量的集合,并借助电路实现的Bloomfilter操作进行锁的互斥性检测.
在软件实现中,由于数据竞争检测问题需要得到准确的d而必须使用变量指派[53,55],这带来较大的运行时开销.
在此领域中诞生了一些动态指派的工作用于提高数据竞争检测的高效性.
若使用对象指派检测对象之间的数据竞争,虽能提高高效性但存在误报风险[124].
因此Yu等人提出使用对象指派检测潜在数据竞争,并据此把有潜在数据竞争的对象切换为变量指派,以实现高效性和准确性之间的权衡[134].
考虑到准确依赖追踪的开销主要来自数组访问,Wilcox等人提出对数组访问的模42第三章技术框架与相关工作综述式进行提取,对若干常见的数组访问模式中的锁进行合并,从而提高数据竞争检测的效率[127].
锁指派的另一个研究方向是用尽可能少的锁保护若干条而非一条指令.
由于必须在指令执行前即持有正确的锁,此类工作是由静态分析实现的.
Cherem等人对这类指派问题以及锁的正确性进行了形式化,归纳总结了静态锁类型、锁组合的正确语义,并用此框架实现了基于抽象对象锁和读-写锁组合的高效事务支持[36].
Lee等人进一步结合了静态和动态数据竞争分析的信息,针对不同抽象变量的访问特点分别使用函数锁、基本块锁或循环锁,使之能够高效地获取访存依赖[85].
3.
2.
1.
2锁的实现缓存一致性协议为硬件访存依赖技术提供了自然的上锁机制,因此此类技术上锁带来的时间开销通常不是其可用性的关键问题[35].
但由于系统缓存一致性事件发生频繁,短时间内即产生大量依赖,因此研究工作的核心关注在如何在不大幅改变系统实现的前提下减少依赖的数量.
Xu等人提出在不违背tot的前提下对记录的偏序进行调整,删除冗余的依赖[129,130];Ceze等人提出记录指令块依赖以实现记录精简[32,31].
Chen等人提出在上锁的同时增加和记录额外的全局时钟信息能快速筛除在全局时钟意义下已排序的事件,从而实现大幅的记录简化[34].
锁还可以借助存储访问控制机制实现.
Dunlap等人提出使用分页保护机制实现写者在内存页级的互斥,通过在有访存依赖发生时触发缺页异常而实施记录[52].
这类似于按逻辑页进行变量指派,并使用读-写锁予以保护.
这一技术也应用在并发控制技术中[21,92,20].
在不借助定制硬件的前提下,追踪访存依赖需要插装程序或修改运行系统,使用锁保持访存和依赖获取的原子性.
由锁保护临界区通常只需少量机器指令,而互斥的开销是影响高效性的首要因素,而高效性又直接关系到访存依赖获取技术的实用性.
Patil等人提出直接将基于硬件的访存依赖获取技术[129]使用二进制改写在软件层次实现[110],但这一做法在很多应用中都表现出巨大的运行时开销.
偏向锁技术[113]假设不同线程访问同一锁的频率不同,且"偏向"频繁持有锁的线程以提高其性能.
在访存依赖追踪技术中,类似的偏向设计也成为决定其是否高效的重要因素.
例如Chen等人提出偏向读操作,在写共享内存时使用互斥锁并在临界区中用原子操作更新版本号,而在读操作时使用读版本号的方式降低开销[33].
Bond等人利用线程局部性设计乐观锁[28],其基本假设3.
2获取访存依赖的技术43图3.
5访存依赖合成技术的关键问题:权衡高效性/简化性与合成代价.
是同一变量的连续访问通常发生在同一线程.
因此在线程获得对象锁完成访存后乐观地认为下次访问仍然发生在同一线程,并不立即释放该锁,而是在虚拟机安全点检查到有等待该锁的线程时释放.
这一技术能大幅提高线程局部性强之应用的访存依赖追踪高效性,但在依赖产生频繁的应用中会造成较大的性能问题.
因此该技术的扩展[30]实现了在乐观锁和朴素锁之间的自适应切换(根据访问模式切换锁的实现).
由于锁机制导致额外的同步操作,通常依赖追踪算法都会改变程序的内存模型.
大部分访存依赖追踪技术在对运行系统修改后保证了程序执行满足顺序一致性[69,28,32,31].
另一方面,一些技术则刻意放松了内存模型(以软件模拟的局部写缓存为代表[46])以实现高效的依赖获取.
基于硬件定制的技术能够捕获硬件底层乱序执行、写缓存、总线事务等行为,从而记录松弛内存系统上的并发程序行为[34,130,67,101,66].
3.
2.
2离线合成相比追踪技术在运行时即得到访存依赖,合成技术在运行时实施间接记录,在执行结束后对记录进行分析并恢复执行中的访存依赖.
这类技术放弃了访存依赖追踪的即时性,因而记录通常更高效、更简化,同时也意味着合成访存依赖的时间复杂度较高且记录之信息可能不足以合成一致的依赖.
原则上说,只要有极少量的信息(如程序崩溃的现场信息[136]),就能通过搜索的方式合成出用于重现并发缺陷的执行.
记录更多信息会降低合成算法的时间复杂性,同时也降低记录的高效性和简化性.
因此,访存依赖合成技术的关键问题是记录何种信息以实现记录的高效性/简化性与合成的准确性/高效性之间的权衡(图3.
5).
44第三章技术框架与相关工作综述3.
2.
2.
1框架合成框架合成技术放弃准确性,只记录运行时的框架信息,实现记录高效性和简化性的同时牺牲合成的准确性和高效性.
Zamfir等人提出在仅有程序崩溃现场(核心转储)的情况下,对程序的路径、调度予以启发式搜索,从而生成一个满足崩溃现场的执行[136].
由于在程序执行过程中完全没有实施记录,恢复tot是不可能的,但搜索算法在理论上保证能返回一个与tot执行产生同样错误的执行轨迹(如复现原执行中最后一条引发错误的指令),以达到调试的目的.
通过记录对错误重现有重大意义的信息(如Park等人提出记录程序中的同步顺序[109];Altekar等人提出记录程序的输出[12])并约束生成的访存依赖满足所记录的信息且以这些信息制导搜索,则能有效地减少搜索空间、降低依赖合成的代价.
3.
2.
2.
2数值/路径合成数值/路径合成的思想是在线程本地实施记录,然后根据本地记录生成全局合法的d.
虽然d可能不完全准确地反应tot中事件执行的顺序,但合成得到的d保证每个线程执行与tot相同的路径,从而可保证并发程序行为(输出、错误)的重现.
数值合成的优势是记录发生在线程本地而不需锁、原子操作等同步操作.
数值合成在线程本地记录每一访存事件ei访问的变量ei.
x以及相应读/写操作的值ei.
v.
Netzer等人证明了若所有写操作的ei.
v均不同,则存在一个O(nlogn)的算法推导出d(n为总事件数量)[106];但若允许写入相同值,则满足条件的d不唯一且合成的时间复杂性是NP-完全的[57].
为了应对合成大型记录的复杂性,Lee等人借助硬件实现的全局同步点将依赖合成问题限制在一段执行窗口中,以减小问题的规模[87,103].
在窗口内为每个访存事件ei建立变量Oi代表其序号,则po的约束可用OiOj)表示,最后使用SMT求解器求解使所有读事件均有其对应写者的约束可满足性问题即可合成d.
除了考虑执行轨迹中的访存操作外,Huang等人提出在线程执行到if(xtk)gotoij指令时记录条件判断的真/假值,以得到高度可压缩的记录[74].
这一记录可以用于确定每一线程唯一的执行路径(从而推导出每一线程的访存事件).
通过在文献[87]提出的约束可满足性问题的基础上增加符号化的变量数值和路3.
3访存依赖的应用45径条件约束,求解约束问题即可合成访存依赖.
这类合成技术需要求解复杂的约束可满足性问题.
由于现实程序具有各类局部性,通过记录一定的额外信息,能起到简化约束的效果.
例如Yuan等人提出在访存时记录处理器的本地时钟,并根据此信息推断出具有物理时间先后关系的访存事件以删除冗余的约束,提高约束求解的效率[135].
由于数值/路径合成的记录完全存放于线程本地,因而其对运行系统的修改通常不会对内存模型造成影响.
所以在对访存语义进行适当建模后能实现松弛内存模型意义上的重放.
例如Lee等人扩展了文献[103]的建模方式以适用于TSO内存模型[86];另一文献[74]提出的技术则能生成在PSO内存模型下的访存事件调度.
3.
2.
2.
3依赖合成依赖合成意味着我们可以在运行时记录访存依赖的一个子集,再通过合成的方式求解未记录的依赖.
例如,按照两个访存事件的先后关系,访存依赖的类型可分为写后读、写后写和读后写依赖.
在偏向锁的设计中,写后读和写后写依赖通常可以较小的开销得到,而记录读后写依赖的代价则可能超过其他二者之和[28].
在依赖合成中,写后读和写后写依赖可以推导出读后写依赖.
因此Zhou等人提出了使用写后写依赖和读值合成写后读、读后写依赖的技术,能够在多项式时间内实现d的合成[144].
Liu等人进一步证明了即使在运行时只记录写后读依赖,也可保证合成d复现每个线程的行为.
其核心思想是丢弃那些未产生依赖的写操作[90],然后使用类似于文献[87]的技术构造约束进行求解,并且隐式地使用了同步局部性进行优化.
3.
3访存依赖的应用3.
3.
1轨迹分析访存依赖反映了程序运行时访问共享内存的顺序,亦包涵了程序执行中不确定性事件的因果关系.
轨迹分析技术即从执行轨迹中提取信息,实现并发程序的测试、调试等质量保障方面的技术.
一般而言,轨迹分析技术需要完全准确或一致的访存依赖以正确地恢复执行轨迹、检出并发缺陷.
3.
3.
1.
1执行重放轨迹分析最基础的应用是重现过往并发程序的执行.
通常,在开发、测试环境下实施依赖获取能复现执行并予以单步调试:要求获得满足一致性的访存46第三章技术框架与相关工作综述依赖d,再次执行同一程序,在外部输入相同(通常可以实施记录)的假设下,能保证重现tot所对应每一线程的执行路径和输出,从而保证能够观测到与之前执行相同的结果.
这类应用对准确性的要求较高,而高效性和简化性只要满足应用需求即可,可以使用依赖追踪或依赖合成技术实现[52,69,144].
最后,由于对运行系统的修改不可避免会改变程序的语义(如增加额外的同步操作),而导致部分缺陷在获取依赖的过程中被隐藏,这一问题的终极解决方案是对硬件加以对程序语义无任何干扰的修改(如借助缓存一致性协议[129]).
目前Honarmand等人已经提出了硬件级松弛内存模型实现下执行重放的技术框架和实现[66].
执行重放的另一应用场景是生产系统缺陷的复现.
在这一场景中,获取一致的访存依赖带来的开销通常是难以接受的.
此时依赖合成技术[136,109,12]可以较少的运行时开销帮助开发者复现生产环境中的并发缺陷.
3.
3.
1.
2轨迹预测分析有时,记录的执行轨迹可能没有产生错误,但若对其稍作修改,则可能暴露其中的并发缺陷.
轨迹预测分析即为这类技术,分析由访存依赖确定的执行轨迹,以预测潜在的并发缺陷.
数据竞争检测是访存依赖的一类直接应用.
定义数据竞争为eiej且ei和ej之间没有发生任何直接或间接的同步操作.
数据竞争是多种并发缺陷的诱因[94],应为开发者所尽力避免.
比较两个事件在同步意义下的因果关系即可实现数据竞争预测分析.
由于数据竞争检测需要完全准确的访存依赖,即确定每一个访存事件e的数据依赖,因而其记录难以实现高效、简化.
长久以来,这类预测分析都带来较大的运行时开销.
Flanagan等人提出了一个时钟维护方法,大大降低了开销[55]并被广泛使用[25].
Wilcox等人在其基础上提升了数组访问的高效性[127],Yu等人则使用动态锁指派,在检测到对象级数据竞争后才切换到变量指派,通过检测准确的数据竞争而提升高效性[134].
这些技术的发展也代表了访存依赖获取技术的进步.
上述的数据竞争定义在happens-before[82]模型上.
但这一模型只是ei和ej之间实际因果性的一个近似[122].
基于因果性的定义,研究者提出了在没有程序语义情况下仅观察访存事件所能推断出的最大因果模型[118]及基于此的预测分析算法[71].
Huang等人则提出将一般性的缺陷模式(资源竞争、原子性违反、并发迭代器、空指针引用等)编码为轨迹上的性质,使用约束求解器找出轨迹中的并发缺陷[70].
3.
3访存依赖的应用47这些基于访存依赖的动态分析技术不仅能检测数据竞争,还能检测原子性违反[73,95]、假共享[91]等并发缺陷,在并发程序质量保障方面起到了卓著的成效,但因其具体技术超出本文的讨论范围而不再叙述.
3.
3.
1.
3轨迹的其他应用一次执行轨迹分析的结果也能为更复杂的并发程序测试和分析技术提供指导.
Sen等人分析轨迹中可能的数据竞争点,再使用FuzzTesting技术予以确认[116];无状态模型检验技术[102,108]通过反转执行轨迹中的依赖实现状态空间的遍历;Cai等人提出通过启发式地反转多个依赖实现高效的数据竞争检测[29];Lee等人提出利用轨迹信息决定静态变量应当指派的锁[85].
3.
3.
2并发控制除测试、调试类的支持外,访存依赖还可用于在运行时调整并发程序行为,从而实现并发缺陷的避免.
此类技术可实现为编程语言的扩展以供开发者在编程时使用(如事务内存),也可直接在运行时系统上实现(如数据竞争避免、确定多线程).
由于并发控制技术通常用于生产系统,其主要挑战便成为高效地在运行时获取准确或一致的访存依赖.
3.
3.
2.
1事务内存事务内存允许开发者使用atomic关键字包裹一段需要实现原子性的程序代码,并由运行时系统保证这段代码的原子性(即满足可序列化[60]).
事务内存既可在硬件实现,也可使用软件实现,而其实现的两个关键问题是冲突检测和冲突化解.
事务冲突定义为并发事务中存在两个访存事件访问同一地址且至少有一个是写,因此冲突检测等价于运行时访存依赖的追踪.
访存依赖追踪技术的两个关键技术(锁指派、锁实现)也可以用于理解事务内存技术.
Dice等人总结了事务内存的设计空间[47],其中包含锁的指派(文献中讨论了静态的对象指派、缓存线指派、区间指派等)和锁的设计(主要讨论了基于版本的锁)等关键技术,这和访存依赖追踪技术是十分类似的.
Dice等人还提出使用变量指派与用位压缩存储字节数组实现的偏向锁,大幅提高了读操作的性能[48];Dalessandro等人提出将所有变量指派为同一锁,从而能实现最简的冲突检测和解决[43];Zhang等人提出基于偏向锁[28]实现的事务内存,使用了面向对象语言中常用的对象指派和偏向锁实现冲突检测[137].
48第三章技术框架与相关工作综述3.
3.
2.
2数据竞争避免数据竞争带来并发缺陷的主要原因是竞争的写操作破坏了其他线程的原子性.
因此,避免数据竞争所致并发缺陷的一类方法是修改运行时系统的语义,将一个连续区域中的指令作为事务处理以保证其原子性,从而降低并发缺陷发生的概率.
为避免数据竞争及其引发的其他后果,Berger等人提出使用分页保护技术实现页面指派[21]并建立了松弛内存模型系统,使竞争写操作发生在线程本地而不会破坏其他线程的原子性.
Sengupta等人提出通过扩展事务内存技术,在静态时对程序进行插装,将控制流图中不包含同步操作、方法调用和回边的极大区域包裹为事务,以避免数据竞争[117].
另一种避免数据竞争有害后果的方式是修改运行时系统,在数据竞争发生时抛出异常.
Lucia等人提出通过定制硬件修改内存模型隔离数据竞争,并在同步操作时予以竞争检测,在数据竞争发生时抛出异常[96].
这类数据竞争检测技术需要准确的访存依赖,因此纯软件实现的开销对于生产系统来说是难以接受的.
鉴于数据竞争检测的开销主要来自读后写依赖的追踪,Biswas等人提出在线程本地维护读事件的列表,将这类竞争的检测延迟到同步区域结束,从而实现高效的区域冲突检测(仅能检出区域间的读后写数据竞争)[25].
3.
3.
2.
3确定多线程鉴于并发缺陷的主要诱因是执行的不确定性,确定多线程试图从根本上消除不确定性,使并发程序在相同的输入上表现出相同的行为,以降低并发程序测试、调试的难度,并在运行时避免并发缺陷的发生.
在线追踪访存依赖亦是确定多线程技术的基石.
Devietti等人提出在线程之间以确定性的方式传递令牌,通过缓存一致性协议捕获访存依赖,并在其发生时等待令牌,以此实现系统的确定化[45].
Bergan等人扩展文献[21]的技术将写操作缓存在本地从而减少访存依赖的数量,在实现确定多线程的同时减少等待令牌的时间[19].
另一类工作[46,92,20]则利用存储保护机制以页面粒度实施锁的指派来实现确定化.
Cui等人提出事先记录程序执行轨迹,使程序即使在输入不同的情况下也尽最大可能复用已有轨迹中的调度,从而降低可能导致出错的调度(如数据竞争和原子性违反)的概率,实现并发缺陷的避免[42,41].
在此基础上对同步操作使用令牌传递机制,则可同时实现确定多线程和并发错误避免[40].
3.
4研究契机493.
4研究契机本章提出的技术框架以"访存依赖获取"为主线,综述了来自计算机体系结构、计算机系统、程序设计语言和软件工程四个领域的研究工作,探讨了访存依赖获取技术在即时性、准确性、高效性和简化性四个方面作出的权衡,并且研究了现有基于访存依赖的并发程序动态分析技术.
在这一过程中,我们发现已有技术的研究思路通常是从具体的动态分析技术出发,在一个特定的问题空间中设计访存依赖获取的技术,其视角具有局限性.
只有少量工作认识到访存依赖获取问题的重要性并予以单独研究[28].
即便如此,其研究也缺乏系统性.
回顾我们已经完成的访存依赖获取问题的理论框架,其中既包含对问题的形式化定义,也包含并发程序对共享内存访问的局部性理论.
我们以这一理论框架为指导,在技术框架中发现如下研究契机:1.
现有访存依赖获取技术对现实中并发程序所具有的性质利用不足.
特别地,虽然有一些工作使用了现实并发程序所具有的局部性[28,144],但因缺乏系统化的局部性理论指导,其对局部性的利用是较为初步的(仅利用了一些比较明显易用的性质,例如具有线程局部性的读操作占绝大部分).
2.
在技术框架中,我们发现访存依赖虽在并发程序动态分析中得到广泛应用,但相关的技术仍有不足之处,需通过新技术实现更高效/更有效的动态分析.
此外,由于软件产业的增长,社会对软件可靠性提出日益增长的需求,新兴类型软件(如移动应用)的质量保障仍然未能有效实现,存在研究契机.
技术框架正能指导我们系统性地总结现有工作、解决在新型应用场景中遇到的新问题.
3.
纵观二十多年来对访存依赖获取问题的研究,我们发现尚未有人能在不引入额外同步的前提下、在多项式时间内获取访存依赖.
已有的研究表明,只通过线程本地的记录实现访存依赖合成是NP-完全问题[57];只通过读/写实现互斥则是不可能的[15].
在这两个结论的基础上可能引发对访存依赖获取复杂性的深入探讨.
我们分别对这三点展开了研究.
鉴于目前访存依赖获取技术对局部性利用不足的局限,我们在第4章提出基于局部性理论的高效访存依赖获取技术:基于乐观锁的访存依赖追踪和基于二分组协议的访存依赖约减.
针对技术框架中动态分析技术方面存在的空白,我们在第5章提出多种基于访存依赖的动态分析技术——基于缓存的执行重放、基于二分组协议的动态分析、崩溃一致性的自动检测、移动应用的并发缺陷暴露,以实现软件质量保障.
针对缺乏访存依赖获取问题理论探讨的研究现状,我们在第6章提出"没有免费午餐"猜想:在50第三章技术框架与相关工作综述仅对程序进行wait-free修改且对读/写事件的记录限于线程本地的前提下,获取满足顺序一致性的访存依赖是NP-完全问题.
我们对这一猜想的两个特殊情形提出了证明,并探讨了这些理论结果对未来工作的启示.
51第四章高效的访存依赖获取基于第2.
2节提出的局部性理论,并发程序的共享内存访问具有线程局部性和空间-线程局部性的特征:在一段时间内,在同一线程内对同一变量(或一段地址空间上的连续变量)的连续访问倾向于具有相同的线程间数据依赖.
根据对第3章中技术框架的进一步总结,我们发现已有的访存依赖获取技术对并发程序共享内存访问的局部性利用不足.
因此,本章介绍我们设计、实现的利用并发程序共享内存访问局部性的高效访存依赖获取技术:1.
基于并发程序具有的线程局部性,我们提出一种O(1)wait-free的算法用于检测读操作是否满足线程局部性,称之为"乐观锁"技术.
这一检测技术仅会漏报而不会误报实际具有线程局部性的事件,因而能高效地过滤具有线程局部性的访存事件,同时保证获得一致的访存依赖.
第4.
1节描述基于乐观锁的访存依赖追踪技术,包括问题定义与解决思路(第4.
1.
1节)、利用线程局部性实现的访存依赖追踪算法(第4.
1.
2节)与在顺序一致性内存模型和松弛内存模型上的正确性讨论(第4.
1.
3节).
2.
基于并发程序具有的空间-线程局部性,我们提出二分组协议在运行时动态维护满足空间-线程局部性的地址空间划分,并在空间-线程局部性被违反时对划分进行调整,以实现空间-线程局部性的利用,而在得到一致访存依赖的前提下,实现访存依赖记录数量的大幅减少.
第4.
2节描述基于二分组协议的访存依赖约减,包括问题定义与解决思路(第4.
2.
1节)、二分组协议的基本原理和协议描述(第4.
2.
2节).
最后,我们在LLVM工具上实现了乐观锁技术,并在此基础上实现了二分组协议,将其用于C/C++程序的在线访存依赖追踪,并使用来自桌面计算、科学计算和服务器的程序对其性能进行评估.
详细的系统实现和实验评估描述将在第4.
3节予以展示.
4.
1基于乐观锁的访存依赖追踪4.
1.
1问题定义与解决思路问题定义.
在技术框架中,我们已经认识到在共享内存访问事件发生前即时获得较为准确(满足一致性)的访存依赖是众多并发程序动态分析的基础[28].
这类具有即时性和准确性的访存依赖在线追踪技术需要使用锁对共享内存访问进行包裹,因而满足高效性(较少的运行时开销)就成为一项非常具有挑战性的工52第四章高效的访存依赖获取作.
朴素的算法在访问共享内存变量x时使用互斥锁保证访存事件和数据更新的原子性,但由于这一处理串行化了所有对x的访问(在现代多处理器系统中,多个处理器核心可以同时读取同一共享变量),会造成较大的运行时开销,拖慢并发程序的执行.
为了实现即时、准确、高效的在线访存依赖追踪,我们希望保证临界区原子性的lock(x)/unlock(x)操作能够尽可能地高效.
虽然分布式理论表明,使用共享内存读/写操作在wait-free的前提下实现互斥是不可能的[15],但我们仍然能够利用并发程序实际执行所具有的特征(如局部性)来减少锁操作在大部分情况下的开销.
一类有代表性的高效访存依赖获取技术使用乐观锁[28]利用并发程序的线程局部性以减少访存依赖追踪的运行时开销.
线程局部性表明,在一段时间内,对同一变量的访问要么被某一线程独占,要么被多个线程以只读的方式共享.
因此,如果我们能有效地识别出这些情况(如只使用O(1)的时间开销并不引入额外的同步),并根据绝大部分共享内存访问具有局部性的事实,就能大幅提高访存依赖获取的效率.
乐观锁技术最早被用于实现共享内存多处理器中的缓存一致性[107].
MESI或类似的协议在现代共享内存多处理器系统中被广泛应用:对于线程独占的缓存线,它们均处于M(Modified)或E(Exclusive)状态因而并不引发处理器间的通信;处于S(Shared)状态的缓存线可以在多个处理器间共享数据;仅当产生处理器间数据依赖时才在处理器间进行总线通信.
类似地,Octet[28]在软件上实现了类似的协议:当线程获得对于共享变量x的互斥锁x后并不立即释放,而是在另一线程需要对x上锁时才对持有锁的线程发出请求,在持有锁的线程运行到虚拟机安全点(VMSafePoint)时检查请求并释放锁.
然而,这类技术在共享内存访问不满足线程局部性时将带来巨大的开销[30],且需要虚拟机安全点的支持,具有一定实用上的缺陷.
本节讨论如何对并发程序的线程局部性加以利用,以实现即时、准确(满足一致性)、高效的访存依赖在线追踪.
解决思路.
本节实现的高效访存依赖在线追踪算法基于如下两点观察:1.
对共享内存的读操作可以多次进行,且取任意一次的结果作为实际读取的数值,都不破坏程序的语义.
换言之,对于共享变量x的读指令xtk=R(x),我们在其前后插入若干对共享变量x的读取指令,只要其不改变线程局部变量Xt的状态,就不会改变程序的状态、执行路径和输出结果.
4.
1基于乐观锁的访存依赖追踪531rx←rx[t→er];2er:xtk=R(x);3ifthread_locality_test(er)then4lock(x);//er可能不满足线程局部性5begin6e′r:xtk=R(x);//在临界区中再次读取x7ew←wx;8rx←rx[t→er];9unlock(x);10thread_locality_update(ew);//更新用于线程局部性测试的状态11记录访存依赖eww→rer;图4.
1乐观锁对读指令作出的修改,下划线为被修改的读指令.
2.
具有线程局部性的读事件占并发程序共享内存访问的绝大部分.
这是由于(1)并发程序的共享内存访问具有线程局部性;(2)现实并发程序执行轨迹中的读事件通常远远多于写事件.
基于这两点观察,我们设计乐观的锁机制,对读和写操作分别处理,通过避免对具有线程局部性的读操作使用同步操作,以达到高效访存依赖追踪的目的:1.
对于共享变量x的写操作,我们使用互斥锁x进行保护,并对访存依赖予以记录.
由于写操作只占共享内存访问中的少部分,这一处理的开销通常在可以接受的范围内[144].
2.
对于共享变量x的读操作,我们首先执行这一读操作,并对读操作是否具有线程局部性进行快速检测.
由于大部分读操作均具有线程局部性,检测通过则意味着无需记录访存依赖.
若检测不通过,根据我们可以多次读同一变量而不破坏程序语义的性质,我们使用互斥锁x包裹对x的再次读操作,并于互斥锁的保护下获取满足一致性的访存依赖.
因此,实现这一技术的主要挑战是实现一个只会引起单向错误的事件线程局部性检测:若检测认为读事件er具有线程局部性,则这一结果一定是准确的;反之,若检测认为er不具有线程局部性,其仍然有可能是一个具有线程局部性的读事件.
同时,这一检测应满足能在O(1)时间内完成,并不使用任何同步/原子操作.
54第四章高效的访存依赖获取1lock(x);2begin3e′w←wx;wx←ew;4ew:W(x,xtk);5r←rx;rx←;6unlock(x);7thread_locality_update(ew);8ifew.
t=e′w.
tthen9记录访存依赖e′ww→wew;10fort∈Tdo11ifr(t)=⊥then12记录访存依赖err→wew;图4.
2乐观锁对写指令作出的修改,下划线为被修改的写指令.
4.
1.
2基于乐观锁的访存依赖追踪为了实现访存依赖的追踪,乐观锁技术在运行时为每一共享变量x维护以下数据结构:1.
最近一次对共享变量x的写入事件wx(wx可用线程号和线程本地的时间戳表示).
虽然在算法描述中我们为表述明确令wx=W(t,x,v),但实际实现时只需在wx中记录写入x时的时间戳和写入的线程号,即可实现访存依赖的追踪.
2.
在最近一次对共享变量x的写入事件之后、当前事件之前发生的读事件集合rx.
对于发生在同一个线程的多个对x的读取事件,我们只需要保留其中发生时间最晚(由于这些事件发生在同一线程,因此po决定了它们发生的先后顺序)的读事件即可获得满足一致性的访存依赖.
因此,rx是T→E的映射,rx(t)为t最后读取x的事件(初始映射r0=满足t.
r0(t)=⊥).
我们暂时假设对wx和rx的操作(映射的更新和重置)能够原子地完成,并在算法描述之后讨论如何对这些操作进行高效、无锁的实现.
为实现访存依赖追踪,我们对读/写共享内存变量x的指令进行修改(通过程序插装实现),分别如图4.
1/图4.
2所示:1.
对于读事件er:R(t,x,v),我们在执行读操作前首先更新rx,使得与er相关的读后写依赖能被后续的写指令正确捕获(rx←rx[t→er]更新t所对4.
1基于乐观锁的访存依赖追踪551Functionthread_locality_test(er)2begin3ew←wx;4ifCt(er.
x)=ewthen5returnTrue;6returnFalse;7Functionthread_locality_update(e)8begin9Ct(e.
x)←e;图4.
3检测读事件e是否具有线程局部性的算法.
应的映射值rx(t)=er),在rx更新完毕后,才实际执行读操作.
读操作执行完毕后,调用thread_locality_test对线程局部性进行检查.
仅当无法确定er具有线程局部性时,才在锁x保护下再次对共享变量x进行读取,以本次读取的数值替代第一次读取的数值(第6行),并得到写后读依赖.
2.
对于写事件ew:W(t,x,v),我们使用互斥锁x对其进行保护,在临界区中完成rx,wx的更新和写后写、读后写依赖的获取.
对于记录的一条访存依赖eidej中ei和ej的读/写类型,我们可以将d分为写后写(write-after-write)依赖w→w、写后读(read-after-write)依赖w→r和读后写(write-after-read)依赖r→w三种类型.
根据图4.
1和图4.
2中的算法描述,易见这一划分是完备的:d=w→w∪w→r∪r→w.
下文我们根据访存依赖的类型分别讨论其获取方法.
追踪写后写依赖w→w.
若对x的连续两次共享内存写事件ew1totew2(ew1.
rw=ew2.
rw=w,ew1.
x=ew2.
x且不存在其他对x的写事件e满足ew1totetotew2)发生在不同线程(ew1.
t=ew2.
t),则它们满足冲突事件的定义(ew1ew2),因此它们之间的依赖必须被记录.
图4.
2第2–5行的临界区串行化了所有对x的写指令(第4行).
相应的写事件ew1在临界区中赋值给wx(第3行),因此能保证在ew2发生时,执行到算法第3行的e′w←wx时读出ew1(即e′w=ew1).
由于ew1.
t=ew2.
t,第8行的判断必定为False,从而记录ew1dew2.
追踪写后读依赖w→r.
为了实现写后读依赖的追踪,我们使用图4.
3中的算法在对x的读操作之后对其是否具有线程局部性进行检查.
若共享内存的读事56第四章高效的访存依赖获取件er(图4.
1第2行)具有线程局部性,考虑在tot中距er最近的一次写事件ew(ewtoter,ew.
rw=w,ew.
x=er.
x且不存在其他向x的写事件e满足ewtotetoter),则以下二者之一必然成立:1.
ew与er发生在同一线程,即ew.
t=er.
t,因此er仅包含线程本地的数据依赖,写后读依赖eww→rer能被po推出从而无需记录;或2.
存在与er发生在同一线程的读事件e′r(e′rpoer,e′r.
rw=r,e′r.
x=er.
x),且其发生在ew之后,即ewtote′rtoter.
在此情况下该线程在过去已经进行过对x的读操作(因此er.
v=e′r.
v),写后读依赖eww→rer能被ewtote′rpoer推出,因此也无需记录.
为了检出这两种情况,我们在每一线程t维护映射Ct,Ct(x)为线程t对共享变量x已知的最晚写事件.
在每次线程t写入x时(图4.
2第7行)或产生一次不具有线程局部性的读事件时(图4.
1第10行),我们都调用thread_locality_update对这一数值进行更新.
我们在检测读事件e是否具有线程局部性时没有使用任何同步操作.
为了保证访存依赖追踪的正确性,我们巧妙地设置内存访问的顺序以确保thread_locality_test不会将实际不具有线程局部性的事件判定为通过:1.
在执行写操作时,我们首先更新元数据wx(图4.
2第3行,对应事件为W(wx)1),再写入x的数值(图4.
2第4行,对应事件为W(x)),因此W(wx)poW(x);2.
在执行读操作时,我们首先读出x的数值(图4.
1第2行,对应事件为R(x)),再读出wx(图4.
3第3行,对应事件为R(wx)),并与线程本地记录的事件Ct(x)进行比较.
因此R(x)poR(wx).
对于一个不具有线程局部性的读事件er和写入er.
v数值的写事件ew满足ewtoter,即W(x)totR(x).
根据偏序关系的传递性,这些事件的顺序被确定为:W(wx)poW(x)totR(x)poR(wx).
换言之,在ew发生前,对wx的更新就已经发生了.
因此,在er之后发生的对wx的读取保证获得与线程本地缓存的Cer.
t(x)不同的值(由每次向wx写入不同的值保证).
至此,我们实现了O(1)不使用任何同步操作或原子操作的读事件线程局部性检测.
这一算法被称为"乐观锁",是因为其首先乐观地假设所有内存读取1在不产生歧义的前提下,我们使用R(x)表示一个对x的读事件、W(x)表示一个对x的写事件以简化描述.
4.
1基于乐观锁的访存依赖追踪57均具有线程局部性.
在我们的算法中,读操作将被直接执行,然后"er具有线程局部性"这一假设被立即验证.
若验证成功则无需记录访存依赖(fastpath),否则回退到"悲观"的互斥锁并重做读操作(slowpath).
由于现实程序的大部分共享内存访问是具有线程局部性的读操作,这一处理能有效减少运行时的时间开销和访存依赖记录的数量.
乐观锁实现访存依赖获取的正确性将在第4.
1.
3节统一讨论.
追踪读后写依赖r→w.
对于任意事件e(无论读写),与它相关的写后读依赖eww→re或写后写依赖eww→we至多仅有一个(数据依赖仅发生在最近一次对x的写事件ew和e之间),但在两次对x的写入事件ew1和ew2之间,可能存在发生在不同线程的多个读事件er,此时每个err→wew2都必须被准确记录.
由于读后写依赖是一对多的关系,因此其追踪也更具有挑战性.
我们使用类似于追踪写后读依赖的内存访问顺序以追踪读后写依赖.
用rx维护在上一次对x的写事件之后每一线程最后一次对x的读事件.
rx实现为一个T→E的映射(我们暂时假设其更新和读取能够原子地完成).
由于对rx的更新(rx←rx[t→er])发生在读操作之前(图4.
1第1行),我们保证W(rx)poR(x);由于对rx的读取发生在写操作之后(图4.
2第5行),我们保证W(x)poR(rx).
对于一个读后写依赖err→wew(即R(x)totW(x)),根据偏序关系的传递性,我们有W(rx)poR(x)totW(x)poR(rx),因此对于任意的读后写依赖err→wew,只要rx维护的原子性得到保证,在ew发生时就能保证从rx中得到er,不会遗漏任何读后写依赖.
与wx的维护类似,我们在维护rx时没有保证rx的读写和其他操作之间的原子性.
因此可能存在读事件er发生前更新了rx并与某个写事件wx形成err→wew的读后写依赖,但由于er的线程局部性检测thread_locality_test失败,导致eww→rer被记录,从而在d中形成er,ew两个事件之间的循环依赖.
这一情形的避免将在正确性讨论中予以说明.
实现高效的wx和rx维护.
我们之前的讨论要求对wx和rx的读取、写入和更新满足原子性.
若在对wx和rx的维护中引入额外的同步操作,则会导致性能瓶颈.
因此,必须高效(无锁)地对这两个数据结构进行维护.
对wx的维护是较为直接的.
首先,wx仅需要存储一个数值(某个写入事件ew∈E),因此可以用固定长度的数据结构表示.
易见所有对wx的写入都被串行化(对wx的写入仅发生在图4.
2第3行,且处于x保护的临界区中),因此直接将wx作为普通的共享内存变量进行读取/写入即可.
在现代多处理器系58第四章高效的访存依赖获取1functionhash_lookup(rx,t)2begin3h=R(rx);4i←hash_probe(h,t);5if查找失败then6returnFAIL;7returni;8functionhash_reclaim(rx)9begin10W(rx,new());11functionhash_insert(rx,t,e)12begin13h=R(rx);14i←hash_lookup(h,t);15if查找失败then16lock(x);17begin18j←find_insert_pos(t);19W(h(j).
key,t);20W(h(j).
value,e);21unlock(x);22else23W(h(i).
value,e);图4.
4读事件集合rx的维护算法.
统中,只要wx在内存中不跨越缓存线的边界,其更新就能原子性地完成,对wx的读取不会读到部分值.
不同于wx仅存储一个访存事件,rx中存储T→E的映射,因此其维护更具挑战性.
由于在每次共享内存读操作之前,我们都要将rx中当前线程t对应的读事件更新,即rx←rx[t→e],而具有线程局部性的读操作又占共享内存访问的绝大部分,因此我们必须实现rx的高效(常数时间、无锁)维护.
能实现O(1)对映射进行维护的数据结构是散列表(HashTable),然而,目前仍然没有满足wait-free性质的通用并发散列表.
分布式计算领域目前最好的实现[93]在性能上仍然难以满足访存依赖追踪的需求.
4.
1基于乐观锁的访存依赖追踪59为了实现rx的高效维护,我们利用了其访问的特殊性.
对rx的操作仅发生在图4.
1第1行和图4.
2第5行,总共分为三种:1.
线程t在无同步的情况下更新其对应的写者:rx←rx[t→er];2.
线程t在有锁保护的情况下对rx进行扫描,以获取其全部元素;3.
线程t在有锁保护的情况下对rx进行初始化操作(rx←);在所有情形中,没有锁保护的情形仅有线程t对rx(t)进行更新(对rx的读取和初始化均被串行化),即线程t永远只更新rx中键为t所对应的值.
在这一限制条件下,我们只需保证数据结构的单调性(若某次访问rx(t)能获得t对应的键-值对,则后续任意访问rx(t)均能获得同一键-值对),即可实现高效的rx维护:只需在查找t失败时使用原子操作/同步操作进行散列表插入,而在查找t成功时则可以直接更新键-值对中的值.
显然,使用闭地址、拉链法解决冲突的散列表满足这一单调性,线程t在将t插入链表时使用原子操作对链表头进行更新,此后散列表对t的查找将总是成功,以实现rx的正确维护.
另一个可行的开放地址散列实现如图4.
4所示.
这些实现均能保证在t已在散列表时能在O(1)时间内无同步、无原子操作地实现rx的更新.
4.
1.
3正确性讨论4.
1.
3.
1在顺序一致内存模型上的正确性我们首先假设并发系统的内存模型满足顺序一致性,即与我们在第2.
1节定义的系统模型相同,存在访存事件的全序tot,并发系统严格按照tot规定的顺序执行访存指令:在写事件ew发生后,数值ew.
v被立即写入共享内存变量ew.
x、读事件er的读值er.
v总是来自tot中最近一次对er.
x的写事件.
写后写依赖追踪的正确性.
我们使用互斥锁保证了所有对同一变量x的写操作以及相应的rx,wx更新的原子性(图4.
2第1–6行).
由于写后写依赖的追踪(读取和更新wx)发生在临界区中,并且对于任意连续两个发生在不同线程的访存事件,都有e′ww→wew被记录(图4.
2第9行),因此d=tr(d∪po)包含了对所有x写入事件的全序.
写后读依赖追踪的正确性.
首先,对于thread_locality_test失败的情形(图4.
1第4–11行),我们使用锁保护了对共享内存的读指令,并在临界区中读取对x的上一次写事件wx的值.
这一情形与写后写依赖追踪类似,由于对wx的写操作被同样的临界区保护(图4.
2第1–6行),因此对wx的操作不存在数据竞争,能够保证获得与读事件er相对应的写事件ew,从而记录的访存依赖ewder代表tot中这一对读写事件发生的实际顺序.
60第四章高效的访存依赖获取因此,写后读依赖追踪的正确性只需论证对于实际产生写后读依赖的读事件er,在er发生后thread_locality_test是否一定返回失败.
对于er=R(x),ew=W(x)(er.
t=ew.
t且不存在对变量er.
x的写事件e′w满足ewtote′wtoter),其写后读依赖及其相应的wx写入/读取事件排列如下:W(wx)poW(x)totR(x)poR(wx),由于W(x)和R(x)之间产生了实际的写后读依赖,因此不存在对er.
x的读事件e′r满足ewtote′rtoter.
由于W(wx)poW(x)处于同一临界区,其间不会插入其他对x或wx的写入事件.
又由于W(x)totR(x)之间包含实际的数据依赖,其间也不存在其他对x或wx的写事件.
因此,er=R(wx)读到的数值仅存在两种情况:1.
读到ew=W(wx)写入的wx;2.
读到在R(x)poR(wx)之间另一线程t=er.
t写入的wx.
基于我们每一访存事件都具有全局唯一标识符的假设(标识符可以用线程号和线程本地的事件计数器实现),每次写入ew的数值均是全局唯一的.
在上述两种情况下,R(wx)均读到另一线程对wx写入的数值,由于其全局唯一性,其一定不等于线程t本地缓存的数值Ct(er.
x).
换言之,在存在写后读依赖时,线程局部性检测thread_locality_test总是返回False.
因此,对于存在写后读依赖的读事件er,我们总是会使用同步再次对er.
x进行读取,从而获取准确的写后读依赖.
读后写依赖追踪的正确性.
读后写依赖的正确性与写后读类似.
此时rx的更新发生在x的读取之前(图4.
1第1行),而rx的读取发生在x的写入之后(图4.
2第5行).
因此,对于读事件er=R(x)和写事件ew=W(x)之间真实存在的读后写依赖,有W(rx)poR(x)totW(x)poR(rx).
假如不存在任何与这一事件序列并发的其他事件,偏序关系的传递性保证了W(rx)totR(rx),即在写事件发生时能获取正确的读后写依赖.
因此,我们只需考虑在这一事件序列中可能发生的并发事件.
首先,因err→wew存在实际的数据依赖,序列中er=R(x)和ew=W(x)之间不存在其他对x的写入事件(否则于读后写依赖矛盾).
由于所有对x的写入和rx的读取/更新被包含在同一临界区中(从而原子性得到保证),因此W(x)poR(rx)可以看作是瞬时发生的,期间不会插入其他产生数据依赖的事件.
在W(x)发生前还可能存在其他线程写入rx的事件,但只要rx能正4.
1基于乐观锁的访存依赖追踪61确支持多个线程的并发写入,就能被R(rx)正确读出.
因此,需要考虑的剩余情形是:1.
W(x)poR(rx)之间对rx的更新事件.
这些更新事件一定来自其他线程对x的读取事件e′r(er.
t=e′r.
t).
图4.
2第3行对wx的更新发生在ew之前(即W(wx)poW(x)),因此e′r的thread_locality_test一定返回失败并导致同步.
这一情况会导致e′rr→weww→re′r的成环情况,我们只需将这一环移除即可.
2.
W(rx)poR(x)之间发生的来自其他线程的W(x)事件.
使用之前对写后读依赖追踪的正确性分析,对wx和x的访存事件满足W(wx)poW(x)totR(x)poR(wx),因此在er=R(x)之后执行的thread_locality_test也必然返回False,从而进入临界区保护的slowpath.
此时,er对应的读事件将作废(以图4.
1第6行的e′r为准,从而er对应的依赖无需记录).
e′r发生在临界区中因此能获得正确的写后读依赖,并且图4.
1第8行中再次对rx进行的更新能保证e′r之后的读后写依赖能被正确追踪.
因此,我们可以保证在具有线程局部性的读操作中不使用同步操作的前提下获取准确的读后写依赖.
4.
1.
3.
2在松弛内存模型上的正确性乐观锁实现不使用同步/原子操作的访存依赖追踪的核心技术是对并发程序/系统进行修改,加入访存依赖追踪相关的代码,其中事件记录和共享内存读写按照如下顺序进行:W(a)poAtotBpoR(a),其中A,B为对共享变量x的读/写事件,a是用于记录访存依赖维护的数据结构(wx或rx).
在写后读(w→r)依赖的追踪中,A=W(x),B=R(x),a=wx;在读后写(r→w)依赖追踪中,A=R(x),B=W(x),a=rx.
偏序关系的传递性保证了W(a)dR(a),因此对元数据的更新一定发生在元数据的读取之前,从而实现访存依赖的在线追踪.
这一正确性论证依赖于并发系统满足顺序一致性的内存模型,各个线程按照程序顺序po顺次执行所有读/写操作,并且读事件的值保证等于最近一次写事件写入的数值.
然而,现代多处理器系统为了弥补缓存缺失造成的延迟(维护多处理器间的缓存一致性和从其他存储器调取数值均会造成比指令执行时间长得多的延迟),62第四章高效的访存依赖获取通常都使用了动态流水线技术,以实现指令的动态调度和乱序执行.
从应用程序的角度看,这一行为虽然保证了单线程程序的顺序一致性,但由于允许交换共享内存访问的顺序,在这些系统上执行多线程程序得到的执行轨迹将不再满足顺序一致性,因而本节的上述正确性论证也不再成立.
常见的松弛内存模型(relaxedmemorymodel)有TotalStoreOrder,PartialStoreOrder等[75].
我们首先在目前最广泛使用的计算机系统:Intelx86系统上讨论访存依赖追踪算法的正确性,再讨论更弱内存模型下实现的修改.
x86-TSO上的正确性.
由于我们对写操作进行了同步,因此写后写(w→w)依赖获取的正确性是显然的.
接下来我们证明获取写后读(w→r)依赖在x86-TSO[119]内存模型上的正确性.
对于thread_locality_test检测出er不具有线程局部性的情况(图4.
1第4–9行),由于我们使用同步操作保护了再次尝试的读操作,因此在这一情形下也能准确地追踪访存依赖.
因此,我们只需证明对于不具有线程局部性的读事件,thread_locality_test总是返回False,即能保证在x86-TSO上的正确性:定理4.
1.
在x86-TSO内存模型中,若er=R(x)(图4.
1第2行)读取到另一线程写入的数值,线程局部性测试将返回False.
证明.
在x86-TSO中,读事件er必满足如下两种情况之一:(1)从本线程的写缓存中读出数值;(2)从另一线程读出数值.
对于从本线程写缓存中读出数值的情况,其实际上具有线程局部性(写缓存中的数值一定是本线程写入的).
因此,无论thread_locality_test成功与否,其正确性都能得到保证.
对于er从共享内存中读出数值的情况,我们依旧考虑修改后的程序所产生的事件序列W(wx)poW(x)totR(x)poR(wx),其中er=R(x),与之相关的写事件ew=W(x).
若er从共享内存中读出另一线程写入的数值,则wx在x被更新前更新,即W(wx)poW(x).
由于x86-TSO保证同一线程满足程序顺序的写入操作按FIFO顺序进入写缓存,并且写缓存也按照FIFO顺序写入共享内存,因而如果R(x)读到了这一数值,说明写缓存中x的数值已经进入了共享内存.
因写缓存的FIFO特性,wx的数值也到达了共享内存.
而对于R(x)事件,x86-TSO中指令按程序顺序执行,R(x)poR(wx)保证了此时wx不会在写缓存中(否则将导致对x的写也在写缓存中,与从共享内存读取x矛盾),故线程局部性测试将返回False.
4.
1基于乐观锁的访存依赖追踪63这一证明即便对于不冲刷硬件写缓冲实现的自旋锁(此类锁是pthread线程库和Linux内核中的标准实现)依然成立[119].
在此情形下,整个系统的行为可能不满足顺序一致性(文献[119]中的SB例子).
即使如此,我们的算法仍然能准确地获得每一读事件对应的写者.
因此在不记录r→w依赖的前提下,我们即便不对算法作出任何修改(不插入内存障碍),仍能通过离线再次运行程序获得准确的访存依赖(w→r依赖能从w→r和w→w依赖离线推导得到,因此这一算法是具有实际意义的).
如需在追踪访存依赖的同时保证程序在x86-TSO内存模型上的顺序一致性,则可通过增加内存障碍来实现:我们只需在写时的锁释放前(图4.
2第6行)使用内存障碍清空写缓存,保证在R(x)poR(wx)事件发生时线程本地的写缓存为空,从而确保所有读事件都从共享内存中读出.
由于x86-TSO保证所有读操作的原子性且不被乱序,则顺序一致性可以得到保证.
对于一对读后写(r→w)依赖,修改后程序的共享内存访问事件序列为W(rx)poR(x)totW(x)poR(rx),由于x86-TSO不保证对不同变量读和写之间的顺序,因而若不增加额外的障碍将会导致访存依赖的丢失.
我们需要使用MFENCE指令实现上述po关系(在图4.
2第4行和第5行之间、图4.
1第1行和第2行之间插入障碍),以保证访存依赖追踪的正确性.
在更弱内存模型上的正确性.
基于乐观锁的访存依赖追踪技术的核心是使用满足如下顺序的事件序列:W(a)poAtotBpoR(a),对于依赖AtotB,通过传递性推导出W(a)totR(a),从而在不使用同步的情况下获得访存依赖.
在更弱的内存模型(如PSO)下,用于追踪读后写、写后读依赖时的访存事件W(a)poA和BpoR(a)均可能被乱序.
因此,我们只需按如下方式增加内存障碍:W(a)poBARRIERpoA和BpoBARRIERpoR(a),即可满足算法的正确性和程序的顺序一致性语义.
虽然增加了内存障碍,但这一算法在具有线程局部性读事件发生时仍然不会引入额外的同步或原子操作且能在O(1)时间内完成,是十分优秀的算法.
64第四章高效的访存依赖获取4.
2基于二分组协议的在线访存依赖数量约减4.
2.
1问题定义与解决思路问题定义.
在上一节中我们利用并发程序共享内存访问的线程局部性设计了基于乐观锁的高效访存依赖获取技术,其对于具有线程局部性的读操作可以不引入额外的同步或原子操作,以实现即时、高效、准确的访存依赖在线追踪.
访存依赖最终用于实现各类并发程序的动态分析技术.
各类动态分析技术对访存依赖获取技术评价指标的需求不同,即时、高效、准确的访存依赖获取技术并不能满足所有动态分析技术的需求,访存依赖记录的简化性同样对实现有效的并发程序动态分析至关重要.
例如,现实并发程序的执行轨迹可能包含海量的共享内存访问,仅仅将这些访存依赖存储都可能导致难以容忍的巨大开销(例如,将事件记录写入速度较慢的磁盘将成为性能瓶颈);处理大量访存依赖记录的时间复杂性有时也是难以忍受的,例如基于约束求解的算法通常无法解析过于庞大的访存事件记录.
因此,并发程序的动态分析技术必须在即时性、高效性、准确性和简化性之间做出权衡.
并不是所有的分析都需要完全准确反映线程间数据依赖的访存依赖(即完全准确的访存依赖),因此放松准确性是一个可行的权衡:如能在运行时追踪满足一致性的访存依赖,就能满足很大一类动态分析技术(如执行重放调试、并发控制技术等)的需求.
因此,本节关注高效访存依赖获取技术在即时性、高效性、准确性和简化性之间的权衡,又称为访存依赖的在线数量约减问题:在满足即时性、不降低或轻微降低高效性、轻微降低准确性(获得的访存依赖仍满足一致性)的前提下,实现访存依赖数量的大幅减少,提高依赖日志的简化性.
形式化地说,我们要求记录的访存依赖d满足对于eiej,eidej当且仅当eitotej,在此前提下尽可能地高效(具有较少的运行时时间开销)、简化(减少|d|记录集合的大小).
相关工作.
为了提高依赖日志的简化性,其约减可以通过在访存依赖eidej被捕获后对其冗余性进行检查实现,即通过排除一些不影响动态分析技术正确性的依赖以达到减少记录数量的目的.
我们称这类技术为在线约减技术.
另一方面,依赖约减也可以在程序执行结束后(此时访存依赖记录已经获得)进行,把"获得等价并且更简化访存依赖"这一问题建模成组合优化问题实现,称为离线约减技术.
对比在线、离线两类访存依赖约减技术,在线约减能实现运行时访存依赖记录的减少(离线约减需先记录日志再进行求解),从而其应用场景通常不受限4.
2基于二分组协议的在线访存依赖数量约减65图4.
5访存依赖的约减:(a)传递约减(TR),(b)正则传递约减(RTR).
虚线为被约减的依赖,双线为添加的依赖.
制.
其挑战主要在于访存依赖获取是服务于动态分析技术的,因此在程序运行时实现访存依赖约减的同时不能大幅降低其即时性、有效性、准确性等指标,否则将无法达到动态分析技术的预期.
离线约减技术由于直接根据完整的访存依赖记录d,能够使用专门算法或组合优化求解器对依赖关系进行化简[72,76],因此通常能得到较在线约减技术更为简化的记录,但缺点是在运行时仍要产生大量的记录.
本节关注访存依赖的在线约减问题,能在即时获得访存依赖的前提下获得简化的记录,从而能直接用于使用访存依赖的动态分析技术.
一个直观的在线访存依赖约减技术是利用d关系的传递性实现冗余访存依赖的过滤,因此被称为传递约减法(TransitiveReduction,TR)[105].
对于访存事件ei,ej,ek,如果我们已知eiej,ejek,那么对eiek进行记录就是多余的:只要满足传递性,eiek就可以从eiej和ejek推导得到.
可以证明,对于任意偏序关系,都存在唯一最简的偏序满足传递不可约,且这一最小偏序可以通过迭代删除传递冗余的依赖关系得到.
TR技术在运行时维护当前访存依赖的传递关系d=tr(d∪po).
对于每一个捕获的访存依赖eidej,都检查eidej是否成立.
若eidej则将eidej这一记录丢弃,否则记录eidej并更新d中的传递关系.
在并发系统或分布式系统中,传递关系可以用向量时钟(vectorclock)[82]在运行时维护,以实现访存依赖的在线约减.
向量时钟不仅可以在软件层面维护[105],还可以在缓存一致性协议层面予以近似[129].
图4.
5a展示了传递约减法TR实现的依赖约减.
执行轨迹中的事件按照W(x)poW(y)poW(z)totR(z)poR(y)poR(x)66第四章高效的访存依赖获取顺序发生,因此x,y,z三个变量之间存在数据依赖.
但是我们只需记录一个依赖关系W(z)dR(z),就能根据偏序关系的传递性推导出其他数据依赖,如W(x)poW(z)dR(z)poR(x),因此TR在此例子中能在仅记录一对事件的前提下得到满足一致性的访存依赖.
传递不可约(transitivelyirreducible)的执行轨迹并不意味着它是满足一致性的最小执行轨迹.
图4.
5b包含了传递不可约的例子,执行轨迹中的事件按照W(x)poW(y)poW(z)totR(x)poR(y)poR(z)顺序发生(本例中按x,y,z的顺序读出共享变量的数值),因此W(x)dR(x),W(y)dR(y),W(z)dR(z)形成"平行"的依赖关系,无法用传递性互相推导得出.
但若我们人为地添加W(z)dR(x)的依赖关系(在一致的d中添加任意的eidej,只要保持d仍是一个合法的偏序,就不会影响d的一致性),则上述三个依赖均可以被传递约减.
然而,求解满足一致性的最小执行轨迹已被证明是NP-完全问题[76].
为进一步实现在线的访存依赖约减,正则传递约减法(RegulatedTransitiveReduction,RTR)使用启发式的算法,在访存依赖eidej被捕获时,试图寻找另一个不引发矛盾、更"强"的依赖关系替代eidej.
具体而言,其寻找事件e′j满足:(1)e′j与ej在同一线程且在ej之前发生,即e′jpoej;(2)依赖ab′仍然能保证d是合法的偏序.
由于ab′在传递关系上能推导ab,因此RTR记录ab′.
对于图4.
5b中的例子,RTR在获得访存依赖W(z)dR(z)后,使用W(z)dR(x)对其进行替代(具有更强的顺序约束且不会引发矛盾),并利用TR技术实现访存依赖的约减.
研究挑战.
尽管TR和RTR都能实现有效的访存依赖约减,但在运行时维护事件之间的传递关系是非常耗时的操作.
对于一般的有向无环图,求解其传递闭包(transitiveclosure)目前已知的最坏情况下最优的算法是将其归约到矩阵乘法,因而具有O(nω)的时间复杂性(目前已知最好的ω=2.
376[38]).
在分布式系统中,通常线程数远小于事件数,因此维护Lamport向量时钟[82]能实现更有效的传递性维护.
然而,维护向量时钟需要O(|T|)的时间(且已被证明此复杂性为最优下界).
尽管利用并发程序共享内存访问的局部性能大幅降低这一开销[55],但其有效维护要么需要使用定制化的硬件[130],要么需要付出远远高于访存依赖追踪的开销[28,79].
4.
2基于二分组协议的在线访存依赖数量约减67图4.
6将变量x,y,z组合为变量组{x,y,z}以实现访存依赖约减.
因此,在已有的软件系统上应用TR或RTR实现访存依赖约减,其带来的简化性优势将同时导致高效性的大幅降低.
如何在不降低高效性的前提下实现访存依赖的在线约减(如实现TR或RTR的依赖约减效果)是主要的技术挑战.
解决思路.
我们发现,利用并发程序具有的空间-线程局部性对变量进行分组,在分组合适的前提下,能不引起较多运行时开销并实现TR和RTR的访存依赖约减效果.
首先,TR和RTR能够实现访存依赖约减的基础是并发程序在执行过程中会访问多个共享变量,而其中一些变量的依赖可以用其他依赖(或其变形)推导得到.
如果并发程序仅有一个变量,即|Xs|=1,则只要过滤掉具有线程局部性的事件,访存依赖d就是传递不可约的,而现有的访存依赖追踪算法通常都能实现此类过滤[28,79].
TR和RTR实现访存依赖约减的主要原理是识别出了并发程序中常见的两种访存依赖可约减模式,如图4.
5所示.
图4.
5a展示了TR实现依赖约减的模式:识别出"传递可约"的事件,在已经存在eidej,ejdek的前提下实现依赖eiek的约减;图4.
5b则展示了RTR实现依赖约减的模式:将"平行"的依赖关系使用一个更强的依赖关系替代,使得平行的依赖关系满足传递可约减的条件.
我们发现,若传递可约或平行可约的依赖关系产生于两个线程之间(对应了图4.
5中的情形),则可将变量x,y,z组合为一个变量组{x,y,z},并以变量组为单位进行访存依赖追踪1,以同时实现TR和RTR的访存依赖约减效果,1无论对地址空间中的变量进行怎样的分组,我们只要记录变量组上满足一致性的访存依赖,就一定能获得对任意变量满足一致性的访存依赖.
68第四章高效的访存依赖获取如图4.
6所示.
此时,无论对x,y,z的操作以何种顺序发生,其访问都相当于对变量组{x,y,z}的访问.
在线程2中首次访问变量组中的变量,将会产生访存依赖,但随后对变量组中的其他变量进行访问都将被视作对该变量组的线程局部访问,不会产生依赖记录,从而实现TR和RTR的访存依赖约减效果.
这类可约减的情形是符合现实并发程序的共享内存访问模式的:并发程序使用共享内存实现线程间通信时,一个线程通常首先准备一系列数据,然后使用同步操作与另一线程同步,之后另一线程再对这些数据进行操作.
这恰好对应了TR和RTR实现访存依赖约减的场景.
因此,我们考虑用变量分组的技术实现访存依赖的在线约减.
现有研究工作已对变量分组进行了尝试(相当于将空间上连续的变量指派为同一锁),例如Octet[28]将属于同一对象的变量分为同一组以实现依赖数量的约减,但目前的研究通常局限于使用固定的策略进行静态变量分组.
根据第2.
2节中证实的并发程序具有空间-线程局部性的实验结果,我们发现现有基于静态分组的技术并不能充分利用现实并发程序共享内存访问具有的空间-线程局部性.
因此,我们提出在运行时将地址空间进行动态可调整的区间划分,并于运行时维护这一区间划分以使每一区间中的变量具有空间-线程局部性,从而将区间中的变量视作一个整体进行访存依赖追踪,以实现访存依赖数量的大幅减少.
4.
2.
2二分组协议利用空间-线程局部性实现访存依赖约减.
假设并发程序运行在大小为M的地址空间(M为内存地址的最大值),程序中的每一全局变量x∈Xs均有一个在区间[0,M)内的地址.
在不引起歧义的前提下,我们既用x表示一个共享变量,也用x表示它的地址.
为了实现空间-线程局部性的利用,我们将变量进行区间分组:将Xs划分为k个不相交的变量组P={G1,G2,.
.
.
Gk},使用映射函数f:[0,M)→[k]将地址x映射到其对应的变量组Gf(x).
当线程访问x时,我们认为其访问了Gf(x)中的所有变量.
换言之,在获取访存依赖时,我们不再将Xs作为共享变量集合,而是将变量组Gi∈P视作共享变量,对x的读写将视作对Gf(x)的读写——只要两个事件属于同一变量组、发生在不同线程且至少有一个是写事件,就认为其为冲突事件.
将变量进行分组并按组获取访存依赖不会影响访存依赖的一致性.
访存依赖满足变量组意义上的一致性,当且仅当对于任意的事件对ei,ej,若ei.
t=ej.
t,(ei.
rw=w)∨(ej.
rw=w)且Gf(ei.
x)=Gf(ej.
x),则有eidejeitotej4.
2基于二分组协议的在线访存依赖数量约减69成立.
因此,对于任意实际冲突的事件对e′ie′j,根据其定义有e′i.
x=e′j.
x,必有Gf(e′i.
x)=Gf(e′j.
x),因此e′ide′je′itote′j成立.
将变量进行区间分组以利用空间-线程局部性实现高效访存依赖获取的技术已得到广泛应用[28,52,69,79,132,144].
变量分组属于第3.
2.
1节中讨论的锁指派技术中的区间指派技术,常见的区间有属于同一对象的数据域[28]、连续一段固定长度的地址[79]、物理内存页面[52]等.
此类分组技术能有效减少元数据维护的数量(对于一个分组只需维护一份元数据),通常能实现运行时开销的减少和部分访存依赖的约减.
然而,这类技术仅仅发挥了空间-线程局部性的少部分潜能.
目前的技术为了防止产生不代表数据依赖的访存依赖(若x,y被两个线程分别独立访问但被分为同一组,则会导致很多冗余的依赖),通常在区间大小上较为保守.
然而在第2.
2节对空间-线程的实证研究中,对于一些程序,只有使用较大的分组(如220字节)才能实现较优的访存依赖约减效果.
尽管我们知道将地址空间进行划分能实现空间-线程局部性的利用从而约减访存依赖的数量,但由于不同程序在不同时刻访问共享内存的模式不同,如何准确地划分地址空间以实现访存依赖的约减就成为一个难题.
动态变量分组技术.
目前使用启发性经验规则进行区间划分的技术都使用一般性准则指导划分(如实现锁的对象指派、物理页指派等)而无法根据并发程序访问共享内存的实际行为模式进行调整.
为了克服这一局限,我们创造性地提出在程序运行时动态维护地址空间的划分,使每一区间中的共享变量访问均满足空间-线程局部性,并在这一假设被违反时重新调整划分.
对于地址空间[0,M),我们在运行时维护其划分P={G1,G2,.
.
.
Gk},且满足如下性质:1.
每一变量组可以视为一个左开右闭区间Gi=[li,ri),对于地址x,x∈Gi当且仅当li≤x>6)&0xfffff的锁对象1.
在锁对象充足(不使用超过226字节内存)的前提下,相当于将内存地址位于连续64字节内的变量指派为同一锁.
64字节是典型计算机系统L1缓存线的宽度.
如并发程序中不存在假共享缺陷,使用这一大小能减少元数据的开销和记录依赖的数量.
2.
在RWTrace的算法描述中,每一线程t都需要在本地维护每一变量x(实际实现时为x对应的锁对象)上次发生在线程t的访存事件Ct(x).
Ct可1>>为二进制位右移运算,&为二进制与运算.
4.
3系统实现与实验评估75以用散列表在O(1)时间内实现,但其仍然会引起相当可观的时间和空间开销.
为了获得更优的性能,我们利用并发程序的线程局部性,使用一个有限大小的缓存来作为Ct.
线程t的Ct实现为大约包含m≈104个元素的直接映射缓存(我们取略小于104的素数作为模数以取得最佳直接映射缓存的命中率).
编号为i锁对象的版本号存储在编号为imodm的缓存项中.
在缓存命中时,只需少量线程本地指令即可实现缓存的读取和更改.
3.
维护读事件映射rx(t)的数据结构需要支持高效并发查找和修改.
我们使用闭地址散列表实现rx,并使用链表解决散列冲突.
由于闭地址散列表的散列函数不会变化,其每一散列桶中的链表是单调递增的,因而保证了一旦t∈rx,后续所有对t的查找都一定成功.
此外,由于闭地址散列表所有内存分配和释放都是固定长度(所有散列表的长度都相同、每一键-值对数据结构的大小也相同),因此可使用环状缓冲区实现均摊O(1)时间的内存分配和释放.
4.
3.
1.
2在RWTrace基础上实现的二分组协议第4.
2节描述了实现在线访存依赖约减的二分组协议.
为了在追踪访存依赖的同时实现二分组协议,必须解决以下技术挑战:1.
在共享内存访问时确定变量x对应的分组编号f(x).
由于分组在运行时不断变化,必须实现f(x)的高效动态维护;2.
根据定义,判定eidej是否是假依赖需要对访存依赖记录进行扫描,必须减少这一算法的开销.
若使用朴素的算法实现二分组协议(使用二叉树查找确定变量分组、扫描访存依赖记录检测假依赖),相比于乐观的访存依赖追踪算法RWTrace,将会引起5–10倍的额外运行时开销,此时二分组协议虽然能够实现有效的访存依赖约减,但却带来了实际中无法容忍的开销.
因此我们应用了一系列技术在RWTrace的基础上高效地实现了二分组协议,描述如下(其评估结果在第4.
3.
2节展示).
确定变量对应的分组.
由于并发程序具有海量的共享内存访问,虽然绝大部分具有空间-线程局部性而无需记录与之相关的访存依赖,但在每次共享内存访问时,都必须确定变量x对应的变量组f(x),因此计算f(x)的时间开销对二分组协议的高效性是至关重要的.
给定共享变量x,f(x)返回唯一的区间Gi=[li,ri)∈P满足x∈Gi.
如图4.
8所示,二分组的历史构成一棵二叉树.
一个直接计算f(x)的算法是从树根76第四章高效的访存依赖获取出发,根据x在区间[li,ri)中的位置(x0的读事件er的数量)和启发式算法能否成功推导出满足顺序一致性的访存依赖.
实验结果表明,由于同步局部性的存在和版本号合并技术,对于真实程序绝大部分读事件都满足|Ew|=0,仅有少量的事件无法准确确定其顺序.
对于这些事件,CARE的启发式算法成功地推导出了满足顺序一致性的访存依赖,从而能够实现正确的执行重放.
相比于LEAP的实验结果(表中第5–6列),CARE总体而言显示出了中位数2.
6倍的运行时开销减少和中位数4.
9倍的记录数量减少.
对于内存密集型92第五章基于访存依赖的动态分析表5.
2CARE和LEAP的运行时开销和日志数量对比.
实验程序CARELEAP时间(*)日志(/s)未定序解决时间(*)日志(/s)avrora1.
522.
18MB23K9.
4824.
3MBbatik1.
491.
51KB03.
772.
32KBh218.
524.
2MB062.
827.
4MBlusearch3.
416.
53MB09.
0146.
0MBsunflow64.
9886MB03896.
03GBtomcat4.
767.
80MB1511.
923.
5MBxalan7.
1813.
6MB012.
2143MBtsp2.
791.
84MB0111570MBmoldyn11.
924.
1MB050.
5303MB2526272829210216345缓存组数时间开销(*)2路4路8路16路2526272829210216051015缓存组数记录数量(MB/s)2路4路8路16路图5.
4CARE在不同缓存设置下的时间开销和记录数量对比.
的基准程序(如tsp),CARE的时间开销和记录数量分别仅为LEAP的1/40和1/300.
因此,我们认为CARE所作出的权衡(无法像LEAP一样在运行时即得到一致的访存依赖,部分情况下需要离线推导,但在数值预测缓存命中时能大幅增加依赖记录的高效性和简化性)能更高效地对现实程序进行执行重放.
最后,我们在tsp基准程序上评估不同缓存设置对运行时开销和记录数量的影响(tsp是其中访存最密集的应用程序,因此其对缓存的性能亦最为敏感),评估结果如图5.
4所示.
可见,在缓存较小(小于512组)时,随着缓存的增加,CARE的运行时间和日志数量大幅降低,但当缓存达到一定数量时(对tsp而言是1024组),其性能增加不再明显.
因此我们有理由认为一个中等大小的缓存即能支持高效的执行重放.
5.
1并发程序的动态分析93小结.
本节描述了利用并发程序共享内存访问的线程局部性实现的基于缓存的执行重放技术.
这一技术体现了我们在访存依赖获取技术指标之间进行的权衡:为执行重放这一并发程序动态分析问题定制高效、简化(同时即时性、准确性相对弱化)的访存依赖获取技术,相比于现有技术能在实现同样目标(确定性重放并发程序执行)的前提下大幅减少时间开销和日志数量.
5.
1.
2基于二分组协议的动态分析5.
1.
2.
1数据竞争检测问题定义与解决思路.
若存在程序P的执行轨迹τ,其中包含先后发生的冲突访存事件eiej1,则称P中的变量ei.
x存在数据竞争(datarace).
除直接导致不符合规约的变量数值外[56],数据竞争也是引起其他类型并发缺陷(如原子性违反或顺序违反)的主要原因[94].
因此对并发程序中数据竞争的检测得到了研究者的广泛关注.
例如可以直接对程序进行静态数据竞争检查[125](静态数据竞争检测),或对执行轨迹中的数据竞争进行检测(动态数据竞争检测).
动态数据竞争检测技术开销小、正确性(soundness)容易保证,在实践中已得到广泛应用,且检出了知名并发程序中前所未知的数据竞争[71].
动态数据竞争检测通过考察执行轨迹中的访存事件推断出并发程序中潜在的数据竞争.
例如,若存在两个访存事件eiej且ei,ej所对应的锁集合交集为空,则它们可能形成数据竞争[115];若能求出执行轨迹中同步事件发生的因果关系syn,则若存在eiej满足(eisynej)∧(ejsynei),则可以证明并发程序中存在数据竞争或死锁.
目前,基于Lamporthappens-before[82]因果模型的数据竞争检测是研究的热点之一[25,55,127].
现有的数据竞争检测技术需要获取准确的访存依赖(必须使用变量指派),并为每一记录的访存依赖eidej检测其是否满足(eisynej)∨(ejsynei),因此可能带来数百甚至数千倍的运行时开销且需要大量内存来维护元数据.
如何降低这些开销是一项重要的研究挑战.
由于二分组协议能在不付出较多运行时开销的前提下大幅降低访存依赖的数量,因而我们很自然地考虑如何使用二分组协议以实现高效的数据竞争检测.
但使用二分组协议获取的访存依赖eidej不能直接用于数据竞争检测:由于对变量进行了分组,即便(eisynej)∨(ejsynei)不成立,eidej仍可能是不存在数据竞争的假依赖.
1eiej当且仅当ei.
x=ej.
x,ei.
t=ej.
t且(ei.
rw=w)∨(ej.
rw=w).
94第五章基于访存依赖的动态分析考虑以上情形的反面:若对于所有的eidej都满足(eisynej)∨(ejsynei),则可证明本次执行不存在syn意义下的数据竞争.
对此,我们提出基于二分组协议的自适应数据竞争检测算法.
基于二分组协议的数据竞争检测.
二分组协议能在小幅增加运行时开销的前提下大幅减少访存依赖的数量.
由于因果关系检查通常是较为耗时的操作,基于二分组协议实现高效数据竞争检测技术的直观想法是尽可能地只对d中的事件二元组ei,ej∈d进行因果关系检查.
二分组协议能大幅减少|d|的数量,因而可减少因果关系检测的次数,进而降低数据竞争检测的开销.
实现基于二分组协议的高效数据竞争检测立足于如下两点观察:1.
对于某一变量组Gk,若对所有其上记录的访存依赖eidej都满足(eisynej)∨(ejsynei),则对于任意变量x∈Gk,都不存在syn意义上的数据竞争;2.
变量组Gk具有空间-线程局部性,即在较长的时间内,要么被一个线程独占访问,要么在多个线程间以只读的方式共享.
对于独占访问的情形,其不存在多线程访问故而不存在数据竞争;对于多线程共享的情形,现实程序通常都以互斥锁或条件变量等同步机制实现,通常亦不存在数据竞争.
同时,因并发程序具有同步局部性,我们有理由相信,对于绝大部分的变量组Gk,其组上的访存依赖不存在syn意义下的数据竞争.
只要这一性质在程序运行过程中保持不变,我们就只需在变量组的粒度上进行数据竞争检测.
因此,我们使用二分组协议对访存依赖进行获取,并在程序运行时维护因果关系syn(例如,对于Lamporthappens-before因果关系,可以使用FastTrack[55]算法进行维护).
在获得变量组Gk上的访存依赖eidej后,若(eisynej)∨(ejsynei)成立,则说明Gk所对应的同一变量组到目前为止都没有产生数据竞争.
我们称这样的检测为"粗粒度检测".
若粗粒度检测一直保持到程序执行结束,则对于任意的eiej,我们有eidej.
由于所有记录的eidej都满足(eisynej)∨(ejsynei),而d为d增加了po的传递闭包,因此有(eisynej)∨(ejsynei)成立,则E中的事件不存在syn意义下的数据竞争.
但当变量组中的依赖eidej是syn意义上的数据竞争(称为变量组数据竞争),即(eisynej)∧(ejsynei)时,我们则需要判定其变量组Gk中的变量是否存在实际的数据竞争.
对于假依赖的情况(图4.
7),虽然记录了访存依赖eidej,但实际并没有任何线程间数据流,也没有数据竞争,若用变量组的数据竞争代替实际数据竞争,会导致假阳性(误报)的发生[124].
5.
1并发程序的动态分析95对于产生了变量组数据竞争的变量组Gk和访存依赖eidej,需要解决以下两个问题:1.
由于变量组存在数据竞争,在没有假依赖的前提下,变量组中的变量是可能产生数据竞争的候选,因此需要对x∈Gk中的变量进行数据竞争检测.
2.
需要判定是否已经存在变量x∈Gk的数据竞争:存在访存事件e满足eej,e.
x=ej.
x,它发生在ei的同一线程且发生在ei之前(epoei),且(esynej)∧(ejsyne).
为了解决问题(1),对于检测到变量组数据竞争的Gk,我们对Gk中的变量使用细粒度数据竞争检测技术[55],以确保Gk中变量未来发生的数据竞争能被正确检出.
我们为Gk中的每一变量追踪准确的访存依赖,并在访存依赖获取后检查是否存在数据竞争.
相当于我们对变量组Gk中的变量,使用已有的技术进行数据竞争检测.
当变量组经过一段时间的细粒度数据竞争检测后,其中所有共享变量访问均在syn中被排序,此时Gk中的变量再次具有空间-线程局部性,从而应当切换到按变量组(即粗粒度)的数据竞争检测检测,以提高性能、减少维护开销.
在细粒度检测时,我们使用队列维护未被syn确定顺序的变量(即可能产生数据竞争的变量).
一旦我们检测到某一变量在某次访存依赖发生后被syn覆盖,就将它从队列中删除.
当队列为空时,这一组依赖中不存在可能产生数据竞争的变量,即可恢复到粗粒度检测.
当二分组发生时,生成的子区间继承父区间的检测粒度.
为了解决问题(2),若eidej包含了真实的数据竞争(eej),由于原始的二分组协议在ej发生时并没有包含Gk变量组对ej.
x的访问历史记录,因而我们必须在运行时记录额外信息以保证数据竞争不会被漏检.
我们在粗粒度检测时保存每一共享变量的访问日志(仅需为每一变量维护每一线程最近的读/写的事件,可使用类似RWTrace中对rx的维护算法,使用并发散列表实现,且具有O(1)wait-free的性质).
当组依赖发生时,组内变量的记录被扫描,并转换为细粒度检测所需的元数据.
上述算法在粗/细粒度检测之间切换.
对于执行轨迹中syn意义下的数据竞争eiej,以下情形之一必然成立:1.
ei.
x=ej.
x对应的变量组Gk处于粗粒度检测模式.
由于检测到变量组数据竞争后Gk会切换到细粒度检测,因而Gk处于粗粒度检测模式意味着之前Gk变量组上获取的访存依赖在syn下不存在数据竞争.
据此,冲突的事件eiej一定对应某一获取的访存依赖edej且(e=ei)∨(epoei).
此时扫描Gk相关的变量访问日志即能检测出这一数据竞争;96第五章基于访存依赖的动态分析1struct{2intx,y;3}global;45voidthread_1(){6for(inti=0;i1)∞compare-and-set、链接加载/条件存储、有界互斥过程中,提出了一致性范数(consensusnumber)的概念,并且证明了在一致性范数的层次结构中,一致性范数小的并发对象不能在wait-free的前提下实现一致性范数大的并发对象[62].
一致性范数的层次结构与常见的并发对象在表6.
1中描述.
后续的研究进一步表明,原子性的变量访问无法在wait-free的前提下实现互斥[15].
这一"不可能性"结论与NFL猜想中"复杂性"的相关的结论具有一定的相似之处:分布式理论表明使用wait-free的变量读/写无法实现互斥;NFL猜想表明使用wait-free的变量读/写无法在多项式时间内确定并发程序访问共享内存的全局顺序.
这两个形式上相似的结论是否有更深层次的内在联系是否有可能使用分布式理论中的相关技术对NFL猜想进行研究本章的理论探讨还揭示了对访存依赖获取既"困难"又"容易"的有趣性质:一方面,NFL猜想及已经证明的部分表明,总存在一个"复杂"的程序,仅通过线程局部的记录获取访存依赖这一问题是有本质的复杂性困难的.
另一方面,尽管导致NP-完全时间复杂性的最坏情况总是存在,但我们提出的局部性理论又表明,现实世界中并发程序的共享内存访问通常遵循特定的模式,即共享内存访问具有线程、空间-线程和同步局部性.
对于具有局部性的程序,获取其访存依赖是相对简单的.
例如若能证明并发程序不存在数据竞争,我们只需对同步事件发生的顺序予以记录即可,此时我们对每个内存访问指令只需添加O(1)的读/写或线程局部计算操作;即使可能存在数据竞争,在运行时高效地检测局部性也能提高访存依赖获取的效率[28].
我们已经看到一些利用访存依赖获取亦难亦易这一特性的研究工作:这些技术虽然在理论上需要求解NP-完全问题,但使用启发式优化和约束求解器却可以使这些研究工作能有效地得到实际程序的访存依赖[74,87].
当我们再次考虑NFL猜想的逻辑结构:P.
M.
((S.
wait-free(P,M,S))→τ.
NPC(τ)),130第六章访存依赖获取复杂性的讨论其中P是程序、M是对P的修改、S是对修改后程序的调度、τ是修改后程序的执行轨迹.
对这一逻辑结构进行拆解,就能发现这一猜想不仅蕴含了引入同步和多项式时间获取访存依赖的矛盾,更揭示了一个更广阔的研究空间:1.
NFL猜想中的P表明了它和局部性理论是不矛盾的.
对于现实中的并发程序P,局部性理论描述了其具有的一些特征,进而促生了一批基于局部性的访存依赖获取技术.
因此扩展局部性理论,更深入地研究现实中并发程序共享内存访问具有的特征,并利用这些特征实现访存依赖的高效获取(甚至有可能通过wait-free的插装就能得到一致的访存依赖),是未来研究工作的重点.
2.
对于一个并非最坏情况的P,很可能M满足S.
wait-free(P,M,S),且根据M修改程序后总能在多项式时间内得到满足顺序一致性的访存依赖.
这启发我们应该对每个P做定制化的修改.
现有技术通常对所有的P都采取完全相同的修改,只有少量研究[85]对P进行了定制化修改的初步尝试.
实际上,对于程序P,很可能只要作出极少的修改,就足以帮助我们在多项式时间内获取访存依赖.
例如我们在尝试扩展文献[57]对VSC问题NP-完全性的证明,并以此证明NFL猜想的特殊情形时发现,只要对原程序增加极少量的读/写操作,就能在多项式时间内恢复满足顺序一致性的执行(因此我们放弃了对原证明的扩展,并提出了全新的证明).
对于任意给定的并发程序,能否根据其访存的特点,用较少的修改获得访存依赖,也是未来研究的方向.
因此,无论最终是否真的存在"免费的午餐",本章从访存依赖获取复杂性的理论探讨出发,最终联系实际并发程序所具有的局部性理论,从一个全新的视角展示了现有工作的空白,帮助我们更深入地理解了访存依赖获取这一问题,对未来可能的研究方向提供了启示.
131第七章总结与展望访存依赖是实现并发程序动态分析(及与之相关的并发程序质量保障技术)的基石.
然而目前访存依赖的相关研究仍存在两点局限:(1)缺乏对访存依赖获取问题的理论认识和对"访存依赖"这一事物的量化研究;(2)缺乏统一的技术框架以研究现有技术的优势与不足.
这两点局限制约了目前访存依赖获取技术的发展,进而影响了基于访存依赖的动态分析技术的发展,导致动态分析应用在真实并发程序中仍面临挑战.
本文针对现有研究的局限,提出了相应的理论框架、技术框架,并在此基础上对访存依赖的获取技术、基于访存依赖的动态分析进行了研究.
本章对全文工作进行了总结,并对未来研究方向予以展望.
7.
1工作总结针对现有研究工作缺乏理论认识、缺乏系统总结的两点局限,我们首先完成了以下框架性的工作:1.
提出了"访存依赖获取"这一问题的理论框架.
首先,理论框架对问题进行了全面的形式化建模,包括并发系统的定义、访存依赖的定义和性质.
其次,为了指导访存依赖获取,我们提出了反映现实程序访问共享内存不均匀(non-uniform)特征的局部性理论,完成了首次对"局部性"的形式化定义和量化研究,在一组现实程序上证实了线程局部性、空间-线程局部性、同步局部性的存在.
2.
在理论框架的基础上,建立了以"四个评价指标、两类获取技术、两类应用"三要素为主线的技术框架,认识到访存依赖获取技术必须在即时性、准确性、高效性、简化性这些指标之间进行权衡,并在这一技术框架下完成了对横跨体系结构、计算机系统、程序设计语言和软件工程四个领域中访存依赖获取的两类技术(在线追踪、离线合成)和两类应用(轨迹分析、并发控制)的综述.
在理论框架和技术框架的共同指导下,对技术框架中已有工作的改进空间和现有技术的空白完成了高效访存依赖获取技术的研究工作:1.
利用线程局部性实现的高效访存依赖获取技术RWTrace.
相比于朴素的互斥锁,RWTrace在访存密集型的程序上能实现多达数百倍的性能提升;132第七章总结与展望2.
利用空间-线程局部性实现的高效访存依赖约减的二分组(bisectionalcoordination)协议.
相比于高度优化的RWTrace,在仅付出0–54.
7%运行时开销的前提下,实现多达97%的访存依赖数量约减.
进而,本文还开展了基于访存依赖的动态分析技术研究:1.
基于访存依赖的并发程序动态分析:基于缓存的执行重放技术CARE相比于使用互斥锁的技术,减少多达数十倍的运行时开销和数百倍的访存依赖数量;基于二分组协议的数据竞争检测和假共享检测技术,能够大幅减少检测调用的数量和元数据维护开销;2.
基于依赖反转的软件测试:应用程序崩溃一致性检测技术C3提出基于编辑距离的测试预言,实现了应用程序崩溃一致性的全自动检测;移动应用的并发测试技术AATT能同时探索移动应用的输入空间和调度空间,暴露其中的并发缺陷.
两项测试技术在知名开源软件中检出前所未知的缺陷.
最后,我们发现至今没有研究工作能在不引入同步的前提下在多项式时间内获取满足顺序一致性访存依赖.
基于这一事实及一些已有的复杂性结论,我们提出了"没有免费午餐"(No-Free-Lunch,NFL)猜想:在只对程序进行wait-free修改的前提下,获得满足顺序一致性访存依赖的时间复杂性是NP-完全的.
我们给出了判定执行轨迹顺序一致性(VSC)问题在一个更受限情况下的证明,并用此技术证明了NFL猜想的一个特殊情形:在仅能对同一共享内存地址作出同样wait-free的修改并且修改能写成一个只读前缀和只写后缀的情况下,无论作出怎样的修改,推导出满足顺序一致性访存依赖的时间复杂性均是NP-完全的.
这一结果可以视作对现有工作的理论总结,并且其分析过程启发了未来可能的研究方向.
7.
2研究展望总结本文开展的针对访存依赖理论框架、技术框架、访存依赖获取技术、基于访存依赖的动态分析和获取访存依赖复杂性的研究,我们发现仍有很多未来可能的研究机遇,现总结如下:1.
已有技术向其他领域的渗透.
由于访存依赖获取问题是并发程序动态分析的基础,其研究分布于多个研究领域.
针对某一应用场景所提出的访存依赖获取技术能否扩展到其他领域的其他应用,是一个值得研究的问题.
我们已经看到一些领域之间融合的例子,例如路径合成技术[74]基于硬件数值合成技术中的约束可满足性问题[87]、使用硬件事务内存能实现数据竞争检测的加速[139].
融合计算机硬件和计算机软件领域的技术是这类7.
2研究展望133研究的关注点之一.
现有的一些使用修改硬件缓存一致性协议的技术(如BulkSC[31])的纯软件实现是一大挑战;反之,软件中使用的技术如何促进硬件相关技术的发展,也是未来可能的研究方向.
例如在硬件层实现本文提出的动态锁指派技术[80]并将若干连续的缓存线进行绑定作为原子处理.
这一融合不仅能够降低访存依赖获取的代价,还可能利用运行时信息(如缓存线之间的空间和线程局部性)实现缓存预取,从而提高多核处理器的执行效率.
2.
基于并发程序自身特性的访存依赖获取.
在NFL猜想及其特殊情形证明中,我们已经发现访存依赖获取是既"困难"又"容易"的.
NFL猜想与并发程序共享内存访问具有的局部性并不矛盾,因此利用并发程序自身的特性,通过巧妙地记录额外信息以实现访存依赖的高效获取是未来可能的研究方向.
目前,有一些研究工作在这一方向上进行了初步的探索:Chen等人利用了时钟信息减少依赖的数量[34];Liu等人使用了程序中的同步操作来降低约束求解的难度[90].
然而,目前对何种信息可以何种方式获取、有怎样的代价、对访存依赖获取有怎样的影响还未有系统性认识.
对这一问题的深入理解势必将促进更高效的访存依赖获取技术.
3.
建模并发程序的执行.
本文提出的局部性理论只是对并发程序建模的初步尝试,一些技术使用的启发式算法的有效性(如CLAP[74]进行约束求解的复杂性)尚不能被局部性理论完美解释.
如能更准确地建模真实世界中的并发程序执行及其特征,则能更好地理解这类技术的优势与不足.
基于建立的模型,已有技术的有效性、优缺点均可直接在理论模型上予以分析;提出的新技术在进行实证研究的同时还能从理论上评估其表现(如在何种情况下表现为多项式时间复杂性,或在模型上对比与其他技术的开销);抑或在现实并发程序的模型上证否NFL猜想,从而最终说明获取访存依赖对于现实并发程序来说确实是"容易"的.
134第七章总结与展望135参考文献[1]ASMtoolkitforbytecodemanipulation.
http://asm.
ow2.
org/.
[2]JVMtoolinterface.
http://docs.
oracle.
com/javase/7/docs/platform/jvmti/jvmti.
html.
[3]TheLLVMcompilerinfrastructure.
http://llvm.
org/.
[4]Processesandthreads.
http://developer.
android.
com/guide/components/processes-and-threads.
html.
[5]UI/ApplicationExerciserMonkey.
https://developer.
android.
com/studio/test/monkey.
html.
[6]TheSingleUNIXSpecification.
http://www.
unix.
org/version3,2002.
[7]JavaSpecificationRequest(JSR)133.
JavaMemoryModelandThreadSpecification.
http://jcp.
org/jsr/detail/133.
jsp,2004.
[8]LinuxKernelblockdriverdocs,2005.
[9]TheScalaProgrammingLanguage.
http://www.
scala-lang.
org,2016.
[10]YehudaAfek,HagitAttiya,DannyDolev,EliGafni,MichaelMerritt,andNirShavit.
Atomicsnapshotsofsharedmemory.
JournalofTheACM,40(4):873–890,1993.
[11]GulAgha.
Actors:AModelofConcurrentComputationinDistributedSystems.
MITPress,1986.
[12]GautamAltekarandIonStoica.
ODR:Output-deterministicreplayformulticoredebugging.
InProceedingsoftheSymposiumonOperatingSystemsPrinciples,SOSP,pages193–206,2009.
[13]C.
ScottAnanian,KrsteAsanovic,BradleyC.
Kuszmaul,CharlesE.
Leis-erson,andSeanLie.
Unboundedtransactionalmemory.
InProceedingsoftheInternationalSymposiumonHighPerformanceComputerArchitecture,HPCA,pages59–69,2005.
136参考文献[14]RemziH.
Arpaci-DusseauandAndreaC.
Arpaci-Dusseau.
OperatingSys-tems:ThreeEasyPieces.
Arpaci-DusseauBooks,0.
91edition,May2015.
[15]HagitAttiya,RachidGuerraoui,DannyHendler,PetrKuznetsov,MagedM.
Michael,andMartinVechev.
Lawsoforder:Expensivesynchronizationinconcurrentalgorithmscannotbeeliminated.
InProceedingsoftheSym-posiumonPrinciplesofProgrammingLanguages,POPL,pages487–498,2011.
[16]TanzirulAzimandIulianNeamtiu.
Targetedanddepth-firstexplorationforsystematictestingofAndroidapps.
InProceedingsoftheInternationalConferenceonObjectOrientedProgrammingSystemsLanguagesandAp-plications,OOPSLA,pages641–660,2013.
[17]DavidF.
BaconandSethCopenGoldstein.
Hardware-assistedreplayofmultiprocessorprograms.
InProceedingsoftheWorkshoponParallelandDistributedDebugging,PADD,pages194–206,1991.
[18]MordechaiBen-Ari.
PrinciplesofConcurrentandDistributedProgramming.
Addison-Wesley,secondedition,2006.
[19]TomBergan,OwenAnderson,JosephDevietti,LuisCeze,andDanGross-man.
CoreDet:Acompilerandruntimesystemfordeterministicmulti-threadedexecution.
InProceedingsoftheArchitecturalSupportforPro-grammingLanguagesandOperatingSystems,ASPLOS,pages53–64,2010.
[20]TomBergan,NicholasHunt,LuisCeze,andStevenD.
Gribble.
Determin-isticprocessgroupsindOS.
InProceedingsoftheConferenceonOperatingSystemsDesignandImplementation,OSDI,pages177–191,2010.
[21]EmeryD.
Berger,TingYang,TongpingLiu,andGeneNovark.
Grace:SafemultithreadedprogrammingforC/C++.
InProceedingsoftheInterna-tionalConferenceonObjectOrientedProgrammingSystemsLanguagesandApplications,OOPSLA,pages81–96,2009.
[22]SanjayBhansali,Wen-KeChen,StuartdeJong,AndrewEdwards,RonMurray,MilenkoDrini,DarekMihoka,andJoeChau.
Frameworkforinstruction-leveltracingandanalysisofprogramexecutions.
InProceedingsoftheInternationalConferenceonVirtualExecutionEnvironments,VEE,pages154–163,2006.
参考文献137[23]PavolBielik,VeselinRaychev,andMartinVechev.
ScalableracedetectionforAndroidapplications.
InProceedingsoftheInternationalConferenceonObjectOrientedProgrammingSystemsLanguagesandApplications,OOP-SLA,pages332–348,2015.
[24]ChristianBienia.
BenchmarkingModernMultiprocessors.
PhDthesis,PrincetonUniversity,January2011.
[25]SwarnenduBiswas,MinjiaZhang,MichaelD.
Bond,andBrandonLucia.
Valor:Efficient,software-onlyregionconflictexceptions.
InProceedingsoftheInternationalConferenceonObjectOrientedProgrammingSystemsLanguagesandApplications,OOPSLA,pages241–259,2015.
[26]BurtonH.
Bloom.
Space/timetrade-offsinhashcodingwithallowableerrors.
CommunicationsofTheACM,13(7):422–426,1970.
[27]MichaelD.
Bond,MilindKulkarni,ManCao,MeisamFathiSalmi,andJipengHuang.
Efficientdeterministicreplayofmultithreadedexecutionsinamanagedlanguagevirtualmachine.
InProceedingsofthePrinciplesandPracticesofProgrammingontheJavaPlatform,PPPJ,pages90–101,2015.
[28]MichaelD.
Bond,MilindKulkarni,ManCao,MinjiaZhang,MeisamFathiSalmi,SwarnenduBiswas,AritraSengupta,andJipengHuang.
OCTET:Capturingandcontrollingcross-threaddependencesefficiently.
InProceedingsoftheInternationalConferenceonObjectOrientedPro-grammingSystemsLanguagesandApplications,OOPSLA,pages693–712,2013.
[29]YanCaiandLingweiCao.
EffectiveandprecisedynamicdetectionofhiddenracesforJavaprograms.
InProceedingsoftheJointMeetingoftheEuropeanSoftwareEngineeringConferenceandtheSymposiumontheFoundationsofSoftwareEngineering,ESEC/FSE,pages450–461,2015.
[30]ManCao,MinjiaZhang,AritraSengupta,andMichaelD.
Bond.
Drinkingfrombothglasses:Combiningpessimisticandoptimistictrackingofcross-threaddependences.
InProceedingsoftheSymposiumonPrinciplesandPracticeofParallelProgramming,PPoPP,pages20:1–20:13,2016.
138参考文献[31]LuisCeze,JamesTuck,PabloMontesinos,andJosepTorrellas.
BulkSC:Bulkenforcementofsequentialconsistency.
InProceedingsoftheInterna-tionalSymposiumonComputerArchitecture,ISCA,pages278–289,2007.
[32]LuisCeze,JamesTuck,JosepTorrellas,andCalinCascaval.
Bulkdisam-biguationofspeculativethreadsinmultiprocessors.
InProceedingsoftheInternationalSymposiumonComputerArchitecture,ISCA,pages227–238,2006.
[33]YufeiChenandHaiboChen.
Scalabledeterministicreplayinaparallelfull-systememulator.
InProceedingsoftheSymposiumonPrinciplesandPracticeofParallelProgramming,PPoPP,pages207–218,2013.
[34]YunjiChen,WeiwuHu,TianshiChen,andRuiyangWu.
LReplay:Apendingperiodbaseddeterministicreplayscheme.
InProceedingsoftheInternationalSymposiumonComputerArchitecture,ISCA,pages187–197,2010.
[35]YunjiChen,ShijinZhang,QiGuo,LingLi,RuiyangWu,andTianshiChen.
Deterministicreplay:Asurvey.
ACMComputingSurveys,48:17:1–17:47,2015.
[36]SigmundCherem,TrishulChilimbi,andSumitGulwani.
Inferringlocksforatomicsections.
InProceedingsoftheConferenceonProgrammingLanguageDesignandImplementation,PLDI,pages304–315,2008.
[37]Jong-DeokChoi,ManishGupta,MauricioSerrano,VugranamC.
Sreedhar,andSamMidkiff.
EscapeanalysisforJava.
InProceedingsoftheInterna-tionalConferenceonObjectOrientedProgrammingSystemsLanguagesandApplications,OOPSLA,pages1–19,1999.
[38]DonCoppersmithandShmuelWinograd.
Matrixmultiplicationviaarith-meticprogressions.
JournalofSymbolicComputation,9(3):251–280,1990.
[39]NorthAmericanElectricReliabilityCouncil.
TechnicalAnalysisoftheAu-gust14,2003,Blackout:WhatHappened,Why,andWhatDidWeLearn,2013.
[40]HemingCui,JiriSimsa,Yi-HongLin,HaoLi,BenBlum,XinanXu,Jun-fengYang,GarthA.
Gibson,andRandalE.
Bryant.
Parrot:Apractical参考文献139runtimefordeterministic,stable,andreliablethreads.
InProceedingsoftheSymposiumonOperatingSystemsPrinciples,SOSP,pages388–405,2013.
[41]HemingCui,JingyueWu,JohnGallagher,HuayangGuo,andJunfengYang.
Efficientdeterministicmultithreadingthroughschedulerelaxation.
InProceedingsoftheSymposiumonOperatingSystemsPrinciples,SOSP,pages337–351,2011.
[42]HemingCui,JingyueWu,Chia-CheTsai,andJunfengYang.
Stabledeter-ministicmultithreadingthroughschedulememoization.
InProceedingsoftheConferenceonOperatingSystemsDesignandImplementation,OSDI,pages207–221,2010.
[43]LukeDalessandro,MichaelF.
Spear,andMichaelL.
Scott.
NOrec:Stream-liningSTMbyabolishingownershiprecords.
InProceedingsoftheSympo-siumonPrinciplesandPracticeofParallelProgramming,PPoPP,pages67–78,2010.
[44]PeterJ.
Denning.
Thelocalityprinciple.
CommunicationsofTheACM,48(7):19–24,2005.
[45]JosephDevietti,BrandonLucia,LuisCeze,andMarkOskin.
DMP:De-terministicsharedmemorymultiprocessing.
InProceedingsoftheArchitec-turalSupportforProgrammingLanguagesandOperatingSystems,ASPLOS,pages85–96,2009.
[46]JosephDevietti,JacobNelson,TomBergan,LuisCeze,andDanGrossman.
RCDC:Arelaxedconsistencydeterministiccomputer.
InProceedingsoftheArchitecturalSupportforProgrammingLanguagesandOperatingSystems,ASPLOS,pages67–78,2011.
[47]DaveDiceandNirShavit.
Understandingtradeoffsinsoftwaretransactionalmemory.
InProceedingsoftheInternationalSymposiumonCodeGenerationandOptimization,CGO,pages21–33,2007.
[48]DaveDiceandNirShavit.
TLRW:Returnoftheread-writelock.
InPro-ceedingsoftheSymposiumonParallelisminAlgorithmsandArchitectures,SPAA,pages284–293,2010.
140参考文献[49]AnneDinningandEdithSchonberg.
Anempiricalcomparisonofmonitoringalgorithmsforaccessanomalydetection.
InProceedingsoftheSymposiumonPrinciplesandPracticeofParallelProgramming,PPoPP,pages1–10,1990.
[50]JulianDolby,ChristianHammer,DanielMarino,FrankTip,MandanaVaziri,andJanVitek.
Adata-centricapproachtosynchronization.
ACMTransactionsonProgrammingLanguagesandSystems,34:4:1–4:48,2012.
[51]GeorgeW.
Dunlap,SamuelT.
King,SukruCinar,MurtazaA.
Basrai,andPeterM.
Chen.
ReVirt:Enablingintrusionanalysisthroughvirtual-machineloggingandreplay.
InProceedingsoftheConferenceonOperatingSystemsDesignandImplementation,OSDI,pages211–224,2002.
[52]GeorgeW.
Dunlap,DominicG.
Lucchetti,MichaelA.
Fetterman,andPe-terM.
Chen.
Executionreplayofmultiprocessorvirtualmachines.
InProceedingsoftheInternationalConferenceonVirtualExecutionEnvi-ronments,VEE,pages121–130,2008.
[53]TayfunElmas,ShazQadeer,andSerdarTasiran.
Goldilocks:Araceandtransaction-awareJavaruntime.
InProceedingsoftheConferenceonPro-grammingLanguageDesignandImplementation,PLDI,pages245–255,2007.
[54]MichaelD.
Ernst.
Staticanddynamicanalysis:Synergyandduality.
InProceedingsoftheWorkshoponDynamicAnalysis,pages24–27,2003.
[55]CormacFlanaganandStephenN.
Freund.
FastTrack:Efficientandprecisedynamicracedetection.
InProceedingsoftheConferenceonProgrammingLanguageDesignandImplementation,PLDI,pages121–133,2009.
[56]CormacFlanaganandStephenN.
Freund.
Adversarialmemoryfordetect-ingdestructiveraces.
InProceedingsoftheConferenceonProgrammingLanguageDesignandImplementation,PLDI,pages244–254,2010.
[57]PhillipB.
GibbonsandEphraimKorach.
Testingsharedmemories.
SIAMJournalonComputing,26:1208–1244,1997.
参考文献141[58]PatriceGodefroid.
Usingpartialorderstoimproveautomaticverificationmethods.
InProceedingsoftheInternationalInternationalComputer-AidedVerification,CAV,pages176–185,1990.
[59]MichelleL.
Goodstein,EvangelosVlachos,ShiminChen,PhillipB.
Gib-bons,MichaelA.
Kozuch,andToddC.
Mowry.
Butterflyanalysis:Adapt-ingdataflowanalysistodynamicparallelmonitoring.
InProceedingsoftheArchitecturalSupportforProgrammingLanguagesandOperatingSystems,ASPLOS,pages257–270,2010.
[60]TimHarris,AdriánCristal,OsmanS.
Unsal,EduardAyguade,FabrizioGagliardi,BurtonSmith,andMateoValero.
Transactionalmemory:Anoverview.
IEEEMicro,27:8–29,2007.
[61]TimHarris,MarkPlesko,AvrahamShinnar,andDavidTarditi.
Optimizingmemorytransactions.
InProceedingsoftheConferenceonProgrammingLanguageDesignandImplementation,PLDI,pages14–25,2006.
[62]MauriceHerlihy.
Wait-freesynchronization.
ACMTransactionsonPro-grammingLanguageandSystems,13(1):124–149,1991.
[63]MauriceHerlihyandJ.
EliotMoss.
Transactionalmemory:Architecturalsupportforlock-freedatastructures.
InProceedingsoftheInternationalSymposiumonComputerArchitecture,ISCA,pages289–300,1993.
[64]MauriceHerlihyandNirShavit.
TheArtofMultiprocessorProgramming.
Elsvevier,2012.
[65]PeterH.
Hofstee.
Futuremicroprocessorsandoff-chipSOPinterconnect.
IEEETransactionsonAdvancedPackaging,27(2):301–303,2004.
[66]NimaHonarmandandJosepTorrellas.
RelaxReplay:Recordandreplayforrelaxed-consistencymultiprocessors.
InProceedingsoftheArchitecturalSup-portforProgrammingLanguagesandOperatingSystems,ASPLOS,pages223–238,2014.
[67]DerekR.
HowerandMarkD.
Hill.
Rerun:Exploitingepisodesforlightweightmemoryracerecording.
InProceedingsoftheInternationalSymposiumonComputerArchitecture,ISCA,pages265–276,2008.
142参考文献[68]Chun-HungHsiaoHsiao,JieYu,SatishNarayanasamy,ZiyunKong,Cris-tianoL.
Pereira,GillesA.
Pokam,PeterM.
Chen,PeterM.
Chen,andJasonFlinn.
Racedetectionforevent-drivenmobileapplications.
InProceedingsoftheConferenceonProgrammingLanguageDesignandImplementation,PLDI,pages326–336,2014.
[69]JeffHuang,PengLiu,andCharlesZhang.
LEAP:Lightweightdeterministicmulti-processorreplayofconcurrentJavaprograms.
InProceedingsoftheSymposiumontheFoundationsofSoftwareEngineering,FSE,pages385–386,2010.
[70]JeffHuang,QingzhouLuo,andGrigoreRosu.
GPredict:Genericpredictiveconcurrencyanalysis.
InProceedingsoftheInternationalConferenceonSoftwareEngineering,ICSE,pages847–857,2015.
[71]JeffHuang,PatrickO'NeilMeredith,andGrigoreRosu.
Maximalsoundpredictiveracedetectionwithcontrolflowabstraction.
InProceedingsoftheConferenceonProgrammingLanguageDesignandImplementation,PLDI,pages337–348,2014.
[72]JeffHuangandCharlesZhang.
Anefficientstatictracesimplificationtech-niquefordebuggingconcurrentprograms.
InProceedingsoftheInterna-tionalStaticAnalysisSymposium,SAS,pages163–179,2011.
[73]JeffHuangandCharlesZhang.
Persuasivepredictionofconcurrencyac-cessanomalies.
InProceedingsoftheInternationalSymposiumonSoftwareTestingandAnalysis,ISSTA,pages144–154,2011.
[74]JeffHuang,CharlesZhang,andJulianDolby.
CLAP:Recordinglocalexe-cutionstoreproduceconcurrencyfailures.
InProceedingsoftheConferenceonProgrammingLanguageDesignandImplementation,PLDI,pages141–152,2013.
[75]SPARCInternationalInc.
TheSPARCArchitectureManualV9,1994.
[76]NicholasJalbertandKoushikSen.
Atracesimplificationtechniqueforef-fectivedebuggingofconcurrentprograms.
InProceedingsoftheSymposiumontheFoundationsofSoftwareEngineering,FSE,pages57–66,2010.
参考文献143[77]YanyanJiang,HaichengChen,FengQin,ChangXu,XiaoxingMa,andJianLu.
Crashconsistencyvalidationmadeeasy.
InProceedingsoftheSymposiumontheFoundationsofSoftwareEngineering,FSE,pages133–143,2016.
[78]YanyanJiang,TianxiaoGu,ChangXu,XiaoxingMa,andJianLu.
CARE:CacheguideddeterministicreplayforconcurrentJavaprograms.
InPro-ceedingsoftheInternationalConferenceonSoftwareEngineering,ICSE,pages457–467,2014.
[79]YanyanJiang,DuLi,ChangXu,XiaoxingMa,andJianLu.
Optimisticsharedmemorydependencetracing.
InProceedingsoftheInternationalConferenceonAutomatedSoftwareEnginnering,ASE,pages524–534,2015.
[80]YanyanJiang,ChangXu,DuLi,XiaoxingMa,andJianLu.
Onlinesharedmemorydependencereductionviabisectionalcoordination.
InProceedingsoftheSymposiumontheFoundationsofSoftwareEngineering,FSE,pages822–832,2016.
[81]YanyanJiang,ChangXu,andXiaoxingMa.
DPAC:AninfrastructurefordynamicprogramanalysisofconcurrencyJavaprograms.
InProceedingsoftheInternationalConferenceonMiddleware,MiddlewareDoctoralSympo-sium,pages2:1–2:6,2013.
[82]LeslieLamport.
Time,clocks,andtheorderingofeventsinadistributedsystem.
CommunicationsofTheACM,21:558–565,1978.
[83]LeslieLamport.
Howtomakeamultiprocessorcomputerthatcorrectlyexe-cutesmultiprocessprograms.
IEEETransactionsonComputers,C-28:690–691,1979.
[84]ThomasJ.
LeblancandJohnM.
Mellor-Crummey.
Debuggingparallelpro-gramswithinstantreplay.
IEEETransactionsonComputers,C-36:471–482,1987.
[85]DongyoonLee,PeterM.
Chen,JasonFlinn,andSatishNarayanasamy.
Chimera:Hybridprogramanalysisfordeterminism.
InProceedingsoftheConferenceonProgrammingLanguageDesignandImplementation,PLDI,pages463–474,2012.
144参考文献[86]DongyoonLee,MahmoudSaid,SatishNarayanasamy,andZijiangYang.
OfflinesymbolicanalysistoinferTotalStoreOrder.
InProceedingsoftheInternationalSymposiumonHighPerformanceComputerArchitecture,HPCA,pages357–358,2011.
[87]DongyoonLee,MahmoudSaid,SatishNarayanasamy,ZijiangYang,andCristianoPereira.
Offlinesymbolicanalysisformulti-processorexecutionreplay.
InProceedingsoftheInternationalSymposiumonMicroarchitecture,MICRO,pages564–575,2009.
[88]NancyG.
LevesonandClarkS.
Turner.
AninvestigationoftheTherac-25accidents.
IEEEComputer,26:18–41,1993.
[89]MikkoH.
Lipasti,ChristopherB.
Wilkerson,andJohnPaulShen.
Valuelocalityandloadvalueprediction.
InProceedingsoftheArchitecturalSup-portforProgrammingLanguagesandOperatingSystems,ASPLOS,pages138–147,1996.
[90]PengLiu,XiangyuZhang,OmerTripp,andYunhuiZheng.
Light:Re-playviatightlyboundedrecording.
InProceedingsoftheConferenceonProgrammingLanguageDesignandImplementation,PLDI,pages55–64,2015.
[91]TongpingLiuandEmeryD.
Berger.
SHERIFF:Precisedetectionandau-tomaticmitigationoffalsesharing.
InProceedingsoftheInternationalConferenceonObjectOrientedProgrammingSystemsLanguagesandAp-plications,OOPSLA,pages3–18,2011.
[92]TongpingLiu,CharlieCurtsinger,andEmeryD.
Berger.
Dthreads:Efficientdeterministicmultithreading.
InProceedingsoftheSymposiumonOperatingSystemsPrinciples,SOSP,pages327–336,2011.
[93]YujieLiu,KunlongZhang,andMichaelSpear.
Dynamic-sizednonblockinghashtables.
InProceedingsoftheSymposiumonPrinciplesofdistributedcomputing,PODC,pages242–251,2014.
[94]ShanLu,SoyeonPark,EunsooSeo,andYuanyuanZhou.
Learningfrommistakes:Acomprehensivestudyonrealworldconcurrencybugcharacteris-tics.
InProceedingsoftheArchitecturalSupportforProgrammingLanguagesandOperatingSystems,ASPLOS,pages329–339,2008.
参考文献145[95]ShanLu,JosephTucek,FengQin,andYuanyuanZhou.
AVIO:detectingatomicityviolationsviaaccessinterleavinginvariants.
InProceedingsoftheArchitecturalSupportforProgrammingLanguagesandOperatingSystems,ASPLOS,pages37–48,2006.
[96]BrandonLucia,LuisCeze,KarinStrauss,ShazQadeer,andHans-J.
Boehm.
Conflictexceptions:Simplifyingconcurrentlanguagesemanticswithprecisehardwareexceptionsfordata-races.
InProceedingsoftheInternationalSymposiumonComputerArchitecture,ISCA,pages210–221,2010.
[97]WayneA.
MadisonandAlanP.
Batson.
Characteristicsofprogramlocali-ties.
CommunicationsofTheACM,19(5):285–294,1976.
[98]PallaviMaiya,AdityaKanade,andRupakMajumdar.
RacedectectionforAndroidapplications.
InProceedingsoftheConferenceonProgrammingLanguageDesignandImplementation,PLDI,pages316–325,2014.
[99]ZhanshuaiMeng,YanyanJiang,andChangXu.
FacilitatingreusableandscalableautomatedtestingandanalysisforAndroidapps.
InProceedingsoftheAsia-PacificSymposiumonInternetware,Internetware,pages166–175,2015.
[100]SangL.
MinandJong-DeokChoi.
Anefficientcache-basedaccessanomalydetectionscheme.
InProceedingsoftheArchitecturalSupportforProgram-mingLanguagesandOperatingSystems,ASPLOS,pages235–244,1991.
[101]PabloMontesinos,LuisCeze,andJosepTorrellas.
DeLorean:Recordinganddeterministicallyreplayingshared-memorymultiprocessorexecutionef-ficiently.
InProceedingsoftheInternationalSymposiumonComputerAr-chitecture,ISCA,pages289–300,2008.
[102]MadanlalMusuvathi,ShazQadeer,ThomasBall,GerardBasler,Pira-manayagamArumugaNainar,andIulianNeamtiu.
FindingandreproducingHeisenbugsinconcurrentprograms.
InProceedingsoftheConferenceonOperatingSystemsDesignandImplementation,OSDI,pages267–280,2008.
[103]SatishNarayanasamy,CristianoPereira,andBradCalder.
Recordingsharedmemorydependenciesusingstrata.
InProceedingsoftheArchitec-turalSupportforProgrammingLanguagesandOperatingSystems,ASPLOS,pages229–240,2006.
146参考文献[104]GonzaloNavarro.
Aguidedtourtoapproximatestringmatching.
ACMComputingSurveys,33(1):31–88,2001.
[105]RobertH.
Netzer.
Optimaltracingandreplayfordebuggingshared-memoryparallelprograms.
InProceedingsoftheWorkshoponParallelandDis-tributedDebugging,PADD,pages1–11,1993.
[106]RobertH.
NetzerandBartonP.
Miller.
Onthecomplexityofeventorder-ingforshared-memoryparallelprogramexecutions.
InProceedingsoftheInternationalConferenceonParallelProcessing,ICPP,pages93–97,1990.
[107]MarkS.
PapamarcosandJanakH.
Patel.
Alow-overheadcoherencesolu-tionformultiprocessorswithprivatecachememories.
InProceedingsoftheInternationalSymposiumonComputerArchitecture,ISCA,pages348–354,1984.
[108]SoyeonPark,ShanLu,andYuanyuanZhou.
CTrigger:Exposingatomicityviolationbugsfromtheirhidingplaces.
InProceedingsoftheArchitec-turalSupportforProgrammingLanguagesandOperatingSystems,ASP-LOS,pages25–36,2009.
[109]SoyeonPark,YuanyuanZhou,WeiweiXiong,ZuoningYin,RiniKaushik,KyuH.
Lee,andShanLu.
PRES:Probabilisticreplaywithexecutionsketch-ingonmultiprocessors.
InProceedingsoftheSymposiumonOperatingSys-temsPrinciples,SOSP,pages177–192,2009.
[110]HarishPatil,CristianoPereira,MackStallcup,GregoryLueck,andJamesCownie.
PinPlay:Aframeworkfordeterministicreplayandreproducibleanalysisofparallelprograms.
InProceedingsoftheInternationalSymposiumonCodeGenerationandOptimization,CGO,pages2–11,2010.
[111]ThanumalayanS.
Pillai,VijayChidambaram,RamnatthanAlagappan,SamerAl-Kiswany,AndreaC.
Arpaci-Dusseau,andRemziH.
Arpaci-Dusseau.
Allfilesystemsarenotcreatedequal:Onthecomplexityofcraftingcrash-consistentapplications.
InProceedingsoftheConferenceonOperatingSystemsDesignandImplementation,OSDI,pages433–448,2014.
[112]MichielRonsseandKoenDeBosschere.
RecPlay:Afullyintegratedpracti-calrecord/replaysystem.
ACMTransactionsonComputerSystems,17:133–152,1999.
参考文献147[113]KennethRussellandDavidDetlefs.
Eliminatingsynchronization-relatedatomicoperationswithbiasedlockingandbulkrebiasing.
InProceedingsoftheInternationalConferenceonObjectOrientedProgrammingSystemsLanguagesandApplications,OOPSLA,pages263–272,2006.
[114]Kari-JoukoRihandEskoUkkonen.
TheshortestcommonsupersequenceproblemoverbinaryalphabetisNP-Complete.
TheoreticalComputerSci-ence,16:187–198,1981.
[115]StefanSavage,MichaelBurrows,GregNelson,PatrickSobalvarro,andThomasAnderson.
Eraser:Adynamicdataracedetectorformultithreadedprograms.
ACMTransactionsonComputerSystems,15:391–411,1997.
[116]KoushikSen.
Racedirectedrandomtestingofconcurrentprograms.
InProceedingsoftheConferenceonProgrammingLanguageDesignandIm-plementation,PLDI,pages11–21,2008.
[117]AritraSengupta,SwarnenduBiswas,MinjiaZhang,MichaelD.
Bond,andMilindKulkarni.
Hybridstatic-dynamicanalysisforstaticallyboundedre-gionserializability.
InProceedingsoftheArchitecturalSupportforProgram-mingLanguagesandOperatingSystems,ASPLOS,pages561–575,2015.
[118]TraianF.
Serbanuta,FengChen,andGrigoreRosu.
Maximalcausalmod-elsforsequentiallyconsistentsystems.
InProceedingsoftheInternationalConferenceonRuntimeVerification,RV,pages136–150,2012.
[119]PeterSewell,SusmitSarkar,ScottOwens,FrancescoZappaNardelli,andMagnusO.
Myreen.
x86-TSO:Arigorousandusableprogrammer'smodelforx86multiprocessors.
CommunicationsofTheACM,53(7):89–97,2010.
[120]NirShavitandDanTouitou.
Softwaretransactionalmemory.
InProceedingsoftheSymposiumonPrinciplesofDistributedComputing,PODC,pages204–213,1995.
[121]JoaoM.
Silva,JoseSimao,andLuisVeiga.
Ditto–DeterministicexecutionReplayability-as-a-ServiceforJavaVMonmultiprocessors.
InProceedingsoftheInternationalMiddlewareConference,Middleware,pages405–424,2013.
148参考文献[122]YannisSmaragdakis,JacobEvans,CaitlinSadowski,JaeheonYi,andCor-macFlanagan.
Soundpredictiveracedetectioninpolynomialtime.
InProceedingsoftheSymposiumonPrinciplesofProgrammingLanguages,POPL,pages387–400,2012.
[123]JosepTorrellas,MonicaS.
Lam,andJohnL.
Hennessy.
Falsesharingandspatiallocalityinmultiprocessorcaches.
IEEETransactionsonComputers,43:651–663,1994.
[124]ChristophvonPraunandThomasR.
Gross.
Objectracedetection.
InPro-ceedingsoftheInternationalConferenceonObjectOrientedProgrammingSystemsLanguagesandApplications,OOPSLA,pages70–82,2001.
[125]JanWenVoung,RanjitJhala,andSorinLerner.
RELAY:Staticracede-tectiononmillionsoflinesofcode.
InProceedingsoftheJointMeetingoftheEuropeanSoftwareEngineeringConferenceandtheSymposiumontheFoundationsofSoftwareEngineering,ESEC/FSE,pages205–214,2007.
[126]JueWang,YepangLiu,ChangXu,XiaoxingMa,andJianLu.
E-GreenDroid:EffectiveenergyinefficiencyanalysisforAndroidapplications.
InProceedingsoftheAsia-PacificSymposiumonInternetware,Internet-ware,pages71–80,2016.
[127]JamesR.
Wilcox,ParkerFinch,CormacFlanagan,andStephenN.
Fre-und.
Arrayshadowstatecompressionforprecisedynamicracedetection.
InProceedingsoftheInternationalConferenceonAutomatedSoftwareEn-ginnering,ASE,pages155–165,2015.
[128]StevenC.
Woo,MoriyoshiOhara,EvanTorrie,JaswinderP.
Singh,andAnoopGupta.
TheSPLASH-2programs:Characterizationandmethod-ologicalconsiderations.
InProceedingsoftheAnnualInternationalSympo-siumonComputerArchitecture,ISCA,pages24–36,June1995.
[129]MinXu,RastislavBodik,andMarkD.
Hill.
Aflightdatarecorderforenablingfull-systemmultiprocessordeterministicreplay.
InProceedingsoftheInternationalSymposiumonComputerArchitecture,ISCA,pages122–135,2003.
[130]MinXu,MarkD.
Hill,andRastislavBodik.
Aregulatedtransitivere-duction(RTR)forlongermemoryracerecording.
InProceedingsofthe参考文献149ArchitecturalSupportforProgrammingLanguagesandOperatingSystems,ASPLOS,pages49–60,2006.
[131]JunfengYang,CanSar,andDawsonEngler.
EXPLODE:Alightweight,generalsystemforfindingseriousstoragesystemerrors.
InProceedingsoftheConferenceonOperatingSystemsDesignandImplementation,OSDI,pages131–146,2006.
[132]ZhemingYang,MinYang,BinyuZang,LvcaiXu,andHaiboChen.
OR-DER:ObjectcentRicDEterministicReplayforJava.
InProceedingsoftheUSENIXAnnualTechnicalConference,ATC,pages1–14,2011.
[133]RichardM.
Yoo,ChristopherJ.
Hughes,KonradLai,andRaviRajwar.
PerformanceevaluationofIntel(R)TransactionalSynchronizationExten-sionsforhigh-performancecomputing.
InProceedingsoftheInternationalConferenceonHighPerformanceComputing,Networking,Storage,andAnalysis,SC,pages1–11,2013.
[134]YuanYu,TomRodeheffer,andWeiChen.
RaceTrack:Efficientdetectionofdataraceconditionsviaadaptivetracking.
InProceedingsoftheSymposiumonOperatingSystemsPrinciples,SOSP,pages221–234,2005.
[135]XiangYuan,ChenggangWu,ZhenjiangWang,JianjunLi,Pen-ChungYew,JeffHuang,XiaobingFeng,YanyanLan,YunjiChen,andYongGuan.
ReCBuLC:Reproducingconcurrencybugsusinglocalclocks.
InProceedingsoftheInternationalConferenceonSoftwareEngineering,ICSE,pages824–834,2015.
[136]CristianZamfirandGeorgeCandea.
Executionsynthesis:Atechniqueforautomatedsoftwaredebugging.
InProceedingsoftheEuropeanConferenceonComputerSystems,EuroSys,pages321–334,2010.
[137]MinjiaZhang,JipengHuang,ManCao,andMichaelD.
Bond.
Low-overheadsoftwaretransactionalmemorywithprogressguaranteesandstrongsemantics.
InProceedingsoftheSymposiumonPrinciplesandPrac-ticeofParallelProgramming,PPoPP,pages97–108,2015.
[138]PingyuZhangandSebastianElbaum.
Amplifyingteststovalidateexceptionhandlingcode.
InProceedingsoftheInternationalConferenceonSoftwareEngineering,ICSE,pages595–605,2012.
150参考文献[139]TongZhang,DongyoonLee,andChangheeJung.
TxRace:Efficientdataracedetectionusingcommodityhardwaretransactionalmemory.
InPro-ceedingsoftheArchitecturalSupportforProgrammingLanguagesandOp-eratingSystems,ASPLOS,pages159–173,2016.
[140]YingZhang,YanyanJiang,ChangXu,XiaoxingMa,andPingYu.
ABC:AcceleratedbuildingofC/C++projects.
InProceedingsoftheAsia-PacificSoftwareEngineeringConference,APSEC,pages182–189,2015.
[141]QinZhao,DavidKoh,SyedRaza,DerekBruening,Weng-FaiWong,andSamanAmarasinghe.
Dynamiccachecontentiondetectioninmulti-threadedapplications.
InProceedingsoftheInternationalConferenceonVirtualExecutionEnvironments,VEE,pages27–38,2011.
[142]MaiZheng,JosephTucek,DachuanHuang,FengQin,MarkLillibridge,ElizabethSYang,BillWZhao,andShashankSingh.
Torturingdatabasesforfunandprofit.
InProceedingsoftheSymposiumonOperatingSystemsDesignandImplementation,OSDI,pages449–464,2014.
[143]MaiZheng,JosephTucek,FengQin,andMarkLillibridge.
UnderstandingtherobustnessofSSDSunderpowerfault.
InProceedingsoftheUSENIXConferenceonFileandStorageTechnologies,FAST,pages271–284,2013.
[144]JinguoZhou,XiaoXiao,andCharlesZhang.
Stride:Search-baseddetermin-isticreplayinpolynomialtimeviaboundedlinkage.
InProceedingsoftheInternationalConferenceonSoftwareEngineering,ICSE,pages892–902,2012.
151简历与科研成果基本信息蒋炎岩,男,汉族,1988年7月出生,江苏省南京市人.
教育背景2011年9月—2017年12月南京大学计算机科学与技术系博士研究生2015年9月—2016年3月美国俄亥俄州立大学计算机科学与工程系访问学者2007年9月—2011年6月南京大学计算机科学与技术系本科学位论文相关的主要学术成果1.
YanyanJiang,TianxiaoGu,ChangXu,XiaoxingMa,andJianLu,CARE:CacheguideddeterministicreplayforconcurrentJavaprograms.
InProceed-ingsofthe36thInternationalConferenceonSoftwareEngineering(ICSE),457–467,2014.
[CCF-A]2.
YanyanJiang,DuLi,ChangXu,XiaoxingMa,andJianLu,Optimisticsharedmemorydependencetracing.
InProceedingsofthe30thInterna-tionalConferenceonAutomatedSoftwareEngineering(ASE),524–534,2015.
[CCF-A]3.
YanyanJiang,ChangXu,DuLi,XiaoxingMa,andJianLu,Onlinesharedmemorydependencereductionviabisectionalcoordination.
InProceedingsofthe24thInternationalSymposiumontheFoundationsofSoftwareEngi-neering(FSE),pages822–832,2016.
[CCF-A]4.
YanyanJiang,HaichengChen,FengQin,ChangXu,XiaoxingMa,andJianLu,Crashconsistencyvalidationmadeeasy.
InProceedingsofthe24thInternationalSymposiumontheFoundationsofSoftwareEngineering(FSE),pages133–143,2016.
[CCF-A]5.
蒋炎岩,许畅,马晓星,吕建.
获取访存依赖:并发程序动态分析基础技术综述,软件学报,28(4):747–763,2017.
152简历与科研成果攻读博士学位期间完成的其他学术成果6.
JueWang,YanyanJiang,ChangXu,QiweiLi,TianxiaoGu,JunMa,XiaoxingMa,andJianLu,AATT+:EffectivelymanifestingconcurrencybugsinAndroidapps.
ScienceofComputerProgramming(SCP),toappear,2017.
[CCF-B]7.
ShengtaoYue,WeizanFeng,JunMa,YanyanJiang,XianpingTao,ChangXu,andJianLu,RepDroid:AnautomatedtoolforAndroidapplicationrepackagingdetection.
InProceedingsofthe25thInternationalConferenceonProgramComprehension(ICPC),132–142,2017.
[CCF-B]8.
TianxiaoGu,XiaoxingMa,ChangXu,YanyanJiang,ChunCao,andJianLu,Synthesizingobjecttransformationfordynamicsoftwareupdating.
InProceedingsofthe39thInternationalConferenceonSoftwareEngineering,(ICSEPosterTrack),2017.
[CCF-A,PosterTrack]9.
QiweiLi,YanyanJiang,TianxiaoGu,ChangXu,JunMa,XiaoxingMa,andJianLu,EffectivelymanifestingconcurrencybugsinAndroidapps.
InProceedingsofthe23rdAsia-PacificSoftwareEngineeringConference(APSEC),209–216,2016.
[CCF-C]10.
XiangyuWu,YanyanJiang,ChangXu,ChunCao,XiaoxingMa,andJianLu,TestingAndroidappsviaguidedgestureeventgeneration.
InProceedingsofthe23rdAsia-PacificSoftwareEngineeringConference(APSEC),201–208,2016.
[CCF-C]11.
JunSui,ChangXu,S.
C.
Cheung,WangXi,YanyanJiang,ChunCao,XiaoxingMa,andJianLu,HybridCPU-GPUconstraintchecking:Towardsefficientcontextconsistency.
InformationandSoftwareTechnology(IST),230–242,2016.
[CCF-B]12.
HaoJin,YanyanJiang,NaLiu,ChangXu,XiaoxingMa,andJianLu,Concolicmetamorphicdebugging.
InProceedingsofthe39thComputerSo-cietyInternationalConferenceonComputers,SoftwareandApplications(COMPSAC),2015.
[CCF-C]13.
YingZhang,YanyanJiang,ChangXu,XiaoxingMa,andPingYu,ABC:AcceleratedbuildingofC/C++projects.
InProceedingsofthe22stAsia-PacificSoftwareEngineeringConference(APSEC),182–189,2015.
[CCF-C]15314.
ZhanshuaiMeng,YanyanJiang,andChangXu,FacilitatingreusableandscalableautomatedtestingandanalysisforAndroidapps,inProceedingsofthe7thAsia-PacificSymposiumonInternetware(Internetware),2015.
15.
XiangyuWu,ChangXu,ZilingLu,YanyanJiang,ChunCao,XiaoxingMa,andJianLu,CoseDroid:Effectivecomputation-andsensing-offloadingforAndroidapps.
InProceedingsofthe39thComputerSocietyInternationalConferenceonComputers,SoftwareandApplications(COMPSAC),2015.
[CCF-C]16.
XiujiangLi,YanyanJiang,YepangLiu,ChangXu,XiaoxingMa,andJianLu,Userguidedautomationfortestingmobileapps.
InProceedingsofthe21stAsia-PacificSoftwareEngineeringConference(APSEC),27–34,2014.
[CCF-C]17.
JunSui,ChangXu,WangXi,YanyanJiang,ChunCao,XiaoxingMa,andJianLu,GAIN:GPU-basedconstraintcheckingforcontextconsistency.
InProceedingsofthe21stAsia-PacificSoftwareEngineeringConference(APSEC),319–326,2014.
[CCF-C]18.
YanyanJiang,ChangXu,andXiaoxingMa,DPAC:AninfrastructurefordynamicprogramanalysisofconcurrencyJavaprograms.
InProceedingsofthe2013MiddlewareDoctoralSymposium,2:1–2:6,2013.
[CCF-B,DoctoralSymposiumTrack]19.
许畅,马晓星,吕建,李其玮,蒋炎岩.
一种安卓应用并发漏洞检测系统:中国,201610952304.
7(授权),2016.
20.
许畅,马晓星,吕建,武翔宇,蒋炎岩.
一种安卓应用的相关手势投放测试框架:中国,201610952301.
3(申请),2016.
21.
马晓星,许畅,吕建,李秀江,蒋炎岩.
一种基于用户执行踪迹重放的移动应用测试方法:中国,201410364808.
8(授权),2014.
攻读博士学位期间参与的科研课题1.
国家自然科学基金重大研究计划集成项目"可信软件理论、方法集成与综合试验平台",No.
91318301;2.
国家重点基础研究发展计划(973计划)项目课题"持续演进的自适应网构软件模型、方法及服务质量保障",No.
2015CB352202;3.
国家自然科学基金重大项目课题"面向演化的群智化软件建模与构造方法",No.
61690204.
154简历与科研成果攻读博士学位期间获得的主要奖励与荣誉1.
奖学金:(a)2016年南京大学优秀博士研究生创新能力提升A计划;(b)2015年国家奖学金、国家公派留学资助;(c)2014年MicrosoftResearchAsiaFellowshipAward(微软学者奖学金);(d)2012年南京大学研究生优秀奖学金.
2.
主要荣誉:(a)2017年"龙芯杯"全国大学生系统能力培养竞赛优秀指导教师(团队位列全国第2名);(b)2016年南京大学学生年度人物;(c)2014年"华为杯"苏-鲁程序设计竞赛冠军;(d)2012年腾讯编程马拉松竞赛亚军、南京大学优秀研究生.
155致谢感谢我的导师吕建教授.
吕老师严谨的治学态度、开阔的视野、敏锐的直觉、科学家的风度都让人景仰.
吕老师总是能站在更高的视角上审视我所做的研究工作,并在方法学层面给予富有智慧的指导意见.
感谢许畅教授和马晓星教授.
感谢两位老师对我研究工作的指导和生活上无微不至的关怀,用宽松又严格的方式培养了我:被改得面目全非的第一次投稿;自信满满的幻灯片却被从头推翻;两位老师无私地帮助我成长和进步,这些痛苦仿佛都变成了最美好的回忆.
感谢俄亥俄州立大学的秦锋副教授在我赴美访问期间的悉心指导,同时也感谢秦老师实验室的徐尔茨和陈海骋,陪伴我顺利完成了访学的任务.
感谢我在美国的室友杨琛和安心,让我在异国他乡却始终有家的感觉.
感谢香港科技大学的S.
C.
Cheung教授和CharlesZhang副教授、德克萨斯州A&M大学的JeffHuang助理教授、南京大学软件研究所的陶先平教授、徐锋教授、黄宇教授、胡昊副教授、曹春副教授、余萍副教授、马骏老师、汪亮老师、姚远老师、魏恒峰老师、张建莹老师、王金路女士等在科研和生活中给我的关心和帮助.
感谢南京大学计算机系的宋方敏教授、袁春风教授、尹一通教授给我的指导和启迪.
感谢南京大学计算机软件研究所的同学们,陪伴我度过读博的时光.
感谢我的父母和爱人,没有你们就没有我今天的成绩.
156致谢