Analyse complète des primitives de synchronisation dans les systèmes d'exploitation

Cet article vous apporte une analyse complète des primitives de synchronisation du système d'exploitation. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. J'espère qu'il vous sera utile.

Condition de concurrence

Dans un système d'exploitation général, différents processus peuvent partager une zone de stockage commune, telle que la mémoire ou les fichiers sur le disque dur. Ces processus sont autorisés à s'exécuter dans ces zones. et écris dessus.
Le système d'exploitation a certaines responsabilités pour coordonner les processus en utilisant l'espace commun afin d'effectuer correctement les opérations souhaitées. Ces processus doivent communiquer entre eux et avoir des discussions pour garantir que les actions d'un processus n'affecteront pas les actions normales d'un autre processus, ce qui empêchera le processus d'obtenir les résultats attendus après son exécution. Dans le concept de système d'exploitation, le terme IPC (Inter Process Communication) est généralement utilisé pour représenter la communication entre plusieurs processus.
Afin d'expliquer ce qu'est une condition de concurrence critique, nous introduisons un exemple simple pour illustrer :
Un numéro n est stocké dans un fichier, et les processus A et B veulent lire ce numéro et l'ajouter. 1 à ce numéro, puis enregistrez-le dans le fichier. En supposant que la valeur initiale de n est 0, dans notre cas idéal, après l'exécution du processus A et du processus B, la valeur de n dans le fichier devrait être 2, mais en fait il peut arriver que la valeur de n soit 1. Nous pouvons considérer les étapes par lesquelles chaque processus doit passer :

1. Lire la valeur de n dans le fichier

2. Soit n = n + 1

3. Enregistrez la nouvelle valeur n dans le fichier.

Avant d'expliquer davantage les conditions de concurrence, nous devons d'abord revoir plusieurs points de connaissance dans les concepts du système d'exploitation :

1. Les processus peuvent s'exécuter simultanément, même lorsqu'il y a n'est qu'un seul CPU)

2. L'interruption de l'horloge du système d'exploitation entraînera la reprogrammation du processus en cours,

3. En plus de l'horloge interruption, les interruptions provenant d'autres appareils entraîneront également la reprogrammation du processus

Supposons qu'une interruption d'horloge se produit lorsque le processus A a fini d'exécuter les étapes 1 et 2 mais n'a pas encore commencé à exécuter l'étape 3 , à ce moment-là, le système d'exploitation planifie le démarrage du processus B. Lorsque le processus B exécute l'étape 1, il constate que la valeur de n est 0, il exécute donc les étapes 2 et 3 et enregistre finalement n = 1 dans un fichier. . Lorsque le processus A continue de s'exécuter plus tard, parce qu'il ne sait pas que le processus B a modifié la valeur dans le fichier avant d'exécuter l'étape 3, le processus A réécrira également n = 1 dans le fichier. C'est le problème. Pendant que le processus A est en cours d'exécution, d'autres processus fonctionneront sur les données qu'il exploite.

La seule façon de faire n = 2 est de s'attendre à ce que le processus A et le processus B exécutent complètement toutes les étapes dans l'ordre respectivement.
Nous pouvons définir une condition de concurrence.

Deux processus ou plus lisent et écrivent certaines données partagées, et le résultat final dépend du moment exact de l'exécution du processus, ce que l'on appelle une condition de concurrence.

Dans le texte ci-dessus, nous utilisons process comme objet pour discuter des conditions de concurrence. En fait, la même chose s'applique aux threads ici, mais sans s'y limiter, les threads du noyau et les threads utilisateur. Parce que dans le système d’exploitation, les processus s’appuient en réalité sur des threads pour exécuter des programmes. De plus, dans la sécurité des threads du langage Java, le concept de conditions de concurrence s'applique également. (Reportez-vous au chapitre 2 de « Programmation simultanée Java en pratique »)

Exclusion mutuelle et sections critiques

Comment éviter les conditions de concurrence critique, nous devons utiliser certains moyens pour garantir que lorsqu'un processus est En utilisant une variable ou des fichiers partagés, les autres processus ne peuvent pas effectuer la même opération. En d'autres termes, nous avons besoin d'une "exclusion mutuelle".
En prenant l'exemple ci-dessus comme exemple, nous pouvons définir le fragment de programme des étapes 1 à 3 comme une section critique. La section critique signifie que cette zone est sensible, car une fois que le processus se déroule dans cette zone, cela signifie qu'il est public. Les données fonctionneront dans une zone ou un fichier signifie également que d'autres processus peuvent s'exécuter dans la section critique. Si des mesures appropriées sont prises pour que les deux processus ne se trouvent pas dans des sections critiques en même temps, les conditions de concurrence peuvent être évitées.
En d’autres termes, nous devons réfléchir à la manière de parvenir à « l’exclusion mutuelle ».

