TL: DR : одни только вставки в порядке, в зависимости от того, что делают читатели (без долговременного повреждения), но удаления, вероятно, невозможны без блокировки или гораздо большей сложности, и, безусловно, для этого необходим демонстрационный шаг. простой алгоритм вставки.
Это двойной связанный список, поэтому вставка неизбежно требует изменения двух областей памяти, которые уже могут видеть другие потоки: head.next и указатель .prev в старом первом узле . Это не может быть выполнено атомарно + без блокировки, если аппаратное обеспечение не имеет DCAS (двойной CAS, два отдельных несмежных местоположения одновременно) . Как говорится в статье в Википедии, она позволяет легко создавать двойные списки без блокировки.
m68k имел DCAS в какой-то момент, но ни у одной современной архитектуры ЦП его нет. ISO C ++ 11 не раскрывает операцию DCAS через std::atomic, потому что вы не можете эмулировать ее в HW, в которой ее нет, не сделав все 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
}
Компилируется для x86 с нулевыми mfence инструкциями вместо 3 для ваших, в проводнике компилятора Godbolt . (Остальная часть asm буквально идентична, в том числе и lock cmpxchg.) Так что в случае неконтролируемого отсутствия RFO (например, многократные вставки из одного и того же ядра), это может быть примерно в 4 раза быстрее. Или лучше, потому что mfence на самом деле даже медленнее, чем префикс lock на процессорах Intel.
Кроме того, do{}while(!CAS) с конечным хранилищем, полностью находящимся за пределами цикла, возможно, людям легче читать и видеть логику сразу.
Удаление является серьезным осложнением
Я не вижу, как вы можете безопасно удалить, пока у вас есть ожидающие вставки. Если вы удалите узел, который инсертор собирался изменить (чтобы добавить обратную ссылку), но еще не удалил, этот диапазон узлов будет навсегда отсутствовать в обратном списке.
(Плюс, если вы перезапустите память для этого узла, то хранилище, вставляемое вставщиком, затем наступит на что-нибудь.)
Синхронизация прямого и обратного списков. Я не вижу способа решить эту проблему без DCAS (или транзакционной памяти, которая является надмножеством DCAS). Я не эксперт по спискам без блокировок, так что, может быть, есть хитрость.
Возможно, даже несколько одновременных съемников являются проблемой, потому что вы можете получить ожидающие модификации узла, который другой поток собирается (или уже удалил) удалить. Или несколько ожидающих модификаций для одного узла, без возможности убедиться, что правильный завершает последний.
Если у вас была блокировка вставок / съемников (несколько вставок / одиночная съемница, точно так же, как блокировка чтения / записи), вы можете убедиться, что при удалении не было ожидающих вставок. Но все же разрешить безблокировочные вставки. Возможно, поместите блокировку в ту же строку кэша, что и head, потому что для вставки потоков всегда нужно будет изменить и ее, и head. Или, может быть, не потому, что вы могли бы просто получить больше разногласий за эту линию, если ядра иногда теряют право собственности на линию после взятия блокировки, но перед фиксацией их изменения в head.