Pouvez-vous expliquer pourquoi plusieurs threads ont besoin de verrous sur un processeur monocœur?

Supposons que ces threads s'exécutent dans un processeur unique. En tant que processeur, exécutez une seule instruction en un cycle. Cela dit, même en pensant qu'ils partagent la ressource CPU. mais l'ordinateur assure qu'une seule fois une instruction. Le verrou n'est-il donc pas nécessaire pour la lecture multiple?

Ceci est mieux illustré par un exemple.

Supposons que nous ayons une tâche simple que nous voulons effectuer plusieurs fois en parallèle et que nous voulons garder une trace globale du nombre de fois que la tâche a été exécutée, par exemple, compter les hits sur une page Web.

Lorsque chaque thread arrive au point où il incrémente le nombre, son exécution ressemble à ceci:

1. Lire le nombre de hits de la mémoire dans un registre de processeur
2. Augmentez ce nombre.
3. Réécrivez ce numéro en mémoire

N'oubliez pas que chaque thread peut se suspendre à tout moment de ce processus. Donc, si le thread A exécute l'étape 1, puis est suspendu, suivi par le thread B effectuant les trois étapes, lorsque le thread A reprend, ses registres auront le mauvais nombre de hits: ses registres seront restaurés, il incrémentera heureusement l'ancien numéro de hits et stocker ce nombre incrémenté.

En outre, un nombre illimité d'autres threads ont pu s'exécuter pendant la période de suspension du thread A, de sorte que le nombre de threads d'écriture A à la fin peut être bien inférieur au nombre correct.

Pour cette raison, il est nécessaire de s'assurer que si un thread exécute l'étape 1, il doit effectuer l'étape 3 avant que tout autre thread soit autorisé à effectuer l'étape 1, ce qui peut être accompli par tous les threads attendant d'obtenir un seul verrou avant de commencer ce processus. et libérer le verrou uniquement une fois le processus terminé, afin que cette "section critique" de code ne puisse pas être entrelacée de manière incorrecte, ce qui entraîne un nombre incorrect.

Et si l'opération était atomique?

Oui, au pays des licornes et des arcs-en-ciel magiques, où l'opération d'incrémentation est atomique, le verrouillage ne serait pas nécessaire pour l'exemple ci-dessus.

Il est important de réaliser, cependant, que nous passons très peu de temps dans le monde des licornes et des arcs-en-ciel magiques. Dans presque tous les langages de programmation, l'opération d'incrémentation se décompose en trois étapes. En effet, même si le processeur prend en charge une opération d'incrémentation atomique, cette opération est nettement plus coûteuse: il doit lire dans la mémoire, modifier le nombre et l'écrire en mémoire ... et généralement l'opération d'incrémentation atomique est une opération qui peut échouer, ce qui signifie que la séquence simple ci-dessus doit être remplacée par une boucle (comme nous le verrons ci-dessous).

Étant donné que, même dans le code multithread, de nombreuses variables sont conservées localement sur un seul thread, les programmes sont beaucoup plus efficaces s'ils supposent que chaque variable est locale sur un seul thread et laissent les programmeurs prendre soin de protéger l'état partagé entre les threads. Surtout étant donné que les opérations atomiques ne sont généralement pas suffisantes pour résoudre les problèmes de threading, comme nous le verrons plus tard.

Variables volatiles

Si nous voulions éviter les verrous pour ce problème particulier, nous devons d'abord réaliser que les étapes décrites dans notre premier exemple ne sont pas réellement ce qui se passe dans le code compilé moderne. Étant donné que les compilateurs supposent qu'un seul thread modifie la variable, chaque thread conservera sa propre copie en cache de la variable, jusqu'à ce que le registre du processeur soit nécessaire pour autre chose. Tant qu'il a la copie en cache, il suppose qu'il n'a pas besoin de revenir en mémoire et de la relire (ce qui coûterait cher). Ils n'écriront pas non plus la variable en mémoire tant qu'elle est conservée dans un registre.

