Проблема ABA - ABA problem

В многопоточный вычисление, то Проблема ABA происходит во время синхронизации, когда местоположение считывается дважды, имеет одинаковое значение для обоих считываний, а «значение одинаково» используется для обозначения «ничего не изменилось». Однако другой поток может выполняться между двумя чтениями и изменять значение, выполнять другую работу, а затем возвращать значение, таким образом обманывая первый поток, заставляя думать, что «ничего не изменилось», даже если второй поток действительно работал, что нарушает это предположение.

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

Процесс ${ displaystyle P_ {7}}$ читает значение A из разделяемой памяти,
${ displaystyle P_ {5}}$ является вытесненный, позволяя процесс ${ displaystyle P_ {7}}$ бежать,
${ displaystyle P_ {7}}$ изменяет значение общей памяти A на значение B и обратно на A перед приоритетным прерыванием,
${ displaystyle P_ {5}}$ снова начинает выполнение, видит, что значение разделяемой памяти не изменилось, и продолжается.

Несмотря на то что ${ displaystyle P_ {5}}$ может продолжить выполнение, возможно, что поведение будет некорректным из-за «скрытой» модификации в общей памяти.

Типичный случай проблемы ABA встречается при реализации без блокировки структура данных. Если элемент удаляется из списка, удаляется, а затем выделяется новый элемент и добавляется в список, обычно выделенный объект находится в том же месте, что и удаленный объект, из-за выделения памяти MRU. Таким образом, указатель на новый элемент часто совпадает с указателем на старый элемент, что вызывает проблему ABA.

Примеры

Рассмотрим программный пример ABA с использованием без блокировки куча:

