Блокировка свободный список удалить операцию

Question

У меня есть следующее определение проблемы:

Дизайн замок свободной простой связанный список со следующими операциями:

• Добавить (пункт): добавить узел в начало (руководитель) списка
• Remove (пункт): удалить данный пункт из списка

Ниже показан код реализован до сих пор:

public class List<T> 
{ 
    private readonly T _sentinel; 
    private readonly Node<T> _head; 

    public List() 
    { 
     _head = new Node<T>(); 
     _sentinel = default(T); 
    } 

    public List(T item) 
    { 
     _head = new Node<T>(item); 
     _sentinel = item; 
    } 

    public void Add(T item) 
    { 
     Node<T> node = new Node<T>(item); 

     do 
     { 
      node.Next = _head.Next; 
     } 
     while (!Atomic.CAS(ref _head.Next, node.Next, node)); 
    } 

    public void Remove(Node<T> item) 
    { 
     Node<T> next; 
     Node<T> oldItem = item; 

     if (item.Value.Equals(_sentinel)) 
      return; 

     item.Value = _sentinel; 

     do 
     { 
      next = item.Next; 

      if (next == null) 
      { 
       Atomic.CAS(ref item.Next, null, null); 
       return; 
      } 

     } while (!Atomic.CAS(ref item.Next, next, next.Next)); 

     item.Value = next.Value; 
    } 
} 

Голова на самом деле является фиктивным (дозорным) узлом, предназначенным для удобства использования. Практический руководитель на самом деле _head.Next. Проблема заключается в операции удаления при попытке удалить последний элемент из списка:

На REMOVE части есть два случая:

1. Узел имеет следующие not- null следующий указатель: затем выполните операцию CAS и украдите данные о значении следующего элемента, удалив фактически следующий элемент.
2. Проблемный случай, когда элемент для удаления является последним в списке:
   • Do Atomically: If (item == oldItem и item.Next == null) then item = null где oldItem - указатель на удаляемый элемент;

Так что я хочу сделать, это в случае удаления C узла:

• если (C == старого C-ссылки и C .next = = null), то C = null => all atomically

Проблема в том, что у меня есть CAS только на одном объекте. Как я могу решить эту проблему атомарно? Или есть лучший способ сделать эту операцию удаления, которую я упускаю здесь?

Answer 1

при удалении B мы делаем трюк путем копирования содержимого Си к B и C: удаление B.Next = C.Next (в цикле) и B.Value = C.Value после того, как движение удалось

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

class ValuePlusNext<T> { 
T Value; 
Node<T> Next; 
} 

class Node<T> { 
ValuePlusNext<T> Value; 
} 

Теперь вы можете записать оба значения в одной атомарной операции. CAS(ref Value, new ValuePlusNext<T>(next.Value, next.Value.Next). Что-то вроде того.

Странно, что ValuePlusNext имеет ту же структуру, что и ваш старый класс узла. В некотором смысле вы теперь управляете двумя физическими узлами связанного списка для каждого логического.

while (true) { 
var old = item.Value; 
var new = new ValuePlusNext(...); 
if (CAS(ref Value, old, new)) break; 
}