Nous pouvons revenir à la situation que nous avons donnée dans le premier exemple (avec tous les mêmes problèmes de thread que nous avons identifiés ci-dessus) en marquant la variable comme volatile , ce qui indique au compilateur que cette variable est en cours de modification par d'autres, et doit donc être lue à partir de ou écrit en mémoire chaque fois qu'il est consulté ou modifié.

Une variable marquée comme volatile ne nous emmènera donc pas au pays des opérations d'incrémentation atomique, elle ne nous rapprochera que de ce que nous pensions déjà.

Rendre l'incrément atomique

Une fois que nous utilisons une variable volatile, nous pouvons rendre notre opération d'incrémentation atomique en utilisant une opération de définition conditionnelle de bas niveau prise en charge par la plupart des processeurs modernes (souvent appelée comparer et définir ou comparer et échanger ). Cette approche est prise, par exemple, dans la classe AtomicInteger de Java :

197       /**
198        * Atomically increments by one the current value.
199        *
200        * @return the updated value
201        */
202       public final int incrementAndGet() {
203           for (;;) {
204               int current = get();
205               int next = current + 1;
206               if (compareAndSet(current, next))
207                   return next;
208           }
209       }

La boucle ci-dessus effectue à plusieurs reprises les étapes suivantes, jusqu'à ce que l'étape 3 réussisse:

1. Lisez la valeur d'une variable volatile directement depuis la mémoire.
2. Augmentez cette valeur.
3. Modifiez la valeur (dans la mémoire principale) si et seulement si sa valeur actuelle dans la mémoire principale est la même que la valeur que nous lisons initialement, en utilisant une opération atomique spéciale.

Si l'étape 3 échoue (car la valeur a été modifiée par un thread différent après l'étape 1), il lit à nouveau la variable directement à partir de la mémoire principale et réessaye.

Bien que l'opération de comparaison et d'échange soit coûteuse, elle est légèrement meilleure que l'utilisation du verrouillage dans ce cas, car si un thread est suspendu après l'étape 1, les autres threads qui atteignent l'étape 1 n'ont pas à bloquer et à attendre le premier thread, ce qui peut empêcher un changement de contexte coûteux. Lorsque le premier thread reprendra, il échouera lors de sa première tentative d'écriture de la variable, mais pourra continuer en relisant la variable, ce qui est encore probablement moins cher que le changement de contexte qui aurait été nécessaire avec le verrouillage.

