Introduction
Dans une plateforme multiprogrammée, plusieurs processus s'exécutent
de manière concurrente et doivent souvent interagir pour accomplir des
tâches complexes. La communication entre ces processus se fait
généralement par le biais de données partagées, stockées soit en
mémoire principale, soit dans des fichiers. Cependant, cette
communication peut poser des problèmes, car l'accès concurrent à ces
données partagées peut entraîner des incohérences.
Lorsque plusieurs processus tentent d'accéder et de modifier
simultanément des ressources communes, il y a un risque de "conditions
de course". Dans ce contexte, le résultat final dépendra de l'ordre
d'exécution des processus, ce qui peut mener à des résultats imprévisibles
ou incorrects. Par conséquent, il est crucial de mettre en place des
mécanismes d'exclusion mutuelle pour garantir que les données partagées
sont protégées, et que chaque processus accède à ces données de
manière ordonnée et sécurisée.
Des solutions telles que les sections critiques, l'utilisation de sémaphores,
et les techniques d'attente active ou d'attente passive sont souvent
employées pour prévenir ces problèmes et garantir l'intégrité des
opérations interprocessus.
Exemple : la spoule d’impression:
Problème: le fichier B ne sera jamais imprimé
Sections critiques et exclusion mutuelle
Le problème des conflits d'accès à une ressource partagée, comme dans le
cas d'une spoule d'impression, survient lorsque plusieurs processus
tentent d'accéder à la même ressource simultanément. Ces conflits
peuvent entraîner des résultats imprévisibles et des dysfonctionnements
dans l'exécution des processus.
La partie du programme à partir de laquelle on accède à la ressource
partagée est appelée: section (région) critique.
Solution: L’exclusion mutuelle est une méthode qui assure qu’un seul
processus est autorisé d’accéder à une ressource partagée; les autres
processus seront exclus de la même activité.
Pour garantir une exclusion mutuelle efficace, quatre conditions
essentielles doivent être respectées :
1.Exclusion mutuelle :
Deux processus ne doivent jamais être dans leur section critique en
même temps. Cela assure que la ressource partagée n'est accédée que
par un seul processus à la fois.
2.Progression :
Si aucun processus n'est dans sa section critique, un processus à
l'extérieur de sa section critique ne doit pas empêcher les autres de
progresser. Autrement dit, si un processus souhaite entrer dans sa section
critique, et qu'aucun autre n'y est, il doit être autorisé à le faire.
3.Absence de famine (ou d’interblocage) :
Aucun processus ne doit être bloqué indéfiniment en essayant d'accéder
à sa section critique. Il doit y avoir une garantie que, tôt ou tard, chaque
processus qui en fait la demande pourra entrer dans sa section critique.
4.Absence d'hypothèses sur la vitesse ou le nombre de
processeurs :
L'algorithme de gestion de l'exclusion mutuelle ne doit pas se baser sur
des suppositions concernant la vitesse des processeurs ou leur nombre.
Les processus doivent fonctionner correctement quelles que soient les
vitesses relatives des processeurs ou des temps d'exécution des
instructions.
Exclusion mutuelle par attente active
L’exclusion mutuelle par attente active est une technique dans laquelle
un processus attend activement (en exécutant une boucle ou en vérifiant
continuellement une condition) jusqu’à ce qu'il puisse accéder à la section
critique. Cette méthode, bien que simple, peut consommer des ressources
processeur inutilement si un processus passe trop de temps à attendre.
a. Algorithme d’accès à une section critique :
l'algorithme d'accès à une section critique, incluant les étapes essentielles
pour gérer l'entrée, l'exécution et la sortie d'une section critique. Cet
algorithme garantit l'exclusion mutuelle et gère l'attente des processus.
Entrer_Section_Critique () /* attente si SC non libre */
Section_Critique() /* un seul processus en SC */
Quitter_Section_Critique() /* libérer l'accès à la SC */
b. Solutions d'attente active
Pour gérer l'accès à une section critique, plusieurs solutions basées sur
l'attente active sont couramment utilisées. Chacune de ces solutions
présente des caractéristiques particulières, des avantages et des
inconvénients :
Masquage des interruptions :
Variables de verrouillage
Alternance stricte
Solution de Peterson
Masquage des interruptions
Dans cette approche, un processus désactive les interruptions pendant
qu'il est en train d'exécuter la section critique. Cela garantit que le
processus ne sera pas interrompu par d'autres processus, permettant une
exécution exclusive. Bien que cela puisse être efficace pour un seul
processeur, cette méthode peut engendrer des problèmes dans des
systèmes multiprocesseurs, car elle empêche l'exécution d'autres
processus sur des cœurs différents, ce qui peut réduire l'efficacité globale
du système.
Lorsqu’un processus entre en section critique il doit masquer les
interruptions
Pas de commutation de processus
Lorsqu’ il quitte sa section critique il doit restaurer les interruptions.
C’est une solution matérielle qui permet de résoudre
complètement le problème. Mais elle est dangereuse en mode
utilisateur s’il oublie de restaurer les interruptions.
Variables de verrouillage
Un verrou est une primitive qui contrôle l'accès à une section critique.
Lorsqu'un processus souhaite entrer dans la section critique, il doit d'abord
acquérir le verrou. Si le verrou est déjà détenu par un autre processus, le
processus en attente doit continuer à vérifier activement (polling) si le
verrou est disponible. Cette méthode est simple à implémenter, mais elle
peut entraîner une consommation élevée de ressources processeur
lorsque de nombreux processus tentent d'accéder simultanément à la
section critique.
le verrou est variable binaire partagée qui indique la présence d’un
processus en section critique.
si verrou=0 alors section critique libre
si verrou=1 alors section critique occupée
Cette solution ne garantit pas l’exclusion mutuelle car le
verrou est une variable partagée qui peut constituer aussi
une section critique.
Alternance stricte
Cette méthode impose une alternance stricte entre deux processus.
Chaque processus doit attendre que l'autre ait terminé sa section critique
avant de pouvoir entrer à son tour. Bien que cela garantisse l'exclusion
mutuelle, cela peut également mener à une inefficacité, car un processus
peut rester inactif alors que la section critique est libre, entraînant ainsi
une perte de temps et de ressources.
Tour est une variable partagée qui indique le numéro de processus
autorisé à entrer en section critique.
Mais, un processus qui possède Tour peut ne pas être intéressé
immédiatement par la section critique et en même temps il bloque un
autre processus qui demande.
Problème de famine
Solution de Peterson
L'algorithme de Peterson est un mécanisme pour assurer l'exclusion
mutuelle entre deux processus. Il utilise deux variables : une pour indiquer
l'intention d'entrer dans la section critique et une autre pour déterminer
quel processus a la priorité d'accès. Ce mécanisme est efficace pour éviter
les conflits d'accès et garantir que les deux processus peuvent s'exécuter
sans interférence. Toutefois, il est limité à deux processus et peut devenir
complexe lorsqu'il s'agit de gérer plus de deux processus.
Cette solution assure complètement l’exclusion mutuelle. Mais, le
processus qui attend sa section critique consomme du temps processeur
inutilement (attente active).
Primitives sleep et wakeup
L'exclusion mutuelle sans attente active repose sur l'idée que, lorsqu'un
processus ne peut pas entrer dans la section critique, il n'attend pas
activement en consommant inutilement des ressources processeur. Au lieu
de cela, il passe à un état bloqué et ne sera réveillé que lorsqu'il pourra
accéder à la section critique. Cette approche est beaucoup plus efficace
que l'attente active, surtout dans des systèmes où de nombreux processus
se disputent l'accès à une ressource partagée.
1.Les primitives sleep et wakeup :
sleep : Lorsqu'un processus ne peut pas entrer dans la section
critique, il appelle la primitive sleep qui le met en état de blocage.
Le processus reste inactif et ne consomme pas de temps processeur.
wakeup : Lorsqu'un processus quitte la section critique, il appelle la
primitive wakeup pour réveiller un processus bloqué, lui
permettant ainsi d'essayer à nouveau d'entrer dans la section
critique.
2.Application des primitives Sleep et Wakeup: (modèle Producteur
Consommateur)
Deux processus (le producteur et le consommateur) coopèrent en
partageant un même tampon:
Le producteur produit des objets qu’il dépose dans le tampon.
Le consommateur retire des objets du tampon pour les consommer.
3.Analyse de cette solution :
1.L’accès à la variable compteur n’est pas protégé, ce qui peut
entraîner des incohérences dans les valeurs prises par cette Variable.
2.Réveils perdus : c’est le principal défaut de ce mécanisme. Un signal
wakeup envoyé à un processus qui ne dort pas encore.
les Sémaphores
Pour remédier au problème des réveils perdus, on utilise un mécanisme
plus robuste appelé sémaphore. Le sémaphore est une variable entière
qui contrôle l'accès à une ressource partagée, et à laquelle est associée
une file d'attente des processus bloqués. Ce mécanisme garantit
qu'aucun signal de réveil n'est perdu et permet de gérer de manière
efficace l'exclusion mutuelle sans attente active.
sémaphore=0 🡪 aucun réveil n’est mémorisé
sémaphore>0 🡪 un ou plusieurs réveils sont en attente
Un sémaphore s est manipulé par les opérations :
down(s) : - décrémente la valeur de s si s>0,
- si s=0, alors le processus est mis en attente.
up(s) : - incrémente la valeur de s,
- si un ou plusieurs processus sont en attente sur ce sémaphore,
l'un d'entre eux est réveillé,
Un sémaphore S est une variable entière qui est accessible uniquement
par deux opérations atomiques, lesquelles sont mutuellement exclusives
(c'est-à-dire qu'elles ne peuvent pas être interrompues ni exécutées
simultanément par plusieurs processus) :
1. down(S) (également appelée P() ) :
Vérifie la valeur du sémaphore.
Si la valeur du sémaphore est positive, elle est décrémentée.
Si la valeur du sémaphore est égale à zéro, le processus est mis en
sommeil et ajouté à une file d'attente jusqu'à ce que le sémaphore
soit de nouveau disponible.
1. up(S) (également appelée V() ) :
Vérifie la valeur du sémaphore.
Incrémente la valeur du sémaphore.
Si des processus sont en attente (bloqués), un processus est réveillé
pour reprendre son exécution.
