Энтони Уильямс - Параллельное программирование на С++ в действии. Практика разработки многопоточных программ

Шаги удаления узла из списка показаны на рис. 3.1:

1. Найти подлежащий удалению узел ( N ).

2. Изменить «указатель на следующий» в узле, предшествующем N , так чтобы он указывал на узел, следующий за N .

3. Изменить «указатель на предыдущий» в узле, следующем за N , так чтобы он указывал на узел, предшествующий N .

4. Удалить узел N .

Рис. 3.1. Удаление узла из двусвязного списка

Как видите, между шагами bи суказатели в одном направлении не согласуются с указателями в другом направлении, и инвариант нарушается.

Простейшая проблема, которая может возникнуть при модификации данных, разделяемых несколькими потоками, — нарушение инварианта. Если не предпринимать никаких мер, то в случае, когда один поток читает двусвязный список, а другой в это же время удаляет из списка узел, вполне может случиться, что читающий поток увидит список, из которого узел удален лишь частично (потому что изменен только один указатель, как на шаге bна рис. 3.1), так что инвариант нарушен. Последствия могут быть разными — если поток читает список слева направо, то он просто пропустит удаляемый узел. Но если другой поток пытается удалить самый правый узел, показанный на рисунке, то он может навсегда повредить структуру данных, и в конце концов это приведет к аварийному завершению программы. Как бы то ни было, этот пример иллюстрирует одну из наиболее распространенных причин ошибок в параллельном коде: состояние гонки (race condition).

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

В параллельном программировании под состоянием гонки понимается любая ситуация, исход которой зависит от относительного порядка выполнения операций в двух или более потоках — потоки конкурируют за право выполнить операции первыми. Как правило, ничего плохого в этом нет, потому что все исходы приемлемы, даже если их взаимный порядок может меняться. Например, если два потока добавляют элементы в очередь для обработки, то вообще говоря неважно, какой элемент будет добавлен первым, лишь бы не нарушались инварианты системы. Проблема возникает, когда гонка приводит к нарушению инвариантов, как в приведенном выше примере удаления из двусвязного списка. В контексте параллельного программирования состоянием гонки обычно называют именно такую проблематичную гонку — безобидные гонки не так интересны и к ошибкам не приводят. В стандарте С++ определен также термин гонка за данными (data race), означающий ситуацию, когда гонка возникает из-за одновременной модификации одного объекта (детали см. в разделе 5.1.2); гонки за данными приводят к внушающему ужас неопределенному поведению .

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

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

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

Другой вариант — изменить дизайн структуры данных и ее инварианты, так чтобы модификация представляла собой последовательность неделимых изменений, каждое из которых сохраняет инварианты. Этот подход обычно называют программированием без блокировок (lock-free programming) и реализовать его правильно очень трудно; если вы работаете на этом уровне, то приходится учитывать нюансы модели памяти и разбираться, какие потоки потенциально могут увидеть те или иные наборы значений. Модель памяти обсуждается в главе 5, а программирование без блокировок — в главе 7.

Еще один способ справиться с гонками — рассматривать изменения структуры данных как транзакцию , то есть так, как обрабатываются обновления базы данных внутри транзакции. Требуемая последовательность изменений и чтений данных сохраняется в журнале транзакций, а затем атомарно фиксируется. Если фиксация невозможна, потому что структуру данных в это время модифицирует другой поток, то транзакция перезапускается. Это решение называется программной транзакционной памятью (Software Transactional Memory — STM), в настоящее время в этой области ведутся активные исследования. Мы не будем рассматривать STM в этой книге, потому что в С++ для нее нет поддержки. Однако к самой идее о том, чтобы выполнить какую-то последовательность действий и за один шаг зафиксировать результаты, я еще вернусь.