基于记录重播的嵌入式系统死锁检测方法

席卫华

摘要：针对嵌入式系统死锁缺陷问题，提出了一种基于Lamport clock插桩记录的嵌入式系统死锁检测方法——LPM（Lamport clock Pile Record Deadlock Detection Method）。首先利用Lamport clock对嵌入式程序线程关系、资源依赖关系进行记录，然后离线提取日志记录信息，获取资源图并进行死锁检测。仿真实验表明，与经典的插桩机制相比，该方法可有效降低插桩开销并能准确检测出死锁。

关键词：嵌入式系统；LPM；Lamport clock；插桩；死锁检测

DOIDOI：10.11907/rjdk.172076

中图分类号：TP306

文献标识码：A 文章编号：1672-7800（2017）012-0022-04

Abstract：Aiming at the problem that the deadlock of the embedded system is more difficult than the usual computer software， a deadlock detection method based on Clock Lamport interpolation is presented in this paper—LPM（Lamport clock Pile Record Deadlock Detection Method）. In this method， the Lamport clock is used to record the relationship between the thread and the resource dependence. Then the log information is extracted， the resource map is obtained and the deadlock detection is carried out. Experimental simulation results have shown that this method can effectively reduce the overhead of the pile， and can detect the deadlock accurately.

Key Words：embedded system； LPM； lamport clock； pile record； deadlock detection

0 引言

随着嵌入式系统性能要求的提高，并发多线程程序设计在嵌入式系统中的应用越来越广泛。嵌入式系统特点是体积小、资源和计算能力有限、程序的执行依赖外部输入。因此，嵌入式软件的并发缺陷比通常的计算机软件更加棘手。死锁是并发缺陷的典型问题，有时会导致整个嵌入式系统陷入瘫痪，严重影响嵌入式系统的稳定性、可靠性[1]。由于死锁难以再现和修正，如何有效检测死锁成为嵌入式软件领域的研究重点。

目前死锁的检测方法主要有静态检测和动态检测。静态检测原理是通过分析源代码进行抽象，构建出状态模型，进而发现潜在的死锁。文献[2，3]设计了基于数据流分析源代码的框架，该框架根据函数、指针等参数构建资源图，并利用环检测等算法检测出死锁。文献[4]通过对程序的预处理获取中间代码、函数依赖关系和控制流图等，进而得到线程之间的函数调用图，并利用Petri[5]网模型进行死锁检测。动态检测原理是通过对运行时的程序插入探针代码，从而获得程序的运行状态和数据信息实现死锁检测，它避免了抽象模型和可执行程序之间不一致问题[6]。动态检测典型工具有Intel Pin[7]和FastTrack[8]。Pin是Intel公司推出的一款动态二进制分析框架，利用Pin提供的API，在可执行二进制代码中插入探测函数从而获取程序运行时的数据和状态变量等。FastTrack基于文献[9，10]提出的DJIT+探测机制进行改进，用轻量级的自适应VCs[11]（Vector Clocks）代替原本繁重的VCs，使其在确保探测精度的情况下减少探针开销。

虽然上述方法在一定程度上实现了死锁检测，但还存在不足：

（1）嵌入式软件的静态死锁检测一般采用保守方法进行变量值估计，需要在电脑端对源码进行分析，而嵌入式软件依赖外部输入，具有突发性和实时性，因此检测结果误报率较高，且缺乏精确的运行信息。

（2）较大的性能开销是所有动态死锁检测工具共同面临的问题，特别是对于嵌入式系统而言，其程序的执行、线程的开创等都依赖于外部输入，而外部输入又是实时突發的，所以嵌入式软件对探针效应[12]的敏感度要远高于桌面软件。

本文提出一种基于插桩记录的嵌入式系统死锁检测方法。该方法分为两个阶段：①对嵌入式程序线程关系、资源依赖关系的记录阶段；②对记录日志信息提取，获取资源图并进行检测的死锁检测阶段。相比于静态检测方法，基于插桩记录的嵌入式系统死锁检测机制能提供更准确的运行信息，对潜在的死锁进行更准确的检测。相对于传统的动态检测机制，该方法能有效减小插桩开销。

1 嵌入式死锁检测机制

基于插桩的程序都是在插桩引擎上加入自定义的程序分析工具，这类工具往往会对被测程序产生影响。由于这类工具结构原理大同小异，因此，下面以典型的Intel Pin插桩工具（以下简称Pin）为例进行分析。

在利用Pin插桩工具进行程序分析时，被测程序和分析程序是交叉运行的，当程序运行到插桩点时，程序会产生中断，保存现场，然后根据采集到的数据执行分析程序。执行完分析程序后，恢复现场并继续执行被测程序。如图1所示，可以很明显地看出，Pin工具的性能开销很大一部分来源于被测程序到分析程序之间的切换和分析程序的执行。