È possibile evitare il blocco garantendo che più thread non accedano alla stessa memoria?

Question

Dire che ho un grande array e voglio elaborare il contenuto con più thread. Se delegare ciascun thread a una sezione specifica, garantendo l'assenza di sovrapposizioni, elimina qualsiasi necessità di blocco, presupponendo che i thread non accedano a nessun'altra memoria al di fuori dell'array?

Qualcosa di simile (pseudo-codice):

global array[9000000]; 

do_something(chunk) { 
    for (i = chunk.start; i < chunk.end; i++) 
     //do something with array 
} 

main() { 
    chunk1 = {start: 0, end: 5000000}; 
    chunk2 = {start: 5000000, end: 9000000}; 

    start_thread(thread1, do_something(chunk1)); 
    start_thread(thread2, do_something(chunk2)); 

    wait_for_join(thread1); 
    wait_for_join(thread2); 
    //do something else with the altered array 
} 

Answer 1

In un compilatore C++ 11 conforme questo è sicuro [intro.memory] (§1.7):

posizione

una memoria è o un oggetto di tipo scalare o un massimo sequenza di bit adiacenti campi tutti aventi larghezza diversa da zero. [...] Due thread di esecuzione (1.10) possono aggiornare e accedere a posizioni separate della memoria senza interferire l'uno con l'altro.

C11 fornisce garanzie identiche (usano anche la stessa formulazione) nel §3.14.

In un compilatore C++ 03 non è garantito il funzionamento dello standard, ma potrebbe comunque funzionare se il compilatore fornisce garanzie analoghe come estensione.

Answer 2

Sì, è possibile infatti.

TCMalloc è un buon esempio.

Answer 3

Sì: se è possibile garantire che due thread non accedano allo stesso elemento, non è necessaria alcuna ulteriore sincronizzazione.

Esiste solo un conflitto (e quindi una potenziale corsa di dati) se due thread accedono alla stessa posizione di memoria (con almeno uno di essi che lo modifica) senza sincronizzazione.

(NOTA: questa risposta è basata sul modello di memoria C++ 11. Ho appena notato che stai anche chiedendo di una seconda lingua, credo che C11 specifichi un modello di memoria molto simile, ma puo ' t di sicuro la risposta è valida anche per C. Per le versioni precedenti di entrambe le lingue, thread-safety era dipendente dall'implementazione.)

Answer 4

Sì.

Non è nemmeno necessario garantire che non ci siano due thread l'accesso allo la stessa posizione di memoria. Tutto ciò che devi garantire è che nessun thread singolo modifica qualsiasi posizione a cui un altro accede (indipendentemente dal fatto che ciò significhi leggere o scrivere).

Dato sia senza l'accesso simultaneo a tutti o sola lettura l'accesso simultaneo, siete pronti ad andare senza bloccare.

Answer 5

Importante problema di prestazioni!

Destra, non è necessario il blocco esplicito, poiché, come detto da altri, nessuna posizione di memoria è condivisa.

Ma è possibile attivare la sincronizzazione hardware implicita , poiché è probabile che i blocchi arbitrari inducano le linee della cache a essere condivise (non molto con le cifre utilizzate nell'esempio, tuttavia). È noto come false sharing.approccio livello

superiore come OpenMP risolve questo tipo di problema:

• allineamento blocchi (e filati numeri) sono sintonizzati secondo hardware sottostante.
• fornisce un controllo migliore sul pool di thread, ad esempio ammortizzando il costo delle istanze di thread.
• è più facile da scrivere e in realtà meno invadente.