The theory of deadlock avoidance via discrete control

摘要: Deadlock in multithreaded programs is an increasingly important problem as ubiquitous multicore architectures force parallelization upon ever wider range of software. This paper presents a theoretical foundation for dynamic deadlock avoidance concurrent that employ conventional mutual exclusion and synchronization primitives (e.g., C/Pthreads programs). Beginning with control flow graphs extracted from program source code, we construct formal model the then apply Discrete Control Theory to automatically synthesize deadlock-avoidance logic implemented by instrumentation. At run time, avoids deadlocks postponing lock acquisitions. guarantees instrumented our synthesized cannot deadlock. Our method furthermore maximally permissive: it postpones acquisitions only when necessary prevent deadlocks, therefore permits maximal runtime concurrency. prototype scales real software including Apache, OpenLDAP, two kinds benchmarks, avoiding both injected naturally occurring while imposing modest overheads.