Top

International Journal of Parallel Programming

Published in:

12-09-2019

Convoider: A Concurrency Bug Avoider Based on Transparent Software Transactional Memory

Authors: Zhen Yu, Yu Zuo, Yong Zhao

Published in: International Journal of Parallel Programming | Issue 1/2020

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

search-config

AI-assisted search

Off

Abstract

Software transactional memory is an effective mechanism to avoid concurrency bugs in multi-threaded programs. However, two problems hinder the adoption of traditional such systems in wild world: high human cost for equipping programs with transaction functionality and low compatibility with I/O calls and conditional variables. This paper presents Convoider to try to solve these problems. By intercepting inter-thread operations and designating code among them as transactions in each thread, Convoider automatically transactionalizes target programs without any source code modification and recompiling. By saving/restoring stack frames and CPU registers on beginning/aborting a transaction, Convoider makes execution flow revocable. By turning threads into processes, leveraging virtual memory protection and customizing memory allocation/deallocation, Convoider makes memory manipulations revocable. By maintaining virtual file systems and redirecting I/O operations onto them, Convoider makes I/O effects revocable. By converting lock/unlock operations to no-ops, customizing signal/wait operations on condition variables and committing memory changes transactionally, Convoider makes deadlocks, data races and atomicity violations impossible. Experimental results show that Convoider succeeds in transparently transactionalizing twelve real-world applications and perfectly avoid 94% of thirty-one concurrency bugs used in our experiments. This study can help efficiently transactionalize legacy multi-threaded applications and effectively improve the runtime reliability of them.

previous article Source-to-Source Parallelization Compilers for Scientific Shared-Memory Multi-core and Accelerated Multiprocessing: Analysis, Pitfalls, Enhancement and Potential

next article Empirical Mode Decomposition and Temporal Convolutional Networks for Remaining Useful Life Estimation

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 "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

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

Sutter, H., Larus, J.: Software and the concurrency revolution. ACM Queue 3(7), 54–62 (2005)CrossRef

Lu, S., Park, S., Seo, E., et al.: Learning from mistakes: a comprehensive study on real world concurrency characteristics. ACM SIGARCH Comput. Archit. News 36(1), 329–339 (2008)CrossRef

Musuvathi, M., Qadeer, S.: Iterative context bounding for systematic testing of multi-threaded programs. ACM SIGPLAN Not. 42(6), 446–455 (2007)CrossRef

Park, S., Lu, S., Zhou, Y.Y.: CTrigger: exposing atomicity violation bugs from their hiding places. ACM SIGPLAN Not. 44(3), 25–36 (2009)CrossRef

Sen, K.: Race directed random testing of concurrent programs. ACM SIGPLAN Not. 43(6), 11–21 (2008)CrossRef

Zhang, W., Lim, J., Olichandran, R., et al.: ConSeq: detecting concurrency bugs through sequential errors. ACM SIGPLAN Not. 47(4), 251–264 (2011)CrossRef

Yin, Z., Yuan, D., Zhou, Y.Y.: ‘How do fixes become bugs?a comprehensive characteristic study on incorrect fixes in commercial and open source operating systems’, In: Proceedings of 19th ACM SIGSOFT Symposium on the Foundations of Software Engineering, Szeged, Hungary, pp. 26–36 (2011)

Zhang, M., Wu, Y., Lu, S., et al.: AI: a lightweight system for tolerating concurrency bugs. In: Proceedings of 22nd ACM SIGSOFT Symposium on Foundations of Software Engineering, Hong Kong, China, pp. 330–340 (2014)

Berger, E.D., Yang, T., Liu, T., et al.: Grace: safe multi-threaded programming for C/C++. ACM SIGPLAN Not. 44(10), 81–96 (2009)CrossRef

10.

Wamhoff, J.T., Fetzer, C., Felber, P., et al.: FastLane: improving performance of software transactional memory for low thread counts. In: Proceedings of 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Shenzhen, China, pp. 113–122 (2013)

11.

Spear, M.F., Dalessandro, L., Marathe, V.J., et al.: A comprehensive strategy for contention management in software transactional memory. ACM SIGPLAN Not. 44(4), 141–150 (2009)CrossRef

12.

Felber, P., Fetzer, C., Marlier, P., et al.: Time-based software transactional memory. IEEE Trans. Parallel Distrib. Syst. 21(12), 1793–1807 (2010)CrossRef

13.

