synchronization - sistemas - ¿Para qué se usa Test-and-Set?

test and test and set

Question

Después de leer la entrada de Test-and-Set Wikipedia , todavía me queda la pregunta "¿Para qué se usaría un Test-and-Set?"

Me doy cuenta de que puedes usarlo para implementar Mutex (como se describe en wikipedia), pero ¿qué otros usos tiene?

Answer 1

Básicamente, su uso es exactamente para mutexes, dada la tremenda importancia de la atomicidad. Eso es.

Test-and-set es una operación que se puede realizar con otras dos instrucciones, no atómicas y más rápidas (la atomicidad tiene una sobrecarga de hardware cuando se usa en sistemas multiprocesador), por lo que normalmente no la usaría por otros motivos.

Answer 2

Imagine que estaba escribiendo una aplicación bancaria, y su solicitud tenía una solicitud para retirar diez libras (sí, soy inglés;)) de la cuenta. Por lo tanto, debe leer el saldo de la cuenta corriente en una variable local, restar el retiro y luego escribir de nuevo el saldo en la memoria.

Sin embargo, ¿qué pasa si ocurre otra solicitud concurrente entre que usted lee el valor y lo escribe? Existe la posibilidad de que el resultado de esa solicitud se sobrescriba completamente por el primero, y el saldo de la cuenta será incorrecto.

Test-and-set nos ayuda a solucionar ese problema comprobando que el valor que sobrescribe es el que usted cree que debería ser. En este caso, puede verificar que el saldo sea el valor original que haya leído. Como es atómico, no se puede interrumpir, por lo que nadie puede tirar de la alfombra debajo de usted entre la lectura y la escritura.

Otra forma de solucionar el mismo problema es eliminar un bloqueo en la ubicación de la memoria. Desafortunadamente, los bloqueos son tremendamente difíciles de acertar, difíciles de razonar, tienen problemas de escalabilidad y se comportan mal frente a fallas, por lo que no son una solución ideal (pero definitivamente práctica). Los enfoques de prueba y configuración forman la base de algunas memorias transaccionales de software, que optimísticamente permiten que cada transacción se ejecute al mismo tiempo, a costa de deshacerse de todas ellas si entran en conflicto.

Answer 3

Lo utiliza en cualquier momento que quiera escribir datos en la memoria después de hacer algún trabajo y asegurarse de que otro hilo no haya sobrescrito el destino desde que comenzó. Muchos algoritmos de bloqueo / sin mutex toman esta forma.

Answer 4

Se usa cuando necesita obtener un valor compartido, hacer algo con él y cambiar el valor, suponiendo que otro hilo no lo haya cambiado todavía.

En cuanto a los usos prácticos, la última vez que lo vi fue en implementaciones de colas concurrentes (colas que pueden ser empujadas / reventadas por múltiples hilos sin necesidad de semáforos o mutexes).

¿Por qué usaría TestAndSet en lugar de un mutex? Porque generalmente requiere menos sobrecarga que un mutex. Cuando un mutex requiere intervención del sistema operativo, un TestAndSet se puede implementar como una única instrucción atómica en la CPU. Cuando se ejecuta en entornos paralelos con cientos de hilos, un único mutex en una sección crítica del código puede causar serios cuellos de botella.

Answer 5

Un buen ejemplo es "incremento".

Digamos que dos hilos ejecutan a = a + 1 . Digamos que comienza con el valor 100 . Si ambos subprocesos se ejecutan al mismo tiempo (multinúcleo), ambos cargarán a como 100 , se incrementarán a 101 y se almacenarán en a . ¡Incorrecto!

Con prueba y configuración, usted está diciendo "Establezca a en 101 , pero solo si actualmente tiene el valor 100 ". En este caso, un hilo pasará esa prueba pero el otro fallará. En el caso de falla, el hilo puede volver a intentar la instrucción completa, esta vez cargando a como 101 . Éxito.

Esto es generalmente más rápido que usar un mutex porque:

1. La mayoría de las veces no hay una condición de carrera, por lo que la actualización ocurre sin tener que adquirir algún tipo de exclusión mutua.
2. Incluso durante una colisión, un hilo no está bloqueado en absoluto, y es más rápido que el otro hilo simplemente gire y vuelva a intentarlo de lo que sería suspenderse en línea por algún mutex.