Systèmes d’Exploitation 2 - freealilou.free.frfreealilou.free.fr/CV_MCF_fichiers/Mes_Cours/Diapos cours SE-2.pdf · Systèmes d’Exploitation 2 Ali Larab, L2-info, CUFR, 08-09

Systèmes d’Exploitation 2Systèmes d’Exploitation 2

Ali Larab, L2-info, CUFR, 08-09 Systèmes d'Exploitation (2ème partie) 1

Ali LarabL2-info, CUFR d’Albi

2008-2009

Présentation du module « S.EPrésentation du module « S.E--2 » 2 »

Objectif : – Approfondir les notions acquises dans le module SE-1 (Notions sur

l'organisation interne et gestion des mémoires et fichiers).

Volume horaire :– 30h (10h cours + 10h TD + 10h TP).

Contenu :– Fonction d’un SE : approfondir les points abordés dans le module SE-1– Gestion des fichiers (Fichiers et catalogues : accès et protection)


– Gestion des fichiers (Fichiers et catalogues : accès et protection)– Gestion des mémoires (principale et secondaires)– Gestion des processus : Organisation d'un SE, concepts de processus, ressources

API, gestion des conflits…

Thèmes de TP : – TP de gestion de fichiers, de la mémoire et des processus.

Evaluation : – Contrôle de connaissances sur table + Evaluation TP ( compte rendu ! ).

BibliographieBibliographie

• Andrew Tanenbaum, Systèmes d'exploitation, Pearson Education (2ème édition), France, ISBN: 2-7440-7002-5.

• J. Archer Harris, Systèmes d'exploitation, Edisciences, 2002, ISBN:2100065130.


• Valérie Martinez, Windows 2000 Professionnel – Notions de base, Edition Dunod, 2001, ISBN:2100046284.

• Jerry Peek, Grace Todino, John Strang, Introduction à Unix, Edition O'Reilly, 2002, ISBN: 978-2841772094.

• ...

Cours 1 Cours 1


Cours 1 Cours 1 Gestion de fichiersGestion de fichiers

Rappels: Définition d'un SE

Un SE (ou OS pour Operating System) est le programme fondamental des programmes systèmes.

Son rôle est de gérer tous les périphériques et de fournir aux programmes utilisateur une interface simplifiée avec le matériel.


matériel.

Il contrôle donc toutes les ressources de l'ordinateur et fournit la base sur laquelle seront construits les programmes d'application.

Fonctions d'un SEFonctions d'un SE (1/5)(1/5)

LeLe SESE aa doncdonc 22 fonctionsfonctions principalesprincipales ::

1. Extension de la machine,�� Machine virtuelle ou machine étendue ,


2. Gestion des ressources .


11.. ExtensionExtension dede lala machinemachine (Machine(Machine virtuelle)virtuelle)� Fournir à l'utilisateur l'équivalent d'une machine virtuelle

plus simple à programmer que la machine réelle. � Masquer les éléments fastidieux liés au matériel (gestion

des interruptions, des horloges, de la mémoire, des périphériques

(déplacement du bras de lecture d'un disque dur)).� Le SE: Créer une interface de programmation plus abstraite qui lui


� Le SE: Créer une interface de programmation plus abstraite qui lui permet de manipuler les périphériques d'une manière plus simple.

• Ex. Présenter le disque dur comme un fichier qu'il faut ouvrir, manipuler (lecture/écriture), puis fermer.

–L'interface de programmation offerte par le SE = ensemble de services que les programmeurs peuvent solliciter par le billet d'instructions spéciales appelées « appels systèmes ».


22.. GestionGestion desdes ressourcesressources (1/3)

– Un ordinateur = ensemble de ressources.– Plusieurs programmes peuvent s'exécuter sur cet ordinateur. Ces

programmes nécessitent de la mémoire, des accès disque et des accès ou utilisation des ressources.

• Le rôle du SE dans ce cas est de gérer de manière équitable, optimale et sans conflit l'allocation des processeurs, de la


optimale et sans conflit l'allocation des processeurs, de la mémoire et des périphériques d'E/S aux différents programmes concurrents qui les sollicitent.

Ex. - Impression simultanée,- Accès aux fichiers,- Autorisation/interdiction d’accès à certaines ressources.

� Partage de ressources



�� PPartageartage dede ressourcesressources::– Dans le temps : Gérer l'accès dans le temps à l'imprimante, à un fichier ou

à la CPU. �Le choix du programme qui va bénéficier de la ressource est la tâche du SE.

– Dans l'espace : Au lieu d'attendre son tour, certaines ressources permettent d'être partagées.


• On peut par exemple partager la mémoire principale entre les processus ou programmes actifs qui s'exécutent à un instant t.

Remarque: � Le rôle du SE est de trouver le juste milieu entre le partage de la ressource dans le

temps et dans l'espace. Ex1. Ne pas allouer toute la mémoire à un seule programme qui n'a besoin que de

quelques kilo octets et de laisser les autres attendre l'utilisation de la CPU. Ex2. Ne pas partager la mémoire entre tous les programmes à un instant t (la mémoire

n'est pas suffisante).



Les ressources à gérer :Les ressources à gérer :– Les fichiers,– Les entrées/sorties,– Les processus,


– Les processus,– La mémoire.

� Points à détailler tout au long de ce module.

Système de Gestion de Fichiers Système de Gestion de Fichiers

(SGF)(SGF)


(SGF)(SGF)



Les ressources à gérer :Les ressources à gérer :– Les fichiers,– Les entrées/sorties,– Les processus,


– Les processus,– La mémoire.

Le Système de Gestion des Fichiers Le Système de Gestion des Fichiers (SGF)(SGF)

• Le SGF est la partie la plus visible d’un SE

• Le SGF permet d’accéder à divers périphériques (disque dur, clé USB,

lecteur de disquette, de CD-ROM et de DVD).

• Rôle: Gérer les fichiers et offrir des primitives pour manipuler ces


• Rôle: Gérer les fichiers et offrir des primitives pour manipuler ces fichiers.– Ces primitives et les appels système qui leur correspondent sont appelés

par l’interpréteur de commande.

• Le SE a pour charge d’établir une correspondance entre la notion logique de fichier et le secteur physique sur lequel le fichier est recopié.

Le Système de Gestion des Fichiers Le Système de Gestion des Fichiers (SGF)(SGF)

Tâches d’un SGFTâches d’un SGF1. Offrir une interface conviviale pour manipuler les fichiers2. Stocker les fichiers sur le disque3. Gérer l’espace libre sur le disque4. Gérer les fichiers dans le cas d’un environnement multi-


4. Gérer les fichiers dans le cas d’un environnement multi-utilisateurs

5. Donner des utilitaires pour le diagnostique, la récupération en cas d’erreur, l’organisation des fichiers.

SGFSGF

Supports de stockageSupports de stockage•• Disque durDisque dur


SGFSGF

Supports de stockageSupports de stockage•• Disque durDisque dur


SGFSGF

Supports de stockageSupports de stockageFormatage d’un support magnétique (disque dur) :Formatage d’un support magnétique (disque dur) :• Formatage de bas niveau (usine)

– Formatage standard: Toutes les pistes ont le même nombre de secteurs

– Formatage complexe: Le nombre de secteur par piste est de plus en


– Formatage complexe: Le nombre de secteur par piste est de plus en plus petit au fur et à mesure qu’on se dirige vers le centre.

• Formatage de haut niveau: organiser les pistes et les secteurs d’une manière compréhensible par le SE.– Chaque SE organise ses pistes et secteurs à sa manière � il est

par exemple possible qu’un disque formaté sous Linux ne puisse être lu sous DOS.

SGFSGF

Supports de stockageSupports de stockagePartitionnement d’un disque Partitionnement d’un disque :• C’est le fait de diviser le disque en partitions.• La partition est une zone du disque qui peut être considérée comme un

disque logique à part. � lecteur logique.• Chaque partition peut recevoir un SE différent. il suffit que le disque

soit amorçable et que le programme d’amorçage du système soit placé


soit amorçable et que le programme d’amorçage du système soit placé dans le secteur de boot.– Ex. commande DOS « fdisk » permet de partitionner le disque en plusieurs

lecteurs. Idem pour l’utilitaire gparted/qparted sous Linux.

• Une fois le disque est partitionné, on peut formater chacune de ses partitions pour le SE qui va la gérer.– Ex. FAT16, FAT32, NTFS, EXT2, EXT3

SGFSGFConcept de fichierConcept de fichier (1/2)

• Un fichier = ensemble de secteurs sur le disque• Le SE doit présenter le stockage des données sur le disque d’une

manière plus simple aux utilisateurs.


� Tout SGF intègre la notion de fichier et de répertoire.

SGFSGFConcept de fichierConcept de fichier (2/2)


SGFSGF

Concept de répertoire (catalogue, directory)Concept de répertoire (catalogue, directory) (1/2)

• La notion de répertoire est créée pour l’organisation de fichiers• Le SE a besoin d’une organisation afin de structurer ses fichiers et de

pouvoir y accéder rapidement.• Un répertoire est vu comme un fichier quand il est stocké sur le disque

et est destiné à contenir des fichiers.• Plusieurs structures:


• Plusieurs structures:– Structure plate à un niveau : on peut avoir plusieurs répertoires mais

chacun d’eux ne peut contenir que des fichiers (pas de répertoire).– Structure à deux niveaux : chaque utilisateur a son propre répertoire

lequel peut contenir des fichiers et des répertoires. Ces sous-répertoires ne peuvent contenir que des fichiers.

– Structure arborescente : on peut avoir un ensemble arbitraire de répertoires et de fichiers. Les répertoires peuvent avoir des sous-répertoires et ainsi de suite (pas de limite).

SGFSGF

Concept de répertoire (catalogue, directory)Concept de répertoire (catalogue, directory) (2/2)

• Du point de vu d’un SGF, un répertoire est un fichier qui dispose d’une structure logique (un tableau qui possède une entrée par fichier).

Données

Répertoire Fichier


Données

NomFich Attributs Info sur le stockage du fichier

NomRep Attributs Info sur le stockage du fichier

NomFich Attributs Info sur le stockage du fichier

Structure d’un répertoire

Structure logique d’un répertoire

SGFSGF

Création d’un fichier (répertoire) par le SECréation d’un fichier (répertoire) par le SE1. Créer la structure de données qui décrit le fichier (ou le répertoire).

– Tout fichier doit être décrit afin que le syst puisse le connaître et le reconnaître. � permet au SE d’organiser au mieux les fichiers

– Les attributs des fichiers sont sauvegardés dans cette structure de données. • Un fichier et un répertoire ne sont pas décrits par la même structure de données.

2. Créer le fichier proprement dit.


2. Créer le fichier proprement dit.– Allouer au fichier un certain nombre de blocs sur le disque selon sa taille– Le contenu d’un bloc sera différent selon qu’il s’agisse d’un fichier ou d’un

répertoire. • Les blocs d’un fichier contiennent des données sans aucune structure

particulière, alors que les blocs d’un répertoire ont une structure bien précise (contiennent des noms et des attributs de fichiers et de sous-répertoires).

SGFSGFOrganisation des fichiers sur le disqueOrganisation des fichiers sur le disque• Les méthodes utilisées pour l’allocation des secteurs (blocs) sur le disque à

un fichier (ou un répertoire) sont propre au SGF et par conséquent au SE �différence entre DOS, Linux…

• Techniques d’allocation des blocs sur le disque:Comment organiser les blocs ou les clusters d’un fichier sur le disque. � il y a 3 (voire 4) manières :


1. Allocation contiguë : Le fichier est enregistré sur des blocs consécutifs sur le disque

2. Allocation chaînée : On divise le fichier en plusieurs blocs qu’on enregistre à des endroits espacés et on les relie avec des liens.

3. Allocation indexée : Les blocs sont indépendants mais on conserve dans une structure statique ou dynamique (bloc index) les numéros des blocs appartenant au fichier.

4. i-nodes : Associer à chaque fichier une structure de données contenant les attributs et les adresses du disque des blocs du fichier.

SGFSGF

Techniques d’allocation des blocs sur le disqueTechniques d’allocation des blocs sur le disque (1/2)

1) Allocation contiguë1) Allocation contiguë• C’est le mode d’allocation le plus implicite• Pour chaque fichier à enregistrer, le système recherche une zone

suffisamment grande pour accueillir le fichier. � Le fichier sera constitué de plusieurs blocs contigus.


Description d’un fichier dans un système qui applique l’allocation contiguë.

Nom du fichier Attributs Adresse de début longueur

SGFSGFTechniques d’allocation des blocs sur le disqueTechniques d’allocation des blocs sur le disque (2/2)

1) Allocation contiguë1) Allocation contiguëAvantages:- Rapidité d’accès. Pour lire les différents secteurs, il suffit d’attendre qu’ils

