56
CNAM Cyril FRANCONIE Architecture des Systèmes Informatiques 1 ARCHITECTURE des SYSTEMES INFORMATIQUES Cours B4 Cyril FRANCONIE Processus...

Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

  • Upload
    others

  • View
    16

  • Download
    1

Embed Size (px)

Citation preview

Page 1: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques1

ARCHITECTUREdes

SYSTEMES INFORMATIQUES

Cours B4Cyril FRANCONIE

Processus...

Page 2: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques2

Architecture des Systèmes

HistoriqueArchitecture d'un Ordinateur / d'un processeurObjectif et rôle d'un Système d'exploitationNotions de base / Mécanismes fondamentauxEntrées / SortiesLes ProcessusOrdonnancementLa MémoireMesures de performancesLes standardsEt l'avenir ...?

Page 3: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques3

Les Processus

Définition (déjà vue)ReprésentationInteractionsSynchronisationEtude de l'implémentation sous Unix/linux

Page 4: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques4

Représentations d'un processus

Une modélisation des processus nous permettra d'analyser leur comportement, et donc d'en

Vérifier le bon fonctionnementDétecter les problèmes tels que blocagestirer des algorithmes de gestion....

Différents modèles existes :Systèmes de tâches et précédenceAutomatesRéseaux de PétriRéseaux colorés...

Page 5: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques5

Système de tâches

Un processus va être décomposé en N tâches élémentaires

P = suite de Tâches = T1 T

2,... T

n

Chaque tâche est ensuite décomposée en 3 éléments :L'événement d, qui correspond à une phase d'initialisation : exemple : lecture d'une valeur en mémoire.Le corps de la tâche : opération sans interaction avec l'extérieur => ne sera pas considéré.L'événement f, qui correspond à une phase de fin de tâche : exemple écriture d'une valeur dans un registreDonc pour un processus séquentiel:P = T

1 T

2,... T

n = d

1f1d

2f2...d

nfn

Page 6: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques6

Graphe de précédence

Dès qu'un processus n'est plus simplement séquentiel, la simple connaissance de la liste des tâches ne suffit plus.

Notion de précédence, c'est à dire d'ordre d'exécution.Notation sous forme de graphe :(exemple tjrs séquentiel)

Lorsque le graphe est sans redondance, (plus petite relation), c'est le « graphe de précédence »

T1

T2

T3

Page 7: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques7

Processus avec parallélisme

Quand des tâches sont indépendantes au sein d'un processus, le graphe devient non séquentiel :

T1 est une tâche initiale.T4 est une tâche terminaleT2 et T3 sont indépendantes.

T1

T2 T

3

T4

Page 8: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques8

Un peu de formalisme

Alphabet = ensemble des événements qui constituent le processus A = {d1, f1, d2, f2, ...dn,fn}Mot = description temporelle de la suite des événements de cet alphabet.

pour l'exemple précédent :m1 = {d1 f1 d2 d3 f2 f3 d4 f4}m2 = {d1 f1 d2 f2 d3 f3 d4 f4}

sont deux mots décrivant deux comportements possibles

Langage = ensemble de tous les mots possibles associés à un graphe de précédence donné.

Page 9: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques9

Notation de la relation de précédence

on note E l'ensemble des tâches du processus P, et « < » le relation de précédence :

Ti < Tj veut dire simplement que Ti doit précéder TjCette relation a certaines propriétés :

On ne peut avoir T < TOn ne peut avoir à la fois T1 < T2 et T2 < T1Elle est transitive : T1 < T2 et T2 < T3 => T1 < T3

Le système de tâche est l'ensemble (E, <)

Page 10: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques10

Combinaison de systèmes de tâches

On appelle produit de deux systèmes l'exécution séquentielle de ces deux systèmes

On doit relier toutes les tâches terminales du premier, à toutes les tâches initiales du second :

T1

T2

T3

T4 T

5

T6

T8

T7

X =

T1

T2

T3

T4

T5

T6

T8

T7

Page 11: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques11

Combinaison de systèmes de tâches (2)

