Ce document constitue le troisième fascicule de Travaux Dirigés (TD3) destiné aux étudiants de première année d'ingénierie en Systèmes d'Exploitation Avancés. Il aborde les concepts fondamentaux de la synchronisation des processus, une thématique cruciale dans la conception des systèmes concurrents.
Ce TD se concentre sur l'exclusion mutuelle et l'attente active, en explorant diverses solutions logicielles. Il couvre les notions suivantes:
- L'exclusion mutuelle et ses problèmes liés aux variables partagées.
- Les mécanismes d'attente active.
- L'analyse et l'implémentation de l'algorithme de Peterson.
- L'étude des propriétés de l'algorithme de Dekker.
Synchronisation des Processus avec Attente Active
Ce document explore la synchronisation des processus, une notion fondamentale en systèmes d'exploitation avancés, en se concentrant sur les mécanismes d'exclusion mutuelle et d'attente active. Il présente des exercices pratiques et des algorithmes clés tels que ceux de Peterson et Dekker.
Exercice 1 : Exclusion Mutuelle avec Accès aux Fichiers
Dans un système informatique, on dispose de trois fichiers F1, F2 et F3 et de trois processus dont les programmes A, B et C ont les structures suivantes :
Programme A
- Actions A1
- Actions A2 (lire F2)
- Actions A3
- Actions A4 (écrire F3)
- Actions A5
Programme B
- Actions B1
- Actions B2 (écrire F3)
- Actions B3 (lire F1)
- Actions B4
- Actions B5
Programme C
- Actions C1 (lire F3)
- Actions C2
- Actions C3
- Actions C4 (écrire F2)
- Actions C5
Chaque fichier ne peut ni être lu et modifié en même temps, ni modifié par plusieurs processus en même temps.
- Donner pour chaque fichier les sections critiques de A, B et C.
- En déduire les sections en exclusion mutuelle.
Explication : Une section critique est une portion de code qui accède à une ressource partagée (ici, les fichiers) et qui doit être exécutée en exclusion mutuelle pour éviter les incohérences. L'exclusion mutuelle garantit qu'un seul processus à la fois peut exécuter sa section critique relative à une ressource donnée.
Exercice 2 : Exclusion Mutuelle par Variables Partagées
Cet exercice explore l'implémentation de l'exclusion mutuelle à l'aide de variables partagées, en examinant les défis liés à la progression et à l'interblocage.
On dispose de deux processus (P0 et P1) dont le squelette de programme est celui donné dans le cours.
- Rappeler le squelette des programmes destinés à s’exécuter en parallèle dans des conditions de concurrence. L’objectif de l’exercice est d’établir un algorithme utilisant des variables partagées par les processus pour réaliser l’exclusion mutuelle des sections critiques en respectant ses spécifications. On ne fait aucune hypothèse sur l’atomicité des manipulations des variables.
- Préciser pourquoi une simple attente active sur une variable
tourqui vaudrait vrai ou faux selon qu’un processus est ou non en section critique, immédiatement suivie d’une mise à jour detour, ne convient pas. - On propose dans un premier algorithme, la solution suivante. La variable
tourprend les valeurs : 0 ou 1. L’algorithme (1) de Pi est le suivant :tant_que vrai faire actions avant section critique tant_que tour <> i faire rien section critique i tour ← 1-i actions après section critiqueNoter que
1-i = 0sii = 1, et1sii = 0. La phase d’initialisation du système est réduite à :tour ← 0. Montrer que l’exclusion mutuelle est bien réalisée mais que la condition de progression n’est pas satisfaite. - Pour remédier à cet inconvénient, on emploie au lieu de
tour, deux variables booléennes D0 et D1.Diest vraie si et seulement siPidemande à passer en section critique. L’algorithme (2) de Pi est alors :tant_que vrai faire actions avant section critique Di ← vrai tant_que D(1-i) faire rien section critique i Di ← faux actions après section critiqueD(1-i)désigneD1sii = 0etD0sii = 1. Les variablesDisont initialisées àfaux. Montrer que la progression est maintenant assurée. Montrer que le système possède un état d’interblocage.
Explication : L'attente active (ou "busy-waiting") est une technique où un processus vérifie continuellement une condition sans libérer le processeur, ce qui peut consommer inutilement des ressources CPU. Les variables partagées sont utilisées pour coordonner l'accès aux sections critiques entre plusieurs processus.
Exercice 3 : Algorithme de Peterson
L'algorithme de Peterson est une solution classique pour l'exclusion mutuelle entre deux processus utilisant l'attente active, sans recourir à des instructions atomiques spéciales.
- Rappeler le principe de l’algorithme de Peterson.
- Prouver que cet algorithme respecte toutes les exigences d’un bon mécanisme de contrôle d’accès (exclusion mutuelle, progression, attente bornée).
Explication : Cet algorithme est remarquable car il garantit l'exclusion mutuelle, la progression et l'attente bornée en combinant une variable de tour et des drapeaux indiquant l'intention d'entrer en section critique.
Exercice 4 : Algorithme de Dekker
L'algorithme de Dekker est historiquement l'une des premières solutions logicielles connues pour le problème de l'exclusion mutuelle à deux processus. Il est plus complexe que celui de Peterson mais repose sur des principes similaires.
C'est une solution logicielle qui utilise une variable tour et deux booléens initialisés à faux : p1_veut_entrer et p2_veut_entrer.
Déclarations communes :
var p1_veut_entrer : boolean ;
p2_veut_entrer : boolean ;
tour : 1..2 ;L'algorithme du Processus P1 est le suivant :
initialisations:
p1_veut_entrer := false ;
p2_veut_entrer := false ;
tour := 1 ; /* ou 2 */
repeat
p1_veut_entrer := true ;
while (p2_veut_entrer) do
if (tour = 2) then
begin
p1_veut_entrer := false ;
while (tour = 2) do ; /* attendre */
p1_veut_entrer := true ;
end ;
Section Critique
tour := 2 ;
p1_veut_entrer := false ;
Section Restante
until false ;- La propriété d'exclusion mutuelle est-elle préservée ?
- La propriété de non-blocage est-elle préservée ?
- Hypothèses : P2 est en attente dans la boucle
while(tour = 1)do;et P1 est en section critique. La propriété suivante est-elle vérifiée : « Si P1 conserve l'unité centrale, il peut exécuter sa section critique autant de fois qu'il le désire. En revanche, lorsque P1 a exécuté sa section de sortie, P2 peut entrer en section critique dès que l'unité centrale lui est accordée. » - Vérifier la propriété de progression : un processus en Section Restante ne peut pas empêcher un autre processus d'entrer en section critique.
- La propriété d'attente bornée est-elle réalisée si l'on adopte la convention suivante : « Lorsqu'un Processus Pi est dans sa section d'entrée avec le booléen
pi_veut_entrerà faux, il n'est provisoirement plus en attente de sa section critique. »
Questions Fréquemment Posées (FAQ)
Qu'est-ce que l'exclusion mutuelle en synchronisation de processus ?
L'exclusion mutuelle est une propriété de synchronisation qui garantit que, à tout moment, un seul processus peut accéder à une ressource partagée ou exécuter une section critique de code. Cela empêche les conflits et assure la cohérence des données dans un environnement multiprocessus.
Pourquoi l'attente active peut-elle être problématique ?
L'attente active, ou busy-waiting, implique qu'un processus attend qu'une condition devienne vraie en vérifiant continuellement son état, sans relâcher le processeur. Cela consomme inutilement des cycles CPU, réduisant l'efficacité globale du système, surtout si l'attente est longue et que le processeur n'est pas libéré pour d'autres tâches.
Quelles sont les propriétés essentielles d'un bon algorithme d'exclusion mutuelle ?
Un bon algorithme d'exclusion mutuelle doit garantir trois propriétés principales : l'exclusion mutuelle (un seul processus en section critique à la fois), la progression (si la section critique est libre et des processus veulent y entrer, l'un d'eux doit pouvoir le faire sans délai infini) et l'attente bornée (il existe une limite au nombre de fois où d'autres processus peuvent entrer dans la section critique pendant qu'un processus attend d'y entrer, évitant ainsi l'inanition).