En informática , la instrucción de prueba y configuración es una instrucción que se utiliza para escribir 1 (conjunto) en una ubicación de memoria y devolver su valor anterior como una sola operación atómica (es decir, no interrumpible). 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 CPU puede usar una instrucción de prueba y configuración ofrecida por otro componente electrónico, como RAM de doble puerto ; una CPU en sí misma también puede ofrecer una instrucción de prueba y configuración.
Se puede construir una cerradura usando una instrucción atómica de prueba y configuración [1] de la siguiente manera:
función Bloqueo (booleano * bloqueo) { while (test_and_set (bloqueo) == 1);}
El proceso de llamada obtiene el bloqueo si el valor anterior era 0; de lo contrario, el bucle while gira esperando adquirir el bloqueo. A esto se le llama spinlock . " Probar y probar y configurar " es otro ejemplo.
Maurice Herlihy (1991) demostró que probar y configurar tiene un número de consenso finito y puede resolver el problema de consenso sin espera para como máximo dos procesos concurrentes. [2] Por el contrario, compare-and-swap ofrece una solución más general a este problema.
Implementación de hardware de prueba y configuración
Las instrucciones de prueba y configuración de DPRAM pueden funcionar de muchas maneras. Aquí hay dos variaciones, las cuales describen una DPRAM que proporciona exactamente 2 puertos, lo que permite el acceso de 2 componentes electrónicos separados (como 2 CPU) a cada ubicación de memoria en la DPRAM.
Variación 1
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 la 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 espera y vuelve a intentarlo. Esta es una implementación de una espera ocupada o un 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 estaba intentando acceder a la ubicación de la memoria, la DPRAM realiza la prueba dada por la CPU 1. Si la prueba tiene éxito, la DPRAM establece la ubicación de la memoria en el valor dado por la CPU 1. Luego, la DPRAM borra su " note "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.
Variación 2
La CPU 1 emite una instrucción de prueba y configuración para escribir en la "ubicación de memoria A". El DPRAM no almacena inmediatamente el valor en la ubicación de memoria A, sino que 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 bandera" especial. Si en este punto, la CPU 2 emite una prueba y configuración en la ubicación de memoria A, la DPRAM detecta el valor de la bandera especial y, como en la Variación 1, emite una interrupción BUSY.
Independientemente de si la CPU 2 estaba intentando acceder a la ubicación de la memoria, 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 del registro especial a la ubicación de memoria A. Cualquiera de las dos operaciones borra el valor de la bandera especial. Si la CPU 2 emite ahora una prueba y configuración, tendrá éxito.
Implementación de software de test-and-set
Algunos conjuntos de instrucciones tienen una instrucción en lenguaje de máquina de prueba y conjunto atómico. Los ejemplos incluyen x86 [3] e IBM System / 360 y sus sucesores (incluido z / Architecture ). [4] Aquellos que no lo hacen aún pueden implementar una prueba atómica y establecer usando una instrucción de lectura-modificación-escritura o comparación-e-intercambio .
La instrucción de prueba y conjunto, cuando se usa con valores booleanos, usa lógica como la que se muestra en la siguiente función, excepto que la función debe ejecutarse atómicamente . Es decir, ningún otro proceso debe poder interrumpir la función en mitad de la ejecución, viendo así un estado que solo existe mientras se ejecuta la función. Eso 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 asume que 'bloqueo' se pasa por referencia (o por nombre) pero la asignación a 'inicial' crea un nuevo valor (no solo copiando una referencia).
función TestAndSet (boolean_ref lock) { inicial booleana = bloqueo; bloqueo = verdadero; volver inicial;}
El código que se muestra no solo 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 invariantes, 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 solo cuando la prueba tiene éxito y el valor establecer y la condición de prueba son especificadas por la CPU. Aquí, el valor para establecer solo 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 limitaciones). Desde ese punto de vista, esto puede, correctamente, llamarse "probar y configurar" en el sentido completo y convencional de ese término. El punto esencial a tener en cuenta es la intención general y el principio de prueba y configuración: un valor se prueba y se establece en una operación atómica de modo que ningún otro subproceso o proceso del programa pueda cambiar la ubicación de la memoria de destino después de que se prueba, pero antes Está establecido. (Esto se debe a que la ubicación solo debe establecerse si actualmente tiene un cierto valor, no si tuvo ese valor en algún momento anterior).
En el lenguaje de programación C , la implementación sería como:
#define LOCKED 1int test_and_set ( int * lockPtr ) { int oldValue ; // - 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é), protección contra optimizaciones // del compilador u otras propiedades requeridas. oldValue = * lockPtr ; * lockPtr = LOCKED ; // - Fin del segmento atómico - return oldValue ; }
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 cierto 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, el resultado de la prueba se ha establecido, incluso si aún no ha sido calculado, por ejemplo, por el operador ==.)
Exclusión mutua mediante test-and-set
Una forma de implementar la exclusión mutua es mediante el uso de un bloqueo basado en prueba y configuración [5] [6] de la siguiente manera:
Implementación de pseudo-C
bloqueo int volátil = 0 ; vacío crítico () { mientras ( prueba_y_conjunto ( & bloqueo ) == 1 ); sección crítica // solo un proceso puede estar en esta sección a la vez lock = 0 // suelte el bloqueo cuando termine 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átiles, el compilador y / o la (s) CPU (s) pueden optimizar el acceso para bloquear y / o usar valores almacenados en caché, lo que hace que el código anterior sea erróneo. Por el contrario, y por desgracia, la presencia de volátiles no no garantizar que lee y escribe están comprometidos con la memoria. Algunos compiladores emiten barreras de memoria para garantizar que las operaciones estén comprometidas con la memoria, pero dado que la semántica de volatile en C / C ++ es bastante vaga, no todos los compiladores lo harán. Consulte la documentación de su compilador para determinar si es así.
Esta función 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 se bloqueen. Es posible que nunca se conceda el bloqueo a un proceso. En tal caso, se repetirá sin cesar. Este es un inconveniente de esta implementación, ya que no garantiza la equidad. Estos temas se desarrollan con más detalle en la sección de desempeño .
Implementación de ensamblaje
entrar_en_region: ; Una etiqueta "saltar a"; punto de entrada de la función. tsl reg , bandera ; Probar y configurar bloqueo; bandera es la ; variable compartida; está copiado ; en el registro reg y flag ; luego se establece atómicamente en 1. cmp reg , # 0 ; ¿La bandera era cero en entry_region? jnz enter_region ; Salte a enter_region si ; reg no es cero; es decir, ; la bandera era distinta de cero en la entrada. ret ; Salida; es decir, la bandera estaba en cero ; entrada. Si llegamos aquí, tsl ; lo 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 ; volver a la persona que llama
Aquí tsl
hay una instrucción atómica y flag
es la variable de bloqueo. El proceso no regresa a menos que adquiera el bloqueo.
Evaluación del rendimiento de cerraduras de prueba y montaje
Las cuatro principales métricas de evaluación para las cerraduras en general son la latencia de adquisición de cerraduras no atendidas, el tráfico de autobuses, la equidad y el almacenamiento. [7]
Probar y establecer puntuaciones bajas en dos de ellos, a saber, alto tráfico de autobuses e 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 los 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 continúan intentando obtener el bloqueo iniciando transacciones de bus repetidamente hasta que se apoderan del bloqueo. Esto aumenta significativamente el requisito de tráfico de autobuses de probar y configurar. Esto ralentiza el resto del tráfico de la caché y fallas de coherencia . Ralentiza la sección general, ya que el tráfico está saturado por intentos fallidos de adquisición de bloqueo. Probar y probar y configurar es una mejora con respecto a TSL, ya que no inicia solicitudes de adquisición de bloqueos de forma continua.
Cuando consideramos la equidad, consideramos 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, es posible que no pueda adquirir el bloqueo durante un período de tiempo prolongado, aunque se haya liberado durante ese tiempo.
La sobrecarga de almacenamiento para TSL es casi nula, ya que solo se requiere un bloqueo. La latencia no asistida también es baja, ya que solo se necesitan una instrucción atómica y una rama.
Ver también
Referencias
- ↑ Anderson, TE (1 de enero de 1990). "El rendimiento de alternativas de bloqueo de giro para multiprocesadores de dinero compartido". Transacciones IEEE en sistemas paralelos y distribuidos . 1 (1): 6–16. doi : 10.1109 / 71.80120 . ISSN 1045-9219 .
- ^ Herlihy, Maurice (enero de 1991). "Sincronización sin espera" (PDF) . ACM Trans. Programa. Lang. Syst . 13 (1): 124-149. CiteSeerX 10.1.1.56.5659 . doi : 10.1145 / 114005.102808 . Consultado el 20 de mayo de 2007 .
- ^ "BTS — Prueba y ajuste de bits" . www.felixcloutier.com . Consultado el 21 de noviembre de 2016 .
- ^ "Centro de conocimiento de IBM" . www.ibm.com . Consultado el 21 de noviembre de 2016 .
- ^ Remzi H. Arpaci-Dusseau y Andrea C. Arpaci-Dusseau (2015). Sistemas operativos: tres piezas fáciles (0.91 ed.). Libros Arpaci-Dusseau: a través de http://www.ostep.org/ .
- ^ Solihin, Yan (2009). Fundamentos de la arquitectura informática paralela: sistemas multichip y multinúcleo . pag. 252. ISBN 9780984163007.
- ^ Solihin, Yan (2016). Fundamentos de la Arquitectura Paralela . Boca Raton, FL: CRC Press. ISBN 978-1-4822-1118-4.
enlaces externos
- Descripción de la Enciclopedia de sistemas insensibles al retardo
- " Prueba y configuración sin espera " de Yehuda Afek
- int testandset (int * lock) - Rutina C-invocable escrita en lenguaje ensamblador Sun SPARC
- Manual para desarrolladores de Intel