Schéma d'exclusion mutuelle

L'essence de l'exclusion mutuelle est d'empêcher plusieurs processus d'entrer dans la section critique en même temps

Masquer les interruptions

Dans l'exemple mentionné précédemment, le processus B a pu entrer dans la section critique car le processus A a été interrompu dans la section critique. Si nous demandons au processus A de masquer toutes les interruptions immédiatement après être entré dans la section critique et de répondre aux interruptions uniquement après avoir quitté la section critique, alors même si une interruption se produit, le processeur ne basculera pas vers d'autres processus, le processus A peut donc modifier le processus en toute sécurité. contenu du fichier sans craindre que d'autres processus n'interfèrent avec son travail.
Cependant, cette idée est belle, mais en fait elle n'est pas réalisable. Premièrement, s'il y a plusieurs processeurs, le processus A ne peut pas masquer les interruptions sur les autres processeurs. Il ne peut masquer que le processeur qui le planifie, de sorte que les processus planifiés par d'autres processeurs peuvent toujours entrer dans la section critique, à propos de l'alimentation. des interruptions bloquantes doivent-elles être données au processus utilisateur ? Si ce processus masque les interruptions et ne répond jamais aux interruptions, alors un processus peut bloquer l'ensemble du système d'exploitation.

Variable de verrouillage

Vous pouvez peut-être définir sa valeur initiale sur 0 en définissant un indicateur de verrouillage Lorsqu'un processus souhaite entrer dans la section critique, vérifiez d'abord si la valeur du verrou est 0. Si c'est 0, définissez-le sur 1, puis entrez dans la section critique et changez la valeur du verrou à 0 après avoir quitté la section critique ; si la valeur du verrou est déjà 1 lors de la vérification, cela signifie que d'autres processus le sont ; déjà dans la section critique, donc le processus boucle Attendez et continuez à vérifier la valeur du verrou jusqu'à ce qu'elle devienne 0.
Mais il existe également une condition de concurrence critique dans cette méthode. La raison en est que lorsqu'un processus lit la valeur du verrou à 0, avant de définir sa valeur sur 1, un autre processus est planifié et il lit également la valeur du verrou. lock est 0, il existe donc une situation où les deux processus sont dans la section critique en même temps.

Méthode de rotation stricte

La raison pour laquelle il y a un problème avec la variable de verrouillage est en fait parce que l'action de changer la variable de verrouillage de 0 à 1 est effectuée par le processus qui souhaite acquérir le verrouillage. Si nous modifions cette action pour qu'elle soit effectuée par le processus qui a obtenu le verrou, il n'y aura alors aucune condition de concurrence critique.
Définissez d'abord un tour variable, qui représente qui est actuellement autorisé à obtenir le verrou. Supposons qu'il y ait deux processus. La logique du processus A est la suivante :

        while (turn != 0){// 如果还没轮到自己获取锁，则进入循环等待
        }
        do_critical_region();// 执行临界区的程序
        turn = 1;// 由获得锁的一方将锁变量修改为其它值，允许其它进程获得锁
        do_non_critical_region();// 执行非临界区的程序

La logique du processus B est. comme suit :

        while (turn != 1) {// 如果还没轮到自己获取锁，则进入循环等待
        }
        do_critical_region();// 执行临界区的程序
        turn = 0;// 由获得锁的一方将锁变量修改为其它值，允许其它进程获得锁
        do_non_critical_region();// 执行非临界区的程序

Mais une chose doit être prise en considération ici. Supposons que do_non_critical_region() du processus A doit être exécuté pendant une longue période. La région du processus A doit être exécutée pendant une longue période, tandis que la logique de la région non critique du processus B doit être exécutée pendant une longue période. La logique est exécutée rapidement. Évidemment, le processus A entrera moins dans la section critique. plus souvent que le processus B. Idéalement, le processus B devrait entrer plusieurs fois plus dans la section critique. Cependant, comme le processus B mettra turn à 0 avant d'exécuter la logique de la section non critique, après avoir exécuté rapidement la logique de la section non critique, lorsqu'il reviendra vérifier la valeur de turn, il s'avère que le la valeur du tour n'a jamais été 1. La valeur nécessite que le processus A la définisse sur 1, mais le processus A exécute actuellement un long code logique de section non critique, donc le processus B ne peut pas entrer dans la section critique.
Cela montre qu'une rotation stricte n'est pas une bonne idée lorsqu'un processus est beaucoup plus lent qu'un autre.

