Sembra vero, ma il mio pensiero è stato fangoso. qualcuno può dare una spiegazione chiara e alcuni casi cruciali in cui funziona sempre senza blocco? Grazie!Perché un thread di coda circolare singolo consumatore del singolo produttore è sicuro senza blocco?
Ciò dipende sicuramente dall'implementazione della coda ciclica. Tuttavia, se è come immagino, hai due indici: lo head e lo tail della coda. Il produttore lavora con lo tail e il consumatore lavora con lo head. Condividono l'array di messaggi, ma usano due puntatori diversi.
L'unico caso in cui il produttore e il consumatore potrebbero imbattersi in conflitto è quello in cui ad es. il consumatore controlla il nuovo messaggio e arriva subito dopo il controllo. Tuttavia in tal caso il consumatore aspetterà un po 'e controllerà ancora una volta. La correttezza del programma non andrà persa.
Il motivo per cui funziona bene con il singolo utente singolo produttore è principalmente perché i due utenti non condividono gran parte della memoria. In caso di più produttori, ad es. avrete più di un singolo thread per accedere allo head e potrebbero sorgere conflitti.
EDIT come dasblinkenlight cita nel suo commento il mio ragionamento vale solo se entrambi i fili incremento/decremento rispettivi contatori come ultima operazione del loro consumo/produzione.
+1 È necessario ricordare che la sicurezza del thread è condizionata al produttore che scrive prima l'articolo in coda e solo successivamente incrementando l'indice 'tail'. Negli ambienti a thread singolo, l'ordine non avrebbe importanza, ma in ambienti concorrenti l'ordine potrebbe rompere le cose. – dasblinkenlight
@dasblinkenlight Grazie, commento ragionevole. –
@dasblinkenlight lungo la stessa linea, nel caso in cui il consumatore debba anche fare prima l'articolo, quindi incrementare l'indice __head__? –
Il vero trucco dietro al singolo produttore: la coda circolare per singolo consumatore è che i puntatori di testa e di coda sono modificati atomicamente. Ciò significa che se una posizione in memoria viene cambiata dal valore A al valore B, un osservatore (cioè un lettore) che legge la memoria mentre il suo valore è cambiato, otterrà A o B come risultato, nient'altro.
Quindi la tua coda non funzionerà se, per esempio, stai usando i puntatori a 16 bit ma li stai modificando in due passi a 8 bit (questo può accadere a seconda dell'architettura della CPU e dei requisiti di allineamento della memoria). Il lettore in questo caso può leggere un valore transitorio completamente sbagliato.
Quindi assicuratevi che i vostri puntatori siano modificati atomicamente nella vostra piattaforma!
Qual è la fonte o il contesto di questo reclamo? Certo, puoi implementarlo con un singolo semaforo, è questo che ti stai riferendo? Il semaforo ha anche un lucchetto all'interno o è atomico nell'hardware. – ypnos
Sarei sorpreso se l'affermazione fosse generalmente vera, se non altro a causa di problemi con il modello di memoria. Cosa rende visibili le modifiche apportate dal produttore al consumatore e viceversa? Potrebbe essere possibile scrivere un'implementazione sicura non bloccante con l'uso di operazioni volatili e/o atomiche, ma ciò può essere fatto per molte strutture di dati. –
Penso che questo sia generalmente vero indipendentemente dal contesto, purché la coda circolare abbia un'implementazione ragionevolmente sana. nessun blocco sarà mai necessario per l'utilizzo con un singolo consumatore, singolo produttore. La domanda è come tutti i casi di conflitto sono gestiti correttamente. –