Deadlock Detection: Background, Techniques, and Future Improvements

doi:10.12142/ZTECOM.202402009

ZTE Communications ›› 2024, Vol. 22 ›› Issue (2): 71-79.DOI: 10.12142/ZTECOM.202402009

• Review • Previous Articles Next Articles

Deadlock Detection: Background, Techniques, and Future Improvements

LU Jiachen¹(), NIU Zhi², CHEN Li², DONG Luming², SHEN Taoli¹

^1.Zhejiang University, Hangzhou 310058, China
^2.ZTE Corporation, Xi’an 710114, China

Received:2023-12-19 Online:2024-06-28 Published:2024-06-25
About author:LU Jiachen (lujc@zju.edu.cn) is a master student in cybersecurity at Zhejiang University, China. His research interests include program analysis and formal methods.
NIU Zhi received his master degree in control engineering from Chongqing University, China. He is currently working at ZTE Corporation. His research interests include distributed system, formal verification and software reliability.
CHEN Li received his bachelor degree in computer science from Northeastern University, China. He is currently working at ZTE Corporation. His research interests include software reliability, open source software risk analysis and network security.
DONG Luming received his master degree in control theory and control engineering from Huazhong University of Science and Technology, China. He is currently working at ZTE Corporation. His research interests include distributed system, formal verification, software reliability and innovative security technology for wireless communication.
SHEN Taoli is a master student in cybersecurity at Zhejiang University, China. His research interests include push-button verification and formal methods.

Abstract

Abstract:

Deadlock detection is an essential aspect of concurrency control in parallel and distributed systems, as it ensures the efficient utilization of resources and prevents indefinite delays. This paper presents a comprehensive analysis of the various deadlock detection techniques, including static and dynamic approaches. We discuss the future improvements associated with deadlock detection and provide a comparative evaluation of these techniques in terms of their accuracy, complexity, and scalability. Furthermore, we outline potential future research directions to improve deadlock detection mechanisms and enhance system performance.

Key words: deadlock detection, static analysis, dynamic analysis

LU Jiachen, NIU Zhi, CHEN Li, DONG Luming, SHEN Taoli. Deadlock Detection: Background, Techniques, and Future Improvements[J]. ZTE Communications, 2024, 22(2): 71-79.

Figures/Tables 10

References 38