Algorithme de Peterson

Le problème avec la méthode de rotation stricte réside dans le mot strict, c'est-à-dire que plusieurs processus entrent tour à tour dans la section critique. La raison fondamentale est le processus qui veut obtenir le. lock.Il doit s'appuyer sur d'autres processus pour modifier la variable de verrouillage, et d'autres processus doivent d'abord exécuter la logique de section non critique avant de modifier la variable de verrouillage.
La variable turn dans la méthode de rotation stricte est non seulement utilisée pour indiquer à qui revient le tour d'acquérir le verrou, mais aussi avant que sa valeur ne change, cela signifie qu'elle empêche toujours les autres processus d'entrer dans la section critique. il arrive qu'un processus toujours La valeur de tour ne sera modifiée qu'après avoir passé par la logique de la section non critique.
Par conséquent, nous pouvons utiliser deux variables pour le représenter. Une variable représente à qui revient le tour d'obtenir le verrou actuellement, et l'autre variable représente que le processus en cours a quitté la section critique. Cette méthode est en fait appelée l'algorithme de Peterson, qui a été développé par les mathématiques néerlandaises proposées par T. Dekker.

    static final int N = 2;
    int turn = 0;
    boolean[] interested = new boolean[N];

    void enter_region(int process) {
        int other = 1 - process;
        interested[process] = true;
        turn = process;
        while(turn == process && !interested[other]) {
        }
    }

    void exit_region(int process) {
        interested[process] = false;
    }

Lorsqu'un processus doit entrer dans la section critique, il appelle d'abord enter_region, et après avoir quitté la section critique, il appelle exit_region. L'algorithme de Peterson amène le processus à éliminer immédiatement son « intérêt » dans la section critique après avoir quitté la section critique, afin que les autres processus puissent juger s'ils peuvent légalement entrer dans la section critique en fonction de la valeur du tour.

Instruction TSL

Rappelez la méthode de "verrouillage de variable" que nous avons mentionnée précédemment. L'un de ses défauts fatals est lors du changement de variable d'état, comme le passage de 0 à 1 ou de 1. Lorsqu'elle est passée à 0, elle est modifiée. peut être interrompu par des interruptions, il existe donc une condition de concurrence critique.
Plus tard, sur la base de la variable de verrouillage, nous avons proposé que si la variable de verrouillage est modifiée non pas par le processus qui veut entrer dans la section critique, mais par le processus qui veut quitter la section critique après être entré dans la section critique, alors Les conditions de course peuvent être évitées, ce qui conduit à la méthode de rotation stricte et à l'amélioration de l'algorithme de Peterson sur la base de la méthode de rotation stricte. Ces méthodes sont toutes considérées d’un point de vue logiciel. En fait, avec la prise en charge du processeur matériel, il est possible de garantir que les modifications des variables de verrouillage ne sont pas interrompues, ce qui fait des variables de verrouillage une bonne méthode pour résoudre l'exclusion mutuelle des processus.
La plupart des processeurs informatiques actuels prennent en charge l'instruction TSL, appelée Test and Set Lock. Elle lit une variable mémoire (mot) dans le registre RX, puis stocke une valeur non nulle à l'adresse mémoire, lue. les opérations et les opérations d'écriture sont garanties sans interruption au niveau matériel, c'est-à-dire atomique. La méthode qu'il utilise consiste à verrouiller le bus mémoire lors de l'exécution de l'instruction TSL, interdisant aux autres processeurs d'accéder à la mémoire avant la fin de l'instruction TSL. C’est aussi ce que l’on appelle souvent CAS (Compare And Set).
Lorsque vous devez changer la variable de verrouillage de 0 à 1, copiez d'abord la valeur de la mémoire dans le registre, définissez la valeur de la mémoire sur 1, puis vérifiez si la valeur du registre est 0. Si elle est 0, l'opération est réussi. S'il est différent de 0, répétez la détection jusqu'à ce que la valeur du registre devienne 0. Si la valeur du registre devient 0, cela signifie qu'un autre processus a quitté la section critique. Lorsque le processus quitte la section critique, il doit définir la valeur de cette variable en mémoire sur 0.

Attente occupée

L'algorithme de Peterson et la méthode TSL mentionnés ci-dessus ont en fait une fonctionnalité, c'est-à-dire qu'ils utilisent l'attente occupée lorsqu'ils attendent d'entrer dans la section critique, nous l'appelons aussi souvent spin. . Son inconvénient est qu'il gaspille des tranches de temps CPU et peut provoquer des problèmes d'inversion de priorité.

