Test-and-set

In informatica l'istruzione test-and-set viene usata per scrivere in una locazione di memoria e restituire il suo vecchio valore come una singola operazione atomica (non interrompibile). Se diversi processi possono accedere alla stessa area di memoria, e se un processo sta eseguendo una test-and-set, nessun altro processo può iniziare un'altra test-and-set finché il primo processo non ha terminato la propria. La CPU può usare l'istruzione test-and-set offerta da altre componenti elettroniche, oppure può fornire una propria istruzione test-and-set. Nell'esempio seguente la funzione controlla e modifica atomicamente il contenuto di un byte.

bool Test_and_Set(bool *_target){
   bool val;
   val = *_target;
   *_target = TRUE;
   return val;
}

L'istruzione permette a più processi coordinanti di modificare una variabile condivisa senza incorrere nell'inconsistenza dei dati cioè modificandola senza il rischio che con la prelazione del sistema operativo un processo non concluda la modifica dei dati portando così a risultati imprevedibili. La zona di codice in cui il programma modifica questi dati condivisi è detta sezione critica. L'obiettivo è che su n processi solamente uno entri in sezione critica evitando così che altri processi cooperanti ad esso accedano a dati non ancora completamente modificati, mantenendo la coerenza dei dati.

bool lock = FALSE;
while(...){
   while(Test_and_Set(&lock))  ; //il processo attende: qualcun altro è in sezione critica
   // -- SEZIONE CRITICA --
   lock = FALSE; //il processo è uscito da SC: permette ad un altro processo di entrare
   // -- RESTO DEL CODICE
}

In questo esempio di implementazione del Test and Set il primo processo che accede all'interno del primo while può entrare in sezione critica dato che lock è inizializzato a FALSE. Il test&set però imposta ora lock a TRUE impedendo così a tutti gli altri processi che incorrono di entrare in SC e quindi "sospendendo" la loro esecuzione al secondo while (busy wait). Quando il processo iniziale ha concluso la SC imposta lock a false permettendo ad un altro processo di entrare proprio nello stesso modo in cui il primo processo è entrato. Questa implementazione però non rispetta l'attesa limitata: infatti un processo potrebbe attendere molto dato che non c'è priorità per chi arriva prima o dopo. Un'implementazione più complessa che prevede l'uso di un array per tener conto dei processi in attesa e di altre variabili ovvia a questo problema permettendo al primo elemento trovate dell'array in attesa di entrare in SC. In questo modo un processo supponendo che l'array sia di N processi non può attendere più di N - 1 volte, equilibrando perciò il tempo di attesa per tutti i processi entranti.