Ainsi, nous pouvons accéder au pays des incréments atomiques (ou d'autres opérations sur une seule variable) sans utiliser de verrous réels, via la comparaison et l'échange.

Alors, quand le verrouillage est-il strictement nécessaire?

Si vous devez modifier plusieurs variables dans une opération atomique, le verrouillage sera nécessaire, vous ne trouverez pas d'instructions de processeur spéciales pour cela.

Tant que vous travaillez sur une seule variable et que vous êtes prêt à tout travail que vous avez fait pour échouer et devoir lire la variable et recommencer, la comparaison et l'échange seront cependant assez bons.

Prenons un exemple où chaque thread ajoute d'abord 2 à la variable X, puis multiplie X par deux.

Si X est initialement un et que deux threads s'exécutent, nous nous attendons à ce que le résultat soit (((1 + 2) * 2) + 2) * 2 = 16.

Cependant, si les threads s'entrelacent, nous pourrions, même si toutes les opérations sont atomiques, que les deux additions se produisent en premier et que les multiplications viennent après, ce qui donne (1 + 2 + 2) * 2 * 2 = 20.

Cela se produit car la multiplication et l'addition ne sont pas des opérations commutatives.

Donc, les opérations elles-mêmes étant atomiques ne suffisent pas, il faut faire la combinaison des opérations atomiques.

Nous pouvons le faire soit en utilisant le verrouillage pour sérialiser le processus, soit en utilisant une variable locale pour stocker la valeur de X lorsque nous avons commencé notre calcul, une deuxième variable locale pour les étapes intermédiaires, puis en utilisant la fonction de comparaison et d'échange pour définissez une nouvelle valeur uniquement si la valeur actuelle de X est la même que la valeur d'origine de X. Si nous échouons, nous devrons recommencer en lisant X et en effectuant à nouveau les calculs.

Plusieurs compromis sont impliqués: à mesure que les calculs s'allongent, il devient beaucoup plus probable que le thread en cours d'exécution soit suspendu et la valeur sera modifiée par un autre thread avant de reprendre, ce qui signifie que les échecs deviennent beaucoup plus probables, conduisant à un gaspillage temps processeur. Dans le cas extrême d'un grand nombre de threads avec des calculs très longs, nous pouvons avoir 100 threads lisant la variable et engagés dans des calculs, auquel cas seul le premier à terminer réussira à écrire la nouvelle valeur, les 99 autres encore terminer leurs calculs, mais découvrir à la fin qu'ils ne peuvent pas mettre à jour la valeur ... à quel point ils liront chacun la valeur et recommenceront le calcul. Nous aurions probablement les 99 threads restants répéter le même problème, gaspillant de grandes quantités de temps processeur.

La sérialisation complète de la section critique via des verrous serait bien meilleure dans cette situation: 99 threads se suspendraient lorsqu'ils n'obtiendraient pas le verrou, et nous exécuterions chaque thread par ordre d'arrivée au point de verrouillage.

Si la sérialisation n'est pas critique (comme dans notre cas d'incrémentation) et que les calculs qui seraient perdus si la mise à jour du nombre échoue sont minimes, il peut y avoir un avantage significatif à tirer de l'utilisation de l'opération de comparaison et d'échange, car cette opération est moins cher que le verrouillage.

Considérez cette citation:

Certaines personnes, confrontées à un problème, pensent: «Je sais, je vais utiliser des fils», puis deux, ils ont des poblesms

vous voyez, même si 1 instruction s'exécute sur un CPU à un moment donné, les programmes informatiques comprennent bien plus que de simples instructions d'assemblage atomique. Ainsi, par exemple, écrire sur la console (ou un fichier) signifie que vous devez verrouiller pour vous assurer que cela fonctionne comme vous le souhaitez.

Il semble que de nombreuses réponses aient tenté d'expliquer le verrouillage, mais je pense que ce dont OP a besoin est une explication de ce qu'est réellement le multitâche.

Lorsque plusieurs threads s'exécutent sur un système, même avec un seul processeur, il existe deux méthodologies principales qui dictent la façon dont ces threads seront planifiés (c'est-à-dire placés pour s'exécuter dans votre processeur simple cœur):

