A cosa serve Test-and-Set?

Question

Dopo aver letto Test-and-Set voce di Wikipedia , sono ancora a sinistra con la domanda " Per cosa sarebbe usato un Test-and-Set? "

Mi rendo conto che puoi usarlo per implementare Mutex (come descritto in Wikipedia), ma quali altri usi ha?

Answer 1

Lo usi ogni volta che vuoi scrivere dati in memoria dopo aver fatto qualche lavoro e assicurati che un altro thread non abbia sovrascritto la destinazione da quando hai iniziato. Molti algoritmi lock / mutex-free prendono questo modulo.

Answer 2

Un buon esempio è " incremento. "

Supponi che due thread eseguano a = a + 1 . Di ' a inizia con il valore 100 . Se entrambi i thread sono in esecuzione contemporaneamente (multi-core), entrambi caricheranno a come 100 , incrementeranno in 101 e lo memorizzeranno torna in a . Sbagliato!

Con test-and-set, stai dicendo " Imposta a su 101 , ma solo se al momento ha il valore 100 . " In questo caso, un thread supererà quel test ma l'altro fallirà. In caso di errore, il thread può riprovare l'intera istruzione, questa volta caricando a come 101 . Successo.

Questo è generalmente più veloce dell'uso di un mutex perché:

1. Il più delle volte non esiste una condizione di competizione, quindi l'aggiornamento avviene senza dover acquisire una sorta di mutex.
2. Anche durante la collisione, un thread non è affatto bloccato ed è più veloce per l'altro thread che gira e riprova piuttosto che sospendersi in linea per alcuni mutex.

Answer 3

Immagina di scrivere una domanda bancaria e che la tua richiesta aveva una richiesta di prelievo di dieci sterline (sì, sono inglese;)) dal conto. Quindi è necessario leggere il saldo del conto corrente in una variabile locale, sottrarre il prelievo e quindi riscrivere il saldo in memoria.

Tuttavia, cosa succede se si verifica un'altra richiesta simultanea tra la lettura del valore e la sua scrittura? Esiste la possibilità che il risultato di tale richiesta venga completamente sovrascritto dal primo e che il saldo del conto non sia corretto.

Test-and-set ci aiuta a risolvere il problema verificando che il valore della sovrascrittura sia quello che pensi dovrebbe essere. In questo caso, è possibile verificare che il saldo fosse il valore originale letto. Dal momento che è atomico, non è interrompibile, quindi nessuno può estrarre il tappeto da sotto di te tra la lettura e la scrittura.

Un altro modo per risolvere lo stesso problema è rimuovere un blocco nella posizione di memoria. Sfortunatamente, i blocchi sono tremendamente difficili da correggere, difficili da ragionare, hanno problemi di scalabilità e si comportano male di fronte a guasti, quindi non sono una soluzione ideale (ma sicuramente pratica). Gli approcci test-and-set costituiscono la base di alcuni Memorie Transazionali del Software, che consentono in modo ottimistico l'esecuzione simultanea di ogni transazione, a costo di annullarle tutte in caso di conflitto.

Answer 4

Fondamentalmente, il suo uso è esattamente per i mutex, data l'enorme importanza dell'atomicità. Questo è tutto.

Test-and-set è un'operazione che può essere eseguita con altre due istruzioni, non atomica e più veloce (l'atomicità porta un sovraccarico hardware su sistemi multiprocessore), quindi in genere non la useresti per altri motivi.

/ p>

Answer 5

Viene utilizzato quando è necessario ottenere un valore condiviso, fare qualcosa con esso e modificare il valore, supponendo che un altro thread non lo abbia già modificato.

Per quanto riguarda gli usi pratici, l'ultima volta che l'ho visto è stato in implementazioni di code simultanee (code che possono essere spinte / spuntate da più thread senza bisogno di semafori o mutex).

Perché dovresti usare TestAndSet piuttosto che un mutex? Perché generalmente richiede meno sovraccarico di un mutex. Laddove un mutex richiede l'intervento del sistema operativo, un TestAndSet può essere implementato come singola istruzione atomica sulla CPU. Quando si esegue in ambienti paralleli con centinaia di thread, un singolo mutex in una sezione critica del codice può causare seri colli di bottiglia.