passent sous la tête de lecture/écriture � accès séquentiel.- Adaptée au CD-ROM, car la taille de tous ses fichiers est connue à l’avance et

ne changera jamais lors de l’utilisation ultérieure du système de fichier du CD-ROM.


ROM. Inconvénients:N’est plus utilisée pour diverses raisons:- Difficulté de prévoir la taille qu’il faut réserver pour le fichier. En plus un fichier

est amené à augmenter- Perte d’espace: car prévoir plus d’espace, risque de ne pas l’occuper, alors

que prévoir moins d’espace risque d’être insuffisant.- Fragmentation: des trous après suppression d’un fichier. Comment remplir ces

trous � avec le temps, apparition de petits trous dont la taille ne suffit pas pour allouer un fichier. � nécessite défragmentation.

SGFSGFTechniques d’allocation des blocs sur le disqueTechniques d’allocation des blocs sur le disque

2) 2) Allocation par liste chaînéeAllocation par liste chaînée (1/2)

• Elle consiste à allouer des blocs chaînés entre eux au fichier.• Le premier mot de chaque bloc sert de pointeur sur le bloc suivant (Le

mot du dernier bloc = 0), Le reste du bloc contient les données. � Un fichier peut désormais être

éparpillé sur le disque Bloc 0 Bloc 1 Bloc 2 Bloc 3 Bloc 4

Fichier A

0


éparpillé sur le disque puisque chaque bloc permetde retrouver le bloc suivant.

Bloc 0 du

fichierBloc physique 4

Bloc 1 du

fichier

7

Bloc 2 du

fichier

2

Bloc 3 du

fichier

10

Bloc 4 du

fichier

12

Bloc 0 du

fichier

6

Bloc 1 du

fichier

3

Bloc 2 du

fichier

11

Bloc 3 du

fichier

14

Fichier B

0

Bloc physique

Figure . Stockage d’un fichier à l’aide d’une liste chaînée de blocs de disque.


2) 2) Allocation par liste chaînéeAllocation par liste chaînée (2/2)

Avantage : – Par rapport à l’allocation contiguë, il n’y a pas d’espace perdu dans une

fragmentation du disque.

Inconvénient :


Inconvénient : – Accès lent aux fichiers (fichiers non séquentiels), car pour accéder au bloc n,

le système doit démarrer au début et lire les n-1 blocs précédents, un par un.– La perte d’un chaînage entraine la perte de tout le reste du fichier.

SGFSGF

• Pour éliminer les problèmes de la méthode précédente, on prend les pointeurs de chaque

Techniques d’allocation des blocs sur le disqueTechniques d’allocation des blocs sur le disque

3) 3) Allocation par liste chaînée utilisant une table en Allocation par liste chaînée utilisant une table en mémoire (allocation indexée) mémoire (allocation indexée) (1/2)(1/2)


prend les pointeurs de chaque bloc du disque et on les range dans une table en mémoire.

• Cette table s’appelle la FAT(File Allocation Table, table d’allocation de fichier).

SGFSGFTechniques d’allocation des blocs sur le disqueTechniques d’allocation des blocs sur le disque3) Allocation par liste chaînée utilisant une table en 3) Allocation par liste chaînée utilisant une table en

mémoire (allocation indexée) (2/2)mémoire (allocation indexée) (2/2)Avantages :• Plus de problème d’indexation de la méthode précédente. � La plupart des SE actuels appliquent ce mode:

– MS-DOS utilise la FAT– Widows NT utilise la MFT


– Widows NT utilise la MFT– UNIX utilise le I-Node

Inconvénient : • La table prend beaucoup d’espace mémoire (elle doit se trouver en mémoire tout

le temps sinon paginée). Si le disque a n blocs et la taille d’une entrée est de koctets, on aura besoin de kn octets (valeur fixe).

– Exemple : pour un disque de 20 Go ayant des blocs de 1Ko, la table doit contenir 20 millions d’entrées. Si 1 entrée = 3 octets, la table occupera 20 Mo.


4) 4) II--nodes (nœuds d’information)nodes (nœuds d’information)• Associer à chaque fichier une structure de données appelée i-node,

laquelle inclut les attributs et les adresses du disque des blocs du fichier.• Exemple : Attribut du fichier A : adresse disque du bloc 0, adresse disque du bloc 1,

adresse disque du bloc 2, adresse disque du bloc 3… Adresse d’un bloc de pointeurs).


Avantage : • l’i-node n’a besoin d’être en mémoire que lorsque le fichier correspondant

est ouvert. � Si un i-node occupe n octets et k fichiers doivent être ouverts simultanément, on aura besoin que de kn octets (alors que dans la méthode précédente on a besoin d’un espace grand et fixe, relatif à l’espace du disque et de ses blocs).

SGFSGF

SGF MSSGF MS--DOS DOS �� FATFAT (1/2)

• Chaque disque formaté avec MS-DOS contient un répertoire racine qui contient des fichiers et des sous-répertoires

• Chaque entrée d’un répertoire a une taille de 32 octets:

Nom_Fich Attributs Adresse du 1er bloc du fichier ou du répertoire


Une entrée de répertoire dans MS-DOS

• Méthode intéressante et prévenant: en ne mettant que le 1er bloc, on ne limite pas la taille du fichier.

• MS-DOS associe un tableau où chaque indice contient la valeur du prochain bloc associé au fichier.

• Mesure de sécurité: deux copies de la FAT sont enregistrées près du répertoire racine.

Nom_Fich Attributs Adresse du 1 bloc du fichier ou du répertoire

SGFSGF

SGF MSSGF MS--DOS DOS �� FATFAT (2/2)

N°cluster Valeur2 5

3 0

4 0

Exo1.c … … 2


� Exo1.c = {cluster 2, 5 et6}

Schéma structurel de la FAT

4 0

5 6

6 FFFFh

… …

SGFSGF

SGF UNIX SGF UNIX �� II--NodeNode (Nœud d’index)

Fig1: Structure d’une entrée de répertoire sous UNIX

•Remarque: Aucune identité pour le fichier sur l’I-Node � se fait dans le rép associé au fichier

Nom Fich ou rép Numéro d’I-NodeTaille

Date de création

Compteur de liens

UID

GID

Bloc d’indirection simple

b.i double

256 @ de blocs sur le disque


Node � se fait dans le rép associé au fichier•Taille d’un I-Node: 64 octets.

•Les blocs physiques contiennent soit les données du fichier, soit l’adresse d’autres blocs physiques. On parle alors de blocs d’indirection.

GID

…

Adresse sur le disque du 1er

bloc associé au fichierAddr 1

Addr 2

…

Addr 10

PS

PD

PT

b.i triple

b.i simple

b.i double

b.i simple

Fig2: Structure d’un I-Node

SGFSGF

SGF Windows NT SGF Windows NT �� NTFSNTFS• Windows NT propose: FAT16, FAT32, et NTFS• NTFS utilise une structure de données organisée en table

