Condizione di gara - Race condition

"Razza critica" reindirizza qui. Per il movimento accademico, vedi Teoria critica della razza .
Race condition in un circuito logico. Qui, t 1 e ∆ t 2 rappresentano i ritardi di propagazione degli elementi logici. Quando il valore di ingresso A cambia da basso ad alto, il circuito emette un breve picco di durata (∆ t 1 + ∆ t 2 ) − ∆ t 2 = ∆ t 1 .

Una condizione di gara o pericolo di gara è la condizione di un'elettronica , software o altro sistema in cui il comportamento sostanziale del sistema dipende dalla sequenza o dalla tempistica di altri eventi incontrollabili. Diventa un bug quando uno o più dei possibili comportamenti non sono desiderabili.

Il termine race condition era già in uso nel 1954, ad esempio nella tesi di dottorato di David A. Huffman "La sintesi dei circuiti di commutazione sequenziali".

Le race condition possono verificarsi soprattutto in circuiti logici , multithread o programmi software distribuiti .

In elettronica

Un tipico esempio di race condition può verificarsi quando una porta logica combina segnali che hanno viaggiato lungo percorsi diversi dalla stessa sorgente. Gli ingressi al gate possono cambiare in momenti leggermente diversi in risposta a un cambiamento nel segnale sorgente. L'uscita può, per un breve periodo, passare a uno stato indesiderato prima di tornare allo stato progettato. Alcuni sistemi possono tollerare tali anomalie, ma se questa uscita funziona come segnale di clock per ulteriori sistemi che contengono memoria, ad esempio, il sistema può discostarsi rapidamente dal comportamento progettato (in effetti, il glitch temporaneo diventa un problema tecnico permanente).

Si consideri, ad esempio, una porta AND a due ingressi alimentata con la seguente logica:

Un segnale logico su un ingresso e la sua negazione, ( la ¬ è una negazione booleana ), su un altro ingresso in teoria non emette mai un valore vero: se, tuttavia, le variazioni del valore di impiegano più tempo a propagarsi al secondo ingresso rispetto al primo quando cambia da falso a vero allora seguirà un breve periodo durante il quale entrambi gli ingressi sono veri, e quindi anche l'uscita della porta sarà vera.

Forme critiche e non critiche

Una race condition critica si verifica quando l'ordine in cui vengono modificate le variabili interne determina lo stato finale in cui si troverà la macchina a stati.

Una race condition non critica si verifica quando l'ordine in cui vengono modificate le variabili interne non determina lo stato finale in cui si troverà la macchina a stati.

Forme statiche, dinamiche ed essenziali

Una race condition statica si verifica quando un segnale e il suo complemento vengono combinati.

Una condizione di competizione dinamica si verifica quando risulta in più transizioni quando ne è prevista solo una. Sono dovute all'interazione tra le porte. Può essere eliminato utilizzando non più di due livelli di gating.

Una condizione di gara essenziale si verifica quando un ingresso ha due transizioni in meno del tempo di propagazione del feedback totale. A volte vengono curati utilizzando elementi di linea di ritardo induttivi per aumentare efficacemente la durata di un segnale in ingresso.

Soluzioni alternative

Le tecniche di progettazione come le mappe di Karnaugh incoraggiano i progettisti a riconoscere ed eliminare le condizioni di gara prima che causino problemi. Spesso è possibile aggiungere ridondanza logica per eliminare alcuni tipi di gare.

Oltre a questi problemi, alcuni elementi logici possono entrare in stati metastabili , che creano ulteriori problemi per i progettisti di circuiti.

Nel software

Una race condition si verifica nel software quando un programma per computer, per funzionare correttamente, dipende dalla sequenza o dalla tempistica dei processi o thread del programma . Condizioni di gara critiche causano esecuzioni non valide e bug del software . Le race condition critiche si verificano spesso quando i processi o i thread dipendono da uno stato condiviso. Le operazioni sugli stati condivisi vengono eseguite in sezioni critiche che devono escludersi a vicenda . La mancata osservanza di questa regola può danneggiare lo stato condiviso.

