多处理机系统的死锁检测方法【综述】.pdf

多处理机系统的死锁检测方法 摘要：在多处理机系统中，并发性得到了有效利用，但并发程序的不确定性使得死锁检测 十分困难。针对现有的工作集中在使用分析、验证或测试的单一途径来检测死锁这一问题， 本文通过分析现有工具的死锁检测能力，提出了综合使用工具的死锁检测方法。同时根据 析、验证和测试途径的不同特点，给出了评估工具检测结果的度量方法，并通过实验验证了 该方法的有效性。 关键词：死锁检测；工具评估；工具综合应用；处理机 Abstract：The non-determinism in concurrent software obstructs the detection of deadlocks. Previous work focuses on detecting deadlocks by only using a single approach or a single tool. This paper evaluates the capabilities of contemporary deadlockdetectiontools.Basedonthecomparisonresults，anintegratedapplication ofdeadlockdetectiontoolsisproposed，which incorporatesalldetectionapproaches from analysis，verification to testing. Moreover a set of metrics ispresented to assess the detection results of these tools based on the different nature of analysis，verification and testing. The empirical results show the effectiveness of this method. Keywords：deadlock detection；tool evaluation；integratedapplication of tools； multiprocessorsystem 1 引言 多处理机系统是由两个或多个处理机合作完成一项任务的计算机体系结构[1]。近年来， 随着大量并发任务的出现，如互联网服务以及大规模数据处理的问世，多处理机系统的优势 日益明显。多处理机系统可在多个计算核上同时执行任务，大大提高了计算效率；同时由于 各并发线程可以共享数据存储，也节省了资源开销。但是多处理机系统在提供高效率的同时 也面临诸多困难，这主要源于并发程序固有的不确定性：即使针对同一个程序的两次运行， 并发程序也可能得到不同的结果。并发程序的不确定性是由程序执行过程中并发事件发生时 序的不确定引起的。使用单线程程序的常规测试方法测试并发程序有两个难点：一是难以控 制程序覆盖期望的执行轨迹；二是难以自动化地比较测试结果。 死锁缺陷是一类常见的并发缺陷。死锁出现时会使整个系统陷于瘫痪，严重影响系统的 可靠性、可用性；更为严重的是许多对安全性要求极高的软件系统如飞行、能源控制系统都 是并发软件，一旦发生死锁将会产生灾难性的后果。同时死锁的发生又具有不确定性，难以 再现，因此死锁一直是开发者和测试者关注的重点。一大批死锁检测算法和工具应运而生， 它们按检测途径可分为分析、验证和测试；按是否执行代码可分为静态检测和动态检测；按 检测对象可分为基于模型和基于代码的工具，其研究成果可谓十分丰富。但是目前的研究工 作仍存在几点不足，影响了这些方法和工具的使用效果：（1）工具的检测能力的分析和评估 不足。现有工作对死锁检测工具方法的评估仅限于对工具性能的比较[2-3]，而缺乏对检测能 力的深入分析和评估。（2）检测手段单一。绝大多数检测工具只使用一种检测途径，或分析、 或验证、或测试。对于死锁缺陷的检测，各途径的检测能力是不同的。（3）在使用众多工具 之后，缺乏科学合理的评价。如何根据检测结果评估软件摆脱死锁的程度，是每一个并发软 件开发者和测试者最为关心的问题，但是尚无针对该问题的研究。 为解决以上问题，进行了并发软件死锁检测工具的能力分析和综合应用的研究。针对检 测能力评估不足的问题，在认真研究了死锁产生的机理和引发死锁的机制的基础上，对现有 的死锁检测工具的检测能力做了深入的分析和评估，比较了各工具检测能力的差异；针对检 测手段单一的问题，提出了同时使用分析、验证和测试工具的综合应用方法，最大程度地检 测死锁；针对