En ciencias de la computación , la instrucción de CPU buscar y agregar ( FAA ) incrementa atómicamente el contenido de una ubicación de memoria en un valor especificado.
Es decir, fetch-and-add realiza la siguiente operación: incrementa el valor en la dirección x en a , donde x es una ubicación de memoria y a es algún valor, y devuelve 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á jamás un resultado intermedio.
La búsqueda y adición se puede utilizar para implementar estructuras de control de concurrencia, como bloqueos mutex y semáforos .
La motivación para tener un método atómico de búsqueda y adición es que las operaciones que aparecen en los lenguajes de programación como x = x + a no son seguras en un sistema concurrente, donde múltiples 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 una operación de este tipo en realidad se implementa como múltiples instrucciones de máquina:
Cuando un proceso está haciendo x = x + a y otro está haciendo x = x + b simultáneamente, hay una carrera de datos . Ambos pueden buscar x old y operar sobre eso, luego ambos almacenan sus resultados con el efecto de que uno sobrescribe al otro y el valor almacenado se convierte en x old + a o x old + b , no x old + a + b como podría esperarse.
En sistemas monoprocesador sin soporte para la prelación del núcleo , es suficiente deshabilitar las interrupciones antes de acceder a una sección crítica . Sin embargo, en sistemas multiprocesador (incluso con interrupciones deshabilitadas) dos o más procesadores podrían estar intentando acceder a la misma memoria al mismo tiempo. La instrucción de búsqueda y adición permite que cualquier procesador incremente atómicamente un valor en la memoria, lo que evita este tipo de colisiones entre procesadores.
Maurice Herlihy (1991) demostró que la operación de búsqueda y adición tiene un número finito de consenso , a diferencia de la operación de comparación y cambio . La operación de búsqueda y adición puede resolver el problema de consenso sin espera para no más de dos procesos concurrentes. [1]
La instrucción fetch-and-add 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 a mitad de su 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 fetch-and-add; la atomicidad requiere soporte de hardware explícito y, por lo tanto, no se puede implementar como una función simple de alto nivel.
<< atómico >> función FetchAndAdd( dirección ubicación, int inc) { int valor := *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 tickets como:
registro locktype { int ticketnumber int turno}procedimiento LockInit( locktype * lock) { bloqueo.número de ticket := 0 bloqueo.giro := 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 // gira hasta que se adquiera el bloqueo }procedimiento UnLock( tipobloqueo * 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:
Una función fetch_add atómica 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]
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 búsqueda y adición que ha existido desde el 8086 (simplemente no se llamaba así en ese entonces) y, con el prefijo LOCK, es atómica en varios procesadores. Sin embargo, no podía devolver el valor original de la ubicación de memoria (aunque devolvía algunos indicadores) hasta que el 486 introdujo la instrucción XADD.
La siguiente es una implementación en C para el compilador GCC , para plataformas Intel x86 de 32 y 64 bits, basada en sintaxis asm extendida:
static inline int fetch_and_add ( int * variable , int valor ) { __asm__ volátil ( "bloqueo; xaddl %0, %1" : "+r" ( valor ), "+m" ( * variable ) // entrada + salida : // Sin solo entrada : "memoria" ); valor de retorno ; } La búsqueda y adición fue introducida por el proyecto Ultracomputer , que también produjo un multiprocesador que soportaba la búsqueda y adición y que contenía conmutadores VLSI personalizados que podían combinar referencias de memoria concurrentes (incluidas las búsquedas y adiciones) para evitar que se serializaran en el módulo de memoria que contenía el operando de destino.