nommée Master File Table (MFT) pour gérer les fichiers.• MFT contient des informations détaillées sur les fichiers et


• MFT contient des informations détaillées sur les fichiers et les répertoires.

Structure d’une entrée de la MFT

entête Attributs NomFich données Attributs de sécu

SGFSGF

Gestion des fichiers dans un environnement Gestion des fichiers dans un environnement multimulti--utilisateursutilisateurs

Partage de ressource et d’accès aux fichiers � Problème de sécurité

� définir des droits d’accès précis au fichier


� Accès différent au fichier selon que l’utilisateur est : propriétaire, membre du groupe du propriétaire ou autres utilisateurs.

Ex. (rwx r-x - -x) � propriétaire peut lire, écrire et exécuter le fichier, les membre du groupe de cet utilisateur peuvent accéder en lecture à ce fichier et l’exécuter. Les autres ne peuvent qu’exécuter ce fichier (ne peuvent ni le modifier, ni le lire).

SGFSGF

Lien symbolique et lien physiqueLien symbolique et lien physiqueUtile pour le partage de fichiers ou de répertoires.Unix offre 2 types de liens: symbolique et physique.• Les liens symboliques représentant des pointeurs virtuels (raccourcis)

vers des fichiers réels. – La suppression du lien symbolique ne supprime pas le fichier pointé. – Commande: ln -s nomFichReel NouvLien


– Commande: ln -s nomFichReel NouvLien

• Les liens physiques représentent un nom alternatif pour un fichier. – La suppression de l'un ou l'autre de ces liens n'entraine pas la suppression

du fichier. Plus exactement, tant qu'il subsiste au minimum un lien physique, le fichier n'est pas effacé. En contrepartie lorsque l'ensemble des liens physiques d'un même fichier est supprimé le fichier l'est aussi.

– Commande (sans option s): ln nom-du-fichier-reel nom-du-lien-physique

SGFSGF

Implémentation des répertoiresImplémentation des répertoires (1/2)(1/2)

1) Rép simple contenant des entrées de taille fixe : a) rép=liste d’entrées, dont la taille est fixée, qui correspondent chacune à un fichier.

Chaque entrée contient un nom de fichier (d’une longueur donnée), une structure des attributs du fichier et une ou plusieurs adresses disques précisant la localisation des blocs de disque.

b) Pour les syst fonctionnant avec les i-nodes: stocker les attributs dans les i-nodes plutôt que dans les entrées de répertoires.


nodes plutôt que dans les entrées de répertoires.

Toto

Jeux

Cours

internet

Toto attributs

Jeux attributs

Cours attributs

internet attributs

Structure de données contenant les attributs

a) Rép simple avec des entrées de taille fixe

a) Rép simple dans lequel chaque entrée fait référence à un i-node

SGFSGFImplémentation des répertoiresImplémentation des répertoires (2/2)(2/2)2) Rép avec des noms longs et de longueur variable :

a) une partie fixe qui débute par la longueur de l’entrée, suivie de données au format fixe (propriétaire, date création, droits d’accès…), nom de fichier qui est variable. � inconvénient: trous après effacement d’un fichier.

b) Entrée de rép=longueur fixe + garder les noms de fichiers ensemble dans un tas à la fin du répertoire

Fichier 1 : longueur d’entrée Fichier 1 : attributs Entrée

Pointeur vers le nom du fichier 1 Fichier 1 : attributs

Entrée d’un fichier


a) sur une ligne b) dans un tas

Fichier 1 : attributs p r o j e t - - b u d g e t Fichier 2 : longueur d’entrée

Fichier 2 : attributs p e r s o n n e l

Fichier 3 : longueur d’entrée Fichier 3 : attributs

f o O …

Entrée d’un

fichier

Fichier 1 : attributs Pointeur vers le nom du fichier 2

Fichier 2: attributs Pointeur vers le nom du fichier 3

Fichier 3: attributs …

p r o j e t - - b u d g e t p e r s o n n e l f o o …

fichier

tas

SGFSGFLes fichiers partagésLes fichiers partagés• Plusieurs utilisateurs � besoin de partager des fichiers• Faire apparaître ce fichier dans les différents répertoires qui

appartiennent aux différents utilisateurs

CBA

Répertoire racine


CBA

Système de fichier contenant un fichier partagé

SGFSGF

Gestion de l'espace disqueGestion de l'espace disque

1. Taille des blocs2. Mémorisation des blocs libres3. Quotas d'espace disque


SGFSGF

Gestion de l'espace disqueGestion de l'espace disque1. 1. Taille des blocsTaille des blocs• Fichiers stockés sur disque � gestion espace disque = important.• Stratégies de stockage: allocation consécutive (contiguë) ou division par

blocs de taille fixe. • Taille des blocs = secteur, piste, cylindre?

- Petits blocs dégradent les performances (trop de blocs � trop de déplacements


- Petits blocs dégradent les performances (trop de blocs � trop de déplacements

et de rotation � vitesse de lecture lente), mais améliorent l’utilisation du disque. - Grands blocs améliorent les performances mais perte d’espace

disque (perte de 97% de l’espace disque)?.

� Taille moyenne: pour UNIX= 1 Ko, Windows NT=~2 Ko (mais change selon la taille du disque)

SGFSGFGestion de l'espace disqueGestion de l'espace disque2. 2. Mémorisation des blocs libresMémorisation des blocs libres• Après avoir choisi la taille du bloc � passer à la mémorisation de l’espace libre. • Utiliser soit une « liste chaînée » soit une « table de bits » :

a) Une liste chaînée de blocs contenant chacun des numéros de blocs libres.1 seul vecteur de blocs en mémoire !.

Ex. si 1 vecteur de blocs = 1 Ko, numéro de bloc sur 32 bits � on enregistre 255 (=256-1 pour


Ex. si 1 vecteur de blocs = 1 Ko, numéro de bloc sur 32 bits � on enregistre 255 (=256-1 pour pointer sur le prochain bloc) blocs libres dans un seul vecteur de bloc.

Si disque = 16 Go � besoin d’une liste de 16 794 blocs pour contenir les 2^24 vecteurs de blocs du disque.

b) Une table de n bits pour un disque de n blocs (ex. 1: si bloc vide, 0: s’il est alloué).

Ex. Un disque de 16 Go a 2^24 blocs de 1 Ko, et nécessite ainsi 2^24 bits pour la table. Ce qui fait 2048 blocs (inférieur à celui des listes chaînée).

42 36 11 67 516 230 162 612 342 482 86 234 897 422 141

10101100 00110000 00110111 11000011 11111111

SGFSGF

Gestion de l'espace disqueGestion de l'espace disque3. 3. Quotas d'espace disqueQuotas d'espace disque• Systèmes multiutilisateur � plusieurs utilisateurs en même temps �

risque d’occupation de tout le disque• Fournir un moyen qui permet d’attribuer des quotas d’espace disque

(logicielles, matérielles).– L’administrateur définit la capacité max de fichiers et de blocs pour chacun


des utilisateurs et le SE vérifie que l’utilisateur n’a pas dépassé ce quotas.

– Si un utilisateur augmente la taille d’un fichier, on enlève cette taille du quotas attribué au propriétaire du fichier !

• "Table des fichiers ouverts" � "Table des quotas". Le fichier des quotas est MAJ quand tous les fichiers sont fermés.

– Limites logicielles peuvent être dépassées, mais pas les limites matérielles.

Ex. gestion des profils � supprimer des fichiers (temporaires) avant de se déconnecter.

SGFSGFFiabilité du système de fichiersFiabilité du système de fichiers• Plus grave panne dans un ordinateur = destruction d’un syst de fichier.

– Restauration de données difficile, voire impossible.

• Sauvegarde : – Pas toute les données � juste une partie du syst de fichiers – Deuxième sauvegarde: juste la partie modifiée depuis la dernière sauvegarde

(copies incrémentales)

– Notion de copie logique/copie physique


• Cohérence du système de fichier– Modification: Lire des blocs, les modifier puis les réécrire – Si le syst tombe en panne avant la réécriture � incohérence.

• Le pb est plus grave si les blocs concernés = blocs i-nodes, blocs de répertoires, blocs contenant la liste des blocs libres.

– Vérification de cohérence • Un bloc est soit libre soit utilisé, sinon incohérence.• Ex. de logiciel de vérif de cohérence: fsck (sous UNIX) ou scandisk

(sous Windows)

SGFSGFPerformance du système de fichiersPerformance du système de fichiers• Un accès disque est beaucoup plus lent qu’un accès en mémoire • Optimisation : Concevoir un syst de fichier de telle manière à

augmenter les performances des accès disque :a) Mémoire cache : prendre une partie du disque (qlq blocs) et les

conserver en mémoire.b) Lecture anticipée des blocs : mettre des blocs en mémoire

cache avant d’en avoir besoin. � utile uniquement avec des


cache avant d’en avoir besoin. � utile uniquement avec des fichiers lus séquentiellement.

c) Réduction du mouvement du bras d'un disque : en rapprochant les blocs susceptibles d’être adressés en séquence et en les plaçant de préférence sur le même cylindre.

�� Système de fichier LFS (voir diapo suivante).

SGFSGFLe système de fichier LFSLe système de fichier LFS• Amélioration technologiques: Rapidité CPU ↑ , capacité disque ↑ , taille

