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

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

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

• Дождаться, когда к структуре данных не будет обращаться ни один поток, и удалить разом все объекты, ожидающие удаления.

• Использовать указатели опасности для выявления потока, обращающегося к конкретному объекту.

• Подсчитывать ссылки на объекты и не удалять их, пока ссылки существуют.

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

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

Проблема ABA свойственна любому алгоритму, основанному на сравнении с обменом. Проявляется она следующим образом.

1. Поток 1 читает атомарную переменную xи обнаруживает, что она имеет значение А.

2. Поток 1 выполняет некоторую операцию, исходя из этого значения, например разыменовывает его (если это указатель), выполняет поиск или делает еще что-то.

3. Операционная система приостанавливает поток 1.

4. Другой поток выполняет некоторые операции с x, в результате которых ее значение изменяется и становится равным B.

5. Затем этот поток изменяет данные, ассоциированные со значением A, после чего значение, хранящееся в потоке 1, оказывается недействительным. Это может быть нечто кардинальное, например освобождение памяти, адресуемой указателем, или просто изменение какого-то ассоциированного значения.

6. Далее поток снова изменяет значение xна A, но уже с новыми данными. В случае указателя это может быть новый объект, который но случайному стечению обстоятельства имеет тот же адрес, что прежний.

7. Поток 1 возобновляется и выполняет сравнение с обменом для переменной x, сравнивая ее значение с A. Операция завершается успешно (потому что значение действительно равно A), но это уже не то А . Данные, ранее прочитанные потоком на шаге 2, более не действительны, но поток 1 ничего об этом не знает и повреждает структуру данных.

Ни один из представленных в этой главе алгоритмов не страдает от этой проблемы, но совсем нетрудно написать свободный от блокировок алгоритм, в котором она проявится. Самый распространенный способ избежать ее — хранить вместе с переменной xсчетчик ABA. Операция сравнения с обменом тогда производится над комбинацией xи счетчика, как над единым целым. Всякий раз, как значение заменяется, счетчик увеличивается, поэтому даже если окончательное значение xне изменилось, сравнение с обменом не пройдёт, если другой поток в промежутке изменял x.

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

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

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