Lock Free Deque, который поддерживает удаление произвольного узла

Question

Это должно быть без блокировки, поскольку оно должно выполняться в обработчике прерываний системы SMP. Я не могу взять замки.

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

Поэтому я вижу, что было бы неплохо сделать следующее: Непрерывный массив содержит не только значения, но и левый и правый указатели, создавая таким образом деку. Только свободные значения имеют действительные указатели влево / вправо. Я могу быстро добраться до произвольных узлов, потому что это всего лишь индексный доступ в очередь.

Теперь, в сущности: есть ли хороший алгоритм блокировки без блокировок, который относительно эффективен и может поддерживать удаление произвольного узла?

Answer 1

Непрерывный массив содержит не только значения, но и левый и правый указатели, таким образом делая deque.

[надрез]

Теперь, в самом деле: есть ли хороший алгоритм блокировки без блокировки, который относительно эффективен и может поддерживать удаление произвольного узла?

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

Существует двухсвязный список без блокировок, но он требует сборки мусора.

Как насчет этого; есть фриланлист Это представляет доступные узлы. Узлы на самом деле являются массивом, так что вы можете индексировать их. Когда вам нужно использовать произвольный узел, индексируйте в массив, а затем CAS флаг в этом элементе, но оставляйте его в списке фриланса (вы, конечно, должны это делать, так как он не находится вверху списка фриланса). Когда вы в будущем зайдете и обнаружите, что извлекаете элемент, который уже использовался, продолжайте нажимать, пока не найдете бесплатный.

Answer 2

В системе сбора мусора можно иметь односвязный список с поддержкой логического удаления элементов без блокировок, если вас не волнует, когда физически освободится память для элементов, и если это невозможно добавить элемент сразу после удаляемого элемента. Присвойте каждому элементу удаленный флаг и создайте процедуру обхода списка, которая будет проверять при посещении каждого элемента, был ли удален следующий узел; если он есть, используйте сравнить и поменять местами, чтобы развернуть указатель «next» текущего узла. Обратите внимание, что возможно, что «следующий» указатель удаляемого узла может быть изменен, но только для пропуска узла, следующего за ним. Возможно, что изменение следующего указателя может привести к повторной привязке узла, который был только что отсоединен от списка (например, A-> B-> C-> D может, если B и C удалены одновременно, стать A-> B- > D (размахивая B s указатель), а затем A-> C-> D (поворачивая указатель A к фиксированному значению указателя «next» B). Однако, если узел C был и продолжает помечаться как «удаленный», это не должно вызывать проблем, так как в следующий раз, когда список будет повторяться, указатель A переместится на D.

Два предостережения: -1- В системе без сбора мусора может быть трудно узнать, когда узел действительно может быть освобожден; освобождение узла и затем возврат указателя на него может привести к неопределенному поведению; -2- Если узел добавляется сразу после удаленного узла, указатель может качаться, чтобы отключить новый узел. Если узлы всегда будут добавляться в конец очереди, можно избежать этой последней проблемы, заканчивая очередь фиктивным узлом, который нельзя удалить, пока за ним не последует другой узел.