mémoire ↑. • Par contre la rapidité (temps d'accès et de déplacement) disque est le

seul paramètre à ne pas être concerné par ces améliorations.� parfois mène même à des réductions des performances

• Solution : un nouveau type de système de fichiers: LFS (Log-structuredFile System, système de fichier structuré en lots d'enregistrements).


File System, système de fichier structuré en lots d'enregistrements).• Principe du Syst. LFS : Satisfaire une quantité non négligeable de

demandes de lectures directement depuis la mémoire cache, sans avoir besoin des accès disques.

• � Toutes les écritures sont tamponnées en mémoire, et périodiquement écrites sur le disque dans un seul segment à la fin de l'ensemble des enregistrements (à l’avenir, probablement la plupart des accès disque seront des accès en écriture).

SGFSGF

Exemples de système de fichiers– Système de fichiers de CD-ROM (ISO 9660)– Système de fichiers CP/M– Système de fichiers MS-DOS– Système de fichiers Windows 98 et NT


– Système de fichiers Windows 98 et NT – Système de fichiers UNIX

� à détailler dans ce qui suit

SGFSGFExemples de système de fichiersExemples de système de fichiers (1/8)

1. Système de fichiers de CD1. Système de fichiers de CD--ROMROM (ISO 9660) (1/2)

• Système simple, car conçu pour des support en écriture seule• N’offre pas la possibilité de garder trace des blocs libres• Chaque CD-ROM :

– Commence par 16 blocs (fonction non définie: ex. pour booter…)– Un bloc qui comprend le descripteur primaire de volume (a des info générales sur le


– Un bloc qui comprend le descripteur primaire de volume (a des info générales sur le CD et une entrée répertoire pour le répertoire racine (ie où trouver le rép racine qui permet de localiser le sys de fichier).

Octets 1 1 8 8 7 1 2 4 1 4-15

Localisation du fichier Taille du fichier Date et heureNum CD

LNom

du fichsys

L’entrée du répertoire de la norme ISO 9660.

Lgueur de l’enregistrement des attributsLgueur de l’entrée de répertoire

drapeauxintervalle Nom.ext;ver

Padding


1. Système de fichiers de CD1. Système de fichiers de CD--ROMROM (ISO 9660) (2/2)

• Norme ISO 9660 trop restrictive � il faut des extensions pour représenter des sys de fichiers autres que les sys simples tels que MS-DOS

Deux (2) extensions pour la norme du sys de fichier ISO 9660:


Deux (2) extensions pour la norme du sys de fichier ISO 9660:• Rock Ridge : pour représenter les sys de fichiers UNIX sur CD-ROM

et les restaurer par la suite correctement sur un sys différent. • Joliet : pour permettre à un sys Windows d’être copié sur un CD-

ROM et d’être restauré par la suite


2. Système de fichiers CP/M2. Système de fichiers CP/M• Le système d’exploitation CP/M (Control Program for Microcomputers) peut

être vu comme l’ancêtre de MS-DOS, mais des syst d’exploitation futurs (embarqués) peuvent se baser sur certains de ses principes de fonctionnement (ex. n’a besoin que de 16 Ko de RAM pour démarrer, simple…).

• Le sys de fichier CP/M dispose d’un seul répertoire, qui comprend des entrées


de taille fixe (32 octets)• Après démarrage (boot) le CP/M parcourt le répertoire et crée un tableau des

blocs de disque libres (en recherchant les blocs qui n’appartiennent à aucun fichier). • À l’arrêt du sys, le tableau n’est pas sauvegardé. � vérification de cohérence:

pas nécessaire.

Octets 1 8 3 1 2 16 (Numéros de blocs disque)

Code utilisateur Nom du fichierType-fich (extens)

ordre RéservéCptr de

blocdate Num du 1er bloc taille

Format d’une entrée de répertoire CP/M


3. Système de fichiers MS3. Système de fichiers MS--DOSDOS• Un CP/M amélioré dédié aux plateformes Intel sur des PC.• Sys de fichiers hiérarchique dans lequel les répertoires peuvent avoir

une profondeur qlcq.• Le sys de fichier représente un arbre qui commence du rép. racine• Pas de multiutilisateur � n’importe quel utilisateur a accès à l’ensemble

des fichiers.


des fichiers.• Rép de tailles variables, mais avec des entrées de taille fixe (32 octets).• MS-DOS garde trace des blocs de fichiers dans une table d’allocation

(FAT) en mémoire principale.

Octets 8 3 1 10 2 2 2 4

Nom-fichier extens attrib réservé heure date Num du 1er bloc taille

Entrée d’un répertoire MS-DOS


4. Système de fichiers Windows 984. Système de fichiers Windows 98• Allonger les noms de fichiers (noms de fichier longs)• Introduction de la FAT-32 � autoriser des taille supérieures à 2 Go

pour les partitions et supérieures à 8 Go pour les disques• …


Octets 8 3 1 1 1 4

Nom-fichier extens attrib NT

seconde Date et heure de création

Entrée d’un répertoire MS-DOS utilisé dans Widows 98

2 2 4 2 4

(suite) Dernier accès

16 bits pds fort du bloc de

début

Date et heure dernière écriture

16 bits pds faible du bloc

de début

Taille du fichier


5. Système NTFS (Windows NT, XP…)5. Système NTFS (Windows NT, XP…)

• NTFS utilise une structure de données organisée en table nommée Master File Table (MFT) pour gérer les fichiers.

• La MFT contient des informations détaillées sur les fichiers et les répertoires.


entête Attributs NomFich données Attributs de sécu

Structure d’une entrée de la MFT


6. Système de fichiers UNIX (UNIX V7) (1/2)6. Système de fichiers UNIX (UNIX V7) (1/2)

• Sys de fichier multiutilisateur sophistiqué• Structure arborescente qui démarre au rép racine• Une entrée de répertoire UNIX comprend une entrée pour chaque

fichier de ce répertoire (des entrées simples, car des i-nodes).


fichier de ce répertoire (des entrées simples, car des i-nodes).• Format d’un i-node: voir fig. de la diapo suivante.

Octets 2 14

Num d’i-node Nom du fichier

Entrée d’un répertoire d’UNIX (UNIX V7)


6. Système de fichiers UNIX (UNIX V7) (2/2)6. Système de fichiers UNIX (UNIX V7) (2/2)

Taille du fichier

UID propriétaire

GID propriétaire

256 numérosde blocs


Attributs:

I-Node

Remarque: L’attribut compteur (dans cette figure)compte le nbr de liens vers cet i-node. Quand ce


Entrée d’un répertoire d’UNIX (UNIX V7)

GID propriétaire

Date de création

Compteur ….

10 numéros deblocs

Simple redirection

Triple redirection

Double redirection

256 doubles

redirections

256 simples

redirections 256 simples

indirections


Adresses disque

cet i-node. Quand ce compteur = 0, l’i-node est récupéré et les blocs de disque sont placés dans la liste des blocs libres.

GESTION GESTION DE LA DE LA

MÉMOIREMÉMOIRE


MÉMOIREMÉMOIRE

Gestion mémoireGestion mémoire

• Définitions• Gestion élémentaire de mémoire (mono et multiprogramation)

• Va-et-vient• Mémoire virtuelle• Algorithmes de remplacement de pages• Conception des systèmes de pagination


• Conception des systèmes de pagination• Problème d’implantation• Segmentation

Gestion mémoireGestion mémoireMémoireMémoire• Mémoire = ressource importante à gérer avec attention.• Type de mémoires:

– Mémoire cache: petite quantité (qlq dizaines ou centaine de Ko), volatile, rapide et chère,

– RAM (mém principale, inclus ROM) : qlq dizaines ou centaines de Mo, vitesse et prix moyen

– Mémoire de masse (disque, clé usb…): dizaines ou centaines de Go, lente,


– Mémoire de masse (disque, clé usb…): dizaines ou centaines de Go, lente, non volatile, pas chère.

• � Rôle SE (partie gestionnaire de la mémoire ) = Coordonner la manière dont ces mémoires sont utilisées :

1. Conserver la trace de la partie mémoire qui est en cours d’utilisation et de celle qui ne l’est pas,

2. Allouer la mémoire libre aux processus qui en ont besoin,3. Libérer la mémoire quand les processus ont fini leur travail,4. Gérer le va-et-vient (swapping) entre la mémoire principale et le disque quand

la mémoire principale est trop petite pour contenir tous les processus.


Gestion élémentaire de la mémoireGestion élémentaire de la mémoire

� Prévoir un bon gestionnaire de mémoire car:– Les programmes grossissent plus/aussi vite que la mémoire– Mémoire de plus en plus sollicitée (multimédia)


Il y a 2 classes de gestionnaires de mémoire :1. La monoprogrammation: simple (ni va-et-vient ni pagination).

2. La multiprogrammation: inclus le va-et-vient (swapping) et/ou la pagination.


Monoprogrammation et gestion mémoireMonoprogrammation et gestion mémoire• Exécuter un seul prgm ( "processus" ) à la fois en partageant la mémoire

entre le prgm et le SE [Le partitionnement peut se faire manuellement]

� 3 variantes simples d’organisation mémoire sont possibles (avec un SE et 1 seul processus utilisateur) :

Prgm 0xFFF… SE en ROM Gestionnaire de périph en ROM


0

utilisateur

SE en RAM0

Prgm utilisateur

0

périph en ROM

Prgm utilisateur

SE en RAM

a): modèle rare aujourd’hui (pour mini-ordinateurs)

b): pour ordi de poche ou sys embarqués

c): pour les 1er PC avec MS-DOS (BIOS)


Multiprogrammation et gestion mémoireMultiprogrammation et gestion mémoire (1/17)(1/17)• Multiprogrammation: plusieurs prgm en même temps. Quand un

processus est bloqué (attente de terminaison d’une E/S) � un autre peut utiliser le processeur.

• Solution simple: diviser la mémoire en n partitions fixes (de préférence inégales), et placer le nouveau processus qui arrive dans la file d’attente de la plus petite partition qui peut le contenir � plusieurs files d’attentes (cf. figure a).


files d’attentes (cf. figure a). • � Multiprogrammation avec un nombre fixé de tâches « MFT ».

• Inconvénient: Les files d’attente des petites partitions peuvent être pleines alors que celles des grandes partitions libres .

� blocage, alors qu’une grande partie de la mémoire est libre.• Solution : avoir une seule file d’attente (cf. figure b).


Multiprogrammation et gestion mémoireMultiprogrammation et gestion mémoire (2/17)(2/17)

Partition 4

Partition 3

800k

600k

400k

Files d’attente multiples

Partition 4

Partition 3

800k

600k

400k

Files d’attente unique


0

Partition 2

Partition 1

SE

a): Partitions mémoires prédéfinies avec des files d’attentes différentes

