【24h】

The Theory of Deadlock Avoidance via Discrete Control

机译:通过离散控制避免死锁的理论

获取原文
获取原文并翻译 | 示例
获取外文期刊封面目录资料

摘要

Deadlock in multithreaded programs is an increasingly importantproblem as ubiquitous multicore architectures force parallelizationupon an ever wider range of software. This paper presents a the-oretical foundation for dynamic deadlock avoidance in concurrentprograms that employ conventional mutual exclusion and synchro-nization primitives (e.g., multithreaded C/Pthreads programs). Be-ginning with control flow graphs extracted from program sourcecode, we construct a formal model of the program and then ap-ply Discrete Control Theory to automatically synthesize deadlock-avoidance control logic that is implemented by program instrumen-tation. At run time, the control logic avoids deadlocks by postpon-ing lock acquisitions. Discrete Control Theory guarantees that theprogram instrumented with our synthesized control logic cannotdeadlock. Our method furthermore guarantees that the control logicis maximally permissive: it postpones lock acquisitions only whennecessary to prevent deadlocks, and therefore permits maximal run-time concurrency. Our prototype for C/Pthreads scales to real soft-ware including Apache, OpenLDAP, and two kinds of benchmarks,automatically avoiding both injected and naturally occurring dead-locks while imposing modest runtime overheads.
机译:随着无所不在的多核体系结构迫使并行化在越来越多的软件上进行,多线程程序中的死锁问题变得越来越重要。本文为使用常规互斥和同步原语的并发程序(例如,多线程C / Pthreads程序)中的动态死锁避免提供了理论基础。首先从程序源代码中提取控制流程图,我们构造程序的形式模型,然后应用离散控制理论自动合成由程序指令实现的避免死锁控制逻辑。在运行时,控制逻辑通过延迟锁获取来避免死锁。离散控制理论保证了采用我们综合控制逻辑的程序不会死锁。我们的方法进一步保证了控制逻辑是最大允许的:它仅在防止死锁的必要时才延迟锁获取,因此允许最大的运行时并发。我们的C / Pthreads原型可扩展到包括Apache,OpenLDAP和两种基准测试在内的实际软件,可自动避免注入的死锁和自然发生的死锁,同时增加适度的运行时开销。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号