È un blocco (attesa) Gratis doppiamente collegata lista possibile?

Question

Questa domanda con C # tag, ma se è possibile, dovrebbe essere possibile in qualsiasi lingua.

E 'possibile implementare una lista doppiamente concatenata utilizzando le operazioni Interlocked per fornire non-attesa di blocco? Vorrei inserire, aggiungere e rimuovere, e chiaro senza aspettare.

Answer 1

Una semplice ricerca su Google rivelerà molte carte lista doppiamente collegata senza blocchi.

Tuttavia, esse sono basate su CAS atomica (confrontare e swap).

Non so come le operazioni atomiche in C # sono, ma secondo il sito

http://www.albahari.com/threading/part4.aspx

Operazioni C # sono garantiti solo per essere atomica per la lettura e la scrittura di un campo a 32 bit. Nessuna menzione di CAS.

Answer 2

Sì, è possibile, ecco la mia implementazione di uno STL-come Blocca-free Doppiamente-Linked List in C ++.

codice di esempio che genera thread per eseguire in modo casuale op sul lista

Si richiede un confronto-e-swap a 64 bit per operare senza problemi ABA. Questo elenco è possibile solo a causa di una lock-libera gestore di memoria .

Controlla la noreferrer parametri di riferimento a pagina 12 . Prestazioni dell'elenco scala linearmente con il numero di fili da aumenti contesa. L'algoritmo supporta il parallelismo per accessi disgiunti, così come le dimensioni dell'elenco aumenta contesa può diminuire.

Answer 3

Ecco un carta che discribes un libero lista collegata doublly serratura.

  

Vi presentiamo un efficiente e pratico   lock-libera implementazione di un   deque concomitante che è   disgiunti-parallelo accessibile e usi   primitive atomiche che sono disponibili   nei moderni sistemi informatici. In precedenza   noti algoritmi senza blocchi di deque   sono sia basata sulla non disponibili   primitive di sincronizzazione atomici,   attuare solo un sottoinsieme della   la funzionalità, o non sono progettati per   disgiunti accessi. Il nostro algoritmo è   sulla base di una lista doppiamente collegata, e   richiede solo single-word   confrontare-e-swap ...

Ross Bencina ha alcuni davvero buoni collegamenti Ho appena trovato con documenti numerious e excamples codice sorgente per " Alcune note su algoritmi di lock-libero e attendere senza ".

Answer 4

Non credo che questo sia possibile, dal momento che stai dover impostare riferimenti multipli in un solo colpo, e le operazioni intrecciate sono limitati nella loro alimentazione.

Per esempio, prendiamo l'operazione di aggiunta - se si sta inserendo il nodo B tra A e C, è necessario impostare B-> prossimo, B-> prev, A-> prossimo, e C-> prev in uno atomica operazione. Interlocked non è in grado di gestire questo. Preselezione elementi di B non ha nemmeno aiuta, perché un altro thread potrebbe decidere di fare un inserto, mentre si sta preparando "B".

Mi piacerebbe concentrarsi di più su come ottenere il blocco di grana fine possibile in questo caso, non cercando di eliminarla.

Answer 5

Leggi la nota - hanno intenzione di tirare ConcurrentLinkedList da 4,0 prima del rilascio finale di VS2010

Answer 6

Beh non si è effettivamente chiesto come farlo. Ma, a condizione che si può fare un CAS atomica in c # è del tutto possibile.

In realtà sto solo lavorando attraverso l'implementazione di una lista libera di attesa doppiamente legata in C ++ al momento.

Ecco carta che descrive esso. http://www.cse.chalmers.se/~tsigas/papers /Haakan-Thesis.pdf

E una presentazione che può anche fornire alcuni indizi. http://www.ida.liu.se/ ~ chrke / corsi / Multi / slides / Lock-Free_DoublyLinkedList.pdf

Answer 7

È possibile scrivere bloccare algoritmi gratuitamente per tutti strutture dati copiabili sulla maggior parte delle architetture [1]. Ma è difficile scrivere quelle efficienti.

ho scritto un della senza blocchi lista doppiamente collegata da Håkan Sundell e Philippas Tsigas per .Net. Si noti, che non supporta popleft atomica a causa del concetto.

[1]: Maurice Herlihy: Impossibilità e risultati di universalita per attendista freesynchronization (1988)

Answer 8

FWIW, .NET 4.0 è l'aggiunta di un ConcurrentLinkedList, un threadsafe doppiamente lista collegata nello spazio dei nomi System.Collections.Concurrent. È possibile leggere il documentazione o post sul blog descriverla.

Answer 9

Direi che la risposta è un molto profondamente qualificato "sì, è possibile , ma difficile". Per attuare ciò che stai chiedendo, avresti fondamentalmente bisogno di qualcosa che avrebbe compilare le operazioni insieme per garantire l'assenza di collisioni; come tale, sarebbe molto difficile creare un'implementazione generale a tale scopo, e sarebbe ancora alcune limitazioni significative. Sarebbe probabilmente più semplice per creare una specifica implementazione su misura per le esigenze specifiche, e anche allora, non sarebbe "semplice" con qualsiasi mezzo.