Module Systèmes dexploitation Chapitre 6 Communication Interprocessus Partie I École Normale Supérieure Tétouan Département Informatique 2008-2009

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


• 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


• 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)


88


• 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


• 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


• 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


• 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


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


• 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?

Documents

Module Systèmes dexploitation Chapitre 6 Communication Interprocessus Partie I École Normale Supérieure Tétouan Département Informatique 2008-2009