- Проблема ABA
-
В многозадачных вычислениях, проблема ABA возникает при синхронизации, когда ячейка памяти читается дважды, оба раза прочитано одинаковое значение, и признак «значение одинаковое» трактуется как «ничего не менялось». Однако, другой поток может выполниться между этими двумя чтениями, поменять значение, сделать что-нибудь ещё, и восстановить старое значение. Таким образом, первый поток обманется, считая, что не поменялось ничего, хотя второй поток уже разрушил это предположение.
Проблема ABA возникает, когда множество потоков (или процессов) обращаются к разделяемой памяти поочерёдно. Вот пример последовательности событий, ведущих к проблеме ABA:
- Процесс читает значение A из разделяемой памяти,
- вытесняется, позволяя выполняться ,
- меняет значение A на B и обратно на A перед вытеснением,
- возобновляет работу, видит, что значение не изменилось, и продолжает…
Хотя может продолжать работу, возможно, что его поведение будет неправильным, из-за других, скрытых, изменений общей памяти (которые он не отслеживал).
Обычно, с проблемой ABA сталкиваются при реализации lock-free структур и алгоритмов. Если из списка удалить элемент, уничтожить его, а затем создать новый элемент и добавить обратно в список, есть вероятность, что новый элемент будет размещён на месте старого. Указатель на новый элемент совпадёт с указателем на старый, что и приведёт к проблеме: равенство признаков не есть равенство данных целиком.
Содержание
Пример
Рассмотрим lock-free стек:
/* Наивная реализация lock-free стека, страдающая проблемой ABA.*/ class Stack { volatile Obj* top_ptr; // // Снимает верхний элемент и возвращает указатель на него. // Obj* Pop() { while(1) { Obj* ret_ptr = top_ptr; if (!ret_ptr) return NULL; Obj* next_ptr = ret_ptr->next; // Если верхний элемент - всё ещё ret, считаем, что никто не менял стек. // (Это утверждение не всегда истинно, из-за проблемы ABA) // Атомарно заменяем top на next. if (CompareAndSwap(top_ptr, ret_ptr, next_ptr)) { return ret_ptr; } // Иначе - стек изменён, пробуем заново. } } // // Добавляет obj_ptr на вершину стека. // void Push(Obj* obj_ptr) { while(1) { Obj* next_ptr = top_ptr; obj_ptr->next = next_ptr; // Если верхний элемент - всё ещё next, считаем, что никто не менял стек. // (Это утверждение не всегда истинно, из-за проблемы ABA) // Атомарно заменяем top на obj. if (CompareAndSwap(top_ptr, next_ptr, obj_ptr)) { return; } // Иначе - стек изменён, пробуем заново. } } };
Этот код обычно может предотвращать проблемы с конкурентным доступом, но страдает проблемой ABA. Рассмотрим следующую последовательность:
Изначально стек содержит top → A → B → C
Поток 1 начинает выполнять pop:
ret = A; next = B;
Поток 1 прерывается непосредственно перед CompareAndSwap...
{ // Поток 2 выполняет pop: ret = A; next = B; CompareAndSwap(A, A, B) // Удача, top = B return A; } // Теперь на стеке top → B → C { // Поток 2 выполняет pop ещё раз: ret = B; next = C; CompareAndSwap(B, B, C) // Удача, top = C return B; } // Теперь на стеке top → C delete B; { // Поток 2 добавляет A обратно на стек: A->next = C; CompareAndSwap(C, C, A) // Удача, top = A }
Теперь стек содержит top → A → C
Поток 1 продолжает работу:
CompareAndSwap(A, A, B)
Эта инструкция выполняется успешно, поскольку top == ret (оба равны A), то она присваивает top значение next (которое равно B). Но B было уничтожено! Это приведёт к плохим последствиям...
Обходные решения
Обычное обходное решение — это добавить дополнительные биты «метки» в проверяемое значение. Например, алгоритм, использующий compare-and-swap над указателями может использовать младшие биты адреса для проверки, сколько раз указатель был изменён. Из-за этого следующий compare-and-swap не сработает, поскольку биты меток не совпадут. Это не решает проблему полностью (так как биты метки могут «перекрутиться» в исходное положение), но помогает избежать её. Некоторые архитектуры предоставляют двухсловный compare-and-swap, что позволяет сделать большую метку. Обычно это называется ABA', потому что второе значение A слегка отличается от первого.
Правильный, но дорогой подход состоит в использовании промежуточных узлов, которые не являются пользовательскими данными, а обеспечивают инвариантность операций добавления и удаления. [Valois].
Другой подход — использовать один или несколько hazard pointer-ов (указателей опасности), — указателей, которые в принципе не могут появиться в структуре данных. Каждый hazard pointer обозначает промежуточное состояние структуры в процессе изменения; наличие указателей требует дальнейшей синхронизации [Doug Lea].
Некоторые архитектуры предоставляют «укрупнённые» атомарные операции, благодаря чему, например, можно атомарно изменять сразу обе ссылки вперёд и назад в двусвязном списке.
Некоторые архитектуры предоставляют инструкцию load linked, store conditional в которой запись в ячейку возможна, только если не было других записей в указанную ячейку. Это эффективно отделяет признаки «ячейка содержит значение» от «ячейка была изменена». Примеры архитектур — DEC Alpha и PowerPC.
Литература
- Damian Dechev, Peter Pirkelbauer, and Bjarne Stroustrup. Lock-free Dynamically Resizable Arrays
Ссылки
- Double checked locking
- Concurrent Data Structures — схемы решения проблемы ABA на C++ (hazard pointers, pass-the-buck, tagged pointers и другие)
Для улучшения этой статьи по информационным технологиям желательно?: - Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
- Проверить достоверность указанной в статье информации.
- Исправить статью согласно стилистическим правилам Википедии.
- Викифицировать статью.
Категория:- Управление конкурентными потоками
Wikimedia Foundation. 2010.