Fetch-and-add

En informàtica, la instrucció de la CPU de buscar i afegir (FAA) augmenta atòmicament el contingut d'una ubicació de memòria en un valor especificat.

És a dir, fetch-and-add realitza l'operació

incrementeu el valor a l'adreça x amb a, on x és una ubicació de memòria i a és un valor, i retorneu el valor original a x.

de tal manera que si aquesta operació és executada per un procés en un sistema concurrent, cap altre procés no veurà mai un resultat intermedi.

Fetch-and-add es pot utilitzar per implementar estructures de control de concurrència com ara bloquejos mutex i semàfors.

Visió general

La motivació per tenir un fetch-and-add atòmic és que les operacions que apareixen en llenguatges de programació com

x = x + a

no són segurs en un sistema concurrent, on s'executen diversos processos o fils simultàniament (ja sigui en un sistema multiprocessador o programats de manera preventiva en alguns sistemes d'un sol nucli). El motiu és que aquesta operació s'implementa en realitat com a instruccions de màquines múltiples:

1. carregar x en un registre;
2. afegir a per registrar-se;
3. emmagatzema el valor del registre de nou a x.

Quan s'està fent un procésx = x + a i un altre està fentx = x + b alhora, hi ha una condició de carrera. Tots dos poden obtenir x_old i operar amb això, llavors tots dos emmagatzemen els seus resultats amb l'efecte que un sobreescriu l'altre i el valor emmagatzemat es converteix en x_old + a o x_old + b, no x_old + a + b com podria ser esperat.

En sistemes uniprocessadors sense suport de preempció del nucli, n'hi ha prou amb desactivar les interrupcions abans d'accedir a una secció crítica. Tanmateix, en sistemes multiprocessador (fins i tot amb les interrupcions desactivades) dos o més processadors podrien estar intentant accedir a la mateixa memòria alhora. La instrucció de buscar i afegir permet que qualsevol processador incrementi atòmicament un valor a la memòria, evitant aquestes col·lisions de processadors múltiples.

Maurice Herlihy (1991) va demostrar que buscar i afegir té un nombre de consens finit, en contrast amb l'operació de comparació i intercanvi. L'operació de buscar i afegir pot resoldre el problema de consens sense espera per a no més de dos processos concurrents.