400k

200k

100k

0

Partition 2

Partition 1

SE

400k

200k

100k

b): Partitions mémoires prédéfinies avec une seule file d’attente.


Multiprogrammation et gestion mémoireMultiprogrammation et gestion mémoire (3/17)(3/17)

• Inconvénient de la file unique: Un petit travail peut attendre longtemps

• Solutions/propositions : – Parcourir la file d’attente et choisir le plus gros travail que peut

contenir la partition libérée, (� pénalise les petits travaux).


contenir la partition libérée, (� pénalise les petits travaux).– Conserver une (ou plusieurs) petite partition aux petits travaux– Un travail ne peut être ignoré plus de k fois,

Gestion mémoireGestion mémoireMultiprogrammation et gestion mémoireMultiprogrammation et gestion mémoire (4/17)(4/17)• Remarque : Aujourd’hui peu de SE se servent du modèle MFT.

� Il faut introduire la notion de probabilité d’attente d’E/S.– "Taux utilisation CPU" � " 1-pn "

(p: probabilité d’attente d’E/S, n: nbr de processus) .• Ex.

– Ordi avec 32 Mo de mémoire,– SE utilise 16 Mo,


– SE utilise 16 Mo,– Attente moyenne d’E/S=80%,– Chaque programme utilisateur nécessite 4 Mo

– � 4 processus peuvent être simultanément en mémoire (32-16=16 = 4*4)– Taux d’utilisation CPU (en ignorant celui du SE)=1 – 0,84 = 60%– Si on ajoute 16 Mo de RAM � taux = 1 - 0,88 = 83% � gain de 38%– Si on ajoute 16 autres � taux= 0,93 �gain d’uniquement 12% � gain

décroissant !!


Multiprogrammation et gestion mémoireMultiprogrammation et gestion mémoire (5/17)(5/17)«« RéallocationRéallocation » et «» et « protectionprotection »»• Lors de la procédure de lien, le programme lieur doit savoir à quelle

adresse le pgm démarrera en mémoire � il faut ajouter l’adresse de la partition qui le recevra. � « réallocation »

– Ex. si adresse de la 1ère instruction = 100 et adresse de la partition2=200k �adresse du lien = 200k + 100 exemple: CALL 200k+100

• Dans les sys multiutilisateurs, il est déconseillé d’autoriser des


• Dans les sys multiutilisateurs, il est déconseillé d’autoriser des processus à lire ou à écrire dans la mémoire appartenant à d’autres utilisateurs ou au sys. � « protection »

• Solution: équiper l’ordi de 2 registres matériels: registre de base (reçoit l’adresse de départ) et registre de limite (reçoit la longueur de partition).

• � Les adresses sont comparées avec la valeur du registre de limites, afin d’assurer qu’elles ne référenceront pas une adresse hors de la partition courante.

• Remarque: Peu d’ordi fonctionnent encore selon ce principe


Multiprogrammation et gestion mémoireMultiprogrammation et gestion mémoire (6/17)(6/17)VaVa--etet--vientvient (swapping) et «(swapping) et « mémoire virtuellemémoire virtuelle »»• Organisation mémoire en partitions fixes = simple et efficace

– Contrainte: Chaque tâche doit rester en mémoire jusqu’à sa terminaison.– Pb engendré: parfois la mémoire principale est insuffisante pour maintenir

tous les processus courant actifs.– Solution: Conserver les processus supplémentaires sur un disq ue et les

charger pour qu’ils s’exécutent dynamiquement.


charger pour qu’ils s’exécutent dynamiquement.

• Deux (2) approches de gestion mémoire peuvent être utilisées:1. Va-et-vient (Swapping): Travailler sur des processus entiers

(exécuter un processus puis le placer sur le disque).2. Mémoire virtuelle: permet aux pgms de s’exécuter même quand ils

sont partiellement en mémoire principale.� Partitions variables : contrairement aux partitions fixes, dans les partitions

variables, leurs nombre, leur localisation et leur taille varient dynamiquement au gré des allers-retours des processus. (Gérés par le SE)


Multiprogrammation et gestion mémoireMultiprogrammation et gestion mémoire (7/17)(7/17)VaVa--etet--vient (swapping)vient (swapping)• Processus = entité indivisible.• L’allocation mémoire change au gré des processus qui viennent en mémoire et

qui la quitteTemps �


(1)

C

B

A

SE(3)

C

B

SE(4)

C

B

D

SE(5)

Non utilisé

A

SE

B

A

SE(2)

C

D

SE(6)

C

A

D

SE(7)


Multiprogrammation et gestion mémoireMultiprogrammation et gestion mémoire (8/17)(8/17)VaVa--etet--vient :vient :

Gestion mémoire Gestion mémoire :Attribution dynamique de la mémoire � gérée par le SE.Gérer= allouer une zone mémoire à un processus, l’enlever de la

mémoire et l’arrêter, l’enlever de la mémoire et le transférer sur


mémoire et l’arrêter, l’enlever de la mémoire et le transférer sur disque, et conserver une trace de l’utilisation de la mémoire.

Il y a principalement deux (2) façons de gérer la mémoire :1. Tableaux de bits2. Listes chaînées


Multiprogrammation et gestion mémoireMultiprogrammation et gestion mémoire (9/17)(9/17)Gestion mémoire avec «Gestion mémoire avec « tableaux de bitstableaux de bits » et avec une «» et avec une « liste chaînéeliste chaînée »»

mémoire


a): Gestion de la mémoire à l’aide d’une table de bits.

(a)


Multiprogrammation et gestion mémoireMultiprogrammation et gestion mémoire (10/17)(10/17)Gestion mémoire avec «Gestion mémoire avec « tableaux de bitstableaux de bits » et avec une «» et avec une « liste chaînéeliste chaînée »»

mémoire


a): Gestion de la mémoire à l’aide d’une table de bits. b) Gestion de la mémoire à l’aide d’une liste chaînée.

(a) (b)


Multiprogrammation et gestion mémoireMultiprogrammation et gestion mémoire (11/17)(11/17)Algorithmes d’allocation mémoire avec une «Algorithmes d’allocation mémoire avec une « liste ch aînéeliste chaînée » » 1. Algo de la 1 ère zone libre (first fit): Le 1er trou qui peut contenir le

processus2. Algo de la zone libre suivante (next fit): idem que first fit mais commence

sa recherche à partir de l’endroit où il s’est arrêté la fois précédente au lieu de recommencer dès le début.


3. Algo du meilleur ajustement (best fit): fait la recherche dans toute la liste et prend le plus petit trou qui convient.

4. Algo du plus grand résidu (worst fit): fait la recherche dans toute liste et prend le plus grand trou disponible.

5. Algo du déplacement rapide (quick fit): utilise plusieurs listes séparées pour certaines des tailles les plus communément demandées � permet de trouver un trou d’une taille donnée d’une façon extrêmement rapide.


Multiprogrammation et gestion mémoireMultiprogrammation et gestion mémoire (12/17)(12/17)Mémoire virtuelleMémoire virtuelle• Certains pgm (processus) sont trop importants pour être supportés par

la mémoire disponible :• � diviser le pgme en parties (Segments de recouvrement ) et exécuter

à chaque fois un segment (en commence tjours par le segment 0). Les autres parties sont sauvegardées sur disque.


• � mémoire virtuelle: – Si un programme A veut s'exécuter alors qu'il n'y a plus de place

en mémoire, un "bout" d'un autre programme est "viré" en mémoire secondaire et remplacé par un "bout" de A.

– Donc, un programme est découpé en bouts que l'on nomme pagespages, de taille fixe. La mémoire physique est elle aussi découpée en cadres de pages (taille pages=taille cadre), ainsi que la mémoire secondaire.


Multiprogrammation et gestion mémoireMultiprogrammation et gestion mémoire (13/17)(13/17)Mémoire virtuelle et paginationMémoire virtuelle et pagination

Le CPU envoie les adresses Le CPU envoie les adresses virtuelle à la MMUvirtuelle à la MMUEnsemble

CPU

Unité de

CPUMémoire

Contrôleur de disque


Unité de gestion

mémoire (MMU)

Le MMU envoie les adresses physiques à la Le MMU envoie les adresses physiques à la mémoiremémoire

Bus

de disque





Multiprogrammation et gestion mémoireMultiprogrammation et gestion mémoire (15/(15/1717))Mémoire virtuelle et paginationMémoire virtuelle et pagination �� exemple 1exemple 1• Un ordi qui peut produire des adresses sur 16 bits, avec des valeurs

entre 0 et 64 Ko (adresses virtuelle), mais il a seulement 32 Ko de mémoire physique.

• Enregistrer sur disque le pgme et diviser l’espace virtuel en pages de 4 Ko par exemple et la mémoire physique en cadres de même taille.


4 Ko par exemple et la mémoire physique en cadres de même taille.� 16 pages virtuelles et 8 cadres

• Si le pgme essaye d’accéder à l’adresse 0 (ex. MOV REG,0), l’adresse virtuelle 0 est envoyée à la MMU qui constate que cette adresse tombe dans la page virtuelle 0 qui correspond au cadre de page 2 (selon la figure précédente). Elle transforme alors cette adresse en 8192 (ie 8Ko) et la présente sur le bus. La mémoire exécute l’instruction demandée en lui transférant le contenu de cette adresse.