Feng, M., Gupta, R., Neamtiu, I.: Programming support for speculative execution with software transactional memory. In: Proceedings of 27th International Symposium on Parallel and Distributed Processing, Boston, USA, pp. 394–403 (2013)

14.

Matveev, A., Shavit, N.: Towards a fully pessimistic STM model. In: Proceedings of 7th ACM SIGPLAN Workshop on Transactional Computing, New Orleans, USA, pp. 1–9 (2012)

15.

Dice, D., Shalev, O., Shavit, N.: Transactional locking II. In: Proceedings of 20th International Symposium on Distributed Computing, Stockholm, Sweden, pp. 194–208 (2006)

16.

Welc, A., Saha, B., Adl-Tabatabai, A.: Irrevocable transactions and their applications. In: Proceedings of 20th Symposium on Parallelism in Algorithms and Architectures, Munich, Germany, pp. 285–296 (2008)

17.

Spear, M.F., Silverman, M., Dalessandro, L., et al.: Implementing and exploiting inevitability in software transactional memory. In: Proceedings of the 37th International Conference on Parallel Processing, Portland, USA, pp. 59–66 (2008)

18.

Volos, H., Tack, A.J., Goyal, N., et al.: xCalls: safe I/O in memory transactions. In: Proceedings of the 4th ACM Euro. Conference on Computer Systems, Nuremberg, Germany, pp. 247–260 (2009)

19.

Dragojevic, A., Felber, P., Gramoli, V., et al.: Why STM can be more than a research toy. ACM Commun. 54(4), 70–77 (2011)CrossRef

20.

Volos, H., Tack, A.J., Swift, M.M., et al.: Applying transactional memory to concurrency bugs. In: Proceedings of 17th Conference on Architectural Support for Programming Language and Operating Systems, London, UK, pp. 211–222 (2012)

21.

Pankratius, V., Adl-Tabatabai, A.R.: Software engineering with transactional memory versus locks in practice. Theor. Comput. Syst. 55(3), 555–590 (2014)MathSciNetCrossRef

22.

Rossbach, C.J., Hofmann, O.S., Witchel, E.: Is transactional programming actually easier? In: Proceedings of the 15th ACM SIGPLAN Symposium on Principle and Practice of Parallel Programming, Bangalore, India, pp. 47–56 (2010)

23.

Zyulkyarov, F., Gajinov, V., Unsal, O.S., et al.: Atomic quake: using transactional memory in an interactive multiplayer game server. In: Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Raleigh, USA, pp. 25–34 (2009)

24.

Harris, T., Marlow, S., Peyton-Jones, S., et al.: Composable memory transactions. In: Proceedings of the 10th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Chicago, USA, pp. 48–60 (2005)

25.

Baugh, L., Zilles, C.: An analysis of I/O and syscalls in critical sections and their implications for transactional memory. In: Proceedings of 2008 IEEE International Symposium on Performance Analysis of Systems and Software, Austin, USA, pp. 54–62 (2008)

26.

Harris, T., Fraser, K.: Language support for lightweight transactions. ACM SIGPLAN Not. 38(11), 388–402 (2003)CrossRef

27.

Nicacio, D., Baldassin, A., Araujo, G.: Transaction scheduling using dynamic conflict avoidance. Int. J. Parallel Pro. 41(1), 89–110 (2013)CrossRef

28.

Skyrme, A., Rodriguez, N.: From locks to transactional memory: lessons learned from porting a real-world application. In: Procedings of the 8th ACM SIGPLAN Workshop on Transactional Computing, Houston, USA, pp. 1–9 (2013)

29.

Ruan, W., Vyas, T., Liu, Y., et al.: Transactionalizing legacy code: an experience report using GCC and Memcached. In: Proceedings of 19th International Conference on Architecture Support for Programming Languages and Operating Systems, Salt Lake City, USA, pp. 399–412 (2014)

30.

Bienia, C., Kumar, S., Singh, J.P., et al.: The PARSEC benchmark suite: characterization and architectural implications. In: Proceedings of 17th International Conference on Parallel Architectures and Compilation Techniques, Toronto, Canada, pp. 72–81 (2008)

31.

The modified SPLASH2 home page. http://www.capsl.udel.edu/splash/ (2018). Accessed 19 Aug 2018

32.

Ranger, C., Raghuraman, R., Penmetsa, A., et al.: Evaluating MapReduce for multi-core and multiprocessor systems. In: Proceedings of the 13th International Symposium on High Performance Computer Architecture, Phoenix, USA, pp. 13–24 (2007)

