elenco concomitante collegato

Question

Sto provando a progettare un elenco collegato in C++ che consente l'accesso simultaneo. Chiaramente l'uso di un singolo blocco per questa lista è grossolanamente inefficiente poiché le aree disgiunte possono essere aggiornate in parallelo. Ora quali sono le mie opzioni oltre alla memorizzazione di un blocco per nodo?

Inoltre, una versione non bloccante sarebbe una scommessa migliore in questo caso? Qualche link pertinente, chiunque?

EDIT: Grazie per le risposte. Un paio di cose che vorrei aggiungere:

1. Che ne dici di memorizzare i blocchi N per ogni nodo M invece del blocco 1: 1: rapporto nodo? Alcuni thread attenderanno, ma è una specie di compromesso. Cosa ne pensi?
2. Se ho intenzione di trovare un nodo in questo elenco collegato sembra che tutti i mutex debbano essere bloccati. Questo è un problema, perché il blocco e lo sblocco di tutti i mutex richiede molto tempo. Qualcuno ha un'alternativa migliore?
3. Sono aperto ad algoritmi non bloccanti. Ma come faccio a usare CAS nel buon vecchio C++ senza usare l'assembly? Ho sentito che gcc ha alcuni attributi __sync che funzionano in modo simile ma non sono sicuri.
4. Con approccio non bloccante, come si fa una ricerca nell'elenco collegato?

Answer 1

E 'possibile implementare un elenco non-blocking singolarmente collegato utilizzando funzioni intrecciate:

Interlocked Singly Linked Lists

Non credo che sia possibile implementare un elenco non-blocking doppiamente legato senza confronto-interlocked e-swap (CAS), che non è ampiamente disponibile.

Answer 2

Sei sicuro che valga la pena risolvere questo problema? Sarebbe forse più utile incapsulare l'effettivo uso finale in una classe che gestisce il blocco di un normale list e fornisce un'interfaccia thread-safe? In questo modo non provi a mettere il blocco a un livello troppo basso (che come hai immaginato non è un problema facile da risolvere).

Answer 3

Linked lists are inherently sequential data structures. Indipendentemente dal tipo di macchinario utilizzato per implementarlo, l'interfaccia e il comportamento previsto implicano una logica sequenziale.

Che cosa stai cercando di fare? Ciò dovrebbe determinare quale struttura dati si utilizza, non la familiarità delle strutture di dati con le quali si è già a proprio agio.

Answer 4

Ci sono molti modi diversi in cui puoi fare questo, a seconda di come userai la lista.

Innanzitutto, per un elenco, un singolo blocco mutex non è necessariamente un grosso problema perché le liste possono supportare lo splicing. Di 'che hai una lista di caratteri AF e un'altra lista BCDE. Non è necessario bloccare il mutex, inserire B, bloccarlo di nuovo, inserire C, ecc. È possibile inserire BCDE tutto in una volta tra A e F impostando il puntatore successivo di A su B e il puntatore successivo di E su F, formando ABCDEF. Indipendentemente dal numero di elementi che si desidera inserire, è sufficiente un solo blocco. Questo è vero anche per una lista doppiamente collegata. Quindi potrebbe non essere un collo di bottiglia nella tua applicazione.

Supponendo che si tratti di un collo di bottiglia, è necessario considerare se si disporrà di uno o più writer e uno o più lettori.

Supponendo di disporre di un singolo writer e di più lettori, è possibile evitare i blocchi mutex interamente utilizzando le istruzioni atomiche, assumendo che siano disponibili per la propria architettura. In GCC questi sono disponibili tramite le funzioni incorporate __sync_ * e in Visual C++ sono disponibili tramite Interlocked *, ma se si è bloccati con un compilatore privo di supporto diretto, è comunque possibile utilizzarli tramite l'assembly inline. Lo scrittore utilizzerà le istruzioni atomiche per impostare atomicamente i puntatori successivi per applicare gli elementi di patch dentro e fuori l'elenco.

Speriamo che questo ti permetta di iniziare. Per ottenere una risposta approfondita suggerirei di fare un'altra domanda e includere:

1. Ci sono uno/più lettori?
2. Esistono uno/più autori?
3. Elenco concatenato o doppiamente collegato?
4. Qualche idea su quale sia il tuo caso d'uso.

Answer 5

E riguardo Skip List? Dai un'occhiata all'implementazione di java nel pacchetto "simultaneo".