Question

Que voulez-vous dire par des instructions atomiques?

Comment devenir atomique ce qui suit?

test-and-set 

int TestAndSet(int *x){
   register int temp = *x;
   *x = 1;
   return temp;
}

Du point de vue du logiciel, si l'on ne veut pas utiliser les primitives de synchronisation non bloquante, comment peut-on assurer l'atomicité de l'enseignement? est-il possible que sur du matériel ou une optimisation de directive de niveau d'assemblage peut être utilisé?

Était-ce utile?

La solution

Certaines instructions de la machine sont intrinsèquement atomique -. Par exemple, la lecture et l'écriture de valeurs correctement alignées de la taille mot de processeur natif est atomique sur de nombreuses architectures

Cela signifie que les interruptions matérielles, les autres processeurs et hyper-fils ne peut pas interrompre la lecture ou de stocker et de lire ou écrire une valeur partielle dans le même emplacement.

Des choses plus compliquées telles que la lecture et l'écriture ensemble atomiquement peuvent être obtenues par des instructions machine atomiques explicites par exemple BLOCAGE cmpxchg sur x86.

Serrure et d'autres produits d'assemblage de haut niveau sont construites sur ces primitives atomiques, qui gardent en général qu'un seul mot du processeur.

Certains algorithmes concurrents intelligents peuvent être construits en utilisant seulement la lecture et l'écriture des pointeurs par exemple dans les listes chaînées partagées entre un seul lecteur et écrivain, ou avec un effort, plusieurs lecteurs et écrivains.

Autres conseils

atomique vient du grec ἄτομος (atomos) qui signifie "indivisible". (caveat: Je ne parle pas grec, alors peut-être qu'il est vraiment quelque chose d'autre, mais la plupart des anglophones citant étymologies interpréter la façon suivante: -.)

Dans le calcul, cela signifie que l'opération, ainsi, se . Il n'y a pas d'état intermédiaire qui est visible avant qu'elle ne se termine. Donc, si votre CPU est interrompu au matériel de service (IRQ), ou si une autre CPU est en train de lire la même mémoire, il ne touche pas le résultat, et ces opérations observera comme terminé ou pas commencé.

À titre d'exemple ... disons que vous vouliez définir une variable à quelque chose, mais seulement si elle n'a pas été réglée avant. Vous pourriez être enclin à le faire: 

if (foo == 0)
{
   foo = some_function();
}

Mais si cela est exécuté en parallèle? Il se pourrait que le programme va chercher foo, voir zéro, quant à lui 2 fil arrive et fait la même chose et définit la valeur à quelque chose. De retour dans le thread d'origine, le code pense toujours foo est égal à zéro, et la variable se voit assigner deux fois.

Pour les cas comme celui-ci, la CPU fournit des instructions qui peuvent faire la comparaison et l'attribution conditionnelle comme une entité atomique. Par conséquent, le test-and-set, comparer et-swap, et la charge liée / stockage conditionnel. Vous pouvez les utiliser pour implémenter des verrous (votre système d'exploitation et votre bibliothèque C a fait.) Ou vous pouvez écrire des algorithmes uniques qui comptent sur les primitives de faire quelque chose. (Il y a des trucs cool à faire ici, mais la plupart de simples mortels éviter ce par crainte de se tromper.)

atomicité est un concept clé lorsque vous avez une forme de traitement parallèle (y compris les différentes applications coopérant ou le partage des données) qui comprend des ressources partagées.

Le problème est bien illustré par un exemple. Disons que vous avez deux programmes qui veulent créer un fichier, mais uniquement si le fichier n'existe pas déjà. Tout peut créer le fichier à tout moment des deux programmes.

Si vous (je vais utiliser C car il est ce qui est dans votre exemple): 

 ...
 f = fopen ("SYNCFILE","r");
 if (f == NULL) {
   f = fopen ("SYNCFILE","w");
 }
 ...

vous ne pouvez pas être sûr que l'autre programme n'a pas créé le fichier entre votre ouverture pour la lecture et votre ouverture pour l'écriture.

