Qual è il metodo più veloce di gara per il polling di una coda senza blocco?

Question

Supponiamo di avere una coda lockless a thread singolo consumatore-thread di singolo produttore e che il produttore potrebbe trascorrere lunghi periodi senza produrre alcun dato. Sarebbe utile lasciare che il thread del consumer si interrompesse quando non c'è nulla nella coda (per i risparmi energetici e per liberare la CPU per altri processi/thread). Se la coda non fosse chiusa a chiave, il modo più semplice per risolvere questo problema è far sì che il thread di produzione blocchi un mutex, esegua il suo lavoro, segnali una variabile di condizione e sblocchi, e per il thread di lettura blocchi il mutex, attendi sulla variabile condition , fai la sua lettura, quindi sblocca. Ma se stiamo usando una coda senza serratura, usando un mutex nello stesso identico modo elimineremo le prestazioni che otteniamo dall'utilizzare una coda senza blocco, in primo luogo.

La soluzione banale è avere produttore dopo ogni inserzione nella coda bloccare il mutex, segnalare la variabile condizione, quindi sbloccare il mutex, mantenendo il lavoro effettivo (l'inserimento nella coda) completamente fuori dalla serratura, e fare in modo che il consumatore faccia lo stesso, bloccando il mutex, aspettando la variabile condition, sbloccandola, estraendo tutto dalla coda, quindi ripetendo, mantenendo la lettura della coda al di fuori del blocco. C'è comunque una condizione di competizione: tra il lettore che tira fuori la coda e va a dormire, il produttore potrebbe aver inserito un articolo nella coda. Ora il lettore andrà a dormire e potrebbe rimanere così indefinitamente finché il produttore non inserirà un altro oggetto e segnalerà di nuovo la variabile di condizione. Ciò significa che a volte puoi finire con oggetti particolari che sembrano richiedere molto tempo per viaggiare attraverso la coda. Se la tua coda è sempre costantemente attiva, questo potrebbe non essere un problema, ma se fosse sempre attivo potresti probabilmente dimenticare completamente la variabile di condizione.

AFAICT la soluzione è che il produttore si comporti come se stesse lavorando con una normale coda di blocco delle esigenze. Dovrebbe bloccare il mutex, inserire nella coda lockless, segnalare la variabile di condizione, sbloccare. Tuttavia, il consumatore dovrebbe comportarsi in modo diverso. Quando si sveglia, dovrebbe sbloccare immediatamente il mutex invece di aspettare finché non viene letta la coda. Quindi dovrebbe tirare il maggior numero possibile di coda e elaborarlo. Infine, solo quando il consumatore sta pensando di andare a dormire, dovrebbe bloccare il mutex, controllare se ci sono dati, quindi in caso affermativo lo sblocchi e lo elabori o, in caso contrario, attenda sulla variabile condition. In questo modo il mutex viene conteso meno spesso di quanto sarebbe con una coda lockfull, ma non c'è il rischio di andare a dormire con i dati ancora lasciati in coda.

È questo il modo migliore per farlo? Ci sono alternative?

Nota: Con 'più veloce' voglio dire 'più veloce senza dedicare un nucleo per il controllo della coda di più e più volte,' ma questo non si adatterebbe nel titolo; p

Un'alternativa: Vai con la soluzione ingenua, ma aspetta il consumatore sulla variabile condition con un timeout corrispondente alla latenza massima che sei disposto a tollerare per un oggetto che viaggia attraverso la coda. Se il timeout desiderato è piuttosto breve, potrebbe essere inferiore al tempo di attesa minimo per il tuo sistema operativo o comunque consumare troppa CPU.

Answer 1

Suppongo che tu stia utilizzando la coda single-consumer single-producer bloccata dallo Dr Dobbs article - o qualcosa di simile - quindi userò la terminologia da lì.

In questo caso, la risposta suggerita nel paragrafo che inizia "AFAICT" è buono, ma penso che può essere ottimizzato un po ':

• nel consumatore - come dici tu, quando il consumatore ha esaurito la coda e sta prendendo in considerazione il sonno (e solo allora), si blocca il mutex, controlla di nuovo la coda, e poi o
  • rilascia il mutex e continua a funzionare, se ci fosse un nuovo elemento nella coda
  • o blocchi sulla variabile condition (rilasciando il mutex quando si sveglia per trovare una coda non vuota, nat urally).
• Nella produttore:
  • Prima prendere una copia di last, chiamano saved_last
  • Aggiungi l'articolo new_item come al solito, poi prendere una copia del puntatore divider, lo chiamano saved_divider.
  • Se il valore di saved_divider è uguale a new_item, l'oggetto appena inserito, l'oggetto è già stato consumato e il lavoro è terminato.
  • Altrimenti, se il valore di saved_divider non è uguale a saved_last, non è necessario riattivare l'utente. Questo perché:
    • In un momento strettamente dopo aver aggiunto il tuo nuovo oggetto, si sa che divider non aveva ancora raggiunto sia new_item o saved_last
    • Da quando hai iniziato l'inserimento, last ha avuto solo i due valori
    • Il consumatore si ferma sempre quando divider è uguale a last
    • Pertanto il consumatore deve essere ancora sveglio e raggiungerà il tuo nuovo oggetto prima di dormire.
  • Altrimenti bloccare il mutex, segnalare il condvar e quindi rilasciare il mutex. (Ottenere il mutex qui assicura che non segnalano il condar nel tempo tra il consumatore notando la coda è vuota, ed effettivamente bloccando sul condvar.)

Questo garantisce che, nel caso in cui il consumatore tende a rimanere occupato, si evita di bloccare il mutex quando si sa che il consumatore è ancora sveglio (e non sta per dormire). Riduce anche il tempo in cui si tiene il mutex, per ridurre ulteriormente la possibilità di contesa.

La spiegazione di cui sopra è abbastanza verbale (perché volevo includere la spiegazione del perché funziona, piuttosto che solo l'algoritmo), ma il codice risultante dovrebbe essere abbastanza semplice.

Ovviamente, se valga la pena dipendere da un sacco di cose, ti incoraggio a misurare se le prestazioni sono fondamentali per te. Le buone implementazioni dei primitivi mutex/condvar utilizzano internamente le operazioni atomiche per la maggior parte dei casi, quindi generalmente fanno solo una chiamata al kernel (il bit più costoso!) Se c'è bisogno di - cioè se c'è bisogno di bloccare, o ci sono sicuramente alcune thread in attesa - quindi il tempo risparmiato non chiamando le funzioni mutex può essere solo il sovraccarico delle chiamate in biblioteca.