Реальные примеры для ABA в многопоточности

Я ищу интересные примеры ABA-проблемы, вызывающие проблемы с многопоточным кодом.

Проблема ABA возникает в параллельном коде при выполнении атомной команды сравнения и замены. Если поток прерывается непосредственно перед выполнением сравнения и свопинга, второй поток может изменить изменение цели сравнения и свопинга от его начального значения А до другого значения B. Если он затем изменяет значение обратно на A до возобновления первого потока, сравнение и обмен будут успешными, несмотря на изменения целевого значения.

Во многих случаях ABA не является проблемой. Возьмите общий счетчик ссылок, например: Даже если пересчет будет изменен одновременно, у нас нет проблемы, если мы никогда не увеличимся с пересчета, который уже упал до 0. Таким образом, нас явно интересует только то, соответствует ли цель ожидаемое значение на момент свопа, а не то, изменилось ли оно в прошлом.

Страница wikipedia содержит пример реализации стека блокировки, который страдает от ABA, но я лично не сталкивался с проблемой в производственный код. Мне было просто любопытно, есть ли у кого-нибудь хорошие истории о войне, чтобы рассказать об АБА.

Ответы

Ответ 1

Предположим, вы хотите реализовать упорядоченный список, используя традиционный связанный список. Предположим, вы хотите добавить новое значение V в список. Во-первых, вам нужно найти нужную позицию для вставки нового элемента с помощью вспомогательного указателя AUX и найти его в последнем node со значением, меньшим, чем V, а также сохранить AUX- > рядом с сравнением в операции CAS, После того, как у вас есть ссылка, вы делаете NEW- > следующие пункты AUX- > next, а затем с помощью CAS вы переключаете AUX- > рядом с NEW, если AUX- > next по-прежнему остается той же ссылкой, которую вы сохранили. Это должно быть примерно так:

AUX = list.HEAD;
WHILE( AUX->next.value < V)
    AUX = AUX->next;
OLD = AUX->next; //line 4
NEW->next = AUX->next; //line 5
IF( CAS(AUX->next, NEW, OLD)) //line 6
    Success!!!
ELSE
    Try again or whatever

Это самый простой способ сделать это. Проблема в том, что между строками 4 и 5 другой поток мог удалить "OLD", а затем вставил другой элемент X меньше V, но все еще больше AUX.value. Если это произойдет, и память, назначенная node со значением X, будет иметь тот же адрес, что и OLD, CAS будет успешным, но список не будет упорядочен. Если действия второго потока происходят между строками 5 и 6, вы потеряете node со значением X. Все это из-за проблемы с ABA.