¿Para qué se utiliza Test-and-Set?

Question

Después de leer el Test-and-Set entrada de wikipedia, todavía me queda la pregunta "¿Para qué se utilizarí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

Lo usa cada vez que desea escribir datos en la memoria después de trabajar un poco y asegurarse de que otro hilo no haya sobrescrito el destino desde que comenzó.Mucho algoritmos sin bloqueo/mutex tomar esta forma.

Answer 2

Un buen ejemplo es el "incremento".

Digamos que se ejecutan dos hilos a = a + 1.Decir a comienza con el valor 100.Si ambos subprocesos se ejecutan al mismo tiempo (multinúcleo), ambos se cargarían a como 100, incrementar a 101, y guárdelo nuevamente en a.¡Equivocado!

Con probar y configurar, estás diciendo "Establecer a a 101, pero sólo 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 declaración completa, esta vez cargando a como 101.Éxito.

Generalmente, esto es más rápido que usar un mutex porque:

1. La mayoría de las veces no existe una condición de carrera, por lo que la actualización se realiza sin tener que adquirir algún tipo de exclusión mutua.
2. Incluso durante la colisión, un subproceso no se bloquea en absoluto, y es más rápido para el otro subproceso simplemente girar y volver a intentarlo que suspenderse en línea por algún mutex.

Answer 3

Imagínese que está escribiendo una solicitud bancaria y su solicitud incluye una solicitud para retirar diez libras (sí, soy inglés;)) de la cuenta.Por lo tanto, debe leer el saldo de la cuenta actual en una variable local, restar el retiro y luego escribir el saldo en la memoria.

Sin embargo, ¿qué pasa si ocurre otra solicitud simultánea entre la lectura del valor y la escritura?Existe la posibilidad de que el resultado de esa solicitud sea sobrescrito completamente por la primera y el saldo de la cuenta sea incorrecto.

Test-and-set nos ayuda a solucionar ese problema al verificar que el valor que sobrescribe es el que cree que debería ser.En este caso, puedes comprobar que el saldo era el valor original que leíste.Dado que es atómico, no es interrumpible, por lo que nadie puede quitarle la alfombra entre la lectura y la escritura.

Otra forma de solucionar el mismo problema es quitar un candado en la ubicación de la memoria.Desafortunadamente, los bloqueos son tremendamente difíciles de corregir, difíciles de razonar, tienen problemas de escalabilidad y se comportan mal ante 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 de manera optimista permiten que cada transacción se ejecute simultáneamente, a costa de revertirlas todas si entran en conflicto.

Answer 4

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

La prueba y configuración es una operación que se puede realizar con otras dos instrucciones, no atómicas y más rápidas (la atomicidad conlleva una sobrecarga de hardware en sistemas multiprocesador), por lo que normalmente no la usarías por otras razones.

Answer 5

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

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

¿Por qué utilizarías TestAndSet en lugar de un mutex?Porque generalmente requiere menos gastos generales que un mutex.Cuando un mutex requiere la intervención del sistema operativo, se puede implementar un TestAndSet como una única instrucción atómica en la CPU.Cuando se ejecuta en entornos paralelos con cientos de subprocesos, un único mutex en una sección crítica de código puede provocar graves cuellos de botella.