Порядок доступа к памяти std::memory_order_seq_cst гораздо проще для понимания и анализа, чем любой другой, потому что операции с такой семантикой полностью упорядочены. Во всех примерах из этой главы мы начинали с упорядочения std::memory_order_seq_cst и только потом ослабляли ограничения. В этом смысле использование других способов упорядочения можно считать
Одна из самых сложных сторон написания свободного от блокировок кода — управление памятью. С одной стороны, требуется любой ценой предотвратить удаление объектов, на которые могут ссылаться другие потоки, а, с другой, удалять объекты как можно раньше, чтобы избежать чрезмерного расхода памяти. В этой главе мы познакомились с тремя методами, обеспечивающими безопасное освобождение памяти.
• Дождаться, когда к структуре данных не будет обращаться ни один поток, и удалить разом все объекты, ожидающие удаления.
• Использовать указатели опасности для выявления потока, обращающегося к конкретному объекту.
• Подсчитывать ссылки на объекты и не удалять их, пока ссылки существуют.
В любом случае идея заключается в том, чтобы каким-то образом отслеживать, сколько потоков обращается к объекту, и удалять его лишь в том случае, когда на него не осталось ни одной ссылки. Существует много методов освобождения памяти в структурах данных, свободных от блокировок. В частности, это идеальная ситуация для применения сборщика мусора. Придумывать алгоритмы гораздо проще, если знаешь, что сборщик мусора удалит узлы, когда они больше не используются, но не раньше.
Другой способ — использовать узлы повторно и полностью освобождать их только тогда, когда уничтожается вся структура данных. Раз узлы используются повторно, то память никогда не становится недействительной, поэтому некоторые проблемы, сопряженные с неопределенным поведением, вообще не возникают. Недостаток же в том, что взамен появляется так называемая
Проблема ABA свойственна любому алгоритму, основанному на сравнении с обменом. Проявляется она следующим образом.
1. Поток 1 читает атомарную переменную x и обнаруживает, что она имеет значение А.
2. Поток 1 выполняет некоторую операцию, исходя из этого значения, например разыменовывает его (если это указатель), выполняет поиск или делает еще что-то.
3. Операционная система приостанавливает поток 1.
4. Другой поток выполняет некоторые операции с x, в результате которых ее значение изменяется и становится равным B.
5. Затем этот поток изменяет данные, ассоциированные со значением A, после чего значение, хранящееся в потоке 1, оказывается недействительным. Это может быть нечто кардинальное, например освобождение памяти, адресуемой указателем, или просто изменение какого-то ассоциированного значения.
6. Далее поток снова изменяет значение x на A, но уже с новыми данными. В случае указателя это может быть новый объект, который но случайному стечению обстоятельства имеет тот же адрес, что прежний.
7. Поток 1 возобновляется и выполняет сравнение с обменом для переменной x, сравнивая ее значение с A. Операция завершается успешно (потому что значение действительно равно A), но
Ни один из представленных в этой главе алгоритмов не страдает от этой проблемы, но совсем нетрудно написать свободный от блокировок алгоритм, в котором она проявится. Самый распространенный способ избежать ее — хранить вместе с переменной x счетчик ABA. Операция сравнения с обменом тогда производится над комбинацией x и счетчика, как над единым целым. Всякий раз, как значение заменяется, счетчик увеличивается, поэтому даже если окончательное значение x не изменилось, сравнение с обменом не пройдёт, если другой поток в промежутке изменял x.
Проблема ABA особенно часто встречается в алгоритмах, в которых используются списки свободных узлов или иные способы повторного использования узлов вместо возврата их распределителю.
