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

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

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

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

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

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

Другой способ — использовать узлы повторно и полностью освобождать их только тогда, когда уничтожается вся структура данных. Раз узлы используются повторно, то память никогда не становится недействительной, поэтому некоторые проблемы, сопряженные с неопределенным поведением, вообще не возникают. Недостаток же в том, что взамен появляется так называемая проблема 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(), должен дождаться, пока другой поток, выполняющий ту же операцию, завершит свои действия. Если ничего не предпринимать, то этот поток будет крутиться в цикле активного ожидания, впустую расходуя процессорное время и не продвигаясь ни на шаг. Наличие цикла ожидания в действительности эквивалентно блокирующей операции, а тогда с равным успехом можно было бы воспользоваться мьютексами. Модифицировав алгоритм таким образом, что ожидающий поток выполняет неполные шаги, если планировщик выделил ему время до завершения работы в исходном потоке, мы сможем устранить активное ожидание и сделать операцию неблокирующей. В примере очереди нам для этого потребовалось сделать одну переменную-член атомарной и использовать для ее установки операции сравнения с обменом, но в более сложных структурах данных могут понадобиться более обширные изменения.