Prueba y configuración

En informática , la instrucción de prueba y establecimiento (test-and-set ) se utiliza para escribir (establecer) un valor de indicador en una ubicación de memoria y devolver su valor anterior como una única operación atómica (es decir, no interrumpible ). El proceso que realiza la llamada puede entonces "probar" el resultado para ver si el estado se modificó. Si varios procesos pueden acceder a la misma ubicación de memoria y si un proceso está realizando una prueba y establecimiento, ningún otro proceso puede iniciar otra prueba y establecimiento hasta que la del primer proceso haya finalizado. Una unidad central de procesamiento (CPU) puede utilizar una instrucción de prueba y establecimiento proporcionada por otro componente electrónico , como la memoria RAM de doble puerto ; la propia CPU también puede ofrecer una instrucción de prueba y establecimiento.

Se puede construir un bloqueo utilizando una instrucción atómica de prueba y establecimiento ^{[ 1 ]} de la siguiente manera:

Este código asume que la ubicación de memoria se inicializó a 0 en algún momento antes de la primera prueba y establecimiento. El proceso que llama obtiene el bloqueo si el valor anterior era 0; de lo contrario, el bucle while se queda esperando para adquirir el bloqueo. Esto se denomina spinlock . En cualquier momento, el poseedor del bloqueo puede simplemente restablecer la ubicación de memoria a 0 para liberar el bloqueo y permitir que otro lo adquiera; esto no requiere ningún manejo especial, ya que el poseedor "es dueño" de esta ubicación de memoria. " Prueba y prueba y establecimiento " 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 como máximo dos procesos concurrentes. ^{[ 2 ]} En contraste, compare-and-swap (comparando de 32 bits) ofrece una solución más general a este problema, y ​​en algunas implementaciones también está disponible compare-and-swap más amplio (comparando de 64 o 128 bits) para una utilidad extendida.

Las instrucciones de prueba y configuración de la DPRAM pueden funcionar de diversas maneras. A continuación, se presentan dos variantes que describen una DPRAM con exactamente dos puertos, lo que permite que dos componentes electrónicos independientes (como dos CPU) accedan a todas las ubicaciones de memoria de la DPRAM.

Algunos conjuntos de instrucciones tienen una instrucción de lenguaje máquina atómica de prueba y establecimiento . Ejemplos de ello son x86 ^{[ 3 ]} e IBM System/360 y sus sucesores (incluida z/Architecture ). ^{[ 4 ]} Aquellos que no la tienen aún pueden implementar una prueba y establecimiento atómicos mediante una instrucción de lectura-modificación-escritura o de comparación e intercambio .

La instrucción de prueba y establecimiento, cuando se usa con valores booleanos, utiliza una lógica similar a la que se muestra en la siguiente función, con la salvedad de que la función debe ejecutarse de forma atómica . Es decir, ningún otro proceso debe poder interrumpir la función durante su ejecución, evitando así que vea un estado que solo existe mientras la función se ejecuta. Esto requiere soporte de hardware; no se puede implementar como se muestra. Sin embargo, el código mostrado ayuda a explicar el comportamiento de la instrucción de prueba y establecimiento. NOTA: En este ejemplo, se asume 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 de referencia booleana) { booleano inicial = bloqueo; bloqueo = verdadero; devolver inicial; }

El código mostrado no solo no es atómico, en el sentido de la instrucción de prueba y establecimiento, sino que también difiere de las descripciones de prueba y establecimiento de hardware DPRAM mencionadas anteriormente. 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 establecimiento de DPRAM, la memoria se establece solo 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 solo puede ser 1, pero si 0 y 1 se consideran los únicos valores válidos para la ubicación de 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 establecimiento" en el sentido completo y convencional del término. Lo esencial a tener en cuenta es la intención y el principio general de la comprobación y asignación de valores: un valor se comprueba y se asigna en una operación atómica, de modo que ningún otro hilo o proceso del programa puede modificar la ubicación de memoria de destino después de la comprobación, pero antes de su asignación. (Esto se debe a que la ubicación solo debe asignarse si actualmente tiene un valor determinado, no si lo tuvo en algún momento anterior).

En el lenguaje de programación C , la implementación sería la siguiente:

