Синхронизация в конкурентных структурах данных на основе анализа зависимостей между операциями
Статья в выпуске: 2 т.15, 2026 года.
Бесплатный доступ
В работе рассматривается оптимизация синхронизаций операций в потокобезопасных структурах данных. В различных структурах данных операции могут по-разному конфликтовать друг с другом с точки зрения одновременного исполнения. Например, стандартная блокировка чтения—записи учитывает, что одновременное чтение из разных потоков часто допустимо, в то время как одновременная запись из разных потоков или параллельная запись и чтение требуют синхронизации. Такая зависимость может быть и более сложной: например, несколько одновременных операций увеличения всех элементов в контейнере на заданную величину допустимы с синхронизацией на уровне доступа к элементу, в то время как параллельное присвоение всем элементам контейнера одного числа из одного потока и другого числа из другого потока требует более сложной синхронизации. В представленной работе рассматривается новый подход к обеспечению синхронизации при выполнении операций с потокобезопасной структурой данных, основанный на анализе графа зависимостей между операциями, с целью обеспечения более эффективной работы такой структуры. Также приводятся результаты экспериментов по сравнению различных подходов, которые показывают эффективность предлагаемого решения.
Короткий адрес: https://sciup.org/147254951
IDS: 147254951 | УДК: 004.021 | DOI: 10.14529/cmse260205
Synchronization in Concurrent Data Structures Based on the Analysis of Dependencies between Operations
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.