La combinaison parallèle de deux systèmes s'obtient facilement en juxtaposant les deux : il n'y a aucun liens entre les deuxPour un produit de 2 systèmes, le Langage résultant est la simple concaténation des deux langages, mot par mot pris deux à deux.Pour la combinaison parallèle, le langage résultant est plus difficile à obtenir.

Page 12: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques12

Application à l'étude des systèmes

Ce modèle nous permettra d'étudier trois aspects de l'interaction de processus :

Vérifier si le système est déterminé, c'est à dire si deux exécutions différentes, à partir des même conditions initiales, donnent toujours le même résultat.Déterminer le graphe de parallélisme maximalDétecter les blocages potentiels.

Page 13: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques13

Exemple

Soit le système suivant :T1 : X=read(5)T2 : X=X+ZT3 : Print YT4 : Z=read(7)T5 : Y=X+Z

Pour les motsd1 f1 d4 f4 d2 f2 d5 f5 d3 f3

on obtient l'affichage Y=19d1 d4 f1 f4 d2 d5 f2 f5 d3 f3

Affichage Y= 12Le système est non déterminé, donc inexploitable.

T1

T2

T4

T3

T5

Page 14: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques14

Système déterminé

On introduit d'abord la notion d'état du système avec la grandeur M = ensemble de la mémoire utilisé par les processus.Un système est donc dit déterminé si :

Pour une valeur définie M0.∀ m ∈ Langage(S); S = système (E,<)L'état final M est le même.

On peut aussi introduire les références suivantes

Li = domaine de lecture de la tâche i = ensemble des cellules mémoire lues par la tâche, pendant l'événement d

i, donc

Ei = domaine d'écriture de la tâche i = ensemble des cellules mémoire modifiées par la tâche, pendant l'événement f

i, donc

Page 15: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques15

Système déterminé (2)

On introduit la notion de tâches non interférentes :T1 et T2 sont non-interférentes entre elles si :

T1<T2 ou T2<T1Ou : L1∩ E2 = L2 ∩ E1 = E1 ∩ E2 = ∅.= Conditions de Bernstein

Si un système est constitué de taches 2 à 2 non-interférentes, il est déterminé, ce qui est le but à atteindre.

Page 16: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques16

Reprenons l'exemple

T1 : X=read(5)T2 : X=X+ZT3 : Print YT4 : Z=read(7)T5 : Y=X+Z

On voit clairement que :T1 et T5 sont interférentesT2 et T4 de mêmeT2 et T5 aussiT5 et T3

Si on impose T2 < T5, le graphe déterminé devient :

T1

T2

T4

T3

T5

T1

T2

T4

T3

T5

Page 17: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques17

Parallélisme maximal

Le but est de réduire au mieux un système de tâches, de façon à avoir le plus grand parallélisme, donc le meilleur taux d'utilisation de la CPU.Il est évident que le système réduit et le système initial doivent donner les même résultats ; c.a.d qu'ils doivent être équivalents :

S(E,<) et S'(E, <') sont équivalents s'ils sont tous les 2 déterminés, et si l'état final Mf de la mémoire est le même, pour un même état M

0.

Une autre définition impose que la suite des état de la mémoire soit identique dans les 2 cas, mais c'est sans doute trop restrictif.

Page 18: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques18

Parallélisme maximal (2)

Un système de tâche sera de parallélisme maximale si :

La suppression de tout arc (T, T') du graphe (c.a.d la suppression d'une relation de précédence T<T' ou T'<T), entraîne l'interférence des tâches (T,T'), donc le non-déterminisme du système.Soit de façon plus formelle :

(T1<T2 ou T2 < T1) et (L1∩ E2 ≠∅ ou L2 ∩ E1 ≠∅ ou E1 ∩ E2 ≠∅) et E1 E2 non vides.

La technique de construction de ce système minimal consiste à éliminer tous les arcs redondants, c.a.d. la fermeture transitive de la relation <

Page 19: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques19

Exemple de réduction

Soit le processus séquentiel suivantP :