Una gara di dati è un tipo di condizione di competizione. Le gare di dati sono parti importanti di vari modelli di memoria formale . Il modello di memoria definito negli standard C11 e C++11 specifica che un programma C o C++ contenente una corsa di dati ha un comportamento indefinito .

Una race condition può essere difficile da riprodurre ed eseguire il debug perché il risultato finale non è deterministico e dipende dalla tempistica relativa tra i thread che interferiscono. Problemi di questa natura possono quindi scomparire durante l'esecuzione in modalità di debug, aggiungendo ulteriore registrazione o collegando un debugger. Un bug che scompare in questo modo durante i tentativi di debug viene spesso definito " Heisenbug ". È quindi meglio evitare le condizioni di gara con un'attenta progettazione del software.

Esempio

Supponiamo che due thread incrementino ciascuno il valore di una variabile intera globale di 1. Idealmente, si verificherebbe la seguente sequenza di operazioni:

Filo 1 Discussione 2 Valore intero
0
leggere il valore ? 0
aumentare il valore 0
rispondere → 1
leggere il valore ? 1
aumentare il valore 1
rispondere → 2

Nel caso mostrato sopra, il valore finale è 2, come previsto. Tuttavia, se i due thread vengono eseguiti contemporaneamente senza blocco o sincronizzazione, l'esito dell'operazione potrebbe essere errato. La sequenza alternativa di operazioni di seguito illustra questo scenario:

Filo 1 Discussione 2 Valore intero
0
leggere il valore ? 0
leggere il valore ? 0
aumentare il valore 0
aumentare il valore 0
rispondere → 1
rispondere → 1

In questo caso, il valore finale è 1 invece del risultato atteso di 2. Ciò si verifica perché qui le operazioni di incremento non si escludono a vicenda. Le operazioni che si escludono a vicenda sono quelle che non possono essere interrotte durante l'accesso a una risorsa come una posizione di memoria.

Gara di dati

Non tutti considerano le gare di dati come un sottoinsieme delle condizioni di gara. La definizione precisa di data race è specifica del modello di concorrenza formale utilizzato, ma in genere si riferisce a una situazione in cui un'operazione di memoria in un thread potrebbe potenzialmente tentare di accedere a una posizione di memoria nello stesso momento in cui un'operazione di memoria in un altro thread è scrivere in quella posizione di memoria, in un contesto in cui questo è pericoloso. Ciò implica che una gara di dati è diversa da una condizione di gara in quanto è possibile avere non determinismo dovuto alla temporizzazione anche in un programma senza gare di dati, ad esempio in un programma in cui tutti gli accessi alla memoria utilizzano solo operazioni atomiche .

Questo può essere pericoloso perché su molte piattaforme, se due thread scrivono contemporaneamente in una posizione di memoria, potrebbe essere possibile che la posizione di memoria finisca per contenere un valore che è una combinazione arbitraria e senza significato dei bit che rappresentano i valori che ogni thread stava tentando di scrivere; questo potrebbe causare il danneggiamento della memoria se il valore risultante è uno che nessuno dei thread ha tentato di scrivere (a volte questo è chiamato " scrittura strappata "). Allo stesso modo, se un thread legge da una posizione mentre un altro thread vi sta scrivendo, potrebbe essere possibile che la lettura restituisca un valore che è una combinazione arbitraria e senza significato dei bit che rappresentano il valore che la posizione di memoria conteneva prima della scrittura, e dei bit che rappresentano il valore in scrittura.

