Специальные методы управления памятью

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

Главную заботу при работе с неблокирующими структурами представляет проблема освобождения памяти, занимаемой удаляемыми узлами. В случае работы со структурой, основанной на блокировках, легко гарантировать, что когда некий поток удаляет узел из динамической структуры, никакой другой поток впоследствии не обратится к памяти этого узла, до тех пор, пока она не будет заново перераспределена. В результате, для удаляющего потока обычно является вполне безопасным освобождение памяти, занимаемой узлом (например, с помощью delete) для последующего произвольного ее выделения в другом потоке (например, с помощью new).

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

Есть несколько способов, которые применяются в различных системах с целью выполнения этой задачи:

• Метод использования специальных тэгов (счетчиков изменений) памяти, основывающийся на ассоциировании специального тега с каждым адресом памяти, который может быть использован в операции;

• Метод неблокирующего подсчета ссылок, основывающийся на включении в структуру динамического узла специального счётчика ссылок;

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

• Метод опасных указателей, основывающийся на ассоциировании с каждым потоком, который должен работать со структурами, некоторого числа (обычно один или два) указателей с типом доступа один писатель – много читателей.

Также существует другая связанная с повторным использованием памяти проблема – это так называемая проблема ABA. Ее наличие влияет практически на все неблокирующие алгоритмы. Проблема эта обнаруживается тогда, когда поток читает значение A из некоей разделяемой области памяти, далее другой поток изменяет значение в этой области памяти на B, после чего снова на A. Позднее, когда первый поток проверяет, не изменилось ли значение, например, с помощью CAS, сравнение с сохраненным значением возвращает истину (то есть не изменилось). И поток продолжает выполнение далее, ошибочно считая, что значение не изменялось с момента первого чтения. В результате, поток может повредить структуру данных или вернуть неверный результат, поскольку другой поток мог произвести другие, скрытые изменения, которые первый поток просто не обнаружит.

Проблема ABA является фундаментальной, и должна быть устранена вне зависимости от способа обеспечения повторного использования памяти. Однако методы обеспечения повторного использования памяти (например, сборка мусора или garbage collection (GC)) часто предотвращают возникновение этой проблемы в качестве побочного эффекта, так сказать, без каких бы то ни было дополнительных затрат, но, к сожалению, в некоторых языках нет сборщика мусора.