Синхронизация и отсутствие гонок данных

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

Definition

Синхронизация — это координация параллельных действий для обеспечения упорядоченности или взаимного исключения при работе с общими ресурсами, а отсутствие гонок данных — это свойство, при котором никакие два потока не обращаются к одной и той же ячейке памяти одновременно, при этом хотя бы один из них осуществляет запись, без промежуточной синхронизации.

Scope

Эта тема охватывает механизмы и свойства, обеспечивающие корректный параллельный доступ к общему состоянию: взаимное исключение, блокировки, семафоры и мониторы, переменные условия, алгоритмы без блокировок и без ожидания, транзакционная память, отношение happens-before и обнаружение гонок данных. Она рассматривает проблемы взаимоблокировок, атомарности и дисциплины, необходимой для обеспечения отсутствия гонок данных в программах.

Core questions

• Как достигается взаимное исключение и каковы его опасности (взаимоблокировка, голодание)?
• Что отличает синхронизацию на основе блокировок от синхронизации без блокировок?
• Как отношение happens-before определяет гонки данных?
• Как можно автоматически обнаруживать гонки данных?

Key theories

Взаимное исключение

Решение Дейкстры проблемы параллельного управления установило взаимное исключение как фундаментальное требование синхронизации, гарантирующее, что критические секции не выполняются одновременно.

Транзакционная память

Херлихи и Мосс предложили транзакционную память, в которой группы операций с памятью выполняются атомарно, предлагая компонуемую альтернативу мелкозернистой блокировке для создания параллельных структур данных.

Happens-before и динамическое обнаружение гонок

Основываясь на отношении happens-before Лэмпорта, детектор Eraser показал, как динамически находить гонки данных путем проверки дисциплины блокировки, что является примером автоматического обнаружения гонок.

Clinical relevance

Корректная синхронизация является критически важной для надежного параллельного и многопоточного программного обеспечения; гонки данных вызывают одни из самых трудноуловимых ошибок на практике. Детекторы гонок, транзакционная память и дисциплинированные шаблоны синхронизации являются центральными инструментами для создания надежных многопоточных систем.

History

Решение Дейкстры 1965 года для взаимного исключения и его последующие семафоры заложили основы синхронизации, за которыми последовали мониторы Хоара и Бринча Хансена. Отношение happens-before Лэмпорта 1978 года лежит в основе современных определений гонок; Херлихи и Мосс представили транзакционную память в 1993 году, а динамические детекторы гонок, такие как Eraser (1997) и более поздние инструменты на основе happens-before, стали стандартом для отладки параллелизма.

Debates

Блокировки против безблокировочных и транзакционных подходов

Разработчики обсуждают традиционную синхронизацию на основе блокировок, которая проста, но подвержена взаимоблокировкам и плохой композиции, в сравнении с безблокировочными алгоритмами и транзакционной памятью, которые улучшают композицию и гарантии прогресса ценой сложности или накладных расходов.

Key figures

• Edsger Dijkstra
• Leslie Lamport
• Maurice Herlihy
• C. A. R. Hoare
• Stefan Savage

Seminal works

• dijkstra1965
• herlihy1993
• savage1997
• lamport1978

Frequently asked questions

Что такое гонка данных?

Гонка данных возникает, когда два потока обращаются к одной и той же ячейке памяти одновременно, по крайней мере один доступ является записью, и доступы не упорядочены синхронизацией, что приводит к неопределенному или непредсказуемому поведению в большинстве моделей памяти.

В чем разница между синхронизацией на основе блокировок и синхронизацией без блокировок?

Синхронизация на основе блокировок использует взаимное исключение, так что только один поток входит в критическую секцию за раз, в то время как синхронизация без блокировок использует атомарные операции, чтобы гарантировать, что какой-либо поток всегда достигает прогресса без удержания блокировок, избегая взаимоблокировок.