1	LIU B Z, HUANG J. D4: fast concurrency debugging with parallel differential analysis [J]. ACM SIGPLAN notices, 2018, 53(4): 359–373. DOI: 10.1145/3296979.3192390
2	CAI Y D, YE C F, SHI Q K, et al. Peahen: fast and precise static deadlock detection via context reduction [C]//The 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering. ACM, 2022: 784–796. DOI: 10.1145/3540250.3549110
3	BENSALEM S, HAVELUND K. Dynamic deadlock analysis of multithreaded programs [EB/OL]. [2023-06-01].
4	CAI Y, CHAN W K. MagicFuzzer: scalable deadlock detection for large-scale applications [C]//Proceedings of 34th International Conference on Software Engineering (ICSE). IEEE, 2012: 606–616. DOI: 10.1109/ICSE.2012.6227156
5	CAI Y, CHAN W K. Magiclock: scalable detection of potential deadlocks in large-scale multithreaded programs [J]. IEEE transactions on software engineering, 2014, 40(3): 266–281. DOI: 10.1109/TSE.2014.2301725
6	ESLAMIMEHR M, PALSBERG J. Sherlock: scalable deadlock detection for concurrent programs [C]//The 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering. ACM, 2014: 353–365. DOI: 10.1145/2635868.2635918
7	ARPACI-DUSSEAU R H, ARPACI-DUSSEAU A C. Operating systems: three easy pieces [M]. Raleigh, USA: Lulu Press, 2018
8	COFFMAN E G, ELPHICK M, SHOSHANI A. System deadlocks [J]. ACM computing surveys, 1971, 3(2): 67–78. DOI: 10.1145/356586.356588
9	ELMAGARMID A K. A survey of distributed deadlock detection algorithms [J]. ACM SIGMOD record, 1986, 15(3): 37–45. DOI: 10.1145/15833.15837
10	HAVENDER J W. Avoiding deadlock in multitasking systems [J]. IBM systems journal, 1968, 7(2): 74–84. DOI: 10.1147/sj.72.0074
11	Alvinashcraft. CreateFileW function (fileapi.h) [EB/OL]. [2023-05-17].
12	BERLIZOV A N, ZHMUDSKY A A. The recursive adaptive quadrature in MS Fortran-77 [EB/OL]. [2023-05-17].
13	Google. mm/rmap.c-kernel/common-Git at Google-android.googlesource.com [EB/OL]. [2023-05-17].
14	IJKSTRA E W. Een algorithme ter voorkoming van de dodelijke omarming [EB/OL]. [2023-05-17].
15	AYEWAH N, PUGH W, HOVEMEYER D, et al. Using static analysis to find bugs [J]. IEEE software, 2008, 25(5): 22–29. DOI: 10.1109/ms.2008.130
16	CLARKE E M. Model checking [C]//The 17th International Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTCS, 1997: 54–56
17	KHEDKER U, SANYAL A, SATHE B. Data flow analysis: theory and practice [M]. Carrollton, UAS: CRC Press, 2017
18	ALLEN F E. Control flow analysis [J]. ACM SIGPLAN notices, 1970, 5(7): 1–19. DOI: 10.1145/390013.808479
19	NAIK M, PARK C S, SEN K, et al. Effective static deadlock detection [C]//The 31st International Conference on Software Engineering. IEEE, 2009: 386–396. DOI: 10.1109/ICSE.2009.5070538
20	BROTHERSTON J, BRUNET P, GOROGIANNIS N, et al. A compositional deadlock detector for android java [C]//The 36th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 2021: 955–966
21	DELIGIANNIS P, DONALDSON A F, RAKAMARIC Z. Fast and precise symbolic analysis of concurrency bugs in device drivers (T) [C]//The 30th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 2015: 166–177. DOI: 10.1109/ASE.2015.30
22	WILLIAMS A, THIES B, ERNST M D. Static deadlock detection for java libraries [EB/OL]. [2023-05-17].
23	KAHLON V, YANG Y, SANKARANARAYANAN S, et al. Fast and accurate static data-race detection for concurrent programs [C]//International Conference on Computer Aided Verification. CAV: 226–239. 10.1007/978-3-540-73368-3_26
24	KROENING D, POETZL D, SCHRAMMEL P, et al. Sound static deadlock analysis for C/Pthreads [C]//Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering. ACM, 2016: 379–390. DOI: 10.1145/2970276.2970309
25	HAVELUND K. Using runtime analysis to guide model checking of java programs [C]//The 7th International SPIN Workshop on Model Checking of Software. SPIN, 2000: 245–264
26	JOSHI P, PARK C S, SEN K, et al. A randomized dynamic program analysis technique for detecting real deadlocks [J]. ACM SIGPLAN notices, 2009, 44(6): 110–120. DOI: 10.1145/1543135.1542489
27	HARROW J J. Runtime checking of multithreaded applications with visual threads [C]//The 7th International SPIN Workshop in Model Checking and Software Verification. SPIN, 2000: 331–342
28	LUO Z D, DAS R, QI Y. Multicore SDK: a practical and efficient deadlock detector for real-world applications [C]//The 4th IEEE International Conference on Software Testing, Verification and Validation. IEEE, 2011: 309–318. DOI: 10.1109/ICST.2011.22
29	MAJUMDAR R, XU R G. Directed test generation using symbolic grammars [C]//The 22nd IEEE/ACM international conference on Automated software engineering. IEEE, 2007: 134–143
30	GODEFROID P, KLARLUND P, SEN K. Dart: directed automated random testing [C]//The ACM SIGPLAN conference on Programming language design and implementation. ACM, 2005: 213–223
31	SEN K, AGHA G. CUTE and jCUTE: concolic unit testing and explicit path model-checking tools [C]//International Conference on Computer Aided Verification. CAV, 2006: 419–423. DOI: 10.1007/11817963_38
32	SEN K. Concolic testing [C]//The 22nd IEEE/ACM international conference on automated software engineering. IEEE, 2007: 571–572
33	SAID M, WANG C, YANG Z, et al. Generating data race witnesses by an SMT-based analysis [C]//The Third International Conference on NASA Formal Methods. NASA Formal Methods Symposium, 2011: 313–327
34	BLACKBURN S M, GARNER R, HOFFMANN C, et al. The DaCapo benchmarks: java benchmarking development and analysis [C]//The 21st Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications. ACM, 2006: 169–190. DOI: 10.1145/1167473.1167488
35	CAI Y, MENG R, PALSBERG J. Low-overhead deadlock prediction [C]//The 42nd International Conference on Software Engineering. IEEE, 2020: 1298–1309
36	Bugzilla. Bugzilla main page: bugzilla.kernel.org [EB/OL]. [2023-06-01].
37	Bugzilla. Bugzilla main page: bugzilla.mozilla.org [EB/OL]. [2023-06-01].
38	JOSHI P, NAIK M, SEN K, et al. An effective dynamic analysis for detecting generalized deadlocks [C]//The 18th ACM SIGSOFT international symposium on Foundations of software engineering. ACM, 2010: 327–336. DOI: 10.1145/1882291.1882339

Type	Tools	Release Date
Static	D4^[1]	Jun. 2018
Static	Peahen^[2]	Nov. 2022
Dynamic	GoodLock^[3]	Nov. 2005
	MagicLock^[4–5]	Mar. 2014
	Sherlock^[6]	Aug. 2014

Type	Tools	Release Date
Static	D4^[1]	Jun. 2018
Static	Peahen^[2]	Nov. 2022
Dynamic	GoodLock^[3]	Nov. 2005
	MagicLock^[4–5]	Mar. 2014
	Sherlock^[6]	Aug. 2014

Type	Tools	Scalability	False Positives	False Negatives	New Bugs
Static	D4	High	True	True	False
Static	Peahen	High	True	Almost false	True
Dynamic	GoodLock	Low	True	True	False
	MagicLock	Medium	True	True	False
	Sherlock	Medium	True	True	True

Type	Tools	Scalability	False Positives	False Negatives	New Bugs
Static	D4	High	True	True	False
Static	Peahen	High	True	Almost false	True
Dynamic	GoodLock	Low	True	True	False
	MagicLock	Medium	True	True	False
	Sherlock	Medium	True	True	True

Deadlock Detection: Background, Techniques, and Future Improvements

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 38

Related Articles 1

Recommended Articles

Metrics