Come scrivere una lista doppiamente collegata per l'uso multi-core senza blocco globale?

Question

Come scrivere una lista doppiamente collegata per l'uso multi-core senza blocco globale?

#1 da (2 voti)

6

Sto provando a scrivere una lista ciclica collegata doppiamente dove i nodi o anche i puntatori del link sono bloccati individualmente. Oppure un'implementazione senza blocco o addirittura senza attendere (penso che non sia possibile)

L'elenco verrà utilizzato in un kernel semplice per i sottosistemi di pianificazione e di inoltro dei messaggi. Il kernel non è interrompibile, quindi il codice non verrà mai preimpostato nel mezzo, ma è un kernel SMP, quindi più core possono provare a lavorare sull'elenco in parallelo.

Operazioni necessarie:

inserisci il nodo dopo il nodo corrente
inserisci il nodo alla fine
sposta il nodo corrente da una lista a un'altra
elimina il nodo corrente
passa dal nodo corrente al nodo successivo

Nota: se l'algoritmo è così complesso che è 10 volte più lento di bloccare l'intera lista, allora è inutile. Sarebbe più veloce eseguire i core in sequenza rispetto al parallelo, anche se provano a modificare l'elenco tutti allo stesso tempo.

Quindi, qualsiasi suggerimento per un algoritmo o dovrei semplicemente usare un lucchetto per l'intera lista?

linked-list multi-core

posta Goswin von Brederlow 04.06.2015 - 01:41

fonte

1 risposta

Leggi altre domande sui tag linked-list multi-core

Oggetto console statico o dipendenza da iniezione? Associazioni eterogenee - Data Modeling quando un oggetto che deve essere correlato a una delle molte classi

score 2 · Answer 1

Se hai bisogno di sincronizzazione e un elenco copy-on-write non è accettabile, posizionerei la granularità del blocco a livello di nodo.

In particolare, bloccherai due o tre nodi adiacenti ed eseguirai le tue operazioni. Ciò si basa sul fatto che è ciclico, il che semplifica in realtà alcune delle logiche.

inserisci il nodo dopo il nodo corrente: blocca il nodo corrente e quello successivo, quindi fai il tuo inserimento, ricablando i puntatori tra i due nodi per puntare al nuovo nodo.
inserisci il nodo alla fine: come sopra, eccetto il nodo successivo è il primo nodo.
sposta il nodo corrente da una lista a un'altra: questo è lo scollegamento da una lista e l'inserimento in un'altra. Dovresti bloccare il nodo che viene spostato e i nodi adiacenti in entrambi gli elenchi.
cancella il nodo corrente: blocca il nodo corrente e i due attorno ad esso. Scollega il nodo corrente.
passaggio dal nodo corrente al nodo successivo: non bloccare nulla, ma attendere il rilascio del blocco se ci si sposta su un nodo bloccato. Dopo il rilascio del blocco, rivalutare il "nodo successivo".

Senza misurarlo, la mia sensazione istintiva è che le prestazioni sarebbero probabilmente migliori, più grande è la lista. C'è un po 'di overhead sia nella progettazione / codifica che nella chiusura. Bloccare l'intera lista è veramente facile, ma penalizza le letture inutilmente. Man mano che la lista cresce, il numero di nodi penalizzati in questo modo aumenta linearmente.

Non hai dato una lingua, ma potrebbe valere la pena vedere quale codice esistente si trova nella sua libreria standard e vedere se funziona. Se la performance non è accettabile o non esiste nulla (ad es. C), tira il tuo. Confronta i due e vedi cosa funziona meglio.