Correspondance adresse virtuelle Correspondance adresse virtuelle ↔↔↔↔↔↔↔↔ adresse physique adresse physique



Multiprogrammation Multiprogrammation et gestion mémoireet gestion mémoire(17/17)(17/17)Mémoire virtuelle et Mémoire virtuelle et paginationpagination�� ExempleExemple

1 1 0 0 0 0 0 0 0 0 0 0 1 0 0

15 000 014 000 013 000 012 000 011 111 110 000 09 101 18 000 07 000 0

Table des

pages

Sortie de l’adresse physique (24580)

Le décalage sur 12 bits est

copié directement de l’entrée vers la

sortie


0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0

7 000 06 000 05 011 14 100 13 000 02 110 11 001 10 010 1

110

Bit de présence/absence

La page virt 2 est utilisée comme indexe dans la table des pages

Entrée de l’adresse virtuelle (8196)

Figure : Fonctionnement interne d’une MMU avec 16 pages de 4 octets.


Multiprogrammation et gestion mémoireMultiprogrammation et gestion mémoireMémoire virtuelle et paginationMémoire virtuelle et pagination �� défaut de pagedéfaut de page• Si l'adresse virtuelle référence une page qui n'est pas présente en

mémoire physique (cf. ‘0’ dans la figure précédente ou ‘x’ dans la figure d’avant), le mécanisme d'adressage génère un défaut de page . � déroutement (le processeur est restitué au SE)

• Si la mémoire physique est pleine :


• Si la mémoire physique est pleine :• Virer de la mémoire physique une page (remplacement ) :

– choisir une page "victime",– si elle a été modifiée, la réécrire sur disque,– modifier les indicateurs de présence en TPV (Table des Pages Virtuelles) ;

• Puis, dans tous les cas :– charger la page référencée en mémoire physique (placement) ;– modifier les indicateurs de présence en TPV.

La mémoire virtuelleLa mémoire virtuelle

Multiprogrammation et gestion mémoireMultiprogrammation et gestion mémoireMémoire virtuelle et paginationMémoire virtuelle et pagination �� Le choix d'une victime Le choix d'une victime ––

remplacementremplacement• De nombreux algorithmes :

– FIFO - First In First Out : ordre chronologique de chargement ;– NRU – Not Recently Used : ordre chronologique d'utilisation ;


– NRU – Not Recently Used : ordre chronologique d'utilisation ;– FINUFO - First In Not Used, First Out (algorithme de l'horloge ou

Clock) : approximation du LRU;– LFU - Least Frequently Used ;– Random : au hasard ;– MIN : algorithme optimal.

• Performances : MIN, LRU, FINUFO, [FIFO, Random].


Multiprogrammation et gestion mémoireMultiprogrammation et gestion mémoire

Mémoire virtuelle et Mémoire virtuelle et segmentationsegmentation• Contrairement à la pagination, dans la segmentation, la mémoire a des

partitions variables. (partition= segment). �Segment = partition à taille variableSegment = partition à taille variable.

• Ensemble des segment est généré à la compilation,• Taille segment peut varier (↑↓) au cours de l’exécution.


• Taille segment peut varier (↑↓) au cours de l’exécution.– � des vides entre les partitions de la mémoire centrale !

• Différence segment et page:– Dans chaque segment les adresses démarrent à 0– Il n’y a aucun lien entre les segments logiques d’un programme,

contrairement aux pages qui, elles se suivent.– Segment = solution efficace, mais doit être gérée par le

programmeur.


Multiprogrammation et gestion Multiprogrammation et gestion mémoiremémoire

Mémoire virtuelle et Mémoire virtuelle et

segmentationsegmentation

0

1024

Segment 1 10002025

70000 Segment 2

9000

6000 1100

Segment


physique0 Segment 3

3080

0..500 Segment 4

19000

0 Segment 5

2050 23000

…

Espace d’adressage logique du programme P1

Mémoire centrale

Partition vide à occuper si le

segment voisin est trop petit

pour le processus qui

l’occupe.



Mémoire virtuelle et Mémoire virtuelle et segmentationsegmentation

• Conversion des adresses:– Adresse logique a la forme: (s,d) où s= n°segment et d= adresse dans le

segment.– Retrouver l’emplacement du segment en mémoire centrale grâce à une


– Retrouver l’emplacement du segment en mémoire centrale grâce à une table de segments,

– Effectuer un déplacement de d au sein du segment s.



Mémoire virtuelle et Mémoire virtuelle et segmentationsegmentation

• Avantages:– Protection: le programmeur peut interdire l’accès à son segment, mais il

peut aussi le partager pour que plusieurs processus puissent l’exécuter.– Seules les adresses appartenant au segment ayant été modifié le seront.


– Seules les adresses appartenant au segment ayant été modifié le seront.– Fragmentation interne…


À suivre… À suivre…


• Exam intermédiaire le :Mercredi 18 ou 25 mars ???

(salle TP-info 2)


GESTION GESTION DES DES

PROCESSUSPROCESSUS


PROCESSUSPROCESSUS

PROCESSUS .PROCESSUS .

PLANPLAN1. Rappels sur la multiprogrammation2. Introduction aux processus3. Description d’un processus4. Interruption d’un processus5. Structure de données pour la gestion des processus


5. Structure de données pour la gestion des processus6. Ordonnancement de processus7. Synchronisation de processus (accès concurrents)8. Interblocages9. Communication interprocessus10. Appels systèmes pour la gestion des processus

Rappels sur la multiprogrammationRappels sur la multiprogrammation

Monoprogrammation : – Un seul programme (processus) s’exécutant en UC, sans interruption

• � si le processus contient une instruction d’E/S, le processeur restera inactif durant une longue période en attendant que cette instruction se termine.

Multiprogrammation : – Plusieurs programmes (processus) se partagent les ressources


– Plusieurs programmes (processus) se partagent les ressources (mémoires, périphériques…) de l’ordinateur � pb de protection, de concurrence et contrôle.

– Le processeur exécute un autre processus au lieu de rester inactif pendant tout le temps occupé par l’instruction d’E/S du 1er processus.

– Ça donne illusion à l'utilisateur que les processus s'exécutent tous en même temps. � pseudo parallélisme

• Sur une machine mono processeur � Seul un programme est actif à un moment donné.

Introduction aux processusIntroduction aux processus

• Processus = instance d’exécution d’un programme (créée par le SE ou par l’utilisateur) .

� il possède son conteur ordinal, ses registres et ses variables mémoires.

Processus créé par le SE afin d’exécuter le

programme.


Programme enregistré sur le

D.D.

Programme chargé en

mémoire centrale.

programme.

Exécution du processus par le processeur

Processeur

Un programme et son processus

Introduction aux processusIntroduction aux processus

Rôle du SE concernant la gestion des processusRôle du SE concernant la gestion des processus– Créer, supprimer et interrompre un processus– Ordonnancer les processus (exécution équitable entre processus tout en

privilégiant les processus système)

– Synchroniser les processus:• Choisir le processus à exécuter à un instant donné• Choisir le moment où interrompre un processus


• Choisir le moment où interrompre un processus• Choisir le processus qu’il faut exécuter ensuite (le suivant)• Spécifier les ressources dont a besoin (et qu’il faut affecter à) un

processus– Gestion des conflits d’accès aux ressources partagées– Protection des processus d’un utilisateur contre les actions d’un

autre utilisateur– …

Description d’un processus (1/2)Description d’un processus (1/2)

• Processus= suite d’instructions. On peut l’exécuter et l’interrompre. � Peut se retrouver dans plusieurs états (actif, suspendu, terminé,

en attente d’un événement…).

Actif(en exécution)Prêt Terminé

(1)

(4)(5)


Différents états d’un processus

(en exécution)Prêt

Bloqué(en attente d’E/S)

Terminé

(2)

(3)

(6) (7)

Description d’un processus (2/2)Description d’un processus (2/2)

Etats d’un processusEtats d’un processus(1) Naissance du processus.(2) Transition "actif � bloqué " se produit quand le processus qui est en

exécution a besoin d’une ressource non disponible.(3) Transition "actif � prêt " se produit si le temps (quantum) alloué au

processus est épuisé ou si un processus plus prioritaire (proc. urgent ou proc. système) arrive.

(4) Transition " � " se produit quand le SE sélectionne le


(4) Transition "prêt � actif " se produit quand le SE sélectionne le processus en question pour l’exécuter.

(5) Transition "actif � terminé " se produit quand le processus a fini son exécution.

(6) Transition "bloqué � prêt " se produit quand l’événement qui bloque le processus s’est produit.

(7) Transition "bloqué � terminé " se produit quand l’événement attendu par le processus ne peut se réaliser (ex. interbloquage).

Espace mémoire d’un processus (1/5)Espace mémoire d’un processus (1/5)

L’espace mémoire utilisé par un processus est divisé en plusieurs (4) zones:

1. Segment de code 2. Segment de données 3. Pile

Pile

24 k


4. Tas 24 k

16 k

Données

0

Texte(code)

Structure de l’espace d’adressage d’un processus


1. Segment de code– Copie du segment de code du fichier exécutable. – Placé dans des zones fixes de la mémoire

(début de la zone disponible).– La prochaine instruction à exécuter dans ce

segment est repérée par le pointeur d’instruction. – Cette zone est en lecture seule. Pile


– Cette zone est en lecture seule. – Elle peut être partagée par tous les processus

exécutant le même programme. Ce qui n’est pas le cas pour les segments de données et de pile (jamais partagés)

Pile

24 k

16 k

Données

0

Texte (code)


2.2. Segment de donnéesSegment de données– Se trouve au dessus du seg. de code.– Il est amené à grandir ou à rétrécir durant

l’exécution.– Il est composé de:

• Un seg. de données initialisées : copié directement de l’exécutable. Les données Pile


directement de l’exécutable. Les données initialisées correspondent aux var. globales et statiques initialisées d’un programme C par exemple.