Il n'y a aucun moyen que vous pouvez le faire vous-même, vous avez besoin d'aide du système d'exploitation, qui fournissent généralement des primitives de synchronisation à cet effet, ou un autre mécanisme qui est garanti d'être atomique (par exemple une base de données relationnelle où l'opération de verrouillage est atomique ou un mécanisme de niveau inférieur comme processeurs « essai et régler » instructions).

Voici quelques-unes de mes notes sur atomicité qui peuvent vous aider à comprendre le sens. Les notes sont des sources énumérées à la fin et je recommande la lecture de certains d'entre eux si vous avez besoin d'une explication plus approfondie plutôt que des balles sous forme de points que moi. S'il vous plaît signaler toute erreur afin que je puisse les corriger.

Définition:

  • Du mot grec qui signifie « non divisible en parties plus petites »
  • Une opération « atomique » est toujours observé à faire ou ne pas faire, mais jamais fait à mi-chemin.
  • Une opération atomique doit être entièrement réalisée ou non réalisée à tous.
  • Dans les scénarios multi-thread, une variable passe de non muté à muté directement, sans « à mi-chemin mutées » valeurs

Exemple 1: Opérations atomique

  • Considérons les nombres entiers suivants utilisés par différents threads: 

     int X = 2;
 int Y = 1;
 int Z = 0;

 Z = X;  //Thread 1

 X = Y;  //Thread 2

  • Dans l'exemple ci-dessus, deux fils font usage de X, Y, et Z

  • Chaque lecture et écriture sont atomiques
  • Les fils courront:
    • Si fil 1 gagne, alors Z = 2
    • Si le thread 2 victoires, alors Z = 1
    • Z sera certainement l'un de ces deux valeurs

Exemple 2: Non-atomique Opérations: ++ / - Opérations

  • Considérez l'incrément / expressions décrémentation: 

    i++;  //increment
i--;  //decrement

  • Les opérations se traduisent par:

    1. Lire i
    2. Augmentation / diminution de la valeur de lecture
    3. Ecrire la nouvelle valeur à i
  • Les opérations sont composées chacune de 3 opérations atomiques et ne sont pas eux-mêmes atomique
  • Deux tentatives pour incrémenter i sur des threads séparés pourrait entrelacer de telle sorte que l'un des incréments est perdu

Exemple 3 - Opérations non-atomique: Les valeurs supérieures à 4 octets

  • Considérez la struct immuable suivante: 
  struct MyLong
   {
       public readonly int low;
       public readonly int high;

       public MyLong(int low, int high)
       {
           this.low = low;
           this.high = high;
       }
   }

  • Nous créons des champs avec des valeurs spécifiques de type Mylong: 

    MyLong X = new MyLong(0xAAAA, 0xAAAA);   
MyLong Y = new MyLong(0xBBBB, 0xBBBB);     
MyLong Z = new MyLong(0xCCCC, 0xCCCC);

  • Nous modifions nos champs dans des threads séparés sans fil de sécurité: 

    X = Y; //Thread 1                                  
Y = X; //Thread 2

  • .NET, lors de la copie d'un type de valeur, le CLR ne remet pas un constructeur - il déplace les octets d'une opération atomique à la fois

  • En raison de cela, les opérations dans les deux fils sont maintenant quatre opérations atomiques
  • S'il n'y a pas de sécurité de fil appliquée, les données peuvent être corrompues

  • Considérez l'ordre d'exécution des opérations suivantes: 

    X.low = Y.low;      //Thread 1 - X = 0xAAAABBBB            
Y.low = Z.low;      //Thread 2 - Y = 0xCCCCBBBB              
Y.high = Z.high;    //Thread 2 - Y = 0xCCCCCCCC             
X.high = Y.high;    //Thread 1 - X = 0xCCCCBBBB   <-- corrupt value for X

  • Lecture et écriture des valeurs supérieures à 32 bits sur plusieurs fils sur un système d'exploitation 32 bits sans ajouter une sorte de verrouillage pour rendre l'opération atomique est susceptible d'entraîner des données corrompues comme ci-dessus

Opérations de processeur

  • Sur tous les processeurs modernes, vous pouvez supposer que les lectures et écritures des types natifs naturellement alignés sont atomiques à condition que:

    • 1: Le bus de mémoire est au moins aussi large que le type lecture ou l'écriture
    • 2: La CPU lit et écrit ces types en une seule transaction de bus, ce qui rend impossible pour d'autres fils de les voir dans un état de demi-rempli

  • x86 et X64 il n'y a aucune garantie que lit et écrit plus de huit octets sont atomiques

  • fournisseurs de Processeur définissent les opérations atomiques pour chaque processeur dans un Manuel de Software Developer
  • Dans les processeurs / systèmes unipolaires simples, il est possible d'utiliser des techniques de verrouillage standard pour empêcher les instructions CPU d'être interrompu, mais cela peut être inefficient
  • La désactivation des interruptions est une autre solution plus efficace, si possible
  • Dans multiprocesseurs / systèmes multi-cœurs, il est encore possible d'utiliser des verrous, mais simplement à l'aide d'une seule instruction ou la désactivation des interruptions ne garantit pas l'accès atomique
  • atomicité peut être réalisé en veillant à ce que les instructions utilisées assert le signal « LOCK » sur le bus pour empêcher d'autres processeurs dans le système d'accès à la mémoire en même temps

Les différences de langue

C #

  • C # garantit que les opérations sur tout type de valeur intégrée qui prend jusqu'à 4 octets sont atomiques
  • Opérations sur les types de valeurs qui prennent plus de quatre octets (double, long, etc.) ne sont pas garantis atomique
  • Les garanties CLI qui lit et écrit des variables de type de valeur qui sont la taille (ou moins) de la taille du pointeur naturel du processeur sont atomiques
    • Ex - en cours d'exécution C # sur un système d'exploitation 64 bits dans une version 64 bits du CLR exécute lit et écrit des doubles 64 bits et entiers longs atomiquement
  • Création d'opérations atomiques:
    • .NET provodes la classe Interlocked dans le cadre de l'espace de noms System.Threading
    • La classe Interlocked fournit des opérations atomiques telles que incrémentation, comparer, échange, etc. 
using System.Threading;             

int unsafeCount;                          
int safeCount;                           

unsafeCount++;                              
Interlocked.Increment(ref safeCount);

C ++

  • norme C ne garantit pas de comportement atomique
  • Toutes les opérations C / C sont présumés de non-atomique, sauf indication contraire par le compilateur ou le fournisseur du matériel - y compris l'attribution d'entiers de 32 bits
  • Création d'opérations atomiques:
    • La bibliothèque C ++ 11 concurrency comprend la - Bibliothèque des opérations atomique ()
    • La bibliothèque atomique fournit des types atomiques en tant que classe de modèle à utiliser avec tout type que vous voulez
    • Les opérations sur les types atomiques sont atomiques et donc thread-safe
  

struct AtomicCounter
  {

   std::atomic< int> value;   

   void increment(){                                    
       ++value;                                
   }           

   void decrement(){                                         
       --value;                                                 
   }

   int get(){                                             
       return value.load();                                    
   }
     

}

Java

  • Java garantit que les opérations sur tout type de valeur intégrée qui prend jusqu'à 4 octets sont atomiques
  • Affectations des positions longues et doubles volatils sont également garantis à être atomique
  • Java fournit une petite boîte à outils de classes qui prennent en charge la programmation de thread-safe sans blocage sur des variables individuelles par java.util.concurrent.atomic
  • Cela permet un fonctionnement sans verrouillage atomiques basées sur des primitives matérielles atomiques de bas niveau tels que comparer et-swap (CAS) - aussi appelé comparer et définir:
    • formulaire de CAS - compareAndSet booléen (expectedValue, UpdateValue);
      • Cette méthode définit atomiquement une variable à la UpdateValue si elle détient actuellement le expectedValue - rapports en cas de succès 
import java.util.concurrent.atomic.AtomicInteger;

public class Counter
{
     private AtomicInteger value= new AtomicInteger();

     public int increment(){
         return value.incrementAndGet();  
     }

     public int getValue(){
         return value.get();
     }
}

Sources http://www.evernote.com/shard / s10 / sh / c2735e95-85ae-4d8c-a615-52aadc305335 / 99de177ac05dc8635fb42e4e6121f1d2

atomicité ne peut être garantie par le système d'exploitation. Le système d'exploitation utilise les fonctionnalités du processeur sous-jacent pour y parvenir.

créer donc votre propre fonction est impossible test-and-set. (Bien que je ne suis pas sûr si l'on pouvait utiliser un extrait de asm en ligne et utiliser directement le mnémonique test-and-set (Peut-être que cette déclaration ne peut être fait avec priviliges OS))

EDIT: Selon les commentaires ci-dessous ce poste, ce qui rend votre propre fonction « bittestandset » à l'aide d'une directive ASM est possible directement (sur x86 intel). Cependant, si ces astuces fonctionnent aussi sur d'autres processeurs ne sont pas claires.

Je maintiens mon point: si vous voulez faire des choses atmoic, utilisez les fonctions OS et ne le faites pas vous-même

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top