Écriture d'un compteur modulaire thread safe en Java

Je dirais qu'à part l'emballage, c'est bien. Lorsque deux appels de méthode sont effectivement simultanés, vous ne pouvez pas garantir ce qui se produira en premier.

Le code est toujours atomique, car quoi qu'il arrive en premier, ils ne peuvent pas interférer les uns avec les autres.

Fondamentalement, si vous avez un code qui essaie de s'appuyer sur l'ordre des appels simultanés, vous avez déjà une condition de concurrence. Même si dans le code appelant, un thread arrive au début de l'appel next() avant le d'autre part, vous pouvez l'imaginer arriver à la fin de sa tranche de temps avant qu'il n'obtienne dans l'appel next()-permettant au deuxième thread d'y entrer.

Si l'appel next()avait un autre effet secondaire - par exemple, il imprimait "En commençant par thread (thread id)" et alors renvoyait la valeur suivante, alors ce ne serait pas atomique; vous auriez une différence de comportement observable. Comme il est, je pense que vous êtes beaux.

Une chose à penser en ce qui concerne l'emballage: vous pouvez faire le le compteur dure beaucoup plus longtemps avant d'emballer si vous utilisez un AtomicLong :)

EDIT: Je viens de penser à un moyen soigné d'éviter le problème d'emballage dans tous les scénarios réalistes:

• Définir un grand nombre M * 100000 (ou autre). Cela devrait être choisi pour être assez grand pour ne pas être touché trop souvent (car cela réduira les performances) mais assez petit pour que vous puissiez vous attendre à ce que la boucle de "fixation" ci-dessous soit efficace avant que trop de threads ne soient ajoutés à la tique pour la provoquer envelopper.

• Lorsque vous récupérez la valeur avec getAndIncrement(), vérifiez si elle est supérieure à ce nombre. Si c'est le cas, entrez dans une "boucle de réduction" qui ressemblerait à ceci:

  long tmp;
  while ((tmp = tick.get()) > SAFETY_VALUE))
  {
      long newValue = tmp - SAFETY_VALUE;
      tick.compareAndSet(tmp, newValue);
  }
  

Fondamentalement, cela dit: "Nous devons ramener la valeur dans une plage de sécurité, en décrémentant un multiple du module" (afin qu'il ne change pas la valeur mod M). Il le fait dans une boucle serrée, travaillant essentiellement sur ce que devrait être la nouvelle valeur, mais ne faisant qu'un changement si rien d'autre a changé la valeur entre les deux.

Cela pourrait causer un problème dans des conditions pathologiques où vous aviez un nombre infini de threads essayant d'incrémenter la valeur, mais je pense que ce serait réaliste.

Concernant le problème de l'atomicité: je ne crois pas qu'il soit possible pour le Compteur lui-même de fournir un comportement pour garantir la sémantique que vous impliquez.

Je pense que nous avons un thread qui fait du travail

  A - get some stuff (for example receive a message)
  B - prepare to call Counter
  C - Enter Counter <=== counter code is now in control
  D - Increment
  E - return from Counter <==== just about to leave counter's control
  F - application continues

La médiation que vous recherchez concerne l'ordre d'identité de" charge utile " établi à A.

Par exemple, deux threads lisent chacun un message - un lit X, un lit Y. Vous voulez vous assurer que X obtient le premier incrément de compteur, Y obtient le second, même bien que les deux threads s'exécutent simultanément, et peuvent être planifiés arbitrairement sur 1 ou plusieurs PROCESSEURS.

Par conséquent, tout ordre doit être imposé à travers toutes les étapes A-F, et appliqué par un certain countrol de concurrence en dehors du Compteur. Par exemple:

pre-A - Get a lock on Counter (or other lock)
  A - get some stuff (for example receive a message)
  B - prepare to call Counter
  C - Enter Counter <=== counter code is now in control
  D - Increment
  E - return from Counter <==== just about to leave counter's control
  F - application continues
post- F - release lock

Maintenant, nous avons une garantie au détriment d'un certain parallélisme; les threads s'attendent les uns aux autres. Lorsque la commande stricte est une exigence, cela a tendance à limiter la concurrence; c'est un problème courant dans la messagerie système.

Concernant la question de la liste. La sécurité des threads doit être considérée en termes de garanties d'interface. Il y a une exigence minimale absolue: la liste doit être résiliente face à un accès simultané à partir de plusieurs threads. Par exemple, nous pourrions imaginer une liste dangereuse qui pourrait bloquer ou laisser la liste mal liée afin que toute itération boucle pour toujours. La prochaine exigence est que nous devrions spécifier le comportement lorsque deux threads accèdent en même temps. Il y a beaucoup de cas, voici quelques -

a). Two threads attempt to add
b). One thread adds item with key "X", another attempts to delete the item with key "X"
C). One thread is iterating while a second thread is adding