• Un seg. de données non initialisées : créé dynamiquement. Les données non initialisées correspondent aux var. globales et statiques non initialisées

Pile

24 k

16 k

Données

0

Texte (code)


3.3. PilePile– Sert à stocker les données obtenues en cours

d’exécution.– Son nom de pile (stack en anglais) vient de la

manière dont elle est gérée: empiler puis dépiler les données.

– Le plus souvent située en haut de l’espace Pile


– Le plus souvent située en haut de l’espace d’adressage et croit vers le bas.

– Ex. Appel d’une fonction :• Empiler le nom de la fonction, les paramètres à lui

passer et les différentes var locales de cette fct.• Exécuter la fonction,• Une fois la fonction terminée, le système dépile les

données utilisées par la fonction et retrouve les données d’avant,

• Poursuivre l’exécution du pgm.

Pile

24 k

16 k

Données

0

Texte (code)


4.4. TasTas– Est un autre segment utilisé par le SE pour

les allocations dynamiques.– ////// …………..

Pile


Pile

24 k

16 k

Données

0

Texte (code)

Interruption d’un processusInterruption d’un processus

Interruption : Interruption :

• Dans le cas des transitions "actif � bloqué " et "actif �

prêt " on parle d’interruption (IT).

D’où vient une IT ?Quand :


Quand :– Le processus a atteint une inst d’E/S,– Le tps (quantum) attribué au processus est écoulé,– Un processus plus urgent doit être exécuté,– Un processus nécessite une ressource (matérielle ou logicielle) ou

une donnée (un résultat calculé par un autre processus, ou un ensemble d’instructions qui ne sont pas encore chargées en mémoire) détenue par un autre processus (elle n’est pas disponible),


Traitement d’une IT :Traitement d’une IT :

1. Arrivée de l’IT � le processus en cours est interrompu et un gestionnaire d’IT est chargé dans les registres du processeur et s’exécute pour traiter l’IT en question.

2. Une fois le signal de l’IT reconnu, le gestionnaire d’IT accède à la table des vecteurs d’IT et y recherche l’adresse du programme


table des vecteurs d’IT et y recherche l’adresse du programme associé (« Routine d’IT ») et l’exécute.

3. Une fois l’IT traitée, le SE charge un autre processus à partir de la file d’attente et l’exécute.


Traitement d’une IT : exempleTraitement d’une IT : exemple

………

………..

……..

………………..……..

IT qui arrive.

Ex. ctrl+Alt+Supp ou

IT100

Gest-IT(100)………..

…………

…………

………..

N° Code

… …

100 -----------.----

Routine d’IT 100

Processusen exécution


……..………………..……..………………..……..

IT100

Afficher la fenêtre de Ctrl+Alt+Supp Fermeture de la

fenêtre


Traitement d’une IT : exempleTraitement d’une IT : exemple

P1…………………..……..………Exécution d’un

programme quelconque puis arrivée de l’IT « Ctrl+Alt+Supp ».

Gestionnaire d’IT………………

IRQ100

-----------.----

100

……

CodeN°

Routine d’IT 100

Exécuter le pgme associé à la routine

� Afficher la fenêtre du Fermeture de

Processus en exécution

Table des vect d’IT

Charger un autre

processus


« Ctrl+Alt+Supp ». On la symbolise ici par le numéro IT100

� Afficher la fenêtre du gestionnaire des tâches.

Fermeture de la fenêtreP2

……………………..……..……..


• Une IT est provoquée par un signal généré soit par un événement internesoit par un événement externe .

– Éven. Interne : lié au processus: • Appel système • Déroutement: dû généralement aux erreurs telles qu’une division par zéro,

débordement de la mémoire, exécution d’une instruction non autorisée…)

– Éven. externe : panne, intervention de l’utilisateur à l’aide d’une frappe au clavier. Par exemple « Ctrl+Alt+Supp », bouton « reset »….


clavier. Par exemple « Ctrl+Alt+Supp », bouton « reset »….

• Deux (2) sortes d’IT: matérielles et logicielles– IT Matérielles (IRQ) : générées par les périphériques. Parviennent au

processeur par l’intermédiaire du Ctrleur d’IT. – IT Logicielles : des IT internes. C’est le processus qui appelle cet IT (à

l’aide du N°de l’IT). Ex. pour appeler une IT DOS, appeler l’IT N°21H.• Si plusieurs IT arrivent au même temps, c’est celle qui a le plus petit n°qui

est la plus prioritaire (ex. IRQ horloge sys = 0, IRQ port // = 7…).

Structure de données pour la gestion des Structure de données pour la gestion des processus processus (1/3)(1/3)

Pour gérer un processus, le SE manipule 2 structures de données :

1. Le bloc de contexte d’un processus et

2. La table des processus


2. La table des processus


1) Contexte d’un processus1) Contexte d’un processus : • C’est la structure de données qui décrit un processus en cours

d’exécution. • Il s’agit des info sauvegardées par le SE lors de l’IT d’un processus. • Elles sont créées au même moment que le processus et sont MAJ la

plus part du temps lors de l’IT du processus.• Parmi les données du cotexte d’un processus on a:

• Le compteur ordinal (adresse de la prochaine inst),


• Le compteur ordinal (adresse de la prochaine inst), • Le contenu des registres généraux, • Les registres d’occupation mémoire, • Registre de variable d’état (état du processus), • Valeur d’horloge, • Priorité du processus…

• Lors de l’IT d’un processus, le SE sauvegarde le contexte du processus en cours et charge celui du processus à exécuter �«commutation de contexte» (changement de contexte).


2) Table des processus2) Table des processus : • Tout processus contient une entrée dans cette table. • Cette table contient toutes les info indispensables au SE pour assurer

une gestion cohérente des processus.

• Parmi ces info on a :• un pointeur vers le bloc de contexte du processus, • l’identifiant du processus,


• l’identifiant du processus, • son lien de parenté, • les fichiers qu’il a ouvert, • occupation mémoire (pointeurs sur le segment de code, de données et

de pile),

• Cette table est stockée dans l’espace mémoire du SE. � Donc aucun processus ne peut y accéder .

Ordonnancement de processus (1/7)Ordonnancement de processus (1/7)

