Top

Published in:

2018 | OriginalPaper | Chapter

Dl-Check: Dynamic Potential Deadlock Detection Tool for Java Programs

Authors : Nikita Koval, Dmitry Tsitelov, Roman Elizarov

Published in: Tools and Methods of Program Analysis

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Deadlocks are one of the main problems in multithreaded programming. This paper presents a novel approach to detecting potential deadlocks at run-time. As opposed to many dynamic methods based on analyzing execution traces, it detects a potential deadlock immediately at the point of the lock hierarchy violation which happens first during execution, so all the run-time context is available at the point of detection. The approach is based on the target program instrumentation to capture lock acquisition and release operations. An acyclic lock-order graph is maintained incrementally, so cycles are detected during graph maintenance. The presented algorithm is based on topological order maintenance and uses various heuristics and concurrent data structures which improve performance and scalability. Experimental results show that Dl-Check is efficient for large-scale multithreaded applications.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Technology and Tools for Developing Industrial Software Test Suites Based on Formal Models and Implementing Scalable Testing Process on Supercomputer

next chapter A Survey on Model-Based Testing Tools for Test Case Generation

Sutter, H.: The free lunch is over: a fundamental turn toward concurrency in software. Dr. Dobb’s J. 30(3), 202–210 (2005)

Knapp, E.: Deadlock detection in distributed databases. ACM Comput. Surv. 19(4), 303–328 (1987)CrossRef

Singhal, M.: Deadlock detection in distributed systems (1989)

Da Luo, Z., Das, R., Qi, Y.: MulticoreSDK: a practical and efficient deadlock detector for real-world applications. In: Proceedings - 4th IEEE International Conference on Software Testing, Verification, and Validation, ICST 2011, pp. 309–318 (2011)

Artho, C., Biere, A.: Applying static analysis to large-scale, multi-threaded Java programs. In: Proceedings of the Australian Software Engineering Conference, ASWEC, pp. 68–75, January 2001

Williams, A., Thies, W., Ernst, M.D.: Static deadlock detection for Java libraries. In: Black, A.P. (ed.) ECOOP 2005. LNCS, vol. 3586, pp. 602–629. Springer, Heidelberg (2005). https://doi.org/10.1007/11531142_26 CrossRef

Agarwal, R., Wang, L., Stoller, S.D.: Detecting potential deadlocks with static analysis and run-time monitoring. In: Ur, S., Bin, E., Wolfsthal, Y. (eds.) HVC 2005. LNCS, vol. 3875, pp. 191–207. Springer, Heidelberg (2006). https://doi.org/10.1007/11678779_14 CrossRef

Naik, M., Park, C.-S., Sen, K., Gay, D.: Effective static deadlock detection. In: Proceedings of the 31st International Conference on Software Engineering

Mazzanti, F., Spagnolo, G.O., Della Longa, S., Ferrari, A.: Deadlock avoidance in train scheduling: a model checking approach. In: Lang, F., Flammini, F. (eds.) FMICS 2014. LNCS, vol. 8718, pp. 109–123. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10702-8_8

10.

Antonino, P., Gibson-Robinson, T., Roscoe, A.W.: Efficient deadlock-freedom checking using local analysis and SAT solving. In: Ábrahám, E., Huisman, M. (eds.) IFM 2016. LNCS, vol. 9681, pp. 345–360. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-33693-0_22 CrossRef

11.

JCarder – dynamic deadlock finder for Java (2010). http://www.jcarder.org

12.

Cai, Y., Wu, S., Chan, W.K.: ConLock: a constraint-based approach to dynamic checking on deadlocks in multithreaded programs. In: Proceedings of the 36th International Conference on Software Engineering - ICSE 2014, pp. 491–502 (2014)

13.

Havelund, K.: Using runtime analysis to guide model checking of Java programs. In: Havelund, K., Penix, J., Visser, W. (eds.) SPIN 2000. LNCS, vol. 1885, pp. 245–264. Springer, Heidelberg (2000). https://doi.org/10.1007/10722468_15 CrossRef

14.

Agarwal, R., Bensalem, S., Farchi, E., Havelund, K., Nir-Buchbinder, Y., Stoller, S.D., Ur, S., Wang, L.: Detection of deadlock potentials in multithreaded programs. IBM J. Res. Dev. 54(5), 3:1–3:15 (2010)

15.

Bensalem, S., Havelund, K.: Dynamic deadlock analysis of multi-threaded programs. In: Ur, S., Bin, E., Wolfsthal, Y. (eds.) HVC 2005. LNCS, vol. 3875, pp. 208–223. Springer, Heidelberg (2006). https://doi.org/10.1007/11678779_15 CrossRef

16.

Harrow, J.J.: Runtime checking of multithreaded applications with visual threads. In: Havelund, K., Penix, J., Visser, W. (eds.) SPIN 2000. LNCS, vol. 1885, pp. 331–342. Springer, Heidelberg (2000). https://doi.org/10.1007/10722468_20 CrossRef

17.

Herlihy, M.: The art of multiprocessor programming (2006)

18.

Meisel, J.: Multithreaded programming. EE Eval. Eng. 46(12), 12–17 (2007)

19.

Marchetti-Spaccamela, A., Nanni, U., Rohnert, H.: Maintaining a topological order under edge insertions. Inf. Process. Lett. 59(1), 53–58 (1996)MathSciNetCrossRefMATH

20.

Pearce, D.J., Kelly, P.H.J.: A batch algorithm for maintaining a topological order. In: Conferences in Research and Practice in Information Technology Series, vol. 102(1), pp. 79–87 (2010)

21.

Cormen, T.H.: Introduction to Algorithms. MIT Press, Cambridge (2009)MATH

22.

Apache Derby (2016). https://db.apache.org/derby

23.

IntelliJ IDEA the Java IDE (2016). https://www.jetbrains.com/idea/

24.

dxFeed Market Data (2016). http://www.dxfeed.com/

25.

Chan, W.K.: Magiclock: scalable detection of potential deadlocks in large-scale multithreaded programs. IEEE Trans. Softw. Eng. 40(3), 266–281 (2014)CrossRef

26.

Dl-Check – tool for finding potential deadlocks in Java programs (2016). https://github.com/Devexperts/dlcheck

27.

Bruneton, E.: ASM 4.0-A Java bytecode engineering library (2011). http://download.forge.objectweb.org/asm/asm4-guide.pdf. Accessed 18 May 2013

28.

Kuleshov, E.: Using the ASM framework to implement common Java bytecode transformation patterns. Aspect-Oriented Software Development (2007)

29.

Monson, L.: Caching & weakreferences. JAVA Dev. J. 3(8), 32–36 (1998)

30.

Shiv, K., Chow, K., Wang, Y., Petrochenko, D.: SPECjvm2008 performance characterization. In: Kaeli, D., Sachs, K. (eds.) SBW 2009. LNCS, vol. 5419, pp. 17–35. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-540-93799-9_2 CrossRef

31.

Apache Lucene (2010)

32.

DaCapo benchmark suite (2009). http://dacapobench.org/

Title: Dl-Check: Dynamic Potential Deadlock Detection Tool for Java Programs
Authors: Nikita Koval
Dmitry Tsitelov
Roman Elizarov
Publisher: Springer International Publishing
Book: Tools and Methods of Program Analysis
Print ISBN: 978-3-319-71733-3

Electronic ISBN: 978-3-319-71734-0

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-71734-0_6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner