Race condition

Uno dei problemi più comuni nella sincronizzazione tra unità di esecuzione sono le race condition.

Definizione: race condition

Una race condition (in italiano situazione di corsa) è un problema causato dall’incorretta sincronizzazione tra unità di esecuzione nei sistemi concorrenti quando il risultato finale dell’esecuzione concorrente di unità di esecuzione dipende dalla temporizzazione o dalla sequenza con cui vengono eseguiti.

Vediamo ora un classico esempio di race condition.

Esempio di race condition

Un esempio di race condition è il seguente: supponiamo di avere una variabile intera $\text{counter}$ il cui valore iniziale è $\text{5}$ e che due processi $P_0$ e $P_1$ eseguano rispettivamente le istruzioni $\text{counter++}$ e $\text{counter--}$ in modo concorrente. Il solo risultato corretto di questa esecuzione è $\text{counter == 5}$, ma ciò potrebbe non avvenire.

Queste istruzioni, infatti vengono codificate così in un tipico linguaggio macchina:

• L’istruzione $\text{counter++}$ viene codificata come: $$\begin{array}{rl}& \text{register1 := counter}\\ & \text{register1 := register1 + 1}\\ & \text{counter := register1}\end{array}$$
• L’istruzione $\text{counter--}$ viene codificata come: $$\begin{array}{rl}& \text{register2 := counter}\\ & \text{register2 := register2 - 1}\\ & \text{counter := register2}\end{array}$$

(dove $\text{register1}$ e $\text{register2}$ sono due registri della CPU).

L’esecuzione concorrente delle istruzioni $\text{counter++}$ e $\text{counter--}$ equivale a un’esecuzione sequenziale di queste istruzioni in linguaggio macchina, intercalate in una qualunque sequenza che però conservi l’ordine interno della rispettiva istruzione di alto livello. Ciò significa, per esempio, che in una sequenza qualsiasi si può far eseguire $\text{counter := register2}$ prima di $\text{register1 := counter}$, ma non potrà mai essere possibile eseguire $\text{counter := register1}$ prima di $\text{register1 := counter}$ perché altrimenti violerebbero l’ordine interno della loro sequenza nella codifica dell’istruzione $\text{counter++}$.

Una delle sequenze possibili in cui queste istruzioni possono essere intercalate è la seguente:

Istante	Processo	Istruzione eseguita	Valore modificato
$T_0$	$P_0$	$\text{register1 := counter}$	$\text{register1 = 5}$
$T_1$	$P_0$	$\text{register1 := register1 + 1}$	$\text{register1 = 6}$
$T_2$	$P_1$	$\text{register2 := counter}$	$\text{register2 = 5}$
$T_3$	$P_1$	$\text{register2 := register2 - 1}$	$\text{register2 = 4}$
$T_4$	$P_0$	$\text{counter := register1}$	$\text{counter = 6}$
$T_5$	$P_1$	$\text{counter := register2}$	$\text{counter = 4}$

Questa sequenza porta al risultato finale $\text{counter = 4}$, che è ovviamente errato. Viceversa, invertendo l’ordine delle istruzioni negli ultimi due istanti $T_4$ e $T_5$, il risultato finale sarebbe $\text{counter = 6}$, altrettanto errato.

Questo è accaduto a causa di una race condition tra i due processi $P_0$ e $P_1$,