En informática , la instrucción test-and-set es una instrucción que se utiliza para escribir (establecer) 1 en una ubicación de memoria y devolver su valor anterior como una única operación atómica (es decir, no interrumpible ). El llamador puede entonces "probar" el resultado para ver si el estado fue cambiado por la llamada. Si varios procesos pueden acceder a la misma ubicación de memoria, y si un proceso está realizando actualmente una prueba y configuración, ningún otro proceso puede comenzar otra prueba y configuración hasta que finalice la prueba y configuración del primer proceso. Una unidad central de procesamiento (CPU) puede utilizar una instrucción test-and-set ofrecida por otro componente electrónico, como una RAM de doble puerto ; una CPU por sí misma también puede ofrecer una instrucción test-and-set.
Se puede construir un bloqueo utilizando una instrucción atómica de prueba y configuración [1] de la siguiente manera:
Este código supone que la ubicación de la memoria se inicializó a 0 en algún momento antes de la primera prueba y configuración. El proceso que realiza la llamada obtiene el bloqueo si el valor anterior era 0; de lo contrario, el bucle while gira esperando adquirir el bloqueo. Esto se denomina spinlock . En cualquier momento, el titular del bloqueo puede simplemente volver a establecer la ubicación de la memoria a 0 para liberar el bloqueo para que otro lo adquiera; esto no requiere ningún manejo especial ya que el titular "posee" esta ubicación de memoria. " Prueba y prueba y configuración " es otro ejemplo.
Maurice Herlihy (1991) demostró que test-and-set (comparando de 1 bit) tiene un número de consenso finito y puede resolver el problema de consenso sin espera para dos procesos concurrentes como máximo. [2] Por el contrario, compare-and-swap (comparando de 32 bits) ofrece una solución más general a este problema, y en algunas implementaciones compare-double-and-swap (comparando de 64 bits) también está disponible para una utilidad extendida.
Las instrucciones de prueba y configuración de DPRAM pueden funcionar de muchas maneras. A continuación se presentan dos variantes, que describen una DPRAM que proporciona exactamente 2 puertos, lo que permite que 2 componentes electrónicos independientes (como 2 CPU) accedan a cada ubicación de memoria en la DPRAM.
Cuando la CPU 1 emite una instrucción de prueba y configuración, la DPRAM primero hace una "nota interna" de esto almacenando la dirección de la ubicación de memoria en un lugar especial. Si en este punto, la CPU 2 emite una instrucción de prueba y configuración para la misma ubicación de memoria, la DPRAM primero verifica su "nota interna", reconoce la situación y emite una interrupción BUSY, que le dice a la CPU 2 que debe esperar y volver a intentarlo. Esta es una implementación de una espera ocupada o bloqueo de giro que utiliza el mecanismo de interrupción. Dado que todo esto sucede a velocidades de hardware, la espera de la CPU 2 para salir del bloqueo de giro es muy corta.
Independientemente de si la CPU 2 intenta acceder a la ubicación de memoria o no, la DPRAM realiza la prueba dada por la CPU 1. Si la prueba tiene éxito, la DPRAM establece la ubicación de memoria en el valor dado por la CPU 1. Luego, la DPRAM borra su "nota interna" de que la CPU 1 estaba escribiendo allí. En este punto, la CPU 2 podría emitir una prueba y configuración, que tendría éxito.
La CPU 1 emite una instrucción de prueba y configuración para escribir en la "ubicación de memoria A". La DPRAM no almacena inmediatamente el valor en la ubicación de memoria A, sino que, en cambio, mueve simultáneamente el valor actual a un registro especial, mientras establece el contenido de la ubicación de memoria A en un "valor de indicador" especial. Si en este punto, la CPU 2 emite una instrucción de prueba y configuración en la ubicación de memoria A, la DPRAM detecta el valor de indicador especial y, como en la Variante 1, emite una interrupción BUSY.
Independientemente de si la CPU 2 intentaba acceder a la ubicación de memoria o no, la DPRAM ahora realiza la prueba de la CPU 1. Si la prueba tiene éxito, la DPRAM establece la ubicación de memoria A en el valor especificado por la CPU 1. Si la prueba falla, la DPRAM copia el valor nuevamente desde el registro especial a la ubicación de memoria A. Cualquier operación borra el valor del indicador especial. Si la CPU 2 ahora emite una prueba y configuración, tendrá éxito.
Algunos conjuntos de instrucciones tienen una instrucción de lenguaje de máquina de prueba y configuración atómica. Algunos ejemplos incluyen x86 [3] e IBM System/360 y sus sucesores (incluido z/Architecture ). [4] Aquellos que no lo tienen pueden implementar una prueba y configuración atómica utilizando una instrucción de lectura-modificación-escritura o de comparación e intercambio .
La instrucción test and set, cuando se utiliza con valores booleanos, utiliza una lógica como la que se muestra en la siguiente función, excepto que la función debe ejecutarse de forma atómica . Es decir, ningún otro proceso debe poder interrumpir la función a mitad de la ejecución, con lo que se verá un estado que solo existe mientras se ejecuta la función. Esto requiere soporte de hardware; no se puede implementar como se muestra. Sin embargo, el código que se muestra ayuda a explicar el comportamiento de test-and-set. NOTA: En este ejemplo, se supone que 'lock' se pasa por referencia (o por nombre) pero la asignación a 'initial' crea un nuevo valor (no solo copia una referencia).
función TestAndSet(bloqueo booleano_ref) { booleano inicial = bloqueo; bloqueo = verdadero; devolver inicial;}El código que se muestra no sólo no es atómico, en el sentido de la instrucción de prueba y configuración, sino que también difiere de las descripciones de prueba y configuración de hardware DPRAM anteriores. Aquí, el valor que se establece y la prueba son fijos e invariables, y el valor se actualiza independientemente del resultado de la prueba, mientras que para la prueba y configuración de DPRAM, la memoria se establece sólo cuando la prueba tiene éxito, y el valor a establecer y la condición de prueba son especificados por la CPU. Aquí, el valor a establecer sólo puede ser 1, pero si 0 y 1 se consideran los únicos valores válidos para la ubicación de la memoria, y "el valor es distinto de cero" es la única prueba permitida, entonces esto equivale al caso descrito para el hardware DPRAM (o, más específicamente, el caso DPRAM se reduce a esto bajo estas restricciones). Desde ese punto de vista, esto puede, correctamente, llamarse "prueba y configuración" en el sentido completo y convencional de ese término. El punto esencial que hay que tener en cuenta es la intención general y el principio de prueba y configuración: un valor se prueba y se configura en una operación atómica de modo que ningún otro hilo o proceso del programa pueda cambiar la ubicación de la memoria de destino después de que se prueba pero antes de que se configure. (Esto se debe a que la ubicación solo se debe configurar si actualmente tiene un valor determinado, no si tenía ese valor en algún momento anterior).
En el lenguaje de programación C , la implementación sería así:
#define BLOQUEADO 1int prueba_y_conjunto ( int * lockPtr ) { int valorAnterior ; // -- Inicio del segmento atómico -- // Esto debe interpretarse como pseudocódigo solo con fines ilustrativos. // La compilación tradicional de este código no garantizará la atomicidad, el uso de memoria compartida (es decir, valores no almacenados en caché), la protección contra optimizaciones del compilador u otras propiedades requeridas. oldValue = * lockPtr ; * lockPtr = LOCKED ; // -- Fin del segmento atómico -- devolver valorAnterior ; } El código también muestra que en realidad hay dos operaciones: una lectura-modificación-escritura atómica y una prueba. Solo la lectura-modificación-escritura debe ser atómica. (Esto es así porque retrasar la comparación de valores por cualquier cantidad de tiempo no cambiará el resultado de la prueba una vez que se haya obtenido el valor a probar. Una vez que el código escribe el valor inicial, se ha establecido el resultado de la prueba, incluso si aún no se ha calculado, por ejemplo, mediante el operador ==).
Una forma de implementar la exclusión mutua es mediante el uso de un bloqueo basado en pruebas y configuraciones [5] [6] de la siguiente manera:
int volátil bloqueo = 0 ; void critical () { // Bloqueo de giro: bucle indefinidamente hasta que obtengamos el bloqueo; sabemos que el bloqueo se obtuvo exitosamente después de salir de este bucle while porque la función test_and_set() bloquea el bloqueo y devuelve el valor de bloqueo anterior. Si el valor de bloqueo anterior era 1, entonces el bloqueo **ya** estaba bloqueado por otro hilo o proceso. Sin embargo, una vez que el valor de bloqueo anterior era 0, entonces indica que el bloqueo **no** estaba bloqueado antes de que lo bloqueáramos, pero ahora **está** bloqueado porque lo bloqueamos, lo que indica que somos dueños del bloqueo. while ( test_and_set ( & lock ) == 1 ); critical section // solo un proceso puede estar en esta sección a la vez lock = 0 ; // libera el bloqueo cuando terminas con la sección crítica } La variable de bloqueo es una variable compartida, es decir, todos los procesadores/subprocesos pueden acceder a ella. Tenga en cuenta la palabra clave volátil . En ausencia de volátil, el compilador o la(s) CPU pueden optimizar el acceso al bloqueo o utilizar valores almacenados en caché, lo que hace que el código anterior sea erróneo. Por el contrario, y desafortunadamente, la presencia de volátil no garantiza que las lecturas y escrituras se confirmen en la memoria. Algunos compiladores emiten barreras de memoria para garantizar que las operaciones se confirmen en la memoria, pero como la semántica de volátil en C/C++ es bastante vaga, no todos los compiladores lo harán. Consulte la documentación de su compilador para determinar si lo hace.
Esta función de bloqueo de giro puede ser invocada por varios procesos, pero se garantiza que solo un proceso estará en la sección crítica a la vez. El resto de los procesos seguirán girando hasta que obtengan el bloqueo. Es posible que a un proceso nunca se le conceda el bloqueo. En tal caso, se repetirá sin fin. Este es un inconveniente de la implementación de un bloqueo de giro, ya que no garantiza la imparcialidad. Estos problemas se explican con más detalle en la sección de rendimiento.
enter_region: ; Una etiqueta "saltar a"; punto de entrada de la función. tsl reg , flag ; Prueba y establece bloqueo; flag es la variable compartida; se copia en el registro reg y flag ; luego se establece atómicamente en 1. cmp reg , #0; ¿La bandera estaba cero en entry_region? jnz enter_region ; Saltar a enter_region si ; reg no es cero; es decir, ; el indicador no era cero al ingresar. ret ; Salir; es decir, la bandera estaba en cero en ; la entrada. Si llegamos aquí, tsl ; la habrá establecido en un valor distinto de cero; por lo tanto, ; hemos reclamado el recurso ; asociado con la bandera. leave_region: mover bandera , #0; almacenar 0 en la bandera ret ; regresar al llamador Aquí tslhay una instrucción atómica y flages la variable de bloqueo. El proceso no retorna a menos que adquiera el bloqueo.
Las cuatro métricas de evaluación principales para los bloqueos en general son la latencia de adquisición de bloqueo sin competencia, el tráfico de bus, la imparcialidad y el almacenamiento. [7]
Las puntuaciones de prueba y configuración son bajas en dos de ellas, a saber, el alto tráfico de autobuses y la injusticia.
Cuando el procesador P1 ha obtenido un bloqueo y el procesador P2 también está esperando el bloqueo, P2 seguirá incurriendo en transacciones de bus en intentos de adquirir el bloqueo. Cuando un procesador ha obtenido un bloqueo, todos los demás procesadores que también desean obtener el mismo bloqueo siguen intentando obtener el bloqueo iniciando transacciones de bus repetidamente hasta que consiguen el bloqueo. Esto aumenta significativamente el requisito de tráfico de bus de prueba y configuración. Esto ralentiza todo el resto del tráfico de caché y errores de coherencia . Ralentiza la sección en general, ya que el tráfico está saturado por intentos fallidos de adquisición de bloqueo. Prueba y prueba y configuración es una mejora con respecto a TSL, ya que no inicia solicitudes de adquisición de bloqueo de forma continua.
Cuando consideramos la equidad, tenemos en cuenta si un procesador tiene una oportunidad justa de adquirir el bloqueo cuando se libera. En una situación extrema, el procesador podría morir de hambre, es decir, podría no ser capaz de adquirir el bloqueo durante un período prolongado de tiempo, aunque se haya liberado durante ese tiempo.
La sobrecarga de almacenamiento para TSL es prácticamente nula, ya que solo se requiere un bloqueo. La latencia sin contención también es baja, ya que solo se necesitan una instrucción atómica y una bifurcación.