...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>ACM Transactions on Programming Languages and Systems >Interprocedural Slicing of Multithreaded Programs with Applications to Java
【24h】

Interprocedural Slicing of Multithreaded Programs with Applications to Java

机译：多线程程序与应用程序到Java的过程间切片

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Slicing is a well-known program reduction technique where for a given program P and a variable of interest v at some statement p in the program, a program slice contains those set of statements belonging to P that affect v. This article presents two algorithms for interprocedural slicing of concurrent programs—a context-insensitive algorithm and a context-sensitive algorithm. The context-insensitive algorithm is efficient and correct (it includes every statement that may affect the slicing criterion) but is imprecise since it may include certain extra statements that are unnecessary. Precise slicing has been shown to be undecidable for concurrent programs. However, the context-sensitive algorithm computes correct and reasonably precise slices, but has a worst-case exponential-time complexity. Our context-sensitive algorithm computes a closure of dependencies while ensuring that statements sliced in each thread belong to a realizable path in that thread. A realizable path in a thread with procedure calls is one that reflects the fact that when a procedure finishes, execution returns to the site of the most recently executed call in that thread. One of the novelties of this article is a practical solution to determine whether a given set of statements in a thread may belong to a realizable path. This solution is precise even in the presence of recursion and long call chains in the flow graph. The slicing algorithms are applicable to concurrent programs with shared memory, interleaving semantics, explicit waitotify synchronization and monitors. We first give a solution for a simple model of concurrency and later show how to extend the solution to the Java concurrency model. We have implemented the algorithms for Java bytecode and give experimental results.
机译：切片是一种众所周知的程序简化技术，其中对于给定程序P和程序中某个语句p处的感兴趣变量v，程序切片包含属于那些影响v的P的语句集。本文介绍了两种算法并发程序的过程间切片—上下文无关的算法和上下文敏感的算法。上下文无关的算法是高效且正确的（它包括可能影响切片标准的每条语句），但由于它可能包含某些不必要的额外语句，因此不精确。对于并行程序，精确切片已显示不确定。但是，上下文敏感算法可计算正确且合理的切片，但具有最坏情况的指数时间复杂度。我们的上下文相关算法在计算依赖关系的闭包的同时，确保每个线程中切片的语句属于该线程中的可实现路径。具有过程调用的线程中可实现的路径是一种反映以下事实的过程：过程完成后，执行将返回该线程中最近执行的调用的位置。本文的新颖性之一是一种实用的解决方案，用于确定线程中的给定语句集是否可能属于可实现的路径。即使流程图中存在递归和长调用链，该解决方案也是精确的。切片算法适用于具有共享内存，交错语义，显式等待/通知同步和监视器的并发程序。我们首先为简单的并发模型提供解决方案，然后展示如何将解决方案扩展到Java并发模型。我们已经为Java字节码实现了算法，并给出了实验结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号