• Plusieurs processus peuvent se retrouver dans un état "prêt " (ou "en

attente " ). Le SE les place alors dans une file d’attente (� Une file d’attente pour chaque état.).

• Le SE dispose d’un programme qui choisit le processus à exécuter. Ce pgme s’appelle scheduler, dispatcher ou ordonnanceur.

•


•P3 P1 P5 P2 P7 P8 P9

Arrivée du processus P10 et son insertion entre P5 et P2 selon l’algorithme

d’ordonnancement en vigueur

P3 P1 P5 P10 P2 P7 P8 P9

Fonctionnement de l’ordonnanceur

Processeur

Processeur


• Parmi les processus de la file, lequel choisir ? � « Algo d’ordonnancement ».

• Plusieurs Algo existent • � But: optimisation � améliorer le temps de réponse (moyenne des

dates de fin d’exécution) du syst, le tps d’attente (moyenne des délais d’attente pour commencer une exécution).


• Quelques Algo d’ordonnancement:– Ordonnancement selon FIFO (First In First Out)– Ordonnancement circulaire (le tourniquet ou round Robin)– Ordonnancement avec priorité– Ordonnancement selon le plus court d’abord (SJF, Shortest Job First)– Ordonnancement selon le job le plus court qui reste…


Ordonnancement selon Ordonnancement selon FIFOFIFO (First In First Out)(First In First Out)• Le 1er processus arrivé est le 1er servi• � placer le nouveau processus qui arrive à la fin de la liste

• Avantage :– Simple– Ne consomme pas de temps processeur


– Ne consomme pas de temps processeur

• Inconvénient :– Comme si on fait de la monoprogrammation,– Problème avec les processus prioritaires,– Le processeur peut être trop occupé par un gros travail


Ordonnancement circulaire Ordonnancement circulaire (le tourniquet ou (le tourniquet ou round Robinround Robin ))• Allouer à chaque processus un temps d’exécution q (quantum),• Une fois un processus a consommé son temps d’exécution, il est

interrompu et mis à la fin de la file d’attente. • L’ordonnanceur sélectionne le prochain (premier) processus de la file et

l’exécute pendant le même quantum de temps.


• Avantage:– Tous les processus ont la chance (même chance) d’être exécutés.

• Inconvénient:– Si le temps q est faible et comparable à celui du changement de

contexte � le processeur se retrouve à passer plus de temps à charger et décharger des processus plutôt qu’à les exécuter. � devient inefficace.

– Problème avec les processus prioritaires


Ordonnancement avec prioritéOrdonnancement avec priorité– Le processus de plus haute priorité est exécuté le premier

� Cet algo classe les processus dans l’ordre décroisant de leur priorité.

– Chaque processus s’exécute jusqu’à la fin.– Une priorité peut être statique ou dynamique, fixe ou variable.

• Avantages : – Pouvoir privilégier certains processus. Par exemple les processus systèmes


– Pouvoir privilégier certains processus. Par exemple les processus systèmes (ceux du SE) ont la priorité la plus haute.

• Inconvénients :– Problème de la famine : Plusieurs processus de haute priorité monopolisent

l’unité centrale. Les processus de faible priorité ne s’exécuteront que très rarement !!!

– Solutions: Décrémenter de 1 la priorité du processus (à chaque impulsion d’horloge, chaque quantum q…) et le mettre (après avoir effectué son temps q d’exécution) à la fin (queue) de la file de priorité inférieure.


Ordonnancement selon le plus court d’abord (Ordonnancement selon le plus court d’abord ( SJFSJF))• C’est le plus court (du point de vue temps d’exécution) processus qui est

mis à la tête de la file d’attente et qui est exécuté en premier

Avantage:– Utile dans les chaînes de production


Inconvénient:– Suppose la connaissance de la durée d’exécution des processus, ce qui

est rare en pratique sauf si on a utilisé au préalable au moins une fois ces processus.


Conclusion sur les algorithmes d’ordonnancementConclusion sur les algorithmes d’ordonnancement

– Pas d’algorithme idéal sur tous les plans

– Les critères de choix dépendent des besoins et des attentes


Synchronisation de processus Synchronisation de processus (accès concurrents)(accès concurrents)

• Le problème d’accès concurrents se produit quand 2 processus partagent une ressource, matérielle ou logicielle (tq: fichier, variable, périphérique d’E/S), alors que celle-ci ne peut pas être partagée (accès exclusif).

– Généralement les accès en lecture ne posent pas ce pb, ce qui n’est pas le cas pour les accès en écriture.

• Ex.– P1 et P2 : deux processus qui veulent accéder à l’imprimante.– L’imprimante est gérée par le processus démon-plt qui inspecte une var de type


– L’imprimante est gérée par le processus démon-plt qui inspecte une var de type tableau qui contient les fichiers à imprimer et 2 var entières prochain (indique le n°du prochain fichier à imprimer) et libre (indique le 1er emplacement libre où déposer le fichier). Supposons le scénario suivant:

– P1 lit libre. La trouve à 5, puis est interrompu.– P2 lit libre. La trouve toujours à 5, met son fichier à cet emplacement,

incrémente libre à 6, puis interrompu.– P1 reprend et écrase le fichier de P2 avec le sien ! ! !Solution : Ne pas interrompre P1 au moment où on l’a interrompu.

� Notion de section critique et d’exclusion mutuelle.


Section critique et exclusion mutuelleSection critique et exclusion mutuelle• Section critique = partie du processus où peut y avoir un conflit d’accès.

Elle contient des var ou des ressources partagées par d’autres processus.

• Exclusion mutuelle : Si une ressource a été accédée par un processus P1, aucun autre processus ne peut y accéder tant qu’elle n’a pas été libérée par P1.

– Si P1 est interrompu, il faut attendre à ce qu’il reprenne son exécution et qu’il


– Si P1 est interrompu, il faut attendre à ce qu’il reprenne son exécution et qu’il libère la ressource.

• Il y a principalement 2 (voire 4) solutions pour résoudre les pb des accès concurrents :

– Les sémaphores– Les moniteurs– Communication entre processus : primitives send et receive.– Solutions matérielles.


Sémaphores Sémaphores (1/3)

• Sémaphore = var (entière) qui compte le nbre de processus en attente d’une section critique.

• Deux types de Sémaphores:– Sémaphore binaire : peut prendre comme valeur 0 ou 1. Il est utilisé

pour réaliser de l’exclusion mutuelle– Sémaphore n -aire : peut prendre n valeurs. Il sert à spécifier un


– Sémaphore n -aire : peut prendre n valeurs. Il sert à spécifier un nombre d’accès maximal à une ressource (en lecture évidement).

•

• Primitives P et V : Les sémaphores utilisent 2 primitives, P et V, indivisiblesindivisibleset non interruptiblesnon interruptibles.

– P(S): permet de prendre le sémaphore. Si (S<0) alors le processus exécutant P(S) se bloque.

– V(S): permet de libérer le sémaphore et un processus bloqué s’il y en a.



• P(S) est équivalente à :Si (S>0) alors S=S-1

Sinon s’endormir

Finsi

– Si le sémaphore est binaire � une seule exécution de la section critique


• V(S) est équivalente à :Si (un processus est bloqué sur S) alors le libérer

Sinon s=s+1

Finsi

– Le fait de vérifier s’il existe des processus en attente du sémaphore avant d’incrémenter sa valeur permet de respecter l’ordre dans lequel les processus se sont bloqués au niveau de l’accès à cette section critique.



• Instructions typiques d’un processus :

Faire

...instructions...

...

P(S)


Section critique

V(S)

...

...instructions...

...

Fin

• RQ: Il faut faire attention à l’ordre de P et de V.


Moniteurs Moniteurs (1/2)

• Contrairement aux sémaphores, les moniteurs est une solution facile à mettre en œuvre (pas de problème d’inversion de P et de V).

• Moniteur = ensemble de procédures, de variables et de structures de données regroupées dans un module spécial et gérées par le compilateur.

– Si un programme veut mettre en œuvre une Sec Critique, il la


– Si un programme veut mettre en œuvre une Sec Critique, il la reportera dans des procédures du moniteur, qui seront appelées par les processus.

• Primitives Wait et Signal : Leur but est de bloquer les processus sur la réalisation d’une condition et pouvoir ensuite les réveiller.


Moniteurs Moniteurs (2/2) � Exemplemonitor ProducteurConsommateurcondition full, empty;int cpt;

void insert( int objet){if (cpt==N) wait(full);insert_object(objet);cpt++;if (cpt==1) signal(empty);

void producteur(){while( true)

{objet=produce_object;ProducteurConsommateur. insert(objet);

}}


if (cpt==1) signal(empty);}

void remove( int objet){if (cpt==0) wait(empty);remove_object(objet);cpt--;if (cpt==N-1) signal(full);

}cpt=0;endmonitor;

void consommateur(){while( true){

ProducteurConsommateur. remove(objet);consum_objet(objet)

}}


Solution matérielle : désarmement des ITSolution matérielle : désarmement des IT1) Désarmer les IT pendant toute la section critique, puis les réarmer à la fin

de celle-ci.Méthode à n’appliquer qu’entre processus systèmes, car a des risques

(inconvénients):– Blocage de processus plus prioritaires par l’exécution d’une longue section

critique.– Blocage de tout le système si l’utilisateur oublie de réarmer les IT après la


– Blocage de tout le système si l’utilisateur oublie de réarmer les IT après la sortie de la section critique.

2) Instruction TS (Test and Set) : instruction élémentaire qui permet de lire et d’écrire le contenu d’un mot mémoire de manière indivisible.

� Le 1er qui s’exécute trouve verrou à 0, les autres le trouvent à 1 et ne rentreront pas.

void TS(int a,b)

{a=b; b=1;}

La section d’entrée devient: �

TS(test,verrou);

While test==1 do TS(test,verrou);

…Section critique…

verrou=0;

InterblocagesInterblocages

• On parle d’interblocage pour un ensemble de processus quand chacun d’eux est dans l’attente d’un événement de la part d’un de ces processus.

Camion 1

Cam

ion

2

Cam

ion

4


• En cas d’interblocage, les ressources ne seront jamais libérées.

• Interblocage rares dans un PC � beaucoup de SE demandent alors de redémarrer la machine si ce problème arrive � politique de l’autruche.

Camion 3Cam

ion

4


Détection d’interblocageDétection d’interblocage

• On dit qu’il y a interblocage si les 3 conditions suivantes sont vérifiées simultanément:

1. Un processus détenant une ressource est dans l’attente d’une autre ressource.

2. Une ressource au moins est détenue en mode exclusif.


3. Il existe une attente circulaire entre les processus.

P1 P2

P3

R2

R1R3Pi

Rj

Processus Pi

Ressource Rj

P1 demande la ressource R1

P1 détient la ressource R3


Modélisation d’un interblocage Modélisation d’un interblocage (modèle (graphe) de Holt)(modèle (graphe) de Holt)

R1 R3

P1 P2 P3

R1* R3*

P1 P2 P3

R1 R3 *

P1 P2 P3


R2*

R2*

(1) Pas d’interblocage

R2*

R2*

(2) Cycle + les 3 conditions satisfaites � interblocage

R2*

R2*

(3) Cycle mais pas d’interblocage, car pas d’attente circulaire; la libération de P1 pour R2 met fin à l’interblocage


Solutions aux problème d’interblocage :Solutions aux problème d’interblocage :1. Approche préventive : empêcher les interblocages d’avoir lieu.

Nécessite beaucoup d’efforts.2. Approche de détection et de guérison : le syst laisse les

interblocages se produire, ensuite, il les détecte et il les corrige.3. Politique de l’autruche : Les ignorer et redémarrer le système s’ils se

produisent.


Correction des interblocagesCorrection des interblocages1. Dès détection d’un cycle, interrompre un (ou plusieurs) des processus

qui participent à ce cycle afin de mettre fin à l’attente circulaire (avortement processus).

2. Réquisitionner quelques ressources sur lesquelles il y a conflit.

Communication interprocessusCommunication interprocessus

• But de la communication : échanger des données ou des résultats.

• Le programmeur doit utiliser une technique bien définie pour faire communiquer 2 processus puisque ceux-là ne peuvent pas s’échanger des variables (comme c’est le cas entre les procédures). Chaque processus a son espace d’adressage

• Différentes manières de communiquer :


• Différentes manières de communiquer :– Communication par envoi de messages: primitives send et receive.

send(proc1,&message,…)receive(bal,&message,…)

– Communication par mémoire partagéeLes processus partagent une zone mémoire dans laquelle ils placent les variables en commun.

Appels systèmes pour la gestion des Appels systèmes pour la gestion des processusprocessus

• Chaque SE met à la disposition des programmeur des appels systèmes afin de créer et exécuter des processus.

• Créer un processus, puis créer ses fils, l’exécuter, le tuer…


– Les processus fils peuvent hériter les caractéristiques de leurs pères

• pid=fork() � création de processus• s=execve(nom, arg,envp) � exécution d’un programme• exit(etat) � terminaison d’un processus• s=wait(pid,&etat,options) � attente d’un processus

FINFINFINFINFINFINFINFIN


FINFINFINFINFINFINFINFIN

Documents

Systèmes d’Exploitation 2 - freealilou.free.frfreealilou.free.fr/CV_MCF_fichiers/Mes_Cours/Diapos cours SE-2.pdf · Systèmes d’Exploitation 2 Ali Larab, L2-info, CUFR, 08-09