Безопасна ли эта вставка dlist без блокировки?

TL:DR: вставки сами по себе в порядке, в зависимости от того, что делают считыватели (без долговременного повреждения), но удаление, вероятно, невозможно без блокировки или гораздо более изощренных действий, и, безусловно, эта простая вставка является преувеличением. алгоритм.

Это двусвязный список, поэтому вставка неизбежно требует изменения двух областей памяти, которые уже видны другим потокам: head.next и указатель .prev в старом первом узле. Это не может быть выполнено атомарно+без блокировки, если аппаратное обеспечение не имеет DCAS (двойной CAS, два отдельные несмежные местоположения одновременно). Как говорится в статье в Википедии, это упрощает создание двусвязных списков без блокировки.

В какой-то момент у m68k был DCAS, но его нет ни в одной современной основной архитектуре ЦП. ISO C++11 не раскрывает операцию DCAS через std::atomic, потому что вы не можете эмулировать ее на аппаратном обеспечении, в котором ее нет, не сделав все atomic<T> без блокировки. За исключением оборудования с транзакционной памятью, доступного на некоторых последних процессорах x86 от Intel (например, Broadwell и более поздних версиях), но не AMD. Была проведена некоторая работа по добавлению синтаксиса для TM в C++, см. https://en.cppreference.com/w/cpp/language/transactional_memory

Конечно, наблюдатель также не может наблюдать за двумя местоположениями одновременно, атомарно, без транзакционной памяти или чего-то вроде DCAS. Таким образом, любые потоки, читающие список, должны ожидать, что он будет меняться из-под их, особенно если список также должен поддерживать удаление.

Настройка указателей в новых узлах (еще не опубликованных в других потоках) перед публикацией, очевидно, хороша, и вы делаете это. first->prev и last->next установлены правильно до того, как CAS попытается опубликовать эти новые узлы. CAS имеет последовательное упорядочивание памяти, поэтому он гарантирует, что эти предыдущие хранилища видны другим потокам, прежде чем он сам. (Таким образом, эти «частные» хранилища также могут быть std::memory_order_relaxed для эффективности).

Ваш выбор изменить указатель .prev старого первого после изменения head имеет большой смысл. По сути, вы публикуете сначала в прямом направлении, а затем в обратном направлении. Но помните, что поток может длительное время находиться в состоянии сна в любом месте, поэтому нельзя на 100 % предполагать, что это всегда будет временным несоответствием. Представьте себе остановку. один поток в отладчике в любой момент внутри этой функции, и даже пошагово, в то время как другие потоки выполняются. В этом случае есть только 2 интересные операции: CAS и безусловное сохранение в старом первом нефиктивном узле.

Если поток перемещался вперед и зависел от возможности вернуться назад, следуя .prev (вместо запоминания своего предыдущего в локальной переменной), это могло выглядеть для него так, как будто новые узлы были снова удалены. Он может найти .prev, указывающий на head. Это надуманный пример, потому что обычно было бы более эффективно просто запомнить предыдущий узел, если вы хотите иметь возможность найти его снова, особенно в незаблокированном списке. Но, возможно, есть ненадуманные случаи, например, может быть, одна нить движется вперед, а другая - назад, и, возможно, взаимодействуют прямо или косвенно, где несоответствие будет видно.

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

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

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

Поэтому каждая операция вставки "требует" узел, который она использует в качестве точки вставки в обратный список, когда его хранилище в current_next->prev становится видимым.

Цикл do{}while(!CAS()) — хорошая идиома, обычно упрощающая код. Я ослабил упорядочение в памяти других операций, особенно приватных, в первую и последнюю очередь, потому что требовать от компилятора использования медленных барьеров после сохранения элементов, которые другие потоки еще не могут видеть, неэффективно. На x86 релизные хранилища «бесплатны» (без дополнительных барьеров), а хранилища seq-cst стоят дороже. (Хранилище seq-cst на x86 стоит примерно столько же, сколько атомарное чтение-изменение-запись в неконкурентном случае).

// no change in logic to yours, just minimize memory ordering
// and simplify the loop structure.
void insertSublist(Node* first, Node* last)
{
  first->prev.store(&head, std::memory_order_relaxed);
  Node* current_next = head.next.load(std::memory_order_relaxed);

  do {
    // current_next set ahead of first iter, and updated on CAS failure
    last->next.store(current_next, std::memory_order_relaxed);
  }while (!head.next.compare_exchange_weak(current_next, first));
   // acq_rel CAS should work, but leave it as seq_cst just to be sure.  No slower on x86

  current_next->prev.store(last, std::memory_order_release);  // not visible before CAS
}

Кроме того, do{}while(!CAS) с конечным хранилищем, полностью выходящим за пределы цикла, вероятно, легче для людей читать и сразу видеть логику.

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

head.next - а если это единственный узел в списке?

(Кроме того, если вы переработаете память для этого узла, хранилище вставщика затем наступит на что-то.)

Это приведет к рассинхронизации прямого и обратного списков. Я не вижу способа решить эту проблему без DCAS (или транзакционной памяти, которая является расширенным набором DCAS). Однако я не специалист по блокировкам dlist, так что, возможно, здесь есть хитрость.

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

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

Удаление — это серьезное осложнение