英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料
使用线程控制分析跟踪Java线程中的运行时并发依赖性
--Lulu Wanga, Jingyue Li b, Bixin Li a,lowast;
摘要：
超过75％的Java项目包括某种形式的并发编程。由于多线程之间的复杂交互，并发程序通常比单线程程序更难理解和测试。为了便于理解和测试并发程序，我们开发了一种称为TCP（线程控制分析）的新分析方法。TCP的输出呈现控制依赖的频率，其包括执行的线程的线程创建，线程同步，中断等。TCP首先对Java的详细并发语法和语义进行静态分析，以构建剖析图模型TCDG（线程控制依赖图）。然后将TCDG用于仪器和生成配置文件。我们使用案例研究和一些实验评估了TCP。案例研究表明，TCP方法可以有效地优先考虑测试用例以测试并发程序。一项实验表明，TCP的输出有助于开发人员理解并发代码。其他实验评估了TCP方法引入的各种可能的开销。结果表明，TCP可以以合理的成本提供丰富有用的信息。
关键词：
分析动态，分析并发，Java线程，同步
- 引言：
并发在程序中被广泛使用，它允许线程运行交错和交互。并发具有非常特定于语言的语义。Java是一种面向对象的编程语言，提供并发机制。在实践中，并发性是Java项目中非常常用的机制（Pinto等，2015）。与单线程程序不同，分解多线程之间的混乱交互通常非常具有挑战性。因此，并发程序通常很难理解和测试。程序员经常滥用并发编程结构。只有大约3％的项目处理线程异常，这可能导致应用程序性能的缺陷或恶化（Pinto et al。，2015）。在现实世界的应用程序中，几乎不可能确保 并发程序的行为符合预期。因此，对并发元素进行排序非常重要，以显示哪些元素应该被赋予更高的测试和质量保证优先级。
在本文中，我们使用“执行频率”来确定线程的优先级控制依赖。线程控制依赖是一个正在运行的线程与它控制的另一个线程之间的依赖关系。线程控制依赖性是导致并发程序中线程交互复杂性的最重要方面之一。由于未执行的依赖不能有助于或损害程序的功能，依赖于专业执行的重要性在很大程度上取决于其“执行频率”，即概况。
程序分析提供了各种程序元素中运行频率的动态视图，包括CFG（控制流图）边缘（球和拉鲁斯, 1994）和路径（球和拉鲁斯, 1996年），事件（Malony和Huck，2014年），资源（芬克勒，2010年），依赖（Baswana等，2013）和表演（Mi等，2012）， 等等。此类配置文件提供了有关程序如何在大量执行过程中运行的分布的深入视图。分析结果可用于程序分析和改进，包括优化，测试和程序理解（胡等人，2013; Dong et al。，2016）。分析过程通常包含三个步骤（a）探测仪器，即将探针（不改变原始程序功能的语句）插入源代码中;（b）在计划执行期间收集资料;（c）轮廓生成，其中计算探针的执行频率。据我们所知，没有配置文件的技术线程控制依赖。在本研究中，我们将重点放在一种实用的分析技术上，该技术可以通过强大的同步方案直接用于Java并发程序
Java该研究的目的是开发工具以便于分析，理解和测试并发程序，尤其是并发Java程序。在并发Java程序中，程序单元的执行顺序不是由静态结构决定的。相反，在生成和执行线程时决定程序的执行顺序。线程中的依赖关系和规则是预先设置的，但运行具有无限的可能性。因此，理解，测试或分析具有并发性的程序并不容易。通过关于线程控制依赖性的配置文件，我们可以解决此类问题并更好地了解线程在运行时如何相互影响。
我们在研究中讨论的主要问题是如何为动态控制流中的线程依赖生成配置文件。我们的分析方法TCP是一种检测Java程序的线程控制依赖性的新方法（版本为JDK 1.7，也称为JDK 7）。TCP首先构造TCDG，然后在TCDG上处理TCP的检测，并在执行检测的程序之后输出配置文件。我们的评估结果表明，TCP可以以合理的成本提供丰富的并发信息。
本文的其余部分安排如下：第2节 解释与本研究相关的概念和理论;第3节 解释了我们的TCP方法的设计和实现;第4节 提出评估结果;第5节 总结并介绍相关工作;和第6节 总结。
- 相关概念和理论
编写高质量的并发程序非常困难。诸如死锁，错误调用和线程饥饿等问题使程序员难以编写无错误的软件。
解决这些问题的一种流行方法是使用形式验证，例如模型检查（Qadeer和Rehof，2005年）。形式验证方法通常建立并发程序行为的抽象近似，并在并发性是否正确时提供安全的结论。但是，形式验证方法具有以下缺点：
制作模型非常昂贵，特别是在复杂，灵活和大规模的现实世界节目中;
这些模型很难完全准确，因为它需要从程序到模型的非常有见地和细致的过渡
验证输出可能在状态空间而不是程序语句中显示，这使得很难在代码中找到错误并修复错误
分析提供了另一种帮助检测和纠正并发程序错误的方法。由于重现线程之间的交互是域中的关键问题之一，因此分析线程如何控制彼此的执行非常有用
-
- 相关的技术分析
与收集综合运行数据的程序跟踪不同，程序分析是轻量级的，并提供程序某些部分的执行频率。统一的分析过程通常包括三个步骤：
仪表。分析技术的第一步是将仪器探针插入原始程序。仪器用于在程序执行中收集必要的信息。探针永远不应该改变原始程序的功能，即仪器之前和之后的两个程序应该具有相同输入的相同输出。
执行。在程序执行期间，检测的探针在执行时进行必要的操作。探针可以编码或给出关于如何在当前执行中激活分析目标的标记。
计算。在使用仪表化探针重复执行程序时，有效地累加分析目标的频率（如果预先使用编码则应该执行解码）以生成最终分布
概要文件由两部分组成：要分析的程序中的主题，以及它们在程序执行中的相应执行频率。为了描述程序中的不同目标，应特别设计探针和仪器，并且应保持相应的计算一致。
最相关的分析技术列于表格1，它显示了不同的分析主题（要分析的内容），以及分析技术是否支持编码，选择性设置（分析部分主题而不是所有主题），循环，过程间和并发/并行程序。
在这项研究中，我们的分析目标是线程控制依赖。因此，我们的概况包括控制依赖及其执行频率。我们研究中的依赖性被描述为编码号或具有相应依赖类型的程序位置（在哪个文件的哪一行）。
2.2. 相关概念
2.2.1. 控制依赖
控制依赖（Ball和Horwitz，1993年）是一个二进制关系，它首先在程序切片中出现。控制依从性是从控制流程图构建的，并且是程序内的。
2.2.1.1. 控制依赖。假设G是控制流图，X和Y是G中的节点.Y是控制依赖于X iff（1）存在从X到Y的有向路径P，P中的每个节点（不包括X和Y）都是后 - 由Y和（2）X支配不由Y支配。
过程间控制依赖性可用于描述影响彼此执行的程序元素，例如方法调用，线程同步和主机通信。通过使用具有特定语义的方法调用来实现线程同步和主机通信。
控制依赖性和数据依赖性相互作用。它们共同提供了程序元素之间关系的完整视图。具体而言，可以独立提取控制依赖性，并且是数据流分析的基础。
2.2.2. Java并发
Java和Java虚拟机（JVM）支持并发编程。在Java中，代码作为线程执行。每个线程都与Thread类的实例相关联。可以使用Thread对象直接管理线程，也可以使用线程方法调用的抽象机制来管理线程。线程必须同步。线程同步确保一次只有一个线程修改对象。因此，
不允许线程访问部分更新的对象，这些对象是由另一个线程修改的对象。Java有很多方法可以实现同步，例如Notify，FutureGet，Countdown，Signal和Semaphore。
线程也相互依赖。在Java程序中，线程依赖主要可以分为两类：
线程控制依赖。线程alpha;直接影响beta;的执行（包括开始，暂停，恢复和结束）通过调用特定方法1 在并发机制中，可能因此间接影响与beta;相关的变量值。
线程数据依赖。线程alpha;直接影响与beta;相关的变量值，因此可能间接影响beta;的执行。
在我们的研究中，我们专注于线程控制依赖。线程控制依赖在并发程序中被广泛使用，并且可以在多线程程序执行中提供关于控制流的直接信息。
2.2.3. Java线程控制依赖
有许多与 Java 并发相关的依赖图类型。一些依赖图（如（Hammacher等，2009）和（J.Louml;nnberg等，2011））没有详细的线程间依赖性分类。其他依赖图（如（赵，1999) (陈和徐，2001; Singh等，2015））基本上由几种类型的依赖项组成，即线程内控制和数据依赖，方法调用，参数依赖，同步依赖和线程间数据依赖。
但是，当我们关注Java程序中的线程控制依赖关系时，以及当我们想知道一个线程如何控制另一个线程的运行时，从现有方法生成的控件依赖关系图不适用，因为：
bull; 从现有方法生成的控制依赖图包含数据依赖性，这使得图形复杂化。
bull; 不同类型的依赖性可以在Java特定的线程控制依赖性中交织（例如，在“权限”中，应该使用所有的调用，参数和同步的依赖性）。因此，必须进行清晰且细粒度的线程间依赖性分类。
- TCP设计和实现
在本节中，我们将介绍如何使用TCP方法生成特定程序的配置文件。图。1 显示了TCP的主要过程。与一般性能分析过程一样，我们的TCP方法还包括三个高级步骤，即检测，执行和计算。
TCP的检测包括以下子步骤：
bull; 静态分析并发程序的源代码，用于检测：
a) 线程对象。找出新线程在源代码中以线程对象（无论是否匿名）开始的位置。
b) 线程控制依赖。使用已建立的类型和功能找出源代码中的线程控制依赖性。
bull; 构建TCDG。通过使用CFG的节点和边缘以及线程控制依赖来形成TCDG。
bull; 制作仪器。获取必要的探针，这些探针应该基于TCDG检测到源代码中，然后进行检测。
在下面的第3.1节 至3.3，我们对TCP方法的检测步骤给出了更详细的解释。
bull; 在第3.1节，我们解释了如何将Java线程控制依赖关系汇总和分类为不同的类型，以及我们如何提取每种类型的相应特征;
bull; 在第3.2节，我们解释如何自动检测线程控制依赖并用于构建TCDG;
bull; 在第3.3节，我们解释了如何使用TCDG对目标程序执行检测算法，以及如何将探针插入到源代码中。
3.1. 我们对线程控制依赖类型及其特征的总结
在Java程序中，线程控制依赖可以分为六类，即线程启动，中断，通知，授权获取，授权发布和Future-Get。据我们所知，每种类型的线程控件分别具有以下特征。
3.1.1. 线程启动
已经运行的线程通过以下两种可能的方法之一触发新线程，并启动新线程。
bull; 初始化线程对象并显式调用该方法。
bull; 初始化线程对象并隐式调用它的开始，例如ForkJoinPool，Executor和ExecutorService。
3.1.2. 中断
中断是一个线程的指示，线程应该停止正在做的事情并做其他事情 。 中 断 机 制 使 用 称 为 中 断 状 态 的 内 部 标 志 来 实 现 。 调 用Thread.interrupt会将此标志设置为true。在Java中，中断告诉线程它应该停止。但是，停止或不停止由中断的线程本身决定。
3.1.3. 通知
在线程执行期间，线程会相互通信并影响彼此的执行。通常使用两种类型的节点来描述通知关系：块节点和通知节点。块节点暂停正在控制的线程的运行，并且通知节点继续其运行
Java程序中有四种类型的块通知
bull; notify和notifyAll方法继承自超类Object。
bull; 淘汰倒计时机制。
bull; 方法signal和signalAll用于条件变量。
bull; 声明基于Phaser类到达。
对于Java程序中的每种类型的块通知，相应的块节点分别是wait，await，await和awaitAdvance。
3.1.4. 权力获得和权力释放
当线程需要访问相同的关键资源时，两种类型的对象（即ReentrantLock和Semaphore）用于实现权限获取和权限释放以调度线程的机制。ReentrantLock是一个可重入的互斥锁与使用synchronized方法和语句访问的隐式监视器锁相同的基本行为和语义，但具有扩展功能。ReentrantLock由成功锁定的最后一个线程拥有，但尚未解锁。ReentrantLock主要用于调用两个方法，即lock（）to获取权限，解锁（）以释放权限。成功获取后，调用lock（）的线程返回锁，当锁不属于另一个线程时。如果当前线程已拥有锁，则该方法将立即返回
信号量通常用于限制数量线程可以访问某些（ 物理或逻辑 ）资源，相应的方法调用是acquire（）和release（）。如果需要，每个acquire（）都会阻止其他获取者，直到获得许可
是可用的，然后接受它。每个版本（）都会添加一个许可证，最终释放阻塞收购者。但是，不使用实际的许可对象。信号量只是保留可用数量的数量并相应地采取行动。总之，Semaphore具有与ReentrantLock类似的结构，但Semaphore不是可重入的。
3.1.5. 未来-GET
Future表示异步计算的结果。提供方法以检查计算是否完成，等待其完成，以及检索计
全文共16512字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[1121]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