Considérons un ordinateur avec deux processus, H a une priorité plus élevée et L a une priorité plus faible. Les règles de planification stipulent que tant que H est à l'état prêt, il peut s'exécuter. À un certain moment, L est dans la région critique et H est dans un état prêt et prêt à fonctionner. Mais H doit être occupé à attendre, et L ne peut pas être planifié en raison de sa faible priorité, il ne peut donc pas quitter la section critique. Par conséquent, H sera occupé à attendre indéfiniment et L ne pourra jamais quitter la section critique. Cette situation est appelée Problème d'inversion de priorité (problème d'inversion de priorité)

Blocage et réveil du processus

Le système d'exploitation fournit quelques primitives, veille et réveil .

Le processus ou la fonction fourni par le noyau pour les appels en dehors du noyau devient une primitive, et les primitives ne permettent pas d'interruption pendant l'exécution.

sleep est un appel système qui bloque le processus appelant jusqu'à ce qu'un autre processus appelle la méthode de réveil, en prenant le processus bloqué comme paramètre pour le réveiller. La plus grande différence entre le blocage et l'attente occupée est qu'une fois le processus bloqué, le processeur ne lui alloue pas de tranche de temps, tandis que l'attente occupée est toujours inactive et consomme la tranche de temps du processeur.

Sémaphore

La première chose que vous devez comprendre est quel problème le sémaphore semble résoudre puisque le blocage et le réveil d'un processus sont provoqués dans différents processus, par exemple, le processus A appelle sleep(). entrez dans le blocage et l'appel du processus B à wakeup(A) réveillera le processus A. Parce qu’elle s’effectue selon des processus différents, il existe également un problème d’interruption. Selon la logique, lorsqu'il rejoint le processus A, il doit appeler sleep() pour entrer dans l'état de blocage. Cependant, juste avant d'appeler la méthode sleep, en raison de l'interruption de l'horloge, le processus B commence à s'exécuter. appelle la méthode wakeup() pour réveiller le processus A, mais comme le processus A n'est pas encore entré dans l'état de blocage, le signal de réveil est perdu. Lorsque le processus A continue de s'exécuter à partir de la position précédemment interrompue et entre dans le blocage, aucun processus ne peut plus être interrompu. réveille-le.
Il convient donc d'introduire une variable supplémentaire pour enregistrer le blocage et le réveil du processus. Cette variable enregistre le nombre de réveils, la valeur de la variable est incrémentée de 1. Avec cette variable, même si l'opération de réveil précède l'opération de veille, l'opération de réveil sera enregistrée dans la variable. Lorsque le processus dort, car d'autres processus se sont déjà réveillés, on considère que le processus n'a pas besoin d'entrer dans le blocage. État.
Cette variable, dans le concept du système d'exploitation, est appelée sémaphore, méthode proposée par Dijkstra en 1965.
Il existe deux opérations sur les sémaphores, vers le bas et vers le haut.
L'opération down correspond en fait au sommeil. Elle va d'abord détecter si la valeur du sémaphore est supérieure à 0. Si elle est supérieure à 0, alors la décrémenter de 1. Le processus n'a pas besoin de se bloquer à ce moment, ce qui équivaut à consommer un réveil ; si le sémaphore est 0 , le processus entrera dans un état bloquant.
L'opération up correspond au réveil. Après l'opération up, si un processus s'avère bloqué sur ce sémaphore, le système sélectionnera un des processus pour le réveiller. A ce moment, la valeur du sémaphore le fait. pas besoin de changer, mais il est bloqué. Il y a déjà un processus en moins si aucun processus n'est bloqué sur le sémaphore lors de l'opération up, cela augmentera la valeur du sémaphore de 1.
À certains endroits, les opérations de baisse et de hausse sont appelées opérations PV. En effet, dans l'article de Dijkstra, P et V sont utilisés pour représenter respectivement la baisse et la hausse.
Les opérations down et up des sémaphores sont des primitives prises en charge par le système d'exploitation. Ce sont des opérations atomiques et ne seront pas interrompues.

Mutex

Un mutex est en fait un cas particulier de sémaphore. Ses valeurs ne sont que 0 et 1. Lorsqu'on n'a pas besoin d'utiliser la capacité de comptage du sémaphore, on peut. utilisez un mutex, ce qui signifie en fait que la valeur de la section critique ne permet qu'à un seul processus d'entrer en même temps, tandis que le sémaphore permet à plusieurs processus d'entrer dans la section critique en même temps.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!