# Fetch-and-add

Fetch And Add (FAA pour Fetch-And-Add) en informatique, désigne l'instruction d'extraction et d'ajout incrémentant atomiquement le contenu d'un emplacement de mémoire par une valeur spécifiée.
Autrement dit, l'instruction d'extraction et d'ajout effectue l'opération incrémentant la valeur à l'adresse x par a (où x est une adresse de mémoire et a est une valeur quelconque), puis retourne la valeur d'origine de l'adresse x, de telle sorte que si cette opération est exécutée par un processus dans un système simultané, aucun autre processus ne verra jamais un résultat intermédiaire.
L'instruction d'extraction et d'ajout peut être utilisée pour implémenter des structures de contrôle de concurrence telles que des verrous d'exclusion mutuelle et des sémaphores.

## Présentation

La motivation pour avoir une instruction d'extraction et d'ajout atomique est que les opérations qui apparaissent dans les langages de programmation comme x = x + a ne sont pas sûres dans un système simultané, où plusieurs processus ou threads s'exécutent simultanément (soit dans un système multiprocesseur, soit planifié de manière préventive sur certains systèmes monocœur). La raison en est qu'une telle opération est en fait implémentée comme plusieurs instructions machine :
* récupération de la valeur à l'emplacement x, disons x$_{old}$, dans un registre ;
* ajout de a à x$_{old}$ dans le registre ;
* stockage de la nouvelle valeur du registre dans x.
Lorsqu'un processus est en cours x = x + a et un autre fait x = x + b simultanément, il y a une situation de compétition. Ils peuvent tous les deux récupérer x$_{old}$ et opérer sur cela, puis tous les deux stockent leurs résultats avec l'effet que l'un écrase l'autre et la valeur stockée devient soit x$_{old}$ + a ou x$_{old}$ + b, pas x$_{old}$ + a + b comme cela pourrait être attendu.
Dans les systèmes à processeur unique sans prise en charge de la préemption du noyau, il suffit de désactiver les interruptions avant d'accéder à une section critique.
Cependant, dans les systèmes multiprocesseurs (même avec les interruptions désactivées), deux processeurs ou plus peuvent tenter d'accéder à la même mémoire en même temps. L'instruction d'extraction et d'ajout permet à tout processeur d'incrémenter atomiquement une valeur en mémoire, empêchant de telles collisions de processeurs multiples.
Maurice Herlihy (1991) a prouvé que l'instruction d'extraction et d'ajout a un nombre de consensus fini, contrairement à l'opération de comparaison et d'échange. L'opération d'extraction et d'ajout peut résoudre le problème de consensus sans attente pour pas plus de deux processus simultanés.

## La mise en œuvre

L'instruction d'extraction et d'ajout se comporte comme la fonction suivante. Fondamentalement, la fonction entière est exécutée de manière atomique : aucun processus ne peut interrompre la fonction en cours d'exécution et donc voir un état qui n'existe que pendant l'exécution de la fonction. Le code suivant ne sert qu'à aider à expliquer le comportement de l'instruction ; l'atomicité nécessite un support matériel explicite et ne peut donc pas être implémentée comme une simple fonction de haut niveau.
Pour implémenter un verrou d'exclusion mutuelle, nous définissons l'opération FetchAndIncrement, qui est équivalente à FetchAndAdd avec inc=1.
Avec cette opération, un verrou d'exclusion mutuelle peut être implémenté en utilisant l'algorithme de verrouillage de ticket comme:
Ces routines fournissent un verrou d'exclusion mutuelle lorsque les conditions suivantes sont remplies:
* La structure de données Locktype est initialisée avec la fonction LockInit avant utilisation
* Le nombre de tâches en attente de verrouillage ne dépasse à aucun moment INT_MAX
* Le type de données entier utilisé dans les valeurs de verrouillage peut «boucler» lorsqu'il est incrémenté en continu

## Support matériel et logiciel

Une fonction atomique fetch_add apparaît dans la norme C ++ 11 . Elle est disponible en tant qu'extension propriétaire de C dans la spécification Itanium ABI, et (avec la même syntaxe) dans GCC .

### Implémentation x86

Dans l'architecture x86, l'instruction ADD avec l'opérande de destination spécifiant un emplacement mémoire est une instruction d'extraction et d'ajout qui existe depuis le 8086 (elle n'était simplement pas appelée ainsi à l'époque), et avec le préfixe LOCK, est atomique sur plusieurs processeurs. Cependant, elle n'a pas pu retourner la valeur d'origine de l'emplacement de mémoire (bien qu'elle ait renvoyé quelques drapeaux) jusqu'à ce que le 486 introduise l'instruction XADD.
Voici une implémentation C pour le compilateur GCC, pour les plates-formes Intel x86 32 et 64 bits, basée sur la syntaxe ASM étendue :

### Histoire

L'instruction d'extraction et d'ajout a été introduite par le projet Ultracomputer, qui a également produit un multiprocesseur prenant en charge cette instruction et contenant des commutateurs VLSI personnalisés capables de combiner des références de mémoire simultanées (y compris l'instruction d'extraction et d'ajout) pour les empêcher de sérialiser au module de mémoire contenant l'opérande de destination.