Synchronization in Concurrent Data Structures Based on the Analysis of Dependencies between Operations
DOI:
https://doi.org/10.14529/cmse260205Keywords:
thread-safe, concurrent data structures, dependency graph, semantic lock, linearizabilityAbstract
This paper examines the synchronization of operations in thread-safe data structures. In different data structures, operations may conflict with each other in different ways in terms of concurrency. For example, a standard Read-Write lock recognizes that concurrent read accesses from different threads are often permissible, while parallel writes from different threads or parallel reads and writes most often require synchronization. This dependency can also be more complex: for example, incrementing all elements in a container by a given value is permissible with synchronization at the element access level, while concurrently assigning one number from one thread and a different number from another thread to all elements of a container requires more complex synchronization. This paper examines various methods for organizing synchronization between operations. The main result is a proposed new approach to ensuring such synchronization, based on the analysis of the dependency graph between operations, which ensures more efficient synchronization of the structure. Experimental results comparing various approaches are also presented, demonstrating the effectiveness of the proposed solution.
References
Herlihy M.P., Wing J.M. Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 1990. Vol. 12, no. 3. P. 463–492. DOI: 10.1145/78969.78972.
Joung Y.-J. Asynchronous group mutual exclusion (extended abstract). Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing. 1998. P. 51–60. PODC ’98. DOI: 10.1145/277697.277706.
Yuan He K.G., Gafni E. Group mutual exclusion in linear time and space. Theoretical Computer Science. 2018. Vol. 709. P. 31–47. DOI: 10.1016/j.tcs.2017.05.030.
Maor L., Taubenfeld G. Constant RMR Group Mutual Exclusion for Arbitrarily Many Processes and Sessions. 35th International Symposium on Distributed Computing (DISC 2021). Vol. 209. 2021. P. 30:1–30:16. Leibniz International Proceedings in Informatics (LIPIcs). DOI: 10.4230/LIPIcs.DISC.2021.30.
Aksenov V., Kuznetsov P., Shalyto A. Parallel Combining: Benefits of Explicit Synchronization. 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Vol. 125. 2019. P. 11:1–11:16. Leibniz International Proceedings in Informatics (LIPIcs). DOI: 10.4230/LIPIcs.OPODIS.2018.11.
Brown T., Prokopec A., Alistarh D. Non-blocking interpolation search trees with doubly-logarithmic running time. Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York, NY, USA, 2020. P. 276–291. PPoPP ’20. DOI: 10.1145/3332466.3374542.
Blelloch G.E., Wei Y. VERLIB: Concurrent Versioned Pointers. Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming. 2024. P. 200–214. PPoPP ’24. DOI: 10.1145/3627535.3638501.
Lomet D.B. Key Range Locking Strategies for Improved Concurrency. Proceedings of the 19th International Conference on Very Large Data Bases. 1993. P. 655–664. VLDB ’93.
Eswaran K., Gray J., Lorie R., Traiger I. The Notions of Consistency and Predicate Locks in a Database System. Readings in Artificial Intelligence and Databases. Morgan Kaufmann, 1989. P. 523–532. DOI: 10.1016/B978-0-934613-53-8.50039-X.
Badrinath B.R., Ramamritham K. Semantics-Based Concurrency Control: Beyond Commutativity. ACM Trans. Database Syst. 1992. Vol. 17, no. 1. P. 163–199. DOI: 10.1145/128765.128771.
Weihl W. Commutativity-based concurrency control for abstract data types. IEEE Transactions on Computers. 1988. Vol. 37, no. 12. P. 1488–1505. DOI: 10.1109/12.9728.
Harris T., Larus J., Rajwar R. Software Transactional Memory. Transactional Memory. Springer International Publishing, 2010. P. 101–145. DOI: 10.1007/978-3-031-01728-5_4.
Herlihy M., Koskinen E. Transactional boosting: a methodology for highly-concurrent transactional objects. Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 2008. P. 207–216. PPoPP ’08. DOI: 10.1145/1345206.1345237.
Koval N., Fedorov A., Sokolova M., et al. Lincheck: A Practical Framework for Testing Concurrent Data Structures on JVM. Computer Aided Verification. 2023. P. 156–169. DOI: 10.1007/978-3-031-37706-8_8.
Courtois P.J., Heymans F., Parnas D.L. Concurrent control with “readers” and “writers”. Commun. ACM. 1971. Vol. 14, no. 10. P. 667–668. DOI: 10.1145/362759.362813.
Potapov A., Zuev M., Moiseenko E., Koval N. Testing Concurrent Algorithms on JVM with Lincheck and IntelliJ IDEA. Proceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis. 2024. P. 1821–1825. ISSTA 2024. DOI: 10.1145/3650212.3685301.
Korotchenko D.S. SemanticLock. URL: https://github.com/ITMO-PTDC-Team/SemanticLock/tree/PCT-2026 (accessed: 28.07.2026) (in Russian).
Gramoli V. More than you ever wanted to know about synchronization: synchrobench, measuring the impact of the synchronization on concurrent algorithms. Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 2015. P. 1–10. PPoPP 2015. DOI: 10.1145/2688500.2688501.