À condition que l'implémentation ait un comportement clairement défini dans chaque cas, elle est thread-safe. La question intéressante est de savoir quels comportements sont pratiques.

Nous pouvons simplement synchroniser sur la liste, et donc facilement donner un comportement bien compris pour a et b. Cependant, cela a un coût en termes de parallélisme. Et je fais valoir que cela n'avait aucune valeur de le faire, car vous devez toujours vous synchroniser à un niveau supérieur pour obtenir une sémantique utile. Je voudrais donc avoir un spécification d'interface disant "Ajoute arriver dans n'importe quel ordre".

En ce qui concerne l'itération - c'est un problème difficile, jetez un oeil à ce que les collections Java promettent: pas beaucoup!

Cet article , qui traite des collections Java peut être intéressant.

Atomique (comme je le comprends) se réfère au fait qu'un état intermédiaire n'est pas observable de l'extérieur. atomicInteger.incrementAndGet() est atomique, tandis que return this.intField++; n'est pas, dans le sens que, dans l'ancien, vous ne pouvez pas observer un état dans lequel l'entier a été incrémenté, mais n'a pas encore été rendu.

Quant à thread-safety, les auteurs de la concurrence Java en pratique fournissent une définition dans leur livre:

Une classe est thread-safe si elle se comporte correctement lors de l' accessible à partir de plusieurs threads, quelle que soit la planification ou l'entrelacement de l'exécution de ces threads par le runtime environnement, et sans supplément synchronisation ou autre coordination de la part du code appelant.

(Mon opinion personnelle suit)

Maintenant, si nous avons la liste mis à jour avec succès avec deux éléments ajouté, mais le deuxième vient avant le premier, qui est à la fin, est ce " fil coffre-fort"?

Si thread1 a entré le jeu d'entrées de l'objet mutex (Dans le cas des Collections.synchronizedList() la liste elle-même) avant thread2, il est garanti que first est positionné avant second dans la liste après la mise à jour. En effet, le mot-clé synchronized utilise fair lock. Celui qui est assis devant la file d'attente peut faire des choses en premier. Les verrous équitables peuvent être assez chers et vous pouvez également avoir des verrous injustes en java (grâce à l'utilisation de java.util.utilitaires simultanés). Si vous voulez le faire, ensuite, il n'y a aucune garantie.

Cependant, la plate-forme java n'est pas une plate-forme informatique en temps réel, vous ne pouvez donc pas prédire combien de temps un morceau de code nécessite pour s'exécuter. Ce qui signifie que si vous voulez first avant second, vous devez le garantir explicitement en java. Il est impossible de l'assurer en "contrôlant le timing" de l'appel.

Maintenant, qu'est-ce qui est sûr ou dangereux ici? Je pense que cela dépend simplement de ce qui doit être fait. Si vous avez juste besoin d'éviter la liste corrompu et peu importe si first est le premier ou second est le premier dans la liste, pour que l'application fonctionne correctement, il suffit d'éviter la corruption pour établir la sécurité des threads. Si ce n'est pas le cas, ce n'est pas le cas.

Donc, je pense que la sécurité des threads ne peut pas être définie en l'absence de la fonctionnalité particulière que nous essayons d'atteindre.

Le célèbre {[10] }n'utilise aucun "mécanisme de synchronisation" particulier fourni en java, mais il est toujours thread safe car on pouvez l'utiliser en toute sécurité dans leur propre application. sans se soucier de la synchronisation, etc.

Chaîne célèbre.hashCode () astuce:

int hash = 0;

int hashCode(){
    int hash = this.hash;
    if(hash==0){
        hash = this.hash = calcHash();
    }
    return hash;
 }