/ * Наивный стек без блокировок, страдающий от проблем с ABA. * /учебный класс Куча {  стандартное::атомный<Obj*> top_ptr;  //  // Извлекает верхний объект и возвращает указатель на него.  //  Obj* Поп() {    пока (1) {      Obj* ret_ptr = top_ptr;      если (!ret_ptr) возвращаться nullptr;      // Для простоты предположим, что мы можем гарантировать, что это разыменование безопасно      // (т.е. что ни один другой поток пока что не извлекал стек).      Obj* next_ptr = ret_ptr->следующий;      // Если верхний узел все еще удерживается, предположим, что никто не изменил стек.      // (Это утверждение не всегда верно из-за проблемы ABA)      // Атомарно заменить верхнюю на следующую.      если (top_ptr.compare_exchange_weak(ret_ptr, next_ptr)) {        возвращаться ret_ptr;      }      // Стек изменился, начать заново.    }  }  //  // Помещает объект, указанный obj_ptr, в стек.  //  пустота Толкать(Obj* obj_ptr) {    пока (1) {      Obj* next_ptr = top_ptr;      obj_ptr->следующий = next_ptr;      // Если верхний узел все еще следующий, предположим, что никто не изменил стек.      // (Это утверждение не всегда верно из-за проблемы ABA)      // Атомно заменяем top на obj.      если (top_ptr.compare_exchange_weak(next_ptr, obj_ptr)) {        возвращаться;      }      // Стек изменился, начать заново.    }  }};

Этот код обычно может предотвращать проблемы с одновременным доступом, но страдает проблемами ABA. Рассмотрим следующую последовательность:

Стек изначально содержит верх → А → Б → С

Поток 1 запускает pop:

ret = A; следующий = B;

Поток 1 прерывается непосредственно перед compare_exchange_weak...

{ // Поток 2 запускает pop:  Ret = А;  следующий = B;  compare_exchange_weak(А, B)  // Успех, вверху = B  возвращаться А;} // Теперь стек верхний → B → C{ // Поток 2 снова запускает pop:  Ret = B;  следующий = C;  compare_exchange_weak(B, C)  // Успех, вверху = C  возвращаться B;} // Теперь стек вверху → CУдалить B;{ // Поток 2 теперь помещает A обратно в стек:  А->следующий = C;  compare_exchange_weak(C, А)  // Успех, вверху = A}

Теперь стек верх → А → С

Когда поток 1 возобновляется:

compare_exchange_weak (А, В)

Эта инструкция выполняется успешно, поскольку находит верх == ret (оба являются A), поэтому он устанавливает верхний на следующий (который является B). Поскольку B был удален, программа будет обращаться к освобожденной памяти, когда она пытается просмотреть первый элемент в стеке. В C ++, как показано здесь, доступ к освобожденной памяти неопределенное поведение: это может привести к сбоям, повреждению данных или даже просто молча работать правильно. Такие ошибки ABA может быть сложно отладить.

Настоящая проблема заключается не в «ABA», т. Е. Было ли изменено значение A, не имеет значения в данном примере. Настоящая проблема заключается в том, что B удаляется из списка, а занимаемая им память освобождается. Даже если A не был изменен, то есть связанный список одинарно связан в обратном направлении C-> B-> A и tail-> A, но B удаляется и освобождается другим потоком, проблема выше все еще существует. Это приводит к другой проблеме, т. Е. Если B удаляется из списка другим потоком, хвост будет указывать на удаленный B. Таким образом, «проблема ABA» на самом деле является «проблемой B», которая не имеет большого отношения к A.

Обходные пути

Ссылка на состояние с тегами

Обычный обходной путь - добавить дополнительные биты «тега» или «штампа» к рассматриваемому количеству. Например, алгоритм, использующий сравнить и поменять местами в указателе могут использоваться младшие биты адреса, чтобы указать, сколько раз указатель был успешно изменен. Из-за этого следующее сравнение и замена не удастся, даже если адреса совпадают, потому что биты тега не будут совпадать. Иногда это называют ABAʹ, поскольку второй A немного отличается от первого. Такие ссылки на состояние с тегами также используются в транзакционная память. Хотя помеченный указатель может использоваться для реализации, отдельное поле тега предпочтительнее, если доступен CAS двойной ширины.

Если поле «тег» оборачивается, гарантии против ABA больше не действуют. Однако было замечено, что на существующих в настоящее время процессорах и при использовании 60-битных тегов циклический переход невозможен, пока время жизни программы (то есть без перезапуска программы) ограничено 10 годами; Кроме того, утверждалось, что для практических целей обычно достаточно иметь 40-48 бит тега, чтобы гарантировать от зацикливания. Поскольку современные процессоры (в частности, все современные процессоры x64), как правило, поддерживают 128-битные операции CAS, это может дать твердые гарантии против ABA.^[1]

Промежуточные узлы

Правильный, но дорогостоящий подход - использовать промежуточные узлы, которые не являются элементами данных, и таким образом обеспечивать инварианты при вставке и удалении элементов [Валуа].

Отложенная рекламация

Другой подход - отложить восстановление удаленных элементов данных. Один из способов отсрочить восстановление - запустить алгоритм в среде с автоматический сборщик мусора; Однако проблема здесь в том, что если сборщик мусора не является свободным от блокировок, то вся система не является свободным от блокировок, даже несмотря на то, что сама структура данных является.

Еще один способ отсрочить возврат - использовать один или несколько указатели опасности, которые являются указателями на места, которые иначе не могут появиться в списке. Каждый указатель опасности представляет собой промежуточное состояние незавершенного изменения; наличие указателя гарантирует дальнейшую синхронизацию [Дуг Ли]. Указатели опасности не блокируются, но могут отслеживать только фиксированное количество элементов в потоке как используемых.

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

Некоторые архитектуры предоставляют «более крупные» атомарные операции, например, прямые и обратные ссылки в двусвязном списке могут обновляться атомарно; хотя эта функция зависит от архитектуры, она, в частности, доступна для архитектур x86 / x64 (x86 допускает 64-битный CAS, а все современные процессоры x64 допускают 128-битный CAS) и IBM z / Архитектура (что позволяет использовать CAS до 128 бит).

Некоторые архитектуры предоставляют загрузка связана, хранить условно инструкция, при которой магазин выполняется только при отсутствии других магазинов указанного места. Это эффективно отделяет понятие «хранилище содержит значение» от «хранилище было изменено». Примеры включают DEC Alpha, MIPS, PowerPC, RISC-V и РУКА (v6 и новее).

Смотрите также

Проблема читателей – писателей

Параллельные вычисления
Общий	Параллелизм Контроль параллелизма
Расчет процесса	CSP CCS ACP LOTOS π-исчисление Окружающий расчет API-исчисление PEPA Соединение-исчисление
Классические проблемы	Проблема ABA Проблема курильщиков сигарет Тупик Проблема обедающих философов Проблема производителя и потребителя Состояние гонки Проблема читателей – писателей Проблема сна парикмахера Проблема чтения из непостоянной записи
Категория: Параллельные вычисления