33.

Yu, Z., Su, X.H., Ma, P.J.: Mocklinter: linting mutual exclusive deadlocks with lock allocation graphs. Int. J. Hybrid Inf. Tech. 9(3), 355–374 (2016)CrossRef

34.

Google’s data race test. http://code.google.com/p/data-race-test/ 2018. Accessed 19 Aug 2018

35.

Yu, J., Narayanasamy, S., Pereira, C., et al.: Maple: a coverage-driven testing tool for multi-threaded programs. ACM SIGPLAN Not. 47(10), 485–502 (2012)CrossRef

36.

Yu, J., Narayanasamy, S.: A case for an interleaving constrained shared-memory multi-processor. ACM SIGARCH Comput. Archit. News 37(3), 325–336 (2009)CrossRef

37.

Wang, C., Liu, Y., Spear, M.: Transaction-friendly condition variables. In: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, Prague, Czech Republic, pp. 198–207 (2014)

38.

Berger, E.D., Mckinley, K.S., Blumofe, R.D., et al.: Hoard: a scalable memory allocator for multi-threaded applications. In: Proceedings of the 9th International Conference on Architectural Support for Programming Language and Operating Systems, Cambridge, USA, pp. 117–128 (2000)

39.

Berger, E.D., Zorn, B.G., Mckinley, K.S.: Composing high-performance memory allocators. In: Proceedings of the 22nd ACM SIGPLAN Conference on Programming Language Design and Implementation, Snowbird, USA, pp. 114–124 (2001)

40.

Blundell, C., Lewis, E.C., Martin, M.: Unrestricted transactions memory: supporting I/O and system calls within transactions. University of Pennsylvania, pp. 1–12 (2006)

41.

Minh, C.C., Chung, J.W., Kozyrakis, C., et al.: STAMP: Stanford transactional applications for multi-processing. In: Proceedings of the 2008 IEEE International Symposium on Workload Characterization, Seattle, USA, pp. 25–46 (2008)

42.

Jula, H., Tralamazza, D., Zamfir, C., et al.: Deadlock immunity: enabling systems to defend against deadlocks. In: Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation, San Diego, USA, pp. 295–308 (2008)

43.

Yu, Z., Su, X.H., Ma, P.J.: Slider: an online and active deadlock avoider by serial execution of critical sections. Int. J. High Perf. Syst. Archit. 6(1), 36–50 (2016)

44.

Pyla, H.K., Varadarajan, S.: Avoiding deadlock avoidance. In: Proceedings of the 19th International Conference on Parallel Architecture Compilation Techniques, Vienna, Austria, pp. 75–86 (2010)

45.

Shimomura, T., Ikeda, K.: Two types of deadlock detection: cyclic and acyclic. Intell. Syst. Sci. Inform. 54(2), 233–259 (2016)

46.

Wang, J., Dou, W.S., Gao, Y., et al.: A comprehensive study on real world concurrency bugs in Node.js. In: Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering, Urbana-Champaign, USA, pp. 520–531 (2017)

47.

Wang, J., Jiang, Y.Y., Xu, C., et al.: AATT+: effectively manifesting concurrency bugs in Android apps. Sci. Comput. Program. 163, 1–18 (2018)CrossRef

Title: Convoider: A Concurrency Bug Avoider Based on Transparent Software Transactional Memory
Authors: Zhen Yu
Yu Zuo
Yong Zhao
Publication date: 12-09-2019
Publisher: Springer US
Published in: International Journal of Parallel Programming / Issue 1/2020
Print ISSN: 0885-7458
Electronic ISSN: 1573-7640
DOI: https://doi.org/10.1007/s10766-019-00642-1

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 "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2020

Characterizing Scalability of Sparse Matrix–Vector Multiplications on Phytium FT-2000+

Planning Above the API Clouds Before Flying Above the Clouds: A Real-Time Personalized Air Travel Planning Approach

Message Passing Optimization in Robot Operating System

CSMqGraph: Coarse-Grained and Multi-external-storage Multi-queue I/O Management for Graph Computing

Empirical Mode Decomposition and Temporal Convolutional Networks for Remaining Useful Life Estimation

Source-to-Source Parallelization Compilers for Scientific Shared-Memory Multi-core and Accelerated Multiprocessing: Analysis, Pitfalls, Enhancement and Potential

Premium Partner