#define BLOQUEADO 1int test_and_set ( int * lock_ptr ) { int old_value ;// -- Inicio del segmento atómico -- // Esto debe interpretarse como pseudocódigo solo con fines ilustrativos. // La compilación tradicional de este código no garantiza la atomicidad, el // uso de memoria compartida (es decir, valores no almacenados en caché), la protección contra las optimizaciones del compilador , // u otras propiedades requeridas. old_value = * lock_ptr ; * lock_ptr = LOCKED ; // -- Fin del segmento atómico --devolver valor_antiguo ; }

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 necesita ser atómica. (Esto es cierto porque retrasar la comparación de valores, independientemente del 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, el resultado de la prueba ya está establecido, 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 prueba y conjunto ^{[ 5 ] [ 6 ]} de la siguiente manera:

bloqueo entero volátil = 0 ;void critical () {// Bloqueo de giro: bucle infinito hasta que consigamos el bloqueo. // Sabemos que el bloqueo se obtuvo correctamente después de salir // de este bucle while porque la función test_and_set() bloquea // el bloqueo pero devuelve el valor de bloqueo _anterior_. // Si (y solo si) el valor de bloqueo anterior era 1, entonces el bloqueo // ya estaba bloqueado por otro hilo o proceso, por lo que permanecemos en el // bucle y volvemos a intentarlo. // Cuando el valor de bloqueo anterior era 0, eso indica que el // bloqueo **no** estaba bloqueado antes de que lo bloqueáramos. Ahora **está** bloqueado // porque _nosotros_ lo bloqueamos, por lo que poseemos el bloqueo y podemos salir del bucle de giro. while ( test_and_set ( & lock ) == 1 );Sección crítica // Solo un proceso puede estar en esta sección a la vez// Libera el bloqueo cuando termines con la sección crítica. // Era 1 (porque lo bloqueamos). // Cualquier otro proceso que lo haya "cambiado" desde entonces // no estaba en la sección crítica, por lo que los // otros procesos también lo establecieron en 1, pero // no obtuvieron el bloqueo ni entraron en la // sección crítica, y (o bien se rindieron o) // siguen esperando en sus propios bucles de espera. bloqueo = 0 ; }

enter_region: ; Una etiqueta "saltar a"; punto de entrada de la función.tsl reg , flag ; Bloqueo de prueba y establecimiento; flag es la ; variable compartida; se copia ; en el registro reg y flag ; luego se establece atómicamente a 1.cmp reg , #0 ; ¿Era la bandera cero en entry_region?jnz enter_region ; Saltar a enter_region si ; reg no es cero; es decir, ; flag no era cero al entrar.ret ; Salida; es decir, la bandera era cero en ; entrada. Si llegamos aquí, tsl ; la habrá establecido distinta de cero; por lo tanto, ; hemos reclamado el recurso ; asociado con la bandera.leave_region: mover bandera , #0; almacenar 0 en bandera ret ; devolver al llamador

Las cuatro métricas de evaluación principales para los bloqueos en general son la latencia de adquisición de bloqueo sin contención, el tráfico del bus, la equidad y el almacenamiento. ^{[ 7 ]}

Las pruebas estandarizadas obtienen puntuaciones bajas en dos de ellas: el elevado tráfico de autobuses y la injusticia.

Cuando el procesador P1 obtiene un bloqueo y el procesador P2 también lo espera, P2 continúa realizando transacciones en el bus para intentar adquirirlo. Una vez que un procesador obtiene un bloqueo, todos los demás procesadores que también desean obtenerlo siguen intentándolo mediante transacciones repetidas en el bus hasta conseguirlo. Esto aumenta significativamente el tráfico del bus requerido para la operación de prueba y establecimiento. Esto ralentiza todo el tráfico proveniente de fallos de caché y coherencia . Ralentiza la sección en general, ya que el tráfico se satura con intentos fallidos de adquisición de bloqueo. La operación de prueba y establecimiento supone una mejora con respecto a TSL, ya que no inicia solicitudes de adquisición de bloqueo de forma continua.

Al considerar la equidad, analizamos si un procesador tiene una oportunidad justa de adquirir el bloqueo una vez liberado. En una situación extrema, el procesador podría sufrir un bloqueo insostenible, es decir, podría no ser capaz de adquirirlo durante un período prolongado, incluso después de haber quedado libre durante ese tiempo.

El almacenamiento adicional que requiere TSL es prácticamente nulo, ya que solo se necesita un bloqueo. La latencia sin contención también es baja, puesto que solo se requiere una instrucción atómica y una bifurcación.

• Obtener y agregar
• Prueba y prueba y ajuste
• Enlace de carga/almacenamiento condicional
• Comparar e intercambiar

• Descripción de la Enciclopedia de Sistemas Insensibles al Retardo
• "Prueba y configuración sin esperas" en Wayback Machine (archivado el 5 de febrero de 2006) , por Yehuda Afek
• int testandset(int *lock) - Rutina invocable desde C escrita en lenguaje ensamblador de Sun SPARC
• Manual del desarrollador de Intel