Después de leer el Test-and-Set Wikipedia entry, aún me queda la pregunta "¿Para qué se usaría un Test-and-Set?"¿Para qué se usa Test-and-Set?
Me doy cuenta de que puede usarlo para implementar Mutex (como se describe en wikipedia), pero ¿qué otros usos tiene?
Lo utiliza en cualquier momento que desee 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ó. Una gran cantidad de lock/mutex-free algorithms toma esta forma.
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 está en sistemas multiprocesador), por lo que normalmente no la usaría por otros motivos.
Un buen ejemplo es "incremento".
Digamos que dos subprocesos ejecutan a = a + 1. Diga a 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 conjunto, está diciendo "Establecer 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 utilizar un mutex porque:
Se usa cuando necesita obtener un valor compartido, hacer algo al respecto y cambiar el valor, asumiendo 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.
mutex internamente podría usar test & set. ¿cómo se compara TestAndSet y mutex? Creo que no es correcto comparar – user1762571
En Python, los objetos mutex tienen explícitamente un método "testandset". La documentación se refiere a ella como "atómica", con citas, lo que no inspira confianza, pero sí indica que los dos conceptos no son, por ejemplo, mutuamente excluyentes. –
Imagine que estaba escribiendo una aplicación bancaria, y su aplicación 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 sea sobrescrito por completo por el primero, y el saldo de la cuenta sea 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.
+1 Me acabas de ayudar a resolver un problema en el que estaba trabajando. –
@ jason-cohen: Esa es en realidad una descripción de [Compare and Swap] (https://en.wikipedia.org/wiki/Compare-and-swap). La prueba y el conjunto implican solo los valores 0 y 1. La parte ** set ** se refiere a establecer el valor en una ubicación de memoria especificada en 1. Devuelve el valor anterior, ya sea un 1 o un 0, y hace todo esto en una sola operación atómica. –
@GregSlepak es correcto, esto es compare_and_swap. test_and_set() toma un puntero booleano a un objetivo, lo establece en TRUE y devuelve el valor original del puntero. Si el valor de retorno de test_and_set (& lock) (es decir, el valor original de & lock) es verdadero, entonces ingresamos a la sección crítica. – mateor