Detecting Deadlocks Involving Diverse Synchronization Mechanisms Using Extended Petri Nets

详细信息    查看全文

• 作者：Yunkai Du ; Naijie Gu ; Huaxiong Cao
• 关键词：Deadlock detection ; Petri nets ; APNs ; Diversity ; Synchronization
• 刊名：Arabian Journal for Science and Engineering
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：42
• 期：2
• 页码：913-923
• 全文大小：
• 刊物类别：Engineering
• 刊物主题：Engineering, general; Science, Humanities and Social Sciences, multidisciplinary;
• 出版者：Springer Berlin Heidelberg
• ISSN：2191-4281
• 卷排序：42

文摘

Synchronization mechanisms provide flexibility for concurrent programming. However, they also increase the difficulty of deadlock detection, since detection methods have to consider deadlocks caused by different mechanisms and their attributes. Traditional deadlock detection techniques are for deadlocks that involve a few types of synchronization mechanisms, typically mutex only. This paper introduces extensions of Petri nets, called Attribute Petri nets (APNs), which focus on modelling most kinds of synchronization mechanisms and their attributes. APNs are constructed in a modular way; therefore, new synchronization mechanisms can be easily hooked to APNs, each of which is developed as an independent APNs plugin. A tool called SniperX has been developed to analyse C/C++ threaded programs that use the Pthreads (POSIX threads, a POSIX standard for threads), containing plugins for mutual exclusions, semaphores, barriers, condition variables, etc. We have applied it to some open source multithreaded systems and a large commercial system, finding several previously unknown deadlocks that involve multiple synchronization mechanisms.