Синхронизация в конкурентных структурах данных на основе анализа зависимостей между операциями

Денис Сергеевич Коротченко; Виталий Евгеньевич Аксенов

doi:10.14529/cmse260205

Авторы

Денис Сергеевич Коротченко Университет ИТМО
Виталий Евгеньевич Аксенов Университет ИТМО

DOI:

https://doi.org/10.14529/cmse260205

Ключевые слова:

потокобезопасность, конкурентные структуры данных, граф зависимостей, семантическая блокировка, линеаризуемость

Аннотация

В работе рассматривается оптимизация синхронизаций операций в потокобезопасных структурах данных. В различных структурах данных операции могут по-разному конфликтовать друг с другом с точки зрения одновременного исполнения. Например, стандартная блокировка чтения—записи учитывает, что одновременное чтение из разных потоков часто допустимо, в то время как одновременная запись из разных потоков или параллельная запись и чтение требуют синхронизации. Такая зависимость может быть и более сложной: например, несколько одновременных операций увеличения всех элементов в контейнере на заданную величину допустимы с синхронизацией на уровне доступа к элементу, в то время как параллельное присвоение всем элементам контейнера одного числа из одного потока и другого числа из другого потока требует более сложной синхронизации. В представленной работе рассматривается новый подход к обеспечению синхронизации при выполнении операций с потокобезопасной структурой данных, основанный на анализе графа зависимостей между операциями, с целью обеспечения более эффективной работы такой структуры. Также приводятся результаты экспериментов по сравнению различных подходов, которые показывают эффективность предлагаемого решения.

Библиографические ссылки

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.