• Multitâche coopératif - Utilisé dans Win9x, chaque application devait explicitement abandonner le contrôle. Dans ce cas, vous n'aurez pas à vous soucier du verrouillage car tant que le thread A exécute un algorithme, vous serez assuré qu'il ne sera jamais interrompu
• Multitâche préemptif - utilisé dans la plupart des systèmes d'exploitation modernes (Win2k et versions ultérieures). Cela utilise des tranches de temps et interrompra les threads même s'ils font encore du travail. C'est beaucoup plus robuste car un seul thread ne peut jamais bloquer l'intégralité de votre machine, ce qui était une possibilité réelle avec le multitâche coopératif. D'un autre côté, vous devez maintenant vous soucier des verrous, car à tout moment, l'un de vos threads peut être interrompu (c'est-à-dire préempté) et le système d'exploitation peut planifier l'exécution d'un autre thread. Lors du codage d'applications multithread avec ce comportement, vous DEVEZ considérer qu'entre chaque ligne de code (ou même chaque instruction) un thread différent peut s'exécuter. Désormais, même avec un seul cœur, le verrouillage devient très important pour garantir un état cohérent de vos données.

Le problème ne réside pas dans les opérations individuelles, mais dans les tâches plus importantes que les opérations effectuent.

De nombreux algorithmes sont écrits en supposant qu'ils contrôlent pleinement l'état sur lequel ils opèrent. Avec un modèle d'exécution ordonnée entrelacé comme celui que vous décrivez, les opérations peuvent être arbitrairement entrelacées les unes avec les autres, et si elles partagent un état, il existe un risque que l'état se présente sous une forme incohérente.

Vous pouvez le comparer avec des fonctions qui peuvent temporairement casser un invariant afin de faire ce qu'elles font. Tant que l'État intermédiaire n'est pas observable de l'extérieur, il peut faire ce qu'il veut pour accomplir sa tâche.

Lorsque vous écrivez du code simultané, vous devez vous assurer que l'état contesté est considéré comme dangereux, sauf si vous y avez un accès exclusif. La méthode courante pour obtenir un accès exclusif est la synchronisation sur une primitive de synchronisation, comme le maintien d'un verrou.

Une autre chose que les primitives de synchronisation ont tendance à entraîner sur certaines plates-formes est qu'elles émettent des barrières de mémoire, ce qui garantit la cohérence de la mémoire entre les processeurs.

Sauf pour le réglage «bool», il n'y a aucune garantie (au moins en c) que la lecture ou l'écriture d'une variable ne prend qu'une instruction - ou plutôt ne peut pas être interrompue au milieu de la lecture / écriture

La memoire partagée.

C'est la définition de ... threads : un tas de processus simultanés, avec mémoire partagée.

S'il n'y a pas de mémoire partagée, ils sont généralement appelés processus UNIX à l'ancienne .
Cependant, ils peuvent avoir besoin d'un verrou de temps en temps pour accéder à un fichier partagé.

(la mémoire partagée dans les noyaux de type UNIX était en effet généralement implémentée à l'aide d'un faux descripteur de fichier représentant l'adresse de mémoire partagée)

Un processeur exécute une instruction à la fois, mais que faire si vous avez deux processeurs ou plus?

Vous avez raison en ce que les verrous ne sont pas nécessaires, si vous pouvez écrire le programme de telle sorte qu'il profite des instructions atomiques: des instructions dont l'exécution n'est pas interruptible sur le processeur donné et exemptes d'interférences par d'autres processeurs.

Des verrous sont nécessaires lorsque plusieurs instructions doivent être protégées contre les interférences, et qu'il n'y a pas d'instructions atomiques équivalentes.

Par exemple, l'insertion d'un nœud dans une liste à double liaison nécessite la mise à jour de plusieurs emplacements de mémoire. Avant l'insertion et après l'insertion, certains invariants tiennent à la structure de la liste. Cependant, lors de l'insertion, ces invariants sont temporairement rompus: la liste est dans un état "en construction".

Si un autre thread parcourt la liste pendant que les invariants, ou essaie également de le modifier quand il est dans un tel état, la structure des données sera probablement corrompue et le comportement sera imprévisible: peut-être que le logiciel plantera ou continuera avec des résultats incorrects. Il est donc nécessaire que les threads acceptent d'une manière ou d'une autre de rester à l'écart lors de la mise à jour de la liste.

Des listes convenablement conçues peuvent être manipulées avec des instructions atomiques, de sorte que les verrous ne sont pas nécessaires. Les algorithmes pour cela sont appelés "sans verrouillage". Cependant, notez que les instructions atomiques sont en fait une forme de verrouillage. Ils sont spécialement implémentés dans le matériel et fonctionnent via la communication entre les processeurs. Ils sont plus chers que des instructions similaires qui ne sont pas atomiques.

Sur les multiprocesseurs qui n'ont pas le luxe des instructions atomiques, les primitives d'exclusion mutuelle doivent être constituées de simples accès à la mémoire et de boucles d'interrogation. De tels problèmes ont été résolus par des personnes comme Edsger Dijkstra et Leslie Lamport.