Nondeterminismo

Come mostrato negli esempi visti in precedenza, anche solo un programma concorrente semplice, con pochi thread, può avere un numero molto elevato di diversi possibili percorsi di esecuzione (non controllati dal programmatore). Questo aspetto prende il nome di nondeterminismo: il programmatore non può determinare l’ordine assoluto di esecuzione delle istruzioni.

A causa del nondeterminismo, testare un programma concorrente è solitamente difficile.

Race condition

Si dicono race condition (in italiano corse critiche, condizioni di corsa o, genericamente, errori dipendenti dal tempo), tutte quelle situazioni in cui thread diversi operano su una risorsa comune, in modo tale che il risultato dipenda dall’ordine (nondeterminismo) in cui essi effettuano le loro operazioni.

Esempio

Quando si possono verificare

Perchè si possa verificare una race condition, cioè il programma possa fornire risultati diversi in diverse esecuzioni, sono necessarie due condizioni:

• Una risorsa deve essere condivisa tra almeno due thread (nell’esempio precedente, questa è la variabile count dell’oggetto Counter).

• Deve esistere almeno un percorso di esecuzione tra i thread nel quale tale risorsa è condivisa in modo non sicuro. Nell’esempio precedente, il codice di add condivide in modo non sicuro la variabile count perchè effettua una lettura e una scrittura su di essa

  public void add(long value) {
  	long tmp = this.count; // Lettura
  	tmp = tmp + value;
  	this.count = tmp; // Scrittura
  }
  

  ma, tra queste due oeprazioni, può essere eseguito il codice di un altro thread.

Anche riscrivendo il codice in modo da effettuare l’aggiornamento di count con un’unica istruzione Java,

public void add(long value){
	this.count += value;
}

non cambierebbe nulla: i thread vengono interrotti a livello delle istruzioni di byte code, non delle istruzioni sorgente Java, e this.count += value corrisponde a più istruzioni di byte code, cioè, in altre parole, non è atomica.

Come assicurare l’assenza di race condition

In generale, non si può dimostrare l’assenza di race condition attraverso dei test fatti nel modo classico. Infatti, anche se il programma testato si comportasse correttamente $N$ volte, la $(N+1)$-esima volta potrebbe verificarsi una sequenza di istruzioni diversa da tutte le $N$ precedenti, ed essa potrebbe essere proprio quella in cui si manifesta l’errore.

Esistono invece due modi per assicurare la correttezza di un programma concorrente (dal punto di vista delle race condition):

• Dimostrare formalmente che il programma soddisfa le condizioni sufficienti perchè possa essere considerato sicuro (ma effettuare questa dimostrazione a postariori è spesso troppo costoso).
• Sviluppare il programma utilizzando strategie note che permettano di evitare le race condition. Alla base di tali strategia si ha l’idea di fare in modo che una risorsa condivisa sia in uno stato sicuro prima di consentire a un altro thread di accedervi, cioè di bloccare l’accesso a essa mentre è in uno stato non sicuro.

Nell’esempio, le istruzioni del metodo add costituiscono una sezione critica, nella quale avvengono, in tempi successivi, la lettura e la scrittura di una variabile condivisa (count). Per rendere sicuro il programma, è necessario un meccanismo che blocchi l’accesso alla sezione critica quando un thread vi entra, e lo sblocchi quando il thread ne esce: in questo modo, solo un thread alla volta può essere nella sezione critica.

public void add(long value){
	//Qui bisogna bloccare
	long tmp = this.count;
	tmp = tmp + value;
	this.count = tmp;
	//Qui bisogna sbloccare
}