Войти
При многопоточном вычислениях проблема ABAвозникает во время синхронизация, когда местоположение считывается дважды, имеет одинаковое значение для обоих считываний, а «значение одинаково» используется для обозначения «ничего не изменилось». Однако другой поток может выполняться между двумя чтениями и изменять значение, выполнять другую работу, а затем возвращать значение, таким образом обманывая первый поток, заставляя думать, что «ничего не изменилось», даже если второй поток действительно работал, что нарушает это предположение.
Проблема ABA возникает при чередовании нескольких потоков (или процессов ), обращающихся к общим данным. Ниже приведена последовательность событий, которые приведут к проблеме ABA:
считывает значение A из общей памяти,вытеснено, что позволяет запускать процесс 
,изменяет значение общей памяти A на значение B и обратно на значение A до вытеснения,снова начинает выполнение, видит, что значение общей памяти не изменилось, и продолжается.Хотя
Типичный случай проблемы ABA встречается при реализации структуры данных без блокировок. Если элемент удаляется из списка, удаляется, а затем выделяется и добавляется новый элемент в список, обычно выделенный объект находится в том же месте, что и удаленный объект, из-за выделения памяти MRU. Таким образом, указатель на новый элемент часто совпадает с указателем на старый элемент, что вызывает проблему ABA.
Рассмотрим программный пример ABA, использующий lock-free стек :
/ * Наивный стек без блокировок, который страдает от проблемы ABA. * / Class Stack {std :: atomic top_ptr; // // Извлекает верхний объект и возвращает указатель на него. // Obj * Pop () {while (1) {Obj * ret_ptr = top_ptr; если (! ret_ptr) вернуть nullptr; // Для простоты предположим, что мы можем гарантировать, что это разыменование безопасно // (т. Е. Что за это время ни один другой поток не вытолкнул стек). Obj * next_ptr = ret_ptr->next; // Если верхний узел все еще удерживается, предположим, что никто не изменил стек. // (Это утверждение не всегда верно из-за проблемы с ABA) // Атомарно заменить top на next. если (top_ptr.compare_exchange_weak (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; // Если верхний узел все еще следующий, предположим, что никто не изменил стек. // (Это утверждение не всегда верно из-за проблемы ABA) // Атомно замените top на obj. если (top_ptr.compare_exchange_weak (next_ptr, obj_ptr)) {возврат; } // Стек изменился, начинаем заново. }}}; Этот код обычно может предотвратить проблемы с одновременным доступом, но страдает проблемами ABA. Рассмотрим следующую последовательность:
Первоначально стек содержит вершину → A → B → C
Поток 1 запускает pop:
ret = A; next = B;
Поток 1 прерывается непосредственно перед compare_exchange_weak...
{// Поток 2 запускается pop: ret = A; next = B; compare_exchange_weak (A, B) // Успех, вершина = B return A; } // Теперь стек сверху → B → C {// Поток 2 снова запускает pop: ret = B; следующий = C; compare_exchange_weak (B, C) // Успех, вершина = C return B; } // Теперь стек вверху → C delete B; {// Поток 2 теперь помещает A обратно в стек: A->next = C; compare_exchange_weak (C, A) // Успех, вершина = A}Теперь стек находится на вершине → A → C
Когда поток 1 возобновляется:
compare_exchange_weak (A, B)
Эта инструкция выполняется успешно, потому что она находит top == ret (оба значения A), поэтому она устанавливает значение top на next (которое является B). Поскольку B был удален, программа будет обращаться к освобожденной памяти, когда она пытается просмотреть первый элемент в стеке. В C ++, как показано здесь, доступ к освобожденной памяти - это неопределенное поведение : это может привести к сбоям, повреждению данных или даже просто незаметно работать правильно. Такие ошибки ABA может быть сложно отладить.
Настоящая проблема заключается не в «ABA», то есть, было ли изменено значение A, в данном примере не имеет значения. Настоящая проблема заключается в том, что B удаляется из списка, а занимаемая им память освобождается. Даже если A не был изменен, то есть связанный список одинарно связан в обратном направлении C->B->A и tail->A, но B удаляется и освобождается другим потоком, проблема выше все еще существует. Это приводит к другой проблеме, т. Е. Если B удаляется из списка другим потоком, хвост будет указывать на удаленный B. Таким образом, «проблема ABA» на самом деле является «проблемой B», которая не имеет большого отношения к A.
Обычным обходным путем является добавление дополнительных битов «тега» или «штампа» к рассматриваемому количеству. Например, алгоритм, использующий compare и swap для указателя, может использовать младшие биты адреса, чтобы указать, сколько раз указатель был успешно изменен. Из-за этого следующее сравнение и замена не удастся, даже если адреса совпадают, потому что биты тега не будут совпадать. Иногда это называют ABAʹ, поскольку второй A немного отличается от первого. Такие ссылки на тегированные состояния также используются в транзакционной памяти. Хотя для реализации можно использовать тегированный указатель , предпочтительнее использовать отдельное поле тега, если доступен CAS двойной ширины.
Если поле «тег» оборачивается, гарантии против ABA больше не действуют. Однако было замечено, что на существующих в настоящее время процессорах и при использовании 60-битных тегов циклический переход невозможен, пока время жизни программы (то есть без перезапуска программы) ограничено 10 годами; Кроме того, утверждалось, что для практических целей обычно достаточно иметь 40-48 бит тега, чтобы гарантировать от зацикливания. Поскольку современные процессоры (в частности, все современные процессоры x64), как правило, поддерживают 128-битные операции CAS, это может дать твердые гарантии против ABA.
Правильный, но дорогостоящий подход - использовать промежуточные узлы, не являющиеся элементами данных, и таким образом обеспечивать инварианты при вставке и удалении элементов [Валуа].
Другой подход - отложить восстановление удаленных элементов данных. Один из способов отсрочить восстановление - запустить алгоритм в среде с автоматическим сборщиком мусора ; Однако проблема здесь в том, что если сборщик мусора не является свободным от блокировок, то вся система не является свободным от блокировок, даже несмотря на то, что сама структура данных является.
Другой способ отложить восстановление - использовать один или несколько указателей опасности, которые являются указателями на места, которые в противном случае не могут появиться в списке. Каждый указатель опасности представляет собой промежуточное состояние незавершенного изменения; наличие указателя гарантирует дальнейшую синхронизацию [Дуг Ли]. Указатели опасности не имеют блокировок, но могут отслеживать только фиксированное количество элементов в потоке как используемых.
Еще один способ отложить восстановление - использовать обновление чтения-копии (RCU), которое включает в себя включение обновления в критическую секцию RCU на стороне чтения и затем ожидание льготного периода RCU перед освобождением любых удаленных элементов данных. Использование RCU таким образом гарантирует, что любой удаленный элемент данных не может появиться снова, пока все выполняемые в данный момент операции не будут завершены. RCU не требует блокировки, но подходит не для всех рабочих нагрузок.
Некоторые архитектуры предоставляют «более крупные» атомарные операции, например, прямые и обратные ссылки в двусвязном списке могут обновляться атомарно; хотя эта функция зависит от архитектуры, она, в частности, доступна для архитектур x86 / x64 (x86 допускает 64-битный CAS, а все современные процессоры x64 допускают 128-битный CAS) и IBM z / Architecture (что позволяет использовать CAS до 128 бит).
В некоторых архитектурах предусмотрена команда загрузки, связанная с условием сохранения,, в которой сохранение выполняется только тогда, когда нет других хранилищ в указанном месте. Это эффективно отделяет понятие «хранилище содержит значение» от «хранилище было изменено». Примеры включают DEC Alpha, MIPS, PowerPC, RISC-V и ARM (v6 и новее).
| journal =(помощь )| journal =(справка ) 