Tout d'abord, introduisons des serrures optimistes et des serrures pessimistes:
Lock pessimiste: assumez toujours le pire des cas. Chaque fois que je vais obtenir les données, je pense que d'autres les modifieront, donc je les verrouillerai chaque fois que j'obtiens les données, afin que d'autres les bloquent jusqu'à ce qu'elle obtienne le verrou. Les bases de données relationnelles traditionnelles utilisent de nombreux mécanismes de verrouillage de ce type, tels que les verrous en ligne, les verrous de table, etc., lisent les verrous, les serrures d'écriture, etc., qui sont verrouillées avant de faire des opérations. Par exemple, l'implémentation du mot clé synchronisé par mot-clé synchronisé dans Java est également un verrou pessimiste.
Verrouillage optimiste: Comme son nom l'indique, cela signifie très optimiste. Chaque fois que je vais obtenir les données, je pense que d'autres ne le modifieront pas, donc je ne les verrouillerai pas. Cependant, lors de la mise à jour, je jugerai si d'autres ont mis à jour les données au cours de cette période et peuvent utiliser le numéro de version et d'autres mécanismes. Les verrous optimistes conviennent aux types d'applications multi-lectures, ce qui peut améliorer le débit. Par exemple, la base de données fournit une serrure optimiste similaire au mécanisme écrite_condition, mais elles sont en fait toutes fournies par des verrous optimistes. En Java, la classe variable atomique sous le package java.util.concurrent.atomic est implémentée par CAS en utilisant un verrou optimiste.
Une implémentation de Lock-Cas optimistes (comparer et échanger):
Problèmes de verrouillage:
Avant JDK1.5, Java s'est appuyé sur des mots clés synchronisés pour assurer la synchronisation. De cette façon, en utilisant un protocole de verrouillage cohérent pour coordonner l'accès à l'état partagé, il peut s'assurer que peu importe le fil qui contient le verrouillage des variables partagées, il utilise une méthode exclusive pour accéder à ces variables. Ceci est une sorte de serrure exclusive. Le verrouillage exclusif est en fait une sorte de serrure pessimiste, il peut donc être dit que synchronisé est une serrure pessimiste.
Le mécanisme de verrouillage pessimiste a les problèmes suivants:
1. Sous la concurrence multi-thread, l'ajout et la libération de verrous entraîneront davantage de retards de commutation de contexte et de planification, causant des problèmes de performance.
2. Un fil tenant une serrure provoquera tous les autres threads qui nécessitent que cette serrure soit suspendue.
3. Si un fil avec une priorité élevée attend un fil avec une faible priorité pour libérer le verrou, il entraînera une inversion prioritaire, provoquant des risques de performance.
Par rapport à ces problèmes de serrures pessimistes, une autre serrure plus efficace est les verrous optimistes. En fait, le verrouillage optimiste est: chaque fois que vous n’ajoutez pas de verrouillage, mais vous effectuez une opération en supposant qu’il n’y a pas de conflit simultané. Si le conflit simultané échoue, réessayez jusqu'à ce qu'il réussisse.
Verrouillage optimiste:
Le verrouillage optimiste a été mentionné ci-dessus, mais c'est en fait une sorte de pensée. Par rapport aux serrures pessimistes, les verrous optimistes supposent que les données ne provoqueront généralement pas de conflits simultanés, donc lorsque les données sont soumises et mises à jour, il détectera officiellement si les données ont des conflits simultanés. Si un conflit simultané est trouvé, les informations erronées de l'utilisateur seront retournées et l'utilisateur décide de la façon de le faire.
Le concept de verrouillage optimiste mentionné ci-dessus a en fait expliqué ses détails de mise en œuvre spécifiques: il comprend principalement deux étapes: la détection des conflits et la mise à jour des données. L'une des méthodes de mise en œuvre typiques est la comparaison et l'échange (CAS).
CAS:
CAS est une technologie de verrouillage optimiste. Lorsque plusieurs threads essaient d'utiliser CAS pour mettre à jour la même variable en même temps, un seul des threads peut mettre à jour la valeur de la variable, tandis que les autres threads échouent. Le fil qui échoue ne sera pas suspendu, mais on dira que cette concurrence a échoué et peut réessayer.
L'opération CAS contient trois opérandes - l'emplacement de la mémoire (v) qui doit être lu et écrit, la valeur d'origine attendue (a) pour la comparaison et la nouvelle valeur (b) à écrire. Si la valeur de la position de mémoire V correspond à la valeur d'origine attendue A, le processeur mettra automatiquement à jour la valeur de position vers la nouvelle valeur B. Sinon, le processeur ne fera rien. Dans les deux cas, il renvoie la valeur de cet emplacement avant la directive CAS. (Dans certains cas particuliers de CAS, seulement si le CAS réussit ou non, sans extraire la valeur actuelle.) CAS indique efficacement que "je pense que la position V devrait contenir la valeur A Ceci est en fait le même que le principe de vérification des conflits + mise à jour des données des verrous optimistes.
Permettez-moi de souligner ici que le verrouillage optimiste est une sorte de pensée. CAS est une façon de réaliser cette idée.
Support Java pour CAS:
Le nouveau java.util.concurrent (JUC) dans JDK1.5 est construit sur CAS. Par rapport aux algorithmes de blocage tels que synchronisés, le CAS est une implémentation courante d'algorithmes non bloquants. Par conséquent, le juc a considérablement amélioré ses performances.
Prenez AtomicInteger dans java.util.concurrent comme exemple pour voir comment assurer la sécurité des filetages sans utiliser de verrous. Nous comprenons principalement la méthode GetAndincrement, ce qui équivaut à l'opération ++ I.
La classe publique AtomicInteger étend le nombre implémente Java.io.Serializable {private volatile int Value; public final int get () {return Value; } public final int getandincrement () {for (;;) {int courant = get (); int next = courant + 1; if (comparabledset (courant, suivant)) Retour courant; }} public final boolean compaReANDSet (int attende, int update) {return usAve.compathendswapint (this, valuoffset, attend, update); }}Dans le mécanisme sans verrous, la valeur du champ doit être utilisée pour garantir que les données entre les threads sont la visibilité. De cette façon, vous pouvez lire directement lorsque vous obtenez la valeur d'une variable. Voyons alors comment ++ je suis fait.
GetAndIncrement utilise l'opération CAS, et chaque fois que vous lisez les données de la mémoire, puis effectuez l'opération CAS sur ces données et le résultat après +1. En cas de succès, le résultat sera retourné, sinon réessayer jusqu'à succès.
ComparendSet utilise JNI (interface native Java) pour terminer le fonctionnement des instructions du CPU:
Public Final Boolean ComparendSet (int attend, int update) {return usare.compareAndWapint (this, valuoffset, attend, update); }où dis ..CompareAndSwapint (ceci, ValueOffSet, attendez, mise à jour); est similaire à la logique suivante:
if (this == attend) {this = update return true; } else {return false; }Alors, comment comparer ceci == attendre, remplacer ce = mise à jour, comparaisondwapint pour réaliser l'atomicité de ces deux étapes? Se référer aux principes de la CAS
Principe CAS:
CAS est implémenté en appelant le code JNI. ComparandSwapint est implémenté en utilisant C pour appeler les instructions du processeur sous-jacentes.
Ce qui suit explique le principe de mise en œuvre des CAS de l'analyse du CPU plus couramment utilisé (Intel x86).
Voici le code source de la méthode comparablewapint () de la classe Sun.Misc.unsafe:
Public Final Native Boolean CompareAndSwapint (objet O, décalage long, int attendu, int x);
Vous pouvez voir qu'il s'agit d'un appel de méthode local. Le code C ++ que cette méthode locale appelle dans le JDK est:
#Define Lock_IF_MP (MP) __ASM CMMP MP, 0 / __ASM JE L0 / __ASM _EMIT 0XF0 / __ASM L0: Inline Jint Atomic :: CMPXCHG (Jint Exchange_Value, volatile jint * dest, jint compare_value) {// alternative pour interlockéChatChatCar os :: is_mp (); __asm {mov edx, dest mov ecx, exchange_value mov eax, compare_value lock_if_mp (mp) cmmpxchg dword ptr [edx], ecx}}Comme indiqué dans le code source ci-dessus, le programme décidera d'ajouter un préfixe de verrouillage à l'instruction CMMPXCHG en fonction du type du processeur actuel. Si le programme s'exécute sur un multiprocesseur, ajoutez le préfixe de verrouillage à l'instruction CMMPXCHG. Au contraire, si le programme s'exécute sur un seul processeur, le préfixe de verrouillage est omis (le processeur unique lui-même maintient la cohérence séquentielle au sein du processeur unique et ne nécessite pas l'effet de barrière de mémoire fournis par le préfixe de verrouillage).
Cas Inconvénients:
1. Questions ABA:
Par exemple, si un thread sort a de la position de mémoire V, alors un autre thread deux sort également A de la mémoire, et deux effectue certaines opérations et devient B, puis deux tourne les données en position V A. À l'heure actuelle, le thread One effectue l'opération CAS et constate que A est toujours en mémoire, puis on fonctionne avec succès. Bien que l'opération CAS soit réussie, il peut y avoir des problèmes cachés. Comme indiqué ci-dessous:
Il y a une pile implémentée avec une liste liée à sens unique, le haut de la pile étant A. Pour le moment, Thread T1 sait déjà que A.Next est B, puis espère remplacer le haut de la pile par B par Cas:
Head.CompareAndset (A, B);
Avant que T1 exécute l'instruction ci-dessus, le thread T2 intervient, met A et B hors de la pile, puis Pushd, C et A. Pour le moment, la structure de la pile est la suivante, et l'objet B est à l'état libre à l'heure actuelle:
À l'heure actuelle, c'est le tour du fil T1 d'effectuer l'opération CAS. La détection a révélé que le haut de la pile est toujours A, donc Cas réussit, et le haut de la pile devient B, mais en fait B.Next est nul, donc la situation à ce moment devient:
Il n'y a qu'un seul élément B dans la pile, et la liste liée composée de C et D n'existe plus dans la pile. C et D sont jetés sans raison.
À partir de Java 1.5, le package atomique de JDK fournit une classe atomicstampeDeDerence pour résoudre le problème ABA. La méthode de comparaison de cette classe est de vérifier d'abord si la référence actuelle est égale à la référence attendue et si l'indicateur actuel est égal à l'indicateur attendu. Si tous sont égaux, la référence et la valeur de l'indicateur sont définies sur la valeur mise à jour donnée de manière atomique.
Public Boolean ComparanDset (v attenduReference, // Référence attendue v NewReference, // Référence mise à jour int attendstamp, // inducteur attendu int newstamp // indicateur mis à jour)
Code d'application réel:
ATOMICSTAMPEDRADREFENDE STATIQUE PRIVÉ <Integer> ATOMICSTAMPEDREF = NOUVEAU ATOMICSTAMPEDREFERFEFER <Integer> (100, 0); ......... atomicstampedref.comparparedset (100, 101, tampon, tampon + 1);
2. Temps de cycle long et frais généraux:
Spin Cas (s'il échoue, il sera exécuté à vélo jusqu'à ce qu'il réussit) s'il échoue pendant longtemps, il apportera une grande exécution sur la CPU. Si le JVM peut prendre en charge les instructions de pause fournies par le processeur, l'efficacité sera améliorée dans une certaine mesure. Les instructions de pause ont deux fonctions. Tout d'abord, il peut retarder les instructions d'exécution des pipelines (De-Pipeline) afin que le CPU ne consomme pas trop de ressources d'exécution. Le temps de retard dépend de la version d'implémentation spécifique. Sur certains processeurs, le temps de retard est nul. Deuxièmement, il peut éviter la rinçage du pipeline du CPU causée par la violation de l'ordre mémoire lors de la sortie de la boucle, améliorant ainsi l'efficacité d'exécution du CPU.
3. Seules les opérations atomiques d'une variable partagée peuvent être garanties:
Lorsque vous effectuez des opérations sur une variable partagée, nous pouvons utiliser la méthode CAS cyclique pour garantir les opérations atomiques. Cependant, lors de l'utilisation de plusieurs variables partagées, le CAS cyclique ne peut garantir l'atomicité de l'opération. Pour le moment, vous pouvez utiliser des verrous, ou il y a une astuce, qui est de fusionner plusieurs variables partagées en une variable partagée à utiliser. Par exemple, il existe deux variables partagées i = 2, j = a, fusionner ij = 2a, puis utiliser CAS pour faire fonctionner ij. À partir de Java 1.5, JDK fournit la classe atomicréférente pour assurer l'atomicité entre les objets référencés. Vous pouvez mettre plusieurs variables dans un seul objet pour l'opération CAS.
CAS et scénarios d'utilisation synchronisés:
1. Pour les situations où il y a moins de concurrence sur les ressources (conflit de threads légers), en utilisant le verrouillage de synchronisation synchronisé pour le blocage des threads et les opérations de commutation et de commutation entre les états du noyau à l'état utilisateur est un gaspillage supplémentaire de ressources CPU; Bien que le CAS soit implémenté en fonction du matériel, il n'a pas besoin de saisir le noyau, n'a pas besoin de changer de threads, et les chances de faire fonctionner des spins sont moindres, donc des performances plus élevées peuvent être obtenues.
2. Pour les situations où la concurrence des ressources est grave (grave conflit de threads), la probabilité de rotation CAS est relativement élevée, ce qui gaspille plus de ressources CPU et est moins efficace que synchronisé.
Supplément: synchronisé a été amélioré et optimisé après JDK1.6. L'implémentation sous-jacente de synchronisée repose principalement sur la file d'attente sans serrure. L'idée de base est de bloquer après la rotation, de continuer à rivaliser pour les verrous après le changement de compétition, de sacrifier légèrement l'équité, mais d'obtenir un débit élevé. Lorsqu'il y a moins de conflits de fil, des performances similaires peuvent être obtenues; Lorsqu'il y a de sérieux conflits de fil, les performances sont beaucoup plus élevées que celles des CAS.
Implémentation du package simultané:
Étant donné que Java's CAS a à la fois une sémantique de mémoire pour une lecture volatile et une écriture volatile, il y a maintenant quatre façons de communiquer entre les threads Java:
1. Filetage A écrit la variable volatile, puis le thread B lit la variable volatile.
2. Le thread a écrit la variable volatile, puis le thread B utilise CAS pour mettre à jour la variable volatile.
3. Le thread A utilise CAS pour mettre à jour une variable volatile, puis le thread B utilise CAS pour mettre à jour cette variable volatile.
4. Le thread A utilise CAS pour mettre à jour une variable volatile, puis le thread B lit cette variable volatile.
Le CAS de Java utilise des instructions atomiques efficaces au niveau de la machine fournies sur les processeurs modernes, qui effectuent des opérations de lecture-changement sur la mémoire atomiquement, qui est la clé pour atteindre la synchronisation dans les multiprocesseurs (essentiellement, une machine informatique qui peut prendre en charge les instructions de l'écriture de lecture atomique est une machine équivalente asynchrones qui prend en charge séquentiellement les machines Tuture, ainsi que la machine moderne supportera les atosocesss séquentiellement des machines TURING, SO MODERNOCORS ATOMIQUE SÉCULATE SÉCULATE TURING MACHINES, SO ASYNCHONNEUX MACHINE PERSONNEMENTS ATOCULATE RÉCLUMATE TOUR qui peut effectuer des opérations atomiques à l'écriture de changement de lecture sur la mémoire). Dans le même temps, la lecture / écriture et le CAS de la variable volatile peuvent réaliser la communication entre les threads. L'intégration de ces fonctionnalités constitue la pierre angulaire de la mise en œuvre de l'ensemble du package simultané. Si nous analysons soigneusement la mise en œuvre du code source du package simultané, nous trouverons un modèle de mise en œuvre générale:
1. Premièrement, déclarez que la variable partagée est volatile;
2. Ensuite, utilisez la mise à jour de la condition atomique des CAS pour atteindre la synchronisation entre les threads;
3. En même temps, la communication entre les threads est réalisée en utilisant la lecture / l'écriture de volatile et la sémantique mémoire de la lecture et de l'écriture volatiles en CAS.
Les AQ, les structures de données non bloquantes et les classes de variables atomiques (classes dans le package java.util.concurrent.atomic), les classes de base de ces packages simultanés sont implémentées à l'aide de ce modèle, et les classes de haut niveau dans le package simultané reposent sur ces classes de base à mettre en œuvre. Dans une perspective générale, le diagramme de mise en œuvre du package simultané est le suivant:
CAS (affectation d'objets dans le tas):
Java appelle new object() pour créer un objet, qui sera alloué au tas JVM. Alors, comment cet objet est-il enregistré dans le tas?
Tout d'abord, lorsque new object() est exécuté, la quantité d'espace dont cet objet a besoin est réellement déterminé, car les différents types de données en Java et la quantité d'espace qu'ils prennent sont corrigées (si vous n'êtes pas clair sur son principe, veuillez le Google vous-même). Ensuite, le travail suivant consiste à trouver un morceau d'espace dans le tas pour stocker cet objet.
Dans le cas d'un seul thread, il existe généralement deux stratégies d'allocation:
1. Collision du pointeur: Ceci est généralement applicable à la mémoire absolument régulière (si la mémoire est régulière dépend de la stratégie de recyclage de la mémoire). La tâche d'attribution de l'espace est simplement de déplacer le pointeur comme la distance de la taille de l'objet sur le côté de la mémoire libre.
2. Liste gratuite: Cela convient à la mémoire non régulière. Dans ce cas, le JVM conservera une liste de mémoire pour enregistrer les zones de mémoire gratuites et la taille. Lorsque vous allouez de l'espace aux objets, accédez à la liste gratuite pour interroger la zone appropriée, puis allouer.
Cependant, il est impossible pour le JVM de fonctionner en un seul état fileté tout le temps, donc l'efficacité est trop mauvaise. Puisqu'il n'est pas une opération atomique lors de l'allocation de la mémoire à un autre objet, au moins les étapes suivantes sont requises: trouver une liste gratuite, allouer la mémoire, modifier une liste gratuite, etc., qui n'est pas sûre. Il existe également deux stratégies pour résoudre les problèmes de sécurité pendant la concurrence:
1. CAS: En fait, la machine virtuelle utilise CAS pour assurer l'atomicité de l'opération de mise à jour en ne réessayant pas, et le principe est le même que celle mentionnée ci-dessus.
2. TLAB: Si CAS est utilisé, il aura en fait un impact sur les performances, de sorte que le JVM a proposé une stratégie d'optimisation plus avancée: chaque fil pré-alloue un petit morceau de mémoire dans le tas Java, appelé tampon d'allocation de fil local (TLAB). Lorsque le thread doit allouer de la mémoire à l'intérieur, il suffit de l'allouer directement sur TLAB, en évitant les conflits de fil. Ce n'est que lorsque la mémoire tampon est utilisée et doit réaffecter la mémoire que l'opération CAS sera effectuée pour allouer un espace mémoire plus grand.
Si la machine virtuelle utilise TLAB peut être configurée via -XX:+/-UseTLAB (JDK5 et les versions ultérieures sont activées par défaut).
Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.