En ciencias de la computación , la instrucción de CPU de buscar y agregar (FAA) incrementa atómicamente el contenido de una ubicación de memoria en un valor especificado.
Es decir, buscar y agregar realiza la operación
- Incrementar el valor en la dirección x en a , donde x es una ubicación de memoria y a es algún valor, y devolver el valor original en x
de tal manera que si esta operación es ejecutada por un proceso en un sistema concurrente , ningún otro proceso verá nunca un resultado intermedio.
Fetch-and-add se puede utilizar para implementar estructuras de control de concurrencia como bloqueos mutex y semáforos .
Descripción general
La motivación para tener un fetch-and-add atómico es que las operaciones que aparecen en los lenguajes de programación como
- x = x + a
no son seguros en un sistema concurrente, donde varios procesos o subprocesos se ejecutan simultáneamente (ya sea en un sistema multiprocesador o programados de manera preventiva en algunos sistemas de un solo núcleo). La razón es que tal operación se implementa en realidad como múltiples instrucciones de máquina:
- Obtenga el valor en la ubicación x , digamos x antiguo , en un registro;
- añadir una a x viejas en el registro;
- almacenar el nuevo valor del registro de nuevo en x .
Cuando un proceso esta haciendo x = x + ay otro está haciendo x = x + b al mismo tiempo, hay una condición de carrera . Ambos pueden obtener x antiguo y operar en eso, luego ambos almacenan sus resultados con el efecto de que uno sobrescribe al otro y el valor almacenado se convierte en x antiguo + a o x antiguo + b , no x antiguo + a + b como podría ser esperado.
En sistemas monoprocesador sin soporte de preferencia del kernel , es suficiente deshabilitar las interrupciones antes de acceder a una sección crítica . Sin embargo, en sistemas multiprocesador (incluso con interrupciones desactivadas) dos o más procesadores podrían estar intentando acceder a la misma memoria al mismo tiempo. La instrucción buscar y agregar permite que cualquier procesador incremente atómicamente un valor en la memoria, evitando tales colisiones de múltiples procesadores.
Maurice Herlihy (1991) demostró que buscar y agregar tiene un número de consenso finito , en contraste con la operación de comparar e intercambiar . La operación de buscar y agregar puede resolver el problema del consenso sin espera para no más de dos procesos concurrentes. [1]
Implementación
La instrucción buscar y agregar se comporta como la siguiente función. Fundamentalmente, toda la función se ejecuta de forma atómica : ningún proceso puede interrumpir la función en mitad de la ejecución y, por lo tanto, ver un estado que solo existe durante la ejecución de la función. Este código solo sirve para ayudar a explicar el comportamiento de buscar y agregar; La atomicidad requiere soporte de hardware explícito y, por lo tanto, no se puede implementar como una función simple de alto nivel.
Función << atómica >> FetchAndAdd ( ubicación de la dirección , int inc) { valor int : = * ubicación * ubicación: = valor + inc valor de retorno}
Para implementar un bloqueo de exclusión mutua, definimos la operación FetchAndIncrement, que es equivalente a FetchAndAdd con inc = 1. Con esta operación, se puede implementar un bloqueo de exclusión mutua utilizando el algoritmo de bloqueo de ticket como:
record locktype { int ticketnumber int turn}procedimiento LockInit ( tipo de bloqueo * bloqueo) { lock.ticketnumber: = 0 lock.turn: = 0}procedimiento Lock ( locktype * lock) { int myturn: = FetchAndIncrement (& lock.ticketnumber) // debe ser atómico, ya que muchos subprocesos pueden solicitar un bloqueo al mismo tiempo mientras lock.turn ≠ myturn skip // girar hasta que se obtenga el bloqueo }procedimiento Desbloqueo ( tipo de bloqueo * bloqueo) { FetchAndIncrement (& lock.turn) // esto no necesita ser atómico, ya que solo el poseedor del bloqueo ejecutará esto }
Estas rutinas proporcionan un bloqueo de exclusión mutua cuando se cumplen las siguientes condiciones:
- La estructura de datos de tipo de bloqueo se inicializa con la función LockInit antes de su uso
- El número de tareas en espera del bloqueo no supera INT_MAX en ningún momento
- El tipo de datos entero utilizado en los valores de bloqueo puede 'ajustarse' cuando se incrementa continuamente
Soporte de hardware y software
Un atómico La función fetch_add aparece en el estándar C ++ 11 . [2] Está disponible como una extensión propietaria de C en la especificación Itanium ABI , [3] y (con la misma sintaxis) en GCC . [4]
implementación x86
En la arquitectura x86, la instrucción ADD con el operando de destino que especifica una ubicación de memoria es una instrucción de buscar y agregar que ha estado allí desde el 8086 (simplemente no se llamaba así), y con el prefijo LOCK, es atómica. en varios procesadores. Sin embargo, no pudo devolver el valor original de la ubicación de la memoria (aunque devolvió algunos indicadores) hasta que el 486 introdujo la instrucción XADD.
La siguiente es una implementación de C para el compilador GCC , para plataformas Intel x86 de 32 y 64 bits, basada en la sintaxis asm extendida:
static inline int fetch_and_add ( int * variable , int value ) { __asm__ volatile ( "lock; xaddl% 0,% 1" : "+ r" ( valor ), "+ m" ( * variable ) // entrada + salida : / / Sin entrada solo : "memoria" ); valor de retorno ; }
Historia
Fetch-and-add fue introducido por el proyecto Ultracomputer , que también produjo un multiprocesador compatible con fetch-and-add y que contenía conmutadores VLSI personalizados que podían combinar referencias de memoria concurrentes (incluidas fetch-and-added) para evitar que se serializaran en el módulo de memoria que contiene el operando de destino.
Ver también
Referencias
- ^ 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 .
- ^ "std :: atomic :: fetch_add" . cppreference.com . Consultado el 1 de junio de 2015 .
- ^ "Interfaz binaria de aplicación (ABI) específica del procesador Intel Itanium" (PDF) . Intel Corporation . 2001.
- ^ "Atomic Builtins" . Usando la colección de compiladores GNU (GCC) . Fundación de Software Libre. 2005.