Aller au contenu

Fetch-and-add

Un article de Wikipédia, l'encyclopédie libre.
Fetch-and-add
Présentation
Type

modifier - modifier le code - modifier WikidataDocumentation du modèle

Fetch And Add en informatique, désigne l'instruction d'extraction et d'ajout de processeur (FAA pour Fetch-And-Add) 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[modifier | modifier le code]

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ûrs 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 :

  1. Récupérez la valeur à l'emplacement x, disons xold, dans un registre ;
  2. ajouter a à xold dans le registre ;
  3. stocker 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 xold 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 xold + a ou xold + b, pas xold + 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[1].

La mise en œuvre[modifier | modifier le code]

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. 

 << atomique >>
function FetchAndAdd(address location, int inc) {
   int value := *location
   *location  := value + inc 
  return value
}

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: 

 record locktype {
    int ticketnumber
    int turn
 }
 procedure LockInit( locktype* lock ) {
    lock.ticketnumber := 0
    lock.turn := 0
 }
 procedure Lock( locktype* lock ) {
    int myturn := FetchAndIncrement( &lock.ticketnumber ) //must be atomic, since many threads might ask for a lock at the same time
    while lock.turn ≠ myturn 
        skip // spin until lock is acquired
 }
 procedure UnLock( locktype* lock ) {
    FetchAndIncrement( &lock.turn ) //this need not be atomic, since only the possessor of the lock will execute this
 }

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[modifier | modifier le code]

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

Implémentation x86[modifier | modifier le code]

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 : 

  static inline int fetch_and_add(int* variable, int value)
  {
      __asm__ volatile("lock; xaddl %0, %1"
      : "+r" (value), "+m" (*variable) // input+output
      : // No input-only
      : "memory"
      );
      return value;
  }

Histoire[modifier | modifier le code]

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.

Références[modifier | modifier le code]

  1. ↑ Herlihy, « Wait-free synchronization », ACM Trans. Program. Lang. Syst., vol. 13, no 1,‎ , p. 124–149 (DOI 10.1145/114005.102808, lire en ligne, consulté le )
  2. ↑ « std::atomic::fetch_add », cppreference.com (consulté le )
  3. ↑ « Intel Itanium Processor-specific Application Binary Interface (ABI) », Intel Corporation,
  4. ↑ « Atomic Builtins », Using the GNU Compiler Collection (GCC), Free Software Foundation,

Voir également[modifier | modifier le code]

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Fetch-and-add&oldid=215527480 ».