ModuleModuleSystèmes d’exploitationSystèmes d’exploitation
Chapitre 6
Communication Interprocessus
Partie I
École Normale SupérieureÉcole Normale SupérieureTétouanTétouan
Département InformatiqueDépartement Informatique
2008-2009
2
RevueRevue
• Quand est-ce que l’on prend des décision d’ordonnancement?
• Quels sont les buts de l’ordonnancement pour les systèmes interactifs
• Quels facteurs sont pris en compte quand on veut désigner une grandeur de quantum pour l’algorithme tourniquet?
3
SynopsisSynopsis
• Introduction• Concurrence critique (Race Conditions)• Sections critiques• Exclusion mutuelle• Exclusion mutuelle par attente active
– 1ère solution: Masquage des interruptions– 2ème solution: Variables de verrouillage– 3ème solution: Alternance– Instruction TSL
• Synthèse
4
IntroductionIntroduction
• Les processus concurrents s’exécutant dans le système d’exploitation peuvent être des processus coopératifs ou indépendants.– Un processus est indépendant s’il n’affecte pas les autres
processus ou ne peut pas être affecté par eux.
– Un processus qui ne partagent pas de données avec d’autres processus est indépendant
– Un processus est coopératif s’il peut affecter les autres processus en cours d’exécution ou être affecté par eux
– Un processus qui partage des données avec d’autres processus est un processus coopératif. Les données partagées par les processus coopératifs peuvent se trouver en :
• Mémoire principale (RAM)• Fichiers partagés• Registres d’unité périphérique
5
IntroductionIntroduction
• Les processus d’un se ne s’exécutent pas de manière
isolée (indépendant). Certains processus ont besoin de
coopérer, et nécessitent donc des moyens de
communication et de synchronisation, et d’autres se
trouvent en compétition pour les ressources du système,
soit à cause de la nature physique de la ressource (non
partageabilité), soit parce que les opérations sur cette
ressource peuvent provoquer des incohérences ou des
interblocages.
6
IntroductionIntroduction
• Exemple– Considérons la procédure suivante de mise à jour d’un compte
bancaire d’un client. Pour simplifier, on considère qu’un compte est implémenté par un simple fichier qui contient le solde courant du client:
Procedure crediter_compte( entier numero_client, entier somme)entier solde ; debut solde=lire_dans_fichier(numero_client); /* lecture du solde dans
le fichier du client */ solde = solde - somme ;
ecrire_dans_fichier(numero_client, solde) ; /* écrire dans le fichier le nouveau solde */fin;
7
• Supposons maintenant que cette même procédure est exécutée simultanément par deux processus P0 et P1 dans un système d’exploitation à temps partagé. Sans faire aucune hypothèse sur la durée du quantum, on peut faire les exécution suivantes :
P0 : P1 :
crediter_compte( 1233, 1000) crediter_compte( 1233, 500)
solde = lire_dans_fichier(1233) ; solde = lire_dans_fichier(1233) ;
// P0 est bloqué !
solde=solde-1000 ; solde=solde-500
Ecrire_dans_fichier(1233,solde) ; Ecrire_dans_fichier(1233,solde)
IntroductionIntroduction
88
IntroductionIntroduction
• Le problème dans le programme précédent est dû aux conflits d’accès au même fichier (précisément le variable solde). Ces accès sont en lecture et en écriture. Évidemment, il ne peut y avoir de conflit si les accès aux données ne sont qu’en lecture seule.
• On appelle section critique la partie d’un programme où se produit le conflit d’accès
• Comment éviter ces conflits d’accès ?– Il faut trouver un moyen d’interdire la lecture ou l’écriture des
données partagées à plus d’un processus à la fois– Il faut une exclusion mutuelle qui empêche les autres
processus d’accéder à des données partagées si celles-ci sont en train d’être utilisées par un processus
– Dans l’exemple précédent, il faut obliger le processus P1 à attendre la terminaison de P0 avant d’exécuter à son tour la même procédure
9
Concurrence critiqueConcurrence critique
• Une Concurrence critique est une situation où deux processus ou plus essaient de partager des données et le résultat dépend de l’ordre dans lequel chaque processus exécute
• Donc la place dans le code où une condition de concurrence critique peut arriver est d’intérêt particulier et s’appelle une section critique (ou région critique)
10
Sections critiquesSections critiques
• Idéalement, nous essayons de ne pas avoir des sections dans le code où la concurrence critique peut arriver, mais cela n’est pas toujours possible.
• Les programmes doivent être arrangés ou dessinés de tel façon à ce qu’aucun groupe de processus n’opère dans leurs section critique (commune) en même temps
– Les sections critiques doivent être mutuellement exclusive
11
Sections critiquesSections critiques
• Pour que les processus qui partagent des objets (données en mémoire centrale ou dans fichiers) puissent coopérer correctement et efficacement, quatre conditions sont nécessaires :
1. Exclusion mutuelle : deux processus ne peuvent être en même temps en section critique ≡ Aucune paire de processus ne doit être dans leurs sections critique en même temps.
2. Famine : aucun processus ne doit attendre trop longtemps avant d’entrer en section critique ≡ Un processus ne devrait pas avoir à attendre indéfiniment pour entrer dans sa section critique.
3. Interblocage (deadlock) : aucun processus suspendu en dehors d’une section critique ne doit bloquer les autres d’y entrer ≡ Un processus qui n’opère pas dans sa section critique ne doit pas bloquer un autre processus
4. Aucun hypothèse ne doit être faite sur les vitesses relatives des processus ou du nombre de CPU.
12
Une représentation graphique de notre requis pour l’exclusion mutuelle
Exclusion MutuelleExclusion Mutuelle
13
Exclusion MutuelleExclusion Mutuelle
• Un processus désirant entrer dans une section critique doit être mis en attente si la section critique n’est pas libre
• Un processus quittant la section critique doit le signaler aux autres processus
• L’attente peut être :– Active : la procédure entrer_Section_Critique est une
boucle dont la condition est un test qui porte sur des variables indiquant la présence ou non d’un processus en section critique
– Non active : le processus passe dans l’état endormi et ne sera réveillé que lorsqu’il sera autorisé à entrer en section critique
14
Exclusion MutuelleExclusion Mutuelle
• Protocole d’accès à une section critique :
<entrer_Section_Critique> //attente si SC non libre
<Section_Critique> //un seul processus en SC
<Quitter_Section_Critique> // signaler la libération de la
SC aux autres processus
• Que contiennent les procédures entrer_Section_Critique et quitter_Section_Critique?
15
• Trois solution potentielles :
1. Masquer (ou désactiver) les interruptions
2. Utiliser des variables verrous
3. Alternance
Exclusion mutuelle par attente activeExclusion mutuelle par attente active
16
Exclusion mutuelle par attente activeExclusion mutuelle par attente active11èreère solution : Masquage des interruptions solution : Masquage des interruptions
– Chaque processus désactive les interruptions quand ils entre dans leur section critique. Aucun changement de contexte ne peut arriver.
– L’exclusion mutuelle est réalisée à travers la mise en œuvre de primitives (appels) du SE :
DisableInterrupt()
section_critique()
EnableInterrupt()
17
Exclusion mutuelle par attente activeExclusion mutuelle par attente active11èreère solution : Masquage des interruptions solution : Masquage des interruptions
• Problème: Si le processus utilisateur entre dans une boucle infinis le SE sera planter
• Problème: Que ce passe-t-il avec des CPU multiples?
• Problème: Si la section critique est large, qu’est ce qui ce passe si un périphérique a besoin d’attention
• Solution viable? Non.
18
while (verrou == 1) ; //Attente
verrou=1 ; //Verrouillage
section_critique()
verrou=0 ; //Déverrouillage
Exclusion mutuelle par attente activeExclusion mutuelle par attente active22èmeème solution : Variables de verrouillage solution : Variables de verrouillage
• Un verrou (Lock) est une variable binaire partagée qui indique la présence d’un processus en SC:– si verrou = 0 alors la section critique est libre.
– si verrou = 1 alors la section critique est occupée.
• Quand un processus veut entrer dans sa section critique il examine le verrou.
• L’exclusion mutuelle est réalisée dans ce cas :
19
Exclusion mutuelle par attente activeExclusion mutuelle par attente active22èmeème solution : Variables de verrouillage solution : Variables de verrouillage
– Problème: L’exclusion mutuelle n’est assurée que si le test et le positionnement du verrou est ininterruptible (sinon le verrou constitue une section critique). Pour cela il faut disposer d’une instruction (Test and Set) qui teste et modifie le contenu d’un mot en mémoire centrale de façon indivisible.
– Solution viable? Non.
20
Exclusion mutuelle par attente activeExclusion mutuelle par attente active33èmeème solution : Alternance solution : Alternance
• Le problème dans l’algorithme précédent est que les deux processus modifient la même variable en même temps. Pour éviter cela, on peut mettre en œuvre une variable partagée tour (turn) qui mémorise le numéro du processus autorisé à entrer en section critique.
• Exemple d’utilisation pour N processus :
while (tour != pid) ; // attente active (son tour)
section_critique()
tour=(pid +1) % N ; // au suivant!
section_non_critique
21
Exclusion mutuelle par attente activeExclusion mutuelle par attente active33èmeème solution : Alternance solution : Alternance
• Problème: la 2ème règle est violée (famine), un processus possédant tour, peut ne pas être intéressé immédiatement par la section critique.
• Problème: la 3ème règle est violée – si A exécute plus vite que B, A attend pour entrer dans sa région critique pendant que B exécute du code non critique.
• Solution viable? Non. Mais c’est proche...
22
Exclusion mutuelle par attente activeExclusion mutuelle par attente active33èmeème solution : Alternance solution : Alternance
Solution de Peterson (1981)//Cas de deux processus P0 et P1 :
#define N 2int tour ; // variable tourint interesse[N] ; // initialisé à False
void entrer_Section_Critique (pid) //n° de processus : 0 ou 1{interesse[pid]=True ; // indiquer qu’on est intéressétour = pid ; //lever le drapeauwhile (tour == pid && interesse[1-pid] == True) ;}
void quitter_Section_Critique(pid){interesse[pid]=False ;}
23
Exclusion mutuelle par attente activeExclusion mutuelle par attente active33èmeème solution : Alternance solution : Alternance
• Solution de Peterson
– Section critique est maintenant protégée
– Considérons la situation où les deux processus appellent entrer_Section_Critique simultanément. Les deux processus sauvegarderont leur numéro dans la variable tour. La valeur sauvegardée en dernier efface la première. Le processus qui entrera en SC est celui qui a positionné la valeur tour en premier
– Solution viable? Oui!
• Par contre l’attente active est encore requise… une perte de temps du CPU
• Notez aussi que le processus ne peut pas tricher: si les processus n’appelle pas entrer_Section_Critique et quitter_Section_Critique, la solution ne marchera pas
24
Exclusion mutuelle par attente activeExclusion mutuelle par attente activeInstruction TSLInstruction TSL
• Cette solution au problème de l’exclusion mutuelle est basée sur un support matériel, à savoir une instruction spécifique du langage machine.
• TSL veut dire instruction Test and Set Lock– Plusieurs ordinateurs supportent cette instruction ou
une instruction semblable– Comment est-ce utilisé? TSL AX,verrou
• Charge (TEST) le contenu d’un mot mémoire dans un registre, puis met une valeur non-nulle (SET) à cet emplacement mémoire, ces deux opérations étant garanties comme indivisible.
25
Exclusion mutuelle par attente activeExclusion mutuelle par attente activeInstruction TSLInstruction TSL
• Comment utiliser l’instruction TSL?
• Solution viable? Oui! (Avec attente active...)
entrer_Section_Critique :
TSL AX, $verrou //Lecture et positionnement du verrou
CMP AX, 0 //Test si verrou non déjà positionné
JNZ entrer_Section_Critique //Boucle si verrou déjà positionné
RET
quitter_Section_Critique:
MOV $verrou, 0
RET
26
SynthèseSynthèse
• Le problème de toutes les approches que nous avons vues est qu’elles mettent en œuvre des mécanismes d’attente active (spin lock): les processus désirant entrer en SC consomment énormément de ressource processeur, et font un usage abusif du bus mémoire.
• De plus, dans le cas d’un système orienté temps-réel où les priorités relatives des processus sont strictement respectées, si un processus H de haute priorité désire entrer en SC alors q’un processus B de basse priorité s’y trouve déjà, H aura toute la ressource processeur pour boucler et B ne pourra jamais quitter la section critique, d’où blocage des deux processus.
• Y a t-il des mécanismes d’exclusion mutuelle qui évitent l’attente active ?
27
Quiz Time!Quiz Time!
Questions?