Systèmes d’exploitation 10. Processus en parallèle. Exclusion mutuelle. Sections critiques. Sémaphores 10. 1. Processus en parallèle Les processus qui existent et qui sont simultanément exécutés dans le système calculateur sont parallèles. Les processus parallèles peuvent fonctionner en pleine indépendance (processus détachés) ou interagir entre eux (processus interactifs ou coopérants). Les pro pratique au sein des d’exploitation. Natur me , suscités par ce type processus, qui seron interactifs peuvent 6 tent de Vintérêt oblèmes sont nt.
Les processus onctionner de manière synchrone (lorsqu’ un processus suspend son exécution jusqu’à ce qu’ un autre processus n’atteigne un point déterminé de son exécution) ou de manière asynchrone (lorsque les processus ne s’intéressent pas à l’état des autres). Chez les systèmes à multiprocesseurs il existe un parallélisme réel, lors duquel, à un moment donné, le nombre de processus exécutés simultanément est égal au nombre des éléments de processeur.
Dans les systèmes à monoprocesseur, les processus s’exécutent en pseudoparallèle (quasi-parallèle) en partageant le processeur sur la base d’une stratégie éterminée, par exemple, le temps partagé. valeurs courantes du compteur ordinal et des registres de processeur accessibles au programmeur, ainsi que les variables du programme. Autrement dit, le vecteur d’état comporte l’information de gestion du processus, nécessaire au processeur. Le vecteur d’état d’un processus indépendant ne peut être modifié qu’au cours de l’exécution de ce même processus.
Lors des processus interactifs, le vecteur d’état d’un processus donné p peut être modifié par l’évolution d’autres processus, qui se partagent certains des composants du vecteur du processus P variables ou zones de données partagées). Les composants communs, partagés par plusieurs processus, s’appellent ressources. 10. 2. Nécessité d’exclusion mutuelle Lorsque plusieurs processus modifient de manière asynchrone le contenu d’une zone de données partagée, dans certains cas, ces données sont susceptibles de prendre une valeur incorrecte.
Par exemple: Si les programmes des processus Pl et P2 comportent des fragments d’appel à une ressource partagée – la variable r. Pl effectue l’opération a pl: LDA Charge r dans l’accumulat IE n’importe quel moment de l’exécution du processus. En même temps, dans le processeur, s’effectue la procédure standard de stockage du PSW du processus interrompu et de chargement de l’état du processus consécutif activé.
Si la valeur initiale est (le moment t=O) , le processus Pl est interrompu après l’exécution de la première instruction et la gestion est transférée à P2 (le moment t=2), alors, l’effet de l’exécution des deux processus sera: 2 3 ressources communes, partagées (entre quelques processus), est appelée section critique (CS). Afin de résoudre le problème de l’exclusion mutuelle, il est nécessaire de rotéger les sections critiques contre l’accès simultané. A cet effet, il faut satisfaire aux exigences suivantes: 1.
A un moment donné, dans une section critique, il ne peut se trouver qu’un seul processus; 2. Si un ou plusieurs processus désirent entrer dans leurs sections critiques, alors l’un d’entre eux doit obligatoirement en être autorisé ; 3. Chaque processus peut basculer dans un état arbitraire en dehors de sa section critique, c’est-à-dire, il peut être même suspendu. Cela ne doit pas influencer les autres processus lors de l’utilisation de la ressource partagée; 4. Les vitesses relatives du développement des processus sont préalablement inconnues et arbitraires; 5. n processus ne peut pas suspendre son exécution dans une section critique et il doit y passer à une vitesse maximale ; 6. Les sections critiques ne doivent pas avoir de priorités. La seule exigence envers le matériel formulée pour le moment 7. Les opérations de lecture et d’écriture dans la mémoire centrale sont des opérations indivisibles. Les opérations de base avec lesquelles est réalisée la protection (l’exclusion mutuelle) des sections critiques, sont appelées primitifs. Il existe de multiples tentatives de résoudre le problème de l’exclusion mutuelle de deux processus lors d’un a ssource partagée.
La problème pour le cas général lors de processus n (n>2) est considérablement plus compliqué. 10. 4. Protection de programme des sections critiques Le problème de la protection des sections critiques peut être resolu par vole purement logicielle concernant les processeurs qui n’ont pas d’instructions spéciales d’exclusion mutuelle. La protection de programme est possible, étant donné que les instructions de machine sont ininterrompues, c’est-à-dire, chaque nstruction est exécutée comme une opération indivisible, et en plus, l’exigence 7 (le point 3) est en vigueur.
Les solutions de programme doivent être précises, afin d’éviter d’éventuels pièges susceptibles d’enfreindre les exigences 1 – 6 au point 3. Dans les exemples examinés, la section critique est désignée par CSi, et par Progri on désigne le reste du programme du processus Pi. Les processus exécutés en parallèle sont réalisés par la construction parbegin – parend. Dans le cadre de cette construction, tous les opérateurs sont exécutés en parallèle. pour simplifier, il est dmis que les processus mêmes sont cycliques et sont intérieurement exécutés successivement. 10. 4. 1.
Tentatives de résoudre le problème d’exclusion mutuelle A prime abord, le problème d’exclusion mutuelle est relativement simple, mais en réalité tel n’est pas le cas. Les algorithmes appliqués ci-dessous sont incorrects concernant au moins l’une des exigences au oint 3. Leur incorrection ne peut être prouvée qu’aprè une analyse approfondie. Afin d’abréger la description, ce n’est que le code de l’un des processus qui est cité dans les algorithmes, étant donné que le euxième processus est complètement symétrique au premier en ce qui concerne les numéros des flags et les valeurs des variables en entiers. 0. 4. 1. 1. Algorithme I Le problème de la CS peut être résolu par l’établissement d’un ordre d’entrée des processus dans la section critique. L’ordre est réglé par le biais d’une variable partagée. A l’entrée de la CS, chaque processus effectue la vérification, puis il attend son tour, et à la sortie de la CS, il cède le tour à l’autre processus. La variable turn détermine à qui est le tour d’entrer dans la CS. Lors d’une valeur initiale de la variable turn égale à 2 , le processus P2 a le droit d’entrer dans la section critique CS2.
Le processus Pl reste bloqué dans sa boucle while, jusqu’à ce que le processus P2 ne modifie pas la valeur de turn ? 1, à la sortie de la section critique. Ainsi, les Pl et P2 vont passer successivement par leurs sections critiques, en garantissant un accès d’exclusion mutuelle aux données partagées. On voit que les processus entreront et sortiront de leurs sections critiques dans un ordre strict. En outre, il est clair que, si le processus dont le tour est à entrer dans sa CS, st bloqué dans sa partie restante (Progri), cela va bloquer également l’autre processus ? l’entrée de sa CS.
Cela signifie que l’algorithme n’accomplit pas l’exigence 3 du point 3. Proeram Attemptl; 6 OF IE point 3. Program Attemptl; var turn: integer; begin Parbegin { Process 1 } repeat while turn = 2 do; CSI; turn 2; Progrl; until false; { Process 2} Parend; 10. 4. 1. 2. Algorithme 2 On introduit deux variables, partagées par les deux processus, indiquant SI le processus se trouve dans sa section critique ou pas. Chaque processus peut vérifier les deux flags, mais il ne peut modifier que le sien. Program Attempt2; Cl, C2: boolean; beein l’exigence 2.
Program Attempt3; Cl ,C2: boolean; Cl := true; C2 true; Cl := false; while not C2 do ; csl; P2: { Process 2 } end. 10. 4. 1. 4. Algorithme 4 Il devient clair que la solution de mettre son propre flag avant la vérification du flag étranger est correcte, mais il est incorrect de demeurer dans le seul état de vérification infinie à l’entrée de la CS. é dans l’algorithme 8 OF IE simultanée dans la CS. Program Decker_Algorithm; Var queue: integer; Cl C2:=true; Cl :=false; while not C2 do if queue = 2 then Cl :=true; while queue = 2 do ; nd; (1981) propose un algorithme plus simple et plus élégant que celui de Decker.
Au moment de l’entrée dans une section critique, chaque processus cède le tour ? l’autre processus avec la variable queue. Si l’autre processus n’est pas dans une section critique ou il n’a pas tenté d’y entrer (le flag C2 est true), le premier processus entre sans difficulté dans la section critique. Dans le cas contraire, il est obligé d’attendre l’opérateur while. Program Peterson_Algorithm; boolean; Cl true; CZ := true; while true do begin Cl false; queue := 2; while (not C2) and (queue = 2) do ; 0 6
