modello di memoria C ++ 0x e speculativi carichi / negozi

Question

Quindi stavo leggendo sul modello di memoria che fa parte del futuro standard C ++ 0x. Tuttavia, io sono un po 'confuso di alcune delle restrizioni per ciò che il compilatore è autorizzato a fare, in particolare su carichi speculativi e negozi.

Per cominciare, alcune delle cose rilevanti:

pagine di Hans Boehm circa le discussioni e il modello di memoria in C ++ 0x

Boehm, "thread possono non essere implementato come una libreria"

Boehm e Adve, "Fondamenti del C ++ Concurrency modello di memoria "

Sutter, "Prism: A Principle- Sulla base del modello di memoria sequenziale per le piattaforme Microsoft codice nativo", N2197

Boehm, "conseguenze modello di memoria di concorrenza del compilatore ", N2338

Ora, l'idea di base è essenzialmente "Coerenza sequenziale per Data-Race-Free Programmi", che sembra essere un compromesso accettabile tra la facilità di programmazione e permettendo le opportunità del compilatore e hardware per ottimizzare. Una corsa dati è definito per verificare se due accessi alla stessa posizione di memoria da diversi fili non sono ordinati, almeno uno dei quali memorizza la posizione di memoria, e almeno uno di essi non è un'azione di sincronizzazione. Ciò implica che tutti lettura / scrittura a dati condivisi deve avvenire tramite un meccanismo di sincronizzazione, come mutex o operazioni su variabili atomiche (bene, è possibile operare sulle variabili atomiche con l'ordinamento memoria rilassata solo agli esperti , ma il default prevede la consistenza sequenziale).

Alla luce di questo, io sono confuso circa le restrizioni circa spuri o speculativi carichi / negozi su variabili condivise ordinarie. Per esempio, in N2338 abbiamo l'esempio

switch (y) {
    case 0: x = 17; w = 1; break;
    case 1: x = 17; w = 3; break;
    case 2: w = 9; break;
    case 3: x = 17; w = 1; break;
    case 4: x = 17; w = 3; break;
    case 5: x = 17; w = 9; break;
    default: x = 17; w = 42; break;
}

, che il compilatore non è permesso di trasformare in

tmp = x; x = 17;
switch (y) {
    case 0: w = 1; break;
    case 1: w = 3; break;
    case 2: x = tmp; w = 9; break;
    case 3: w = 1; break;
    case 4: w = 3; break;
    case 5: w = 9; break;
    default: w = 42; break;
}

poiché se y == 2 è una scrittura spuria di x che potrebbe essere un problema se un altro thread fosse contemporaneamente aggiornando x. Ma, perché questo è un problema? Questa una gara di dati, che è vietata in ogni caso; in questo caso, il compilatore fa solo peggiorare la situazione scrivendo a x due volte, ma anche una singola scrittura sarebbe sufficiente per una gara di dati, no? Cioè un adeguato programma di C ++ 0x avrebbe bisogno di sincronizzare l'accesso a x, nel qual caso non ci sarebbe più gara di dati, e il negozio spuria non sarebbe un problema neanche?

Sono allo stesso modo confuso su Esempio 3.1.3 in N2197 e alcuni degli altri esempi come pure, ma forse una spiegazione per il problema di cui sopra sarebbe spiegare che anche.

EDIT: La risposta:

Il motivo per cui i negozi speculativi sono un problema è che nell'esempio switch sopra, il programmatore potrebbe aver scelto di acquisire in modo condizionale la serratura protegge solo se x y! = 2. Da qui il negozio speculativa potrebbe introdurre una gara di dati che è stato non esiste nel codice originale, e la trasformazione è quindi vietato. Lo stesso discorso vale per esempio 3.1.3 in N2197 pure.

Answer 1

Non ho dimestichezza con tutte le cose che fa riferimento a, a meno di notare che nel caso y == 2, nel primo pezzo di codice, x non è scritto a tutti (o leggere, è per questo). Nella seconda porzione di codice, è scritto due volte. Questo è più di una differenza di un semplice iscritto una volta contro la scrittura per due volte (almeno, è nei modelli di threading esistente, come pthreads). Inoltre, memorizzare un valore che non sarebbero altrimenti conservato a tutti è più di una differenza di un semplice memorizzare una volta contro memorizzare due volte. Per queste ragioni sia, non si vuole compilatori solo la sostituzione di un no-op con tmp = x; x = 17; x = tmp;.

filo Supponiamo che A vuole pensare che nessun altro thread modifica x. E 'ragionevole vuole che sia consentito di aspettarsi che se y è 2, e scrive un valore di x, quindi legge indietro, otterrà di nuovo il valore che ha scritto. Ma se il thread B è contemporaneamente in esecuzione il secondo pezzo di codice, poi infilare un potrebbe scrivere a x e poi leggerlo, e tornare al valore originale, perché il thread B salvato "prima" della scrittura e restaurato "dopo" di esso. Oppure potrebbe tornare 17, in quanto il thread B memorizzato 17 "dopo" la scrittura, e conservato tmp di nuovo "dopo" filo A legge. Discussione A può fare quello che vuole la sincronizzazione, e non aiuterà, perché thread B non è sincronizzato. Il motivo non è sincronizzato (nel caso == 2 y) è che non sta usando x. Così il concetto di se una particolare porzione di codice "usa x" è importante per il modello di threading, il che significa che i compilatori non può essere consentito di modificare il codice per utilizzare x quando "non dovrebbe".

In breve, se la trasformazione si propone sono stati autorizzati, l'introduzione di una scrittura spuria, allora sarebbe mai possibile analizzare un po 'di codice e concludere che non modifica x (o qualsiasi altro luogo di memoria). Ci sono un certo numero di linguaggi convenienti che sarebbe quindi impossibile, come la condivisione dati immutabili tra fili senza sincronizzazione.

Quindi, anche se non sono familiarità con la definizione di C ++ 0x di "razza dei dati", presumo che comprende alcune condizioni in cui i programmatori sono autorizzati a supporre che un oggetto non viene scritto, e che questa trasformazione violerebbe tali condizioni. I speculare che se y == 2, allora il vostro codice originale, insieme con il codice di concomitante: x = 42; x = 1; z = x in un altro thread, non è definito come una gara di dati. O almeno se si tratta di una gara di dati, non è uno che permette z per finire con il valore o 17, o 42.

Si consideri che in questo programma, il valore 2 in Y potrebbe essere usata per indicare, "ci sono altri thread in esecuzione: non modificare x, perché non sono sincronizzati qui, in modo che sarebbe introdurre una gara di dati". Forse il motivo non c'è alcuna sincronizzazione a tutti, è che in tutti gli altri casi di y, non ci sono altri fili conduttori con accesso a x. Sembra ragionevole a me che C ++ 0x vorrebbe sostenere codice come questo:

if (single_threaded) {
    x = 17;
} else {
    sendMessageThatSafelySetsXTo(17);
}

È chiaro, allora, non si vuole che ha trasformato a:

tmp = x;
x = 17;
if (!single_threaded) {
    x = tmp;
    sendMessageThatSafelySetsXTo(17);
}

che è sostanzialmente la stessa trasformazione come nel tuo esempio, ma con solo 2 casi, invece di esserci abbastanza per farlo sembrare come una buona ottimizzazione del codice-size.

Answer 2

Se modifica y==2, e un altro thread o legge x, come v'è una condizione di competizione nel campione originale? Questo filo non tocca mai x, così altri thread può farlo liberamente.

Ma con la versione riordinato, il nostro thread modifica x, anche se solo temporaneamente, quindi se un altro thread manipola anche, ora abbiamo una condizione di competizione dove non era presente prima.