È possibile avere più produttori, consumatori singoli in un'impostazione senza blocco?

Question

Ho un sacco di thread che stanno facendo molta comunicazione l'uno con l'altro. Preferirei che fosse senza blocco.

Per ogni thread, voglio avere una casella di posta, dove altri thread possono inviarlo messaggi, (ma solo il proprietario può rimuovere i messaggi). Questa è una situazione a singolo consumatore a più produttori. è possibile per me fare questo in un lockfree/ad alte prestazioni? (Questo è nel ciclo interno di una simulazione gigantesca.)

Answer 1

Certo, se si dispone di una atomica CompareAndSwap istruzioni:

for (i = 0; ; i = (i + 1) % MAILBOX_SIZE) 
{ 
    if ((mailbox[i].owned == false) && 
     (CompareAndSwap(&mailbox[i].owned, true, false) == false)) 
     break; 
} 

mailbox[i].message = message; 
mailbox[i].ready = true; 

Dopo aver letto un messaggio, il filo che consumano appena imposta mailbox[i].ready = false; mailbox[i].owned = false; (in questo ordine).

Answer 2

potrebbe voler esaminare i blocchi di costruzione di thread Intel, ricordo di essere stato tenuto da uno sviluppatore Intel che ha menzionato qualcosa di simile.

Answer 3

Ecco uno paper from the University of Rochester illustrating a non-blocking concurrent queue. L'algoritmo descritto nel documento mostra una tecnica per creare una coda senza blocco.

Answer 4

La coda MPSC (Multiple Producer Single Consumer) senza blocco Multiplo è uno degli algoritmi di lock-free più facili da implementare.

L'implementazione di base richiede una semplice lista di collegamenti separati (SList) con solo push() e flush(). Le funzioni sono disponibili nell'API di Windows come InterlockedFlushSList() e InterlockedPushEntrySList(), ma sono molto semplici da eseguire autonomamente.

Più oggetti push() del produttore sullo SList utilizzando un CAS (confronta-e-swap interbloccato).

Il singolo consumatore esegue un flush() che scambia la testa dello SList con un valore NULL utilizzando un XCHG (scambio interbloccato). Il consumatore ha quindi un elenco di articoli nell'ordine inverso.

Per elaborare gli articoli in ordine, è necessario semplicemente invertire l'elenco restituito da flush() prima di elaborarlo. Se non ti interessa l'ordine, puoi semplicemente percorrere immediatamente l'elenco per elaborarlo.

Due note se si tira le proprie funzioni:

1) Se siete su un sistema con una debole ordinazione di memoria (cioè PowerPC), è necessario mettere un "rilascio barriera di memoria" all'inizio della spinta() e una "barriera della memoria dell'acquario" alla fine della funzione flush().

2) È possibile rendere le funzioni notevolmente semplificate e ottimizzate poiché il problema ABA con gli SLIS si verifica durante la funzione pop(). Non puoi avere problemi ABA con una SList se usi solo push() e flush(). Ciò significa che è possibile implementarlo come un singolo puntatore molto simile al codice senza blocco e non è necessario un contatore di sequenza di prevenzione ABA.