Su molte piattaforme sono previste speciali operazioni di memoria per l'accesso simultaneo; in tali casi, in genere l'accesso simultaneo utilizzando queste operazioni speciali è sicuro, ma l'accesso simultaneo utilizzando altre operazioni di memoria è pericoloso. A volte tali operazioni speciali (che sono sicure per l'accesso simultaneo) sono chiamate operazioni atomiche o di sincronizzazione , mentre le operazioni ordinarie (che non sono sicure per l'accesso simultaneo) sono chiamate operazioni sui dati . Questo è probabilmente il motivo per cui il termine è corsa ai dati ; su molte piattaforme, dove esiste una race condition che coinvolge solo operazioni di sincronizzazione , tale race può essere non deterministico ma comunque sicuro; ma una corsa ai dati potrebbe portare alla corruzione della memoria oa un comportamento indefinito.

Definizioni di esempio di gare di dati in particolari modelli di concorrenza

La definizione precisa di gara di dati differisce tra i modelli di concorrenza formali. Questo è importante perché il comportamento simultaneo è spesso non intuitivo e quindi a volte viene applicato un ragionamento formale.

Lo standard C++ , nella bozza N4296 (2014-11-19), definisce la corsa dei dati come segue nella sezione 1.10.23 (pagina 14)

Due azioni sono potenzialmente concorrenti se

  • sono eseguiti da thread diversi, o
  • non sono sequenziati e almeno uno è eseguito da un gestore del segnale.

L'esecuzione di un programma contiene una corsa di dati se contiene due azioni potenzialmente simultanee conflittuali, di cui almeno una non atomica, e nessuna delle due avviene prima dell'altra, salvo il caso speciale per i gestori di segnale descritto di seguito [omesso]. Qualsiasi corsa di dati di questo tipo si traduce in un comportamento indefinito.

Le parti di questa definizione relative ai gestori di segnale sono peculiari del C++ e non sono tipiche delle definizioni di data race .

Il documento Detecting Data Races on Weak Memory Systems fornisce una definizione diversa:

"due operazioni di memoria sono in conflitto se accedono alla stessa posizione e almeno una di esse è un'operazione di scrittura... "Due operazioni di memoria, x e y, in un'esecuzione sequenzialmente coerente formano una corsa x,y〉, iff x e y conflitto, e non sono ordinati dalla relazione hb1 dell'esecuzione. La gara x,y〉 è una corsa di dati se almeno una di x o y è un'operazione sui dati.

Qui abbiamo due operazioni di memoria che accedono alla stessa posizione, una delle quali è una scrittura.

La relazione hb1 è definita altrove nell'articolo ed è un esempio di una tipica relazione " accade-prima "; intuitivamente, se possiamo dimostrare che siamo in una situazione in cui è garantito che un'operazione di memoria X venga eseguita fino al completamento prima che inizi un'altra operazione di memoria Y, allora diciamo che "X accade prima di Y". Se né "X accade prima di Y" né "Y accade prima di X", allora diciamo che X e Y sono "non ordinati dalla relazione hb1". Quindi, la clausola "...e non sono ordinate dalla relazione hb1 dell'esecuzione" può essere tradotta intuitivamente come "...e X e Y sono potenzialmente concorrenti".

L'articolo considera pericolose solo quelle situazioni in cui almeno una delle operazioni di memoria è una "operazione sui dati"; in altre parti di questo documento, il documento definisce anche una classe di " operazioni di sincronizzazione " che sono sicure per un uso potenzialmente simultaneo, in contrasto con le "operazioni sui dati".

La specifica del linguaggio Java fornisce una definizione diversa:

Due accessi a (lettura o scrittura su) la stessa variabile si dicono in conflitto se almeno uno degli accessi è una scrittura... Quando un programma contiene due accessi in conflitto (§17.4.1) che non sono ordinati da un accade-prima della relazione, si dice che contenga una corsa di dati... una corsa di dati non può causare comportamenti errati come restituire la lunghezza errata per un array.

Una differenza fondamentale tra l'approccio C++ e l'approccio Java è che in C++ una corsa di dati è un comportamento indefinito, mentre in Java una corsa di dati influisce semplicemente sulle "azioni inter-thread". Ciò significa che in C++, un tentativo di eseguire un programma contenente una corsa di dati potrebbe (pur aderendo alle specifiche) bloccarsi o potrebbe mostrare un comportamento insicuro o bizzarro, mentre in Java, un tentativo di eseguire un programma contenente una corsa di dati può produrre comportamento di concorrenza indesiderato, ma altrimenti (presupponendo che l'implementazione aderisce alle specifiche) è sicuro.

SC per DRF

Un aspetto importante delle corse di dati è che in alcuni contesti un programma privo di corse di dati è garantito per essere eseguito in modo coerente in sequenza , facilitando notevolmente il ragionamento sul comportamento simultaneo del programma. Si dice che i modelli di memoria formale che forniscono tale garanzia esibiscano una proprietà "SC per DRF" (Sequential Consistency for Data Race Freedom). Si dice che questo approccio abbia ottenuto un consenso recente (presumibilmente rispetto ad approcci che garantiscono la coerenza sequenziale in tutti i casi, o ad approcci che non la garantiscono affatto).

Ad esempio, in Java, questa garanzia è specificata direttamente:

Un programma è sincronizzato correttamente se e solo se tutte le esecuzioni sequenzialmente consistenti sono prive di corse di dati.

Se un programma è sincronizzato correttamente, tutte le esecuzioni del programma appariranno sequenzialmente coerenti (§17.4.3).

Questa è una garanzia estremamente forte per i programmatori. I programmatori non hanno bisogno di ragionare sui riordini per determinare che il loro codice contiene gare di dati. Pertanto non hanno bisogno di ragionare sui riordini per determinare se il loro codice è sincronizzato correttamente. Una volta stabilita la corretta sincronizzazione del codice, il programmatore non deve preoccuparsi che i riordini influiscano sul suo codice.

Un programma deve essere sincronizzato correttamente per evitare i tipi di comportamenti controintuitivi che possono essere osservati quando il codice viene riordinato. L'uso della sincronizzazione corretta non garantisce che il comportamento complessivo di un programma sia corretto. Tuttavia, il suo utilizzo consente a un programmatore di ragionare sui possibili comportamenti di un programma in modo semplice; il comportamento di un programma correttamente sincronizzato è molto meno dipendente da eventuali riordini. Senza una corretta sincronizzazione, sono possibili comportamenti molto strani, confusi e controintuitivi.

Al contrario, una bozza di specifica C++ non richiede direttamente una proprietà SC per DRF, ma osserva semplicemente che esiste un teorema che lo fornisce:

[Nota: si può dimostrare che i programmi che utilizzano correttamente i mutex e le operazioni memory_order_seq_cst per impedire tutte le corse di dati e non utilizzano altre operazioni di sincronizzazione si comportano come se le operazioni eseguite dai loro thread costituenti fossero semplicemente interlacciate, con ogni calcolo del valore di un oggetto preso dall'ultimo effetto collaterale su quell'oggetto in quell'interlacciamento. Questo è normalmente indicato come "coerenza sequenziale". Tuttavia, questo si applica solo ai programmi senza corse di dati e i programmi senza corse di dati non possono osservare la maggior parte delle trasformazioni di programma che non modificano la semantica del programma a thread singolo. In effetti, la maggior parte delle trasformazioni di programmi a thread singolo continuano ad essere consentite, poiché qualsiasi programma che si comporta in modo diverso di conseguenza deve eseguire un'operazione indefinita.— nota finale

Si noti che la bozza della specifica C++ ammette la possibilità di programmi validi ma che utilizzano operazioni di sincronizzazione con un memory_order diverso da memory_order_seq_cst, nel qual caso il risultato potrebbe essere un programma corretto ma per il quale non viene fornita alcuna garanzia di coerenza sequenziale. In altre parole, in C++, alcuni programmi corretti non sono coerenti in sequenza. Si pensa che questo approccio dia ai programmatori C++ la libertà di scegliere un'esecuzione più rapida del programma a costo di rinunciare alla facilità di ragionamento sul proprio programma.

Esistono vari teoremi, spesso forniti sotto forma di modelli di memoria, che forniscono garanzie SC per DRF in diversi contesti. Le premesse di questi teoremi pongono tipicamente dei vincoli sia sul modello di memoria (e quindi sull'implementazione), sia anche sul programmatore; vale a dire, tipicamente è il caso che ci siano programmi che non soddisfano le premesse del teorema e di cui non si potrebbe garantire l'esecuzione in modo sequenzialmente coerente.

Il modello di memoria DRF1 fornisce SC per DRF e consente le ottimizzazioni dei modelli WO (weak ordering), RCsc ( Release Consistency con operazioni speciali sequenzialmente coerenti), modello di memoria VAX e modelli di memoria data-race-free-0. Il modello di memoria PLpc fornisce SC per DRF e consente le ottimizzazioni dei modelli TSO ( Total Store Order ), PSO, PC ( Processor Consistency ) e RCpc ( Release Consistency con operazioni speciali di consistenza del processore). DRFrlx fornisce uno schizzo di un teorema SC per DRF in presenza di atomi rilassati.

Sicurezza del computer

Molte condizioni di gara del software hanno implicazioni sulla sicurezza del computer associate . Una race condition consente a un utente malintenzionato con accesso a una risorsa condivisa di causare il malfunzionamento di altri attori che utilizzano tale risorsa, con effetti che includono la negazione del servizio e l' escalation dei privilegi .

Un tipo specifico di race condition implica il controllo di un predicato (ad esempio per l' autenticazione ), quindi l'azione sul predicato, mentre lo stato può cambiare tra il momento del controllo e il momento dell'uso . Quando questo tipo di bug esiste nel codice sensibile alla sicurezza, viene creata una vulnerabilità di sicurezza chiamata bug time-of-check-to-time-of-use ( TOCTTOU ).

Le race condition sono anche usate intenzionalmente per creare generatori di numeri casuali hardware e funzioni fisicamente non clonabili . I PUF possono essere creati progettando topologie di circuiti con percorsi identici a un nodo e basandosi su variazioni di produzione per determinare casualmente quali percorsi verranno completati per primi. Misurando l'insieme specifico dei risultati delle condizioni di gara di ciascun circuito prodotto, è possibile raccogliere un profilo per ciascun circuito e mantenerlo segreto per verificare in seguito l'identità di un circuito.

File system

Due o più programmi possono entrare in collisione nei loro tentativi di modificare o accedere a un file system, il che può causare il danneggiamento dei dati o l'escalation dei privilegi. Il blocco dei file fornisce una soluzione comunemente utilizzata. Un rimedio più complicato consiste nell'organizzare il sistema in modo tale che un unico processo (che esegue un demone o simili) abbia accesso esclusivo al file e tutti gli altri processi che devono accedere ai dati in quel file lo facciano solo tramite la comunicazione tra processi con quell'unico processo. Ciò richiede la sincronizzazione a livello di processo.

Esiste una diversa forma di race condition nei file system in cui programmi non correlati possono influenzarsi a vicenda utilizzando improvvisamente le risorse disponibili come spazio su disco, spazio di memoria o cicli del processore. Il software non progettato con cura per anticipare e gestire questa situazione di gara potrebbe quindi diventare imprevedibile. Tale rischio può essere trascurato a lungo in un sistema che sembra molto affidabile. Ma alla fine potrebbero accumularsi dati sufficienti o aggiungere altro software sufficiente per destabilizzare in modo critico molte parti di un sistema. Un esempio di ciò si è verificato con la quasi perdita del Mars Rover "Spirit" non molto tempo dopo l'atterraggio. Una soluzione è che il software richieda e prenoti tutte le risorse di cui avrà bisogno prima di iniziare un'attività; se questa richiesta fallisce, l'attività viene posticipata, evitando i molti punti in cui potrebbe essersi verificato l'errore. In alternativa, ciascuno di questi punti può essere dotato di gestione degli errori, oppure il successo dell'intera attività può essere verificato successivamente, prima di continuare. Un approccio più comune consiste nel verificare semplicemente che siano disponibili risorse di sistema sufficienti prima di avviare un'attività; tuttavia, ciò potrebbe non essere adeguato perché nei sistemi complessi le azioni di altri programmi in esecuzione possono essere imprevedibili.

Rete

In rete, considera una rete di chat distribuita come IRC , in cui un utente che avvia un canale acquisisce automaticamente i privilegi di operatore del canale. Se due utenti su server diversi, su estremità diverse della stessa rete, tentano di avviare contemporaneamente il canale con lo stesso nome, il rispettivo server di ciascun utente concederà i privilegi di operatore di canale a ciascun utente, poiché nessuno dei due server avrà ancora ricevuto il segnale di un altro server che ha assegnato quel canale. (Questo problema è stato ampiamente risolto da varie implementazioni di server IRC.)

In questo caso di race condition, il concetto di " risorsa condivisa " copre lo stato della rete (quali canali esistono, nonché quali utenti li hanno avviati e quindi hanno quali privilegi), che ogni server può modificare liberamente purché segnala agli altri server della rete le modifiche in modo che possano aggiornare la loro concezione dello stato della rete. Tuttavia, la latenza nella rete rende possibile il tipo di race condition descritto. In questo caso, scongiurare le race condition imponendo una forma di controllo sull'accesso alla risorsa condivisa, ad esempio nominando un server per controllare chi detiene quali privilegi, significherebbe trasformare la rete distribuita in una centralizzata (almeno per quella parte del funzionamento della rete).

Le race condition possono esistere anche quando un programma per computer è scritto con socket non bloccanti , nel qual caso le prestazioni del programma possono dipendere dalla velocità del collegamento di rete.

Sistemi critici per la vita

I difetti del software nei sistemi vitali possono essere disastrosi. Condizioni di gara sono stati tra i difetti nella Therac-25 Radioterapia macchina, che hanno portato alla morte di almeno tre pazienti e lesioni a molti altri.

Un altro esempio è il sistema di gestione dell'energia fornita da GE Energy e utilizzato da Ohio -based FirstEnergy Corp (tra le altre strutture di potere). Esisteva una race condition nel sottosistema di allarme; quando tre linee elettriche cedevoli sono scattate contemporaneamente, la condizione ha impedito l'invio di avvisi ai tecnici di monitoraggio, ritardando la loro consapevolezza del problema. Questo difetto del software alla fine ha portato al North American Blackout del 2003 . GE Energy ha successivamente sviluppato una patch software per correggere l'errore precedentemente sconosciuto.

Utensili

Esistono molti strumenti software per aiutare a rilevare le condizioni di gara nel software. Possono essere ampiamente classificati in due gruppi: strumenti di analisi statica e strumenti di analisi dinamica .

Thread Safety Analysis è uno strumento di analisi statica per l'analisi statica intra-procedurale basata su annotazioni, originariamente implementato come un ramo di gcc e ora reimplementato in Clang , supportando PThreads.

Gli strumenti di analisi dinamica includono:

  • Intel Inspector , uno strumento di debug e controllo della memoria e dei thread per aumentare l'affidabilità, la sicurezza e l'accuratezza delle applicazioni C/C++ e Fortran; Intel Advisor , uno strumento di assistenza per il threading della memoria condivisa e l'ottimizzazione della vettorizzazione SIMD basato su campionamento per sviluppatori e architetti di software C, C++, C# e Fortran;
  • ThreadSanitizer, che utilizza binario ( basato su Valgrind ) o sorgente, strumentazione basata su LLVM e supporta PThreads); e Helgrind, uno strumento Valgrind per rilevare errori di sincronizzazione nei programmi C, C++ e Fortran che utilizzano le primitive di threading pthread POSIX.
  • Data Race Detector è progettato per trovare gare di dati nel linguaggio di programmazione Go.

Esistono diversi benchmark progettati per valutare l'efficacia degli strumenti di rilevamento della corsa dei dati

  • DataRaceBench è una suite di benchmark progettata per valutare sistematicamente e quantitativamente gli strumenti di rilevamento della corsa dei dati che analizzano le applicazioni multi-thread scritte in OpenMP .

In altre aree

La neuroscienza sta dimostrando che le condizioni razziali possono verificarsi anche nel cervello dei mammiferi (topi).

Nel segnalamento ferroviario del Regno Unito si verificherebbe una race condition nell'attuazione della regola 55 . Secondo questa regola, se un treno veniva fermato su una linea in corsa da un segnale, il pompiere della locomotiva si dirigeva verso la cabina del segnale per ricordare al segnalatore che il treno era presente. In almeno un caso, a Winwick nel 1934, si verificò un incidente perché il segnalatore accettò un altro treno prima dell'arrivo dei vigili del fuoco. La moderna pratica di segnalazione rimuove la condizione di gara consentendo al pilota di contattare istantaneamente la cabina di segnalazione via radio.

Guarda anche

Riferimenti

link esterno