Пытаясь написать незакрепленный личный список, проблемы с удалением

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

Я думаю, что я получил элемент add right (looping и Interlocked.CompareExchange).

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

class Node
{
    Node Next;
    object Value;
}

class SinglyLinkedList
{
    Root _root;

    public void Add(object value)
    {}

    public void Remove(object value)
    {}
}

то есть.

a → b → c

to

a → c

Псевдокод:

Node prev;
Node node = _root;
while (node.Value != nodeValue)
{
  prev = node;
  node = node.Next;
}
prev.Next = node.Next;

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

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

Мои проблемы:

При текущем потоке между циклом и присваиванием может произойти следующее:

  • Сам
  • prev мог быть удален другим потоком.
  • node может быть удален другим потоком.
  • Node.Next может быть удален

Ответы

Ответ 1

Да, добавление - простой двухступенчатый цикл с CAS в предыдущем указателе .Next; но удаление трудно!

На самом деле вы не можете сделать это, не используя дополнительную информацию и логику.

Харрис создал решение этой проблемы, добавив бит маркера, который когда-то запретил кому-либо изменять node. Удаление становится двухступенчатым: сначала (CAS) отметьте удаленный node, чтобы никто не мог его изменить (особенно указатель .Next); второй CAS - предыдущий указатель node.Next, который теперь безопасен, поскольку отмечен другой node.

Проблема в том, что в C Harris использовались два наименее значимых бита указателя .Next как маркер. Это умно, потому что с 4-байтовыми ориентированными указателями они всегда не используются (т.е. 00), и поскольку они подходят к 32-битовому указателю, они могут быть CAS атомарно с самим указателем, что является ключом к этому алгоритму. Конечно, это невозможно в С#, по крайней мере, без использования небезопасного кода.

Решение становится немного более сложным и включает дополнительную ссылку на неизменяемый класс, содержащий два поля (.Next + marker).

Вместо того, чтобы вдаваться в подробное объяснение этих идей, я нашел несколько ссылок в Интернете, которые расскажут обо всех деталях, которые вам нужны, см.:

Связанный список без блокировки (часть 1) Объясняет проблему:

Link-Free Linked List (часть 2) Объясняет решение C + решение для спин-блокировки;

Связанный список без блокировки (часть 3) Объясняет ссылку на неизменяемое состояние;

Если вы действительно интересуетесь этой темой, есть научные статьи с различными решениями и анализ их эффективности, например. этот: Не привязанные по ссылке списки и списки пропуска