7.3.3. Помните о проблеме 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 особенно часто встречается в алгоритмах, в которых используются списки свободных узлов или иные способы повторного использования узлов вместо возврата их распределителю.