Алгоритмы реализации потокобезопасных ассоциативных массивов на основе транзакционной памяти
Предложены алгоритмы реализации потокобезопасных ассоциативных массивов (красно-черное дерево, хеш-таблица с открытой адресацией на основе метода Hopscotch hashing разрешения коллизий) с использованием программной транзакционной памяти (software transactional memory). Представлен анализ эффективности ассоциативных массивов при разном количестве задействованных потоков и процессорных ядер, приведено сравнение с аналогичными структурами данных на основе крупнозернистых и мелкозернистых блокировок, также сформулированы рекомендации по выбору алгоритмов выполнения транзакций. Описаны принципы работы программной транзакционной памяти, различные политики обновления объектов в памяти и стратегии обнаружения конфликтов. Представлены различные методы блокировки при использовании транзакционной памяти, реализованной в компиляторе GCC 5.4.0. Коротко рассмотрены альтернативы, применяемые в настоя-щее время, выделены их достоинства и недостатки.
Авторы: В. А. Смирнов, А. Р. Омельниченко, А. А. Пазников
Направление: Информатика и компьютерные технологии
Ключевые слова: Транзакционная память, потокобезопасные структуры данных, красно-черное дерево, хеш-таблица, многопоточное программирование, синхронизация многопоточных программ
Открыть полный текст статьи