Cercando di scrivere una lista concatenata non bloccata, guai con la rimozione

Question

Sto provando a scrivere una lista di link separati. La coerenza finale non è un problema (qualcuno che attraversa una lista che potrebbe contenere articoli non corretti).

Penso di aver ottenuto l'elemento aggiuntivo corretto (looping e Interlocked.CompareExchange).

Ma non riesco a capire come rimuovere i nodi (in qualsiasi punto dell'elenco) poiché devo ottenere l'elemento precedente e hanno impostato il campo Next nel campo Next dei nodi correnti.

class Node 
{ 
    Node Next; 
    object Value; 
} 

class SinglyLinkedList 
{ 
    Root _root; 

    public void Add(object value) 
    {} 

    public void Remove(object value) 
    {} 
} 

cioè

a -> b -> c

a

un -> c

Pseudo codice:

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

come faccio a fare questa operazione atomica (cioè assicurati che prev.Next = node.Next venga richiamato senza che next o prev sia rimosso in mezzo da un altro thread)?

Potrei usare invece ReaderWriterLockSlim, ma ho trovato questo problema interessante perché so che esistono elenchi concatenati bloccati.

mie preoccupazioni:

segue può accadere se il thread corrente è sospeso tra il loop e l'assegnazione:

• prev stessa potrebbero essere stati rimossi da un altro thread.
• node potrebbe essere stato rimosso da un altro thread.
• Node.Next potrebbe essere rimosso

Answer 1

Sì, aggiungendo è un semplice ciclo a due fasi con CAS sul puntatore precedente .Next; ma rimuovere è difficile!

In realtà non è possibile farlo senza utilizzare un ulteriore elemento di informazione e logica.

Harris ha creato la soluzione a questo problema aggiungendo un bit indicatore che, una volta impostato, non consente a nessuno di modificare il nodo. La rimozione diventa a due passi: il primo (CAS) contrassegna il nodo rimosso per impedire a chiunque di modificarlo (in particolare il puntatore .Next); secondo CAS il nodo precedente. Puntatore successivo, che ora è sicuro perché l'altro nodo è stato contrassegnato.

Il problema è ora che in C Harris sono stati utilizzati i due bit meno significativi del puntatore .Next come marker. Ciò è intelligente perché con i puntatori allineati a 4 byte sono sempre inutilizzati (vale a dire 00) e poiché si inseriscono nel puntatore a 32 bit possono essere atomizzati CAS con il puntatore stesso, che è la chiave di questo algoritmo. Ovviamente questo è impossibile in C#, almeno senza usare codice non sicuro.

La soluzione diventa un po 'più complicata e comporta un riferimento aggiuntivo a una classe immutabile che contiene i due campi (. Successivo + indicatore).

Invece di andare in una lunga spiegazione di quelle idee, ho trovato alcuni riferimenti su internet che andrà in tutti i dettagli che sono necessarie, vedere:

Lock-free Linked List (Part 1) spiega il problema;

Lock-free Linked List (Part 2) Spiega la soluzione C + la soluzione di spinlock;

Lock-free Linked List (Part 3) Spiega il riferimento di stato immutabile;

Se sei davvero curioso dell'argomento, ci sono articoli accademici con varie soluzioni e analisi delle loro prestazioni, ad es. questo: Lock-free linked lists and skip lists