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

Question

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

Per cominciare, alcune delle cose rilevanti:

Hans Boehm's pages about threads and the memory model in C++0x

Boehm, "Threads Cannot be Implemented as a Library"

Boehm and Adve, "Foundations of the C++ Concurrency Memory Model"

Sutter, "Prism: A Principle-Based Sequential Memory Model for Microsoft Native Code Platforms", N2197

Boehm, "Concurrency memory model compiler consequences", N2338

Ora, l'idea di base è essenzialmente "Consistenza sequenziale per i programmi Data-Race-Free", che sembra essere un compromesso accettabile tra la facilità di programmazione e l'ottimizzazione delle opportunità del compilatore e dell'hardware. Si definisce una corsa di dati se non si ordinano due accessi alla stessa posizione di memoria da parte di fili diversi, almeno uno di essi viene archiviato nella posizione di memoria e almeno uno di essi non è un'azione di sincronizzazione. Implica che tutto l'accesso in lettura/scrittura ai dati condivisi deve avvenire tramite un meccanismo di sincronizzazione, come mutex o operazioni su variabili atomiche (beh, è ​​possibile operare sulle variabili atomiche con l'ordine di memoria rilassato per gli esperti solo, ma il l'impostazione predefinita fornisce coerenza sequenziale).

Alla luce di ciò, sono confuso riguardo le restrizioni sui carichi spuri o speculativi/negozi su ordinarie variabili condivise. Ad 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; 
} 

cui 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 stava aggiornando contemporaneamente x. Ma perché questo è un problema? Questa è una gara di dati, che è comunque vietata; in questo caso, il compilatore peggiora semplicemente scrivendo a x due volte, ma anche una singola scrittura sarebbe sufficiente per una corsa di dati, no? Cioè un corretto programma C++ 0x avrebbe bisogno di sincronizzare l'accesso a x, nel qual caso non ci sarebbe più la corsa dei dati, e anche l'archivio spuria non sarebbe un problema?

Sono allo stesso modo confuso circa l'esempio 3.1.3 in N2197 e alcuni degli altri esempi, ma forse una spiegazione per il problema precedente spiegherebbe anche questo.

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 x solo se y = 2! Quindi il negozio speculativo potrebbe introdurre una corsa di dati che non era presente nel codice originale, e la trasformazione è quindi proibita. Lo stesso argomento vale anche per l'esempio 3.1.3 in N2197.

Answer 1

Non ho familiarità con tutte le cose a cui si fa riferimento, ma si noti che nel caso y == 2, nel primo bit del codice, x non è stato scritto affatto (o letto, per quello) . Nel secondo bit di codice, è scritto due volte. Questa è più una differenza rispetto alla semplice scrittura una volta contro la scrittura due volte (almeno, è nei modelli di threading esistenti come pthreads).Inoltre, la memorizzazione di un valore che altrimenti non verrebbe memorizzato è più una differenza rispetto alla semplice memorizzazione una volta rispetto alla memorizzazione due volte. Per entrambi questi motivi, non vuoi che i compilatori sostituiscano semplicemente un no-op con tmp = x; x = 17; x = tmp;.

Supponiamo che il thread A presuma che nessun altro thread modifichi x. È ragionevole desiderare che si possa prevedere che se y è 2 e scrive un valore su x, quindi lo legge indietro, recupererà il valore che ha scritto. Ma se il thread B esegue contemporaneamente il secondo bit di codice, il thread A potrebbe scrivere in x e successivamente leggerlo e recuperare il valore originale, perché il thread B ha salvato "prima" la scrittura e ripristinato "dopo". Oppure potrebbe tornare indietro 17, perché il thread B ha memorizzato 17 "dopo" la scrittura, e memorizzato tmp di nuovo "dopo" il thread A legge. Il thread A può fare qualsiasi sincronizzazione a suo piacimento, e non sarà di aiuto, perché il thread B non è sincronizzato. Il motivo per cui non è sincronizzato (nel caso y == 2) è che non sta usando x. Quindi il concetto di se un particolare bit di codice "usa x" è importante per il modello di threading, il che significa che i compilatori non possono essere autorizzati a cambiare il codice per usare x quando "non dovrebbe".

In breve, se la trasformazione proposta è consentita, introducendo una scrittura spuria, non sarebbe mai possibile analizzare un bit di codice e concludere che non modifica x (o qualsiasi altra posizione di memoria). Esistono numerosi e convenienti idiomi che sarebbero quindi impossibili, come la condivisione di dati immutabili tra thread senza sincronizzazione.

Quindi, anche se non ho familiarità con la definizione di "corsa dei dati" del C++ 0x, presumo che includa alcune condizioni in cui i programmatori sono autorizzati ad assumere che un oggetto non sia stato scritto e che questa trasformazione violare tali condizioni. Suppongo che se y == 2, il codice originale, insieme al codice simultaneo: x = 42; x = 1; z = x in un'altra discussione, non è definito come una corsa di dati. O almeno se si tratta di una corsa di dati, non è quella che permette a z di finire con il valore 17 o 42.

Considera che in questo programma, il valore 2 in y potrebbe essere usato per indicare, "lì ci sono altri thread in esecuzione: non modificare x, perché qui non siamo sincronizzati, quindi introdurrei una corsa di dati ". Forse il motivo per cui non esiste alcuna sincronizzazione, è che in tutti gli altri casi di y, non ci sono altri thread in esecuzione con accesso a x. Sembra ragionevole a me che C++ 0x vorrebbe sostenere codice come questo:

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

Chiaramente, allora, non si vuole che trasformato in:

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 essere abbastanza per farlo sembrare un buon ottimizzazione della dimensione del codice.

Answer 2

Se y==2 e un altro thread modifica o legge x, qual è la condizione della competizione nel campione originale? Questo thread non tocca mai x, quindi altri thread possono farlo liberamente.

Ma con la versione riordinata, il nostro thread modifica x, se solo temporaneamente, quindi se un altro thread lo manipola, ora abbiamo una condizione di competizione in cui nessuno era presente prima.