Boundedness vs. Unboundedness of Lock Chains: Characterizing Decidability of Pairwise CFL-Reachability for Threads Communicating via Locks
Boundedness vs. Unboundedness of Lock Chains: Characterizing Decidability of Pairwise CFL-Reachability for Threads Communicating via Locks
复制标题
锁链的有界性与无界性：表征成对 CFL 的可判定性 - 通过锁进行通信的线程的可达性
DOI：
10.1109/lics.2009.45
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Vineet Kahlon
中科院分区：
文献类型：
--
作者：
Vineet Kahlon
成对的CFL可行性的问题是，在线程中存在递归和安排同步基元素施加的递归的情况下，在不同线程中提供了两个给定的程序位置。分析可以通过锁链来表征同时的程序，如果相邻（未扣除）静音的示波器重叠，则据说将一系列静音锁链，尽管已知成对的意识可以通过嵌套锁相互作用，即，即一长中，这些技术不会扩展到在数据库和设备驱动程序等关键应用程序中使用的非巢锁的程序。现实生活中的锁定模式不会产生无限制的锁定链，我们证明了我们的新结果缩小了对成对CFL的决策差异。锁链的界限，而不是当前最新的锁，即锁的嵌套（长度为一条）。
The problem of Pairwise CFL-reachability is to decide whether two given program locations in different threads are simultaneously reachable in the presence of recursion in threads and scheduling constraints imposed by synchronization primitives. Pairwise CFL-reachability is the core problem underlying concurrent program analysis especially dataflow analysis. Unfortunately, it is undecidable even for the most commonly used synchronization primitive, i.e., mutex locks. Lock usage in concurrent programs can be characterized in terms of lock chains, where a sequence of mutex locks is said to be chained if the scopes of adjacent (nonnested) mutexes overlap. Although pairwise reachability is known to decidable for threads interacting via nested locks, i.e., chains of length one, these techniques don’t extend to programs with non-nested locks used in crucial applications like databases and device drivers. In this paper, we exploit the fact that lock usage patterns in real life programs do not produce unbounded lock chains. For such programs, we show that pairwise CFL-reachability becomes decidable. Our new results narrow the decidability gap for pairwise CFL-reachability by providing a more refined characterization for it in terms of boundedness of lock chains rather than the current state-of-the-art, i.e., nestedness of locks (chains of length one).