Fetch-and-add

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 x_old, dans un registre ;
2. ajouter a à x_old 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 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[1].

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

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] .

  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;
  }

• Test-and-set
• Test and Test-and-set
• Compare-and-swap
• Load-Link/Store-Conditional

• Portail de l’informatique