X=2Y=F(4)Z = Y+G(7)A= X+Y+5B= 2*Y+ZC= (A+B) * ZA += YD= A+B+C

T1

T2

T4

T3

T5

T7

T6

T8

=

Page 20: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques20

Exemple – Etape 1

Déterminer le tableau des domaines de lecture et écriture

Taches \ Variables X Y Z A B C DT1:X=2 ET2:Y=F(4) ET3:Z = Y+G(7) L ET4:A= X+Y+5 L L ET5:B= 2*Y+Z L L ET6:C= (A+B) * Z L L L ET7:A += Y L E/LT8:D= A+B+C L L L E

Page 21: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques21

Exemple Etape -2

Lister les interférences :Le tableau est symétrique transversalement

Taches T1 T2 T3 T4 T5 T6 T7 T8T1:X=2T2:Y=F(4)T3:Z = Y+G(7)T4:A= X+Y+5T5:B= 2*Y+ZT6:C= (A+B) * ZT7:A += YT8:D= A+B+C

Page 22: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques22

Exemple - Etape 3

Déterminer, à partir de ce tableau, les relations à imposer pour éviter des interférences :

T1 < T4T2 < T3, T4, T5, T7T3 < T5, T6T4 < T6 , T7, T8T5 < T6, T8T6 < T7, T8T7 < T8

Page 23: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques23

Exemple – Etape 4

Supprimer, dans le graphe séquentiel d'origine, les arcs non essentiels = ceux qui n'entraineront pas d'interférences :

T1

T2

T4

T3

T5

T7

T6

T8

T1

T2

T4

T3

T5

T7

T6

T8

Page 24: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques24

Exemple – Etape 5Ajouter tous les arcs trouvés par l'étude des interférences;Puis, supprimer les arcs redondants = les plus courts !

T1

T2

T4

T3

T5

T7

T6

T8

T1

T2

T4

T3

T5

T7

T6

T8

x

x

xx

x

xx

Page 25: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques25

Blocages

Blocage entre N processus sous 4 conditions:Les ressources considérées ne sont pas partageablesLes ressources ne sont pas réquisitionnablesUn ensemble de ces ressources est en attente circulaire par les processus considérés, tout en étant tenues par les même processus.

Exemple : graphe d'allocation

P1

P2

R1 R2

requête

alloué à requête

alloué à

Page 26: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques26

Blocages (2)

La modélisation par système de tâches est modifiée:

à un événement di(l) , sera associé l'allocation des ressources de l'étape l.à un événement fi(l), libération des ressources étape l, ET requête pour les ressources de l'étape l+1.

Systèmes modernes plus sensibles au blocage car

Programmation parallèleSystème de Processus communicantsPartage de ressources dynamique pour de meilleures performances.Manipulation d'objets sans avoir forcément la connaissance des verrous utilisés implicitement....

Page 27: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques27

Résolution du problème

Pour remédier au problème du blocage, trois techniques de bases

Si un blocage est détecté, on met en oeuvre un mécanisme de reprise. (détection/reprise)En s'assurant qu'une des trois conditions citées ci-dessus n'est pas remplie. => préventionEn contrôlant pas à pas l'exécution du système pour vérifier qu'on ne rentre pas dans une telle situation => évitement.

Page 28: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques28

Détection – reprise

La détection est « relativement » facileExploration des processus et des ressources qu'ils tiennent de façon exclusive

Le problème est plutôt de permettre la repriseRéquisitionner des ressources implique :

Soit de tuer un processusPeut laisser le système dans un état incorrectSoit de provoquer une reprise arrière d'un processus pour qu'il libère ses ressourcesGénéralement faisable pour les système transactionnels (Bases de données...)

Page 29: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques29

Prévention

Basiquement, il faut supprimer une des quatre conditions :

Rendre les ressources partageablesPouvoir réquisitionner les ressourcesEmpêcher un processus de se mettre en attente avec des ressources détenues.Supprimer l'attente circulaire

Page 30: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques30

Prévention 1

Rendre les ressources partageablesPeu réaliste en réalité;certains type de ressources, comme les verrous, ne peuvent être qu'exclusif.Exemple possible : fichiers accédés en lecture.Dans certains cas particuliers, on peut améliorer la situation en augmentant le nombre d'instances d'une classe de ressource donnée.

plus de mémoire...

Page 31: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques31

Prévention 2

Pouvoir réquisitionner les ressourcesDifficile à réaliser :

nécessite que le processus à qui on prend des ressources puisse faire « machine arrière »faisable pour la gestion de bases de données avec transactions.

Certains cas simples sont implicites :réquisition de la CPU par un processus prioritaireréquisition de mémoire par déplacement d'un processus moins prioritaire sur disque.

Page 32: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques32

Prévention 3

Empêcher un processus de se mettre en attente avec des ressources détenues.

3 solutions :Allouer TOUTES les ressources avant le début de l'exécution du processus.

Fonctionne, si on peut définir la liste des ressources.très peu efficace en terme d'utilisation CPU et ressourcesSolution des machines mono-programmées ; fonctionnement séquentiel.

N'autoriser la requête et l'attente sur une ressource que si le processus n'en détient aucune.

simple si on peut l'implémenterpeu réaliste

Libérer toute les ressources et les ré-allouer toutes (+ la nouvelle) à chaque étape.

peu réaliste dans les faits

Page 33: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques33

Prévention 4

Supprimer l'attente circulaireintroduire une relation d'ordre entre les ressources= Les allouer toujours dans le même ordre !Très efficace; utilisé par exemple dans la gestion de mémoire virtuelle de ChorusOSNe réponds peut-être pas à tous les problèmesOn veut éviter le style de programmation idiot suivant :

P1 :...lock(R1)....lock(R2)...

P2 :...lock(R2)....lock(R1)...

Page 34: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques34

EvitementReprenons l'exemple à deux processus et deux ressources

Il y a blocage si un processus tiens une ressource et attends l'autre, et réciproquement.Représentable par un graphe d'évolution :

xk+1

= xk+1 et y

k+1= y

k si ak est un événement de P1

xk+1

= xk et y

k+1= y

k+1 si ak est un événement de P2

R2

R2

R1

R1

P1

P2Zone de blocage

Zone interdite

Chemin A possible

Chemin B possible

Page 35: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques35

Evitement (2)

L'algorithme d'évitement doit vérifier avant chaque transition qu'on reste dans un état sûr, c.a.d qu'on ne rentre pas dans la zone interdite.Cela implique la connaissance de TOUTES les tâches de chacun des processus, en terme de demande et libération de ressources

Contrainte très forte de spécification d'un systèmepeu réalisable dans les faits.on va considérer une hypothèse plus faible qui sera suffisante bien que non nécessaire :

Page 36: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques36

Algorithme du banquier

Chaque processus i va devoir indiquer le nombre maximum de ressources Rj détenues pour une exécution séquentielle : MAXijA chaque étape, le système va analyser l'étape suivante en supposant que TOUS les processus actifs vont arriver à cet état maximal.

actif = qui tient des ressources ou en a demandé.on prend le cas le plus défavorable.

Si l'état fictif maximal suivant est non bloqué, alors la requête est accordée.Sinon, la requête est rejetée, ce qui provoquera la mise en attente du processus demandeur.

Page 37: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques37

Algorithme du banquier (2)

Avantages :fonctionne

InconvénientsConsommation de CPU pour l'analyse de l'état du système !implique qu'un processus :

définisse une fois pour toute sa requête maximaledéfinisse pour chaque étape ses besoins pour l'étape suivante

Fortes contraintes de programmation...

Page 38: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques38

Blocages : conclusion

Peu d'algorithmes implémentables facilement au sein d'un système d'exploitationLes méthodes sont souvent à adapter au cas considérés : pas de méthodes génériquesOn trouve au sein des OS des parties de solutions de prévention pour des cas particuliers.

ex :relation d'ordre dans l'allocation des ressources.Souvent, les utilisateurs, et les programmeurs, préfèrent un blocage occasionnel à des contraintes fortes de programmation/spécifications.

Page 39: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques39

Synchronisation

On a vu qu'il était important pour un système d'être déterminé !Mais parfois, un graphe de précédence définis des contraintes trop fortes :exemple :

soit la gestion d'un compte bancaire Bun versement se traduit par : B = B + Vun retrait par : B = B - RVersements et retraits effectués en parallèle.

Dans cet exemple on a :T1 : B = B+V ; soit d1 = lecture de B et V, f1 = écriture de BT2 : B = B-R; d2 = lecture de B et R, f2 = écriture de B

Page 40: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques40

Exemple de synchronisation (suite)

Si on laisse le système suivant s'exécuter :

B=0

T1

T'1

T2

T'2

On risque d'avoir les exécutions suivantes :d1 f1 d2 f2 d'1 f'1 ... : correctd1 d2 f1 f2 ... : incorrect

Page 41: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques41

Notion de section critique

On pourrait être tenté de définir les relations :

Cela introduit une trop forte dépendance, car on n'autorise qu'un des comportementsOn introduit alors la notion de section critique :

ensemble d'instructions (tâches) qui doivent être exécutées par un seul processus à un instant donnéelles sont en exclusion mutuelle

T1

T2

T1

T2

ou

Page 42: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques42

Section critiquePour l'étude on considérera les processus en boucle suivants :

répéter<section normale> (non critique)<section critique>

jusqu'à faux;La notion de section critique conduit à introduire deux nouvelles sections :

répéter<section normale> (non critique)

<section d'entrée><section critique>

<section de sortie>jusqu'à faux;

Page 43: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques43

Section critique (suite)

Chaque processus attend dans la section d'entrée une certaines conditions, puisexécute sa section critique en exclusion mutuelleIndique sa sortie de section critique dans la section de sortie.

On distinguera :des solutions logicielles et matérielles simples à ce problème,des solutions de plus haut niveau.

Page 44: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques44

Solutions logicielles élémentaires

Variable « relais »« Drapeaux » de demande d'entréeAlgorithme de PetersonSémaphores

Etudes sur cas à 2 processus; Avec plus de processus, la solution logicielle devient rapidement trop complexe.

Page 45: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques45

Variable « relais »

Chaque processus va « donner » le relais à l'autre, et ne pourra entrer en section critique que s'il a obtenu le relais

relais = une variable entière, initialement à 1.P1 P2répéter répéter <section normale 1> <section normale 2> tant que RELAIS = 2, boucler tant que RELAIS = 1, boucler <section critique 1> <section critique 2> RELAIS = 2 RELAIS = 1jusqu'à faux; jusqu'à faux;

Page 46: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques46

Variable « relais »

inconvénients : impose une alternance stricte d'exécution des sections critiquesattente active.Si un des processus s'arrète (en section normale), l'autre ne peux plus entrer en section critique (il le fait 1 fois en fait)

condition de progression non respectéeex:Mécanisme utilisé pour gérer les buffers ethernet entre le Hardware et le software...

Page 47: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques47

« Drapeaux » de demande d'entrée.

Chaque processus signale son désir d'entrer en section critique par un « drapeau », que l'autre processus doit tester

P1 P2répéter répéter <section normale 1> <section normale 2> D1 = vrai D2 = vrai tant que D2 = vrai, boucler tant que D1 = vrai, boucler <section critique 1> <section critique 2> D1 = faux D2 = fauxjusqu'à faux; jusqu'à faux;

La condition de progression est cette fois vérifiéeMais risque de blocage !!! avec D1=vrai, D2=vrai simultanément => solution non acceptable.

Page 48: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques48

Algorithme de PetersonAdaptation des 2 solutions précédentes pour remédier aux problèmes évoqués :

L'algorithme (symétrique toujours) est :Pi (i=1 ou 2)répéter <section normale i> Di = vrai RELAIS = 3-i tant que (D

3-i = vrai et RELAIS = 3-i), boucler

<section critique 1> Di = fauxjusqu'à faux;

Cet algorithme vérifie les propriétés :exclusion mutuelleabsence de blocageprogression dans tous les caset aussi attente bornée : un processus ne peut pas exécuter plusieurs fois sa S.C au détriment de l'autre.

Page 49: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques49

Semaphores

Variable de type entierDeux opérations :

s.P() : prendre le sémaphore : si s ≤ 0 , boucler, sinon s=s-1s.V() : valoriser le sémaphore : s=s+1

Un sémaphore initialisé à 1 réalise facilement une exclusion mutuelle (mutex)

une section critique est donc encadrée par :s.P(); <section critique>s.V();

Un sémaphore initialisé à une valeur k permet à k processus d'accéder simultanément à leur « SC »

Page 50: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques50

Remarque

Problème des solutions abordées jusqu'à présent : l'attente active

consomme la CPUPeut introduire un blocage si :

un processus de basse priorité tiens un lock,un processus de haute priorité cherche à avoir le même lock

=> il boucle en attente active et donc empêche le processus de basse priorité de libérer le lock !

=> toute solution offerte par l'OS devra faire appel à des files d'attentes .

Le test du lock, et la mise en file d'attente doivent se faire de manière indivisible !Files d'attente de type FIFO par priorité, en général

Page 51: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques51

Solutions matérielles

Masquage des interruptionsInstructions « test and set »

Page 52: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques52

Masquage des interruptions

Généralement au niveau processeur, pour se prémunir contre toute causes possible de préemption

non sélectif : bloque l'ensemble du systèmene respecte pas la priorité des processusDangereux hors du système lui-même.

Technique utilisé néanmoins au sein du système Ne fonctionne pas tel quel avec plusieurs processeurs.

Page 53: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques53

Instruction matérielle spécifique

Appelée « test and set » ou « exchange »AtomiquePrincipe :

Ecrire une valeur dans la cellule mémoire indiquée (1 pour TAS), et retourner la valeur stockée précédemment dans le registre :

ex intel : XCHG (%reg), %eaxon ecrit 1, et on verifie ensuite s'il y avait deja 1 en mémoire :

si oui, le lock était déjà pris => on doit re-bouclersi non, on a le lock.

C'est un mutex simple.Cette instruction est en général utilisée pour implémenter des mutex au sein de l'OS.

Page 54: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques54

Solutions de plus haut niveau

Les solutions précédentes ont l'inconvénients de reposer sur le bon vouloir et les capacités du programmeur

risque de blocage si erreur de conceptionou risque de corruption des sections critiques qu'on veut protéger

On introduit donc de nouveaux mécanismes, offerts par les langages de programmations :

Moniteurs« Sérialiseurs »Expression de séquence d'opérations (« path expression »)...

Page 55: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques55

Moniteur

Structure regroupant des ressources à partager, et les opérations permettant d'y accéderUn seul processus peut être actif au sein d'un moniteur

exclusion mutuelle impliciteExemple : le compte en banque :

Moniteur : compte var N : entierdébut : N = 0;fin;procédure depot(V) { N = N+V; }procédure retrait (V) { N = N -V; }Un retrait : compte.retrait(V); Un dépôt : compte.depot(V);

Page 56: Architecture des Systèmes Informatiques …alexandre.grorud.free.fr/Formation/CNAM/Architecture%20...Architecture des Systèmes Informatiques 2 Architecture des Systèmes Historique

CNAM Cyril FRANCONIE

Architecture des Systèmes Informatiques56

Moniteur (suite)

Typiquement en Java : les objets « synchronized »

Faiblesse des moniteurs :Accès en un seul « bloc », pas de finesse de synchronisationInadapté par exemple au cas des « lecteurs/écrivains »on introduit la notion de variable « condition », qui sont en fait des files d'attentes liés au moniteur, et qui permettent de libérer, temporairement l'accès exclusif, au sein d'une procédure.

X : conditionX.wait(), X.signal() les 2 méthodes

Voir exemple (TD) des lecteurs/écrivainsen Java : wait(), notify();