Upload
hamlin-bouchard
View
110
Download
7
Embed Size (px)
Citation preview
1
GPA435 Systèmes GPA435 Systèmes d’exploitation et d’exploitation et programmation de programmation de systèmesystème
Copyright, 2000 © Tony Wong, Ph.D., ing.
Chapitre 3Gestion des processus,
gestion de la mémoire etordonnancement
Université du Québec
École de technologie supérieureDépartem ent de génie de la production autom atisée
2
Rôles fondamentauxRôles fondamentaux
Tous les S.E. on comme premier Tous les S.E. on comme premier objectif:objectif:
•gestion efficace des processus.gestion efficace des processus.
•gestion de la mémoire.gestion de la mémoire.
•gestion des périphériques.gestion des périphériques.
Processus, mémoire et ordonnancement
Entités manipulées par le Entités manipulées par le S.E. modélise un S.E. modélise un programme en exécution programme en exécution Ressource utilisée par les Ressource utilisée par les
processusprocessus
Ressource utilisée par les Ressource utilisée par les processusprocessus
3
Modèle pratique des Modèle pratique des processusprocessus
Processus, mémoire et ordonnancement
N o uv eau P rêt E x écutio n So rtie
B lo qué
T em p s écou lé
R ép a rti tion
E n a tten te
libérat
ion
A d m ission R etra i t
Susp en sio n
S u sp en d u
Activation
Déplacement d’un processus vers/de la mémoire Déplacement d’un processus vers/de la mémoire secondaire (secondaire (swappingswapping).).
Libère les ressources utilisées afin d’admettre de Libère les ressources utilisées afin d’admettre de nouveaux processus dans le système.nouveaux processus dans le système.
4
Modèle UNIXModèle UNIX
Processus, mémoire et ordonnancement
Modèle des processus de SVR4:Modèle des processus de SVR4:• tenir compte des modes d’exécution tenir compte des modes d’exécution
(mode utilisateur et mode noyau);(mode utilisateur et mode noyau);
• tenir compte de la possibilité de la tenir compte de la possibilité de la préemption.préemption.
Préemption: la prise de contrôle du processeur par un Préemption: la prise de contrôle du processeur par un autre processus de plus haute priorité.autre processus de plus haute priorité.
Un processus est « préemptible » lorsqu’il passe du Un processus est « préemptible » lorsqu’il passe du mode d ’exécution noyau en mode d ’exécution mode d ’exécution noyau en mode d ’exécution utilisateur.utilisateur.
5
Modèle UNIXModèle UNIX
Processus, mémoire et ordonnancement
Modèle des processus de SVR4:Modèle des processus de SVR4:• avant SVR4avant SVR4 un processus dans le mode un processus dans le mode
noyau n’est jamais préemptible;noyau n’est jamais préemptible;
• avant SVR4avant SVR4 le S.E. UNIX ne convient pas aux le S.E. UNIX ne convient pas aux traitements en temps réel;traitements en temps réel;
• modèle à neuf (9) états.modèle à neuf (9) états.
6
Modèle UNIXModèle UNIX
Processus, mémoire et ordonnancement
P réem p té
M o d ed 'ex écutio n
n o yau
Z o m b ie
M o d ed 'ex écutio nutilisateur
A p p els systèm es
R etou r
Retour
Préem
ption
Sorti
e
P rêt (en m ém o ire)
B lo qué (en m ém o ire)Réveil
le
Endormi
Répartition
C réé
Mémoire suff
isante
Mémoire insuffisante
P rêt (susp en d u)
R em p la cem en t
B lo qué (susp en d u)
Réveil
le
R em p la cem en t
N o te: la susp en sio n d 'un p ro cessus im p lique n écessairem en t so n d ép lacem en t v ers lam ém o ire seco n d aire.
7
Modèle UNIXModèle UNIXMode d’exécution utilisateur:Mode d’exécution utilisateur:• processus est en exécution dans le mode utilisateur. Il est processus est en exécution dans le mode utilisateur. Il est
préemptible.préemptible.
Mode d’exécution noyau:Mode d’exécution noyau:• processus est en exécution dans le mode noyau.processus est en exécution dans le mode noyau.
Préempté:Préempté:• processus est en préemption. La préemption n’est possible que lorsque le processus est en préemption. La préemption n’est possible que lorsque le
processus est sur le point de retourner dans l’état « Mode d’exécution utilisateur ».processus est sur le point de retourner dans l’état « Mode d’exécution utilisateur ».
Processus, mémoire et ordonnancement
8
Modèle UNIXModèle UNIX
Processus, mémoire et ordonnancement
Zombie:Zombie:• processus sorti mais laisse dans le système des informations processus sorti mais laisse dans le système des informations
destinées au processus père qui n’existe plus. destinées au processus père qui n’existe plus.
Prêt (en mémoire):Prêt (en mémoire):• processus prêt pour être exécuté et dont le code est en mémoire.processus prêt pour être exécuté et dont le code est en mémoire.
Bloqué (en mémoire):Bloqué (en mémoire):• processus bloqué en attendant un événement déclencheur (code processus bloqué en attendant un événement déclencheur (code
en mémoire).en mémoire).
9
Modèle UNIXModèle UNIX
Processus, mémoire et ordonnancement
Créé:Créé:• nouveau processus qui n’est pas encore prêt pour l’exécution. nouveau processus qui n’est pas encore prêt pour l’exécution.
Prêt (suspendu):Prêt (suspendu):• processus prêt pour être exécuté et dont le code est en mémoire processus prêt pour être exécuté et dont le code est en mémoire
secondaire (disque).secondaire (disque).
Bloqué (suspendu):Bloqué (suspendu):• processus bloqué en attendant un événement déclencheur (code processus bloqué en attendant un événement déclencheur (code
en mémoire secondaire).en mémoire secondaire).
10
Modèle UNIXModèle UNIXPour le SVR4, deux processus fondamentaux toujours en Pour le SVR4, deux processus fondamentaux toujours en
exécution:exécution:• processus qui réalise le déplacement des autres processus processus qui réalise le déplacement des autres processus
de/vers la mémoire centrale (de/vers la mémoire centrale (swapperswapper););
• swapperswapper porte le numéro d’identification de processus PID = 0; porte le numéro d’identification de processus PID = 0;
• ce dernier est responsable de la création du processus « init » ce dernier est responsable de la création du processus « init » (PID = 1);(PID = 1);
• tous les autres processus sont descendants de ce processus init. tous les autres processus sont descendants de ce processus init.
Processus, mémoire et ordonnancement
11
Espace d’adresses des Espace d’adresses des processusprocessusDans le SVR4:Dans le SVR4:
Processus, mémoire et ordonnancement
P ile u tilisateur
F ich ier asso cié à la m ém o ire
D o n n ées in itialisées
T ex te
B ib lio th èque p artagée
P ro gram m e n o yau
D o n n ées n o n in itialisées
0
0xE0000000
0xFFFFFFFF
(3758096384)
(4294967295)
H eap
E sp aceutilisateur
E sp acen o yau
• Il s’agit d’un espace virtuel à Il s’agit d’un espace virtuel à 32bits32bits
• L ’arrangement basé sur le schème L ’arrangement basé sur le schème ELF.ELF.
• La pile utilisateur « grossit » vers La pile utilisateur « grossit » vers les adresses basses.les adresses basses.
• Le heap « grossit » vers les Le heap « grossit » vers les adresses hautes.adresses hautes.
• Les adresses supérieures à Les adresses supérieures à 0xE00000000xE0000000 sont associées au code sont associées au code du noyau.du noyau.
12
Espace d’adresses des Espace d’adresses des processusprocessusEspace virtuel est divisé en segments.Espace virtuel est divisé en segments.Segment « Texte »:Segment « Texte »:• code exécutable du programme;code exécutable du programme;
• entreposé dans le fichier exécutable;entreposé dans le fichier exécutable;
• à lecture seulement;à lecture seulement;
• ce segment est partageable.ce segment est partageable.
Processus, mémoire et ordonnancement
Plusieurs processus Plusieurs processus utilisant le même code utilisant le même code exécutable. Les processus exécutable. Les processus partagent alors le même partagent alors le même segment « Texte ». segment « Texte ».
13
Espace d’adresses des Espace d’adresses des processusprocessusSegment « Données »:Segment « Données »:• entreposage des symboles constants entreposage des symboles constants
ou globaux.ou globaux.
• deux types de données deux types de données données données initialisées et données non initialisées.initialisées et données non initialisées.
Processus, mémoire et ordonnancement
Variables globales Variables globales qui ont une valeur qui ont une valeur assignées dans le assignées dans le code source du code source du programme. Elles ne programme. Elles ne sont pas sont pas partageables. partageables.
Même que les Même que les données initialisées données initialisées
mais leur contenu est mais leur contenu est toujours mise à zéro. toujours mise à zéro.
14
Espace d’adresses des Espace d’adresses des processusprocessus
Processus, mémoire et ordonnancement
Segment « Heap »:Segment « Heap »:• zone de mémoire pour l’entreposage des données du zone de mémoire pour l’entreposage des données du
processus;processus;
• allocation dynamique de la mémoire;allocation dynamique de la mémoire;
• taille du segment varie en fonction des besoins du taille du segment varie en fonction des besoins du processus;processus;
• segment grossit vers les adresses croissantes (schème ELF). segment grossit vers les adresses croissantes (schème ELF).
15
Espace d’adresses des Espace d’adresses des processusprocessus
Processus, mémoire et ordonnancement
Segment « Fichier associé à la mémoire » (Segment « Fichier associé à la mémoire » (Mapped Mapped FileFile):):• facilite l’accès des fichiers par le processus;facilite l’accès des fichiers par le processus;
• au lieu de faire appel aux services systèmes;au lieu de faire appel aux services systèmes;
• on associe un fichier à la mémoire;on associe un fichier à la mémoire;
• accès du fichier est plus rapide;accès du fichier est plus rapide;
• (concept existe également sous Windows NT). (concept existe également sous Windows NT).
16
Espace d’adresses des Espace d’adresses des processusprocessus
Processus, mémoire et ordonnancement
Segment « Bibliothèque partagée » (Segment « Bibliothèque partagée » (shared Libraryshared Library):):• Bibliothèque partagée Bibliothèque partagée code objets utilisables par plus d’un code objets utilisables par plus d’un
processus à la fois;processus à la fois;
• codes objets chargés dans l’espace virtuel du processus par un codes objets chargés dans l’espace virtuel du processus par un appel de système;appel de système;
• espace virtuel réservé pour ces codes objets est le segment espace virtuel réservé pour ces codes objets est le segment « Bibliothèque partagée »;« Bibliothèque partagée »;
• par convention, les bibliothèques partagées portent l’extension par convention, les bibliothèques partagées portent l’extension .so.so
17
Espace d’adresses des Espace d’adresses des processusprocessus Segment « Pile utilisateur »:Segment « Pile utilisateur »:
• entreposage des variables locales;entreposage des variables locales;
• adresse de retour des routines;adresse de retour des routines;
• paramètres d’entrée des fonctions;paramètres d’entrée des fonctions;
• contenu des registres du processeur;contenu des registres du processeur;
• valeur de retour des fonctions appels valeur de retour des fonctions appels systèmes;systèmes;
• segment grossit vers les adresses segment grossit vers les adresses décroissantes (schème ELF).décroissantes (schème ELF).
Processus, mémoire et ordonnancement
18
Espace d’adresses des Espace d’adresses des processusprocessus
Processus, mémoire et ordonnancement
Adresses supérieures à Adresses supérieures à 0xE00000000xE0000000::• image du code noyau;image du code noyau;
• image du code noyau partagée par image du code noyau partagée par tous les processus du système;tous les processus du système;
• un pont reliant tous les processus du un pont reliant tous les processus du système;système;
• permet la réalisation de la permet la réalisation de la communication inter-processus. communication inter-processus.
19
Organisation du noyauOrganisation du noyau
Deux aspects:Deux aspects:
• répondre d’une manière synchrone les répondre d’une manière synchrone les demandes des processus demandes des processus appels de appels de système;système;
• demandes asynchrones demandes asynchrones interruption des interruption des périphériques;périphériques;
• tous les processus sont assignés une tous les processus sont assignés une priorité;priorité;
• celui qui possède la plus haute priorité celui qui possède la plus haute priorité contrôle le processeur.contrôle le processeur.
Processus, mémoire et ordonnancement
20
Organisation du noyauOrganisation du noyau
Processus, mémoire et ordonnancement
Système Solaris:Système Solaris:
• programme du noyau programme du noyau /kernel/genunix/kernel/genunix;;
• taille du fichier taille du fichier 1,2 Mo; 1,2 Mo;
• chargement des serveurs sur par le noyau;chargement des serveurs sur par le noyau;
• chargement des serveurs utilisés seulement;chargement des serveurs utilisés seulement;
• démarrage du système plus rapide;démarrage du système plus rapide;
• architecture du noyau n’est pas monolithique.architecture du noyau n’est pas monolithique.
21
Organisation du noyauOrganisation du noyau
Processus, mémoire et ordonnancement
Système Solaris:Système Solaris:• comprendre l’organisation du noyau comprendre l’organisation du noyau
inspecter les sous-répertoires de inspecter les sous-répertoires de /kernel/kernel;;Sous-répertoire Contenu
drv Pilotes de matériel..
exec Différents formats pour les fichiers exécutables (a.out, COFF,ELF, etc).
fs Différents systèmes de fichiers acceptés (NFS, UFS, s5fs, ufs,etc.)
sched Différentes classes d’ordonnancement.
strmod Modules des flux d’E-S.
sys Interface des appels de système.
misc Divers modules pour le système. On retrouve le module del’encryptage, le module de la communication IPC, le module deremplacement des processus (swapper), etc.
Mod
ule
s M
od
ule
s se
rveu
rsse
rveu
rs
22
Organisation du noyauOrganisation du noyau
Processus, mémoire et ordonnancement
Système Solaris:Système Solaris:• fondamentalement composé de deux fondamentalement composé de deux
composants composants ordonnancement ordonnancement ((/kernel/sched/kernel/sched) et communication IPC ) et communication IPC ((/kernel/sys/semsys/kernel/sys/semsys et et /kernel/sys/shmsys/kernel/sys/shmsys););
• serveur du système de fichier est serveur du système de fichier est également responsable de la gestion de également responsable de la gestion de la mémoire virtuelle.la mémoire virtuelle.
23
Appels de systèmeAppels de système
Processus, mémoire et ordonnancement
Appel de système Appel de système fonction fonction spéciale d’enveloppe (spéciale d’enveloppe (wrapperwrapper):):• encodage des paramètres;encodage des paramètres;
• bascule le processus entre le mode bascule le processus entre le mode utilisateur et le mode noyau;utilisateur et le mode noyau;
• processus effectuant un appel de processus effectuant un appel de système est placé en mode d’exécution système est placé en mode d’exécution noyau momentanément par le système.noyau momentanément par le système.
24
Appels de systèmeAppels de système
Processus, mémoire et ordonnancement
Exemple: fonction Exemple: fonction open()open()• open()open() est une fonction enveloppe; est une fonction enveloppe;• open()open() place le numéro de service et les place le numéro de service et les
paramètres de l ’appel dans des registres paramètres de l ’appel dans des registres globaux du processeur;globaux du processeur;
• open()open() exécute l ’instruction exécute l ’instruction traptrap et change et change l’état du processeur en mode noyau et l’état du processeur en mode noyau et démarre une routine de gestion dans le démarre une routine de gestion dans le noyau;noyau;
• routine de gestion invoque routine de gestion invoque syscall()syscall() pour pour gérer l’appel de système;gérer l’appel de système;
25
Appels de systèmeAppels de système
Processus, mémoire et ordonnancement
Exemple: fonction Exemple: fonction open()open()• noyau réalise l’action demandée (selon le noyau réalise l’action demandée (selon le
numéro de service);numéro de service);
• noyau place le résultat de l ’action dans noyau place le résultat de l ’action dans des registres prédéterminés du des registres prédéterminés du processeur;processeur;
• fonction enveloppe open() retire le fonction enveloppe open() retire le résultat des registres et retourne le tout résultat des registres et retourne le tout au processus appelant.au processus appelant.
26
Exécution multifilièreExécution multifilière Création d’un fil d’exécution:Création d’un fil d’exécution:
• par un par un appel de bibliothèqueappel de bibliothèque et non et non un appel de système;un appel de système;
Rendre le fil exécutable:Rendre le fil exécutable:• noyau associe uns structure appelée noyau associe uns structure appelée
LWPLWP ( (Light Weight ProcessLight Weight Process) au fil;) au fil;• chaque LWP correspond à un fil chaque LWP correspond à un fil
d’exécution du noyau.d’exécution du noyau.
Processus, mémoire et ordonnancement
27
Exécution multifilièreExécution multifilière Ainsi, la création d’un fil n’implique Ainsi, la création d’un fil n’implique
pas le noyau mais leur exécution pas le noyau mais leur exécution passe nécessairement par passe nécessairement par l’association d ’un LWP du noyau.l’association d ’un LWP du noyau.
Processus, mémoire et ordonnancement
L W P L W P L W P L W P L W P
P ro cessus P ro cessus
O rd o n n an cem en t
P 1 P 2 P n
M o d e u tilisateur
M o d e n o yau
P ro cesseurs
28
Exécution multifilièreExécution multifilière Association fil d ’exécuition Association fil d ’exécuition LWP réalisée par la LWP réalisée par la
bibliothèque multifilière bibliothèque multifilière /usr/lib/libthread.so/usr/lib/libthread.so;; chaque LWP est toujours associé à un fil particulier chaque LWP est toujours associé à un fil particulier
((boundedbounded);); pour économiser les ressources du noyau pour économiser les ressources du noyau créer des créer des
fils détachés (fils détachés (unboundedunbounded);); fils détaché peut s ’associer à n’importe quel LWP fils détaché peut s ’associer à n’importe quel LWP
disponible.disponible.
• la faminela famine
Processus, mémoire et ordonnancement
29
Gestion de la mémoireGestion de la mémoire Quantité de la mémoire physique est Quantité de la mémoire physique est
limitée:limitée:• mémoire virtuelle mémoire virtuelle illusion de disposer illusion de disposer
toute la mémoire de la machine pour toute la mémoire de la machine pour chacun des processus; chacun des processus;
• mémoire virtuelle mémoire virtuelle illusion d’une carte de illusion d’une carte de mémoire contiguë pour le programmeur;mémoire contiguë pour le programmeur;
• gestionnaire de mémoire travaille d ’une gestionnaire de mémoire travaille d ’une manière transparente au service des manière transparente au service des processus.processus.
Processus, mémoire et ordonnancement
30
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Gestionnaire de la mémoire:Gestionnaire de la mémoire:• intimement lié à l’architecture de intimement lié à l’architecture de
l’ordinateur; l’ordinateur;
Organisation de la mémoire:Organisation de la mémoire:• pages de taille fixe (8 Ko);pages de taille fixe (8 Ko);
• adresse physique adresse physique {page, décalage}; {page, décalage};
• MMU (MMU (Memory Management UnitMemory Management Unit) sert à ) sert à convertir les adresses physiques en convertir les adresses physiques en adresses virtuelles et vice versa.adresses virtuelles et vice versa.
31
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Conversion adresse physique Conversion adresse physique adresse virtuelle:adresse virtuelle:• simple opération simple opération LUTLUT ( (Look Up TableLook Up Table););
• gestionnaire de mémoire est gestionnaire de mémoire est responsable de placer la bonne table responsable de placer la bonne table dans le MMU.dans le MMU.
G estio n n aire d ela m ém o ire
v irtuelle
M M U
M ém o ire p h ysique
A d resse p h ysique {p age, d écalage}
T ab le d eco n v ersio n
P ro cesseur
Adr
esse
virt
uelle
32
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Augmenter la vitesse des Augmenter la vitesse des conversions:conversions:• mettre le contenu des adresses mettre le contenu des adresses
converties dans le VAC (converties dans le VAC (Virtual Virtual Address CacheAddress Cache););
• fouiller d ’abord dans le VAC avant de fouiller d ’abord dans le VAC avant de passer à MMU.passer à MMU.
G estio n n aire d ela m ém o ire
v irtuelle
M M U
A n té- m ém o ire A d resse p h ysique {p age, d écalage}
T ab le d eco n v ersio n
P ro cesseur
V A C
M ém o ire p h ysique
Adr
esse
virt
uelle
33
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Déroulement d’un accès de mémoire:Déroulement d’un accès de mémoire:• requête initiée par le processeur en requête initiée par le processeur en
utilisant l’adresse virtuelle d’un processus;utilisant l’adresse virtuelle d’un processus;
• requête captée par le VAC. Si possible, requête captée par le VAC. Si possible, retourner le contenu de l ’adresse au retourner le contenu de l ’adresse au processeur;processeur;
• si non, l ’adresse virtuelle est passée à si non, l ’adresse virtuelle est passée à MMU;MMU;
• MMU MMU conversion valide conversion valide le contenu de le contenu de l’adresse virtuelle est en mémoire; l’adresse virtuelle est en mémoire;
34
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Déroulement d’un accès de mémoire Déroulement d’un accès de mémoire (suite):(suite):• MMU MMU conversion invalide conversion invalide faute de faute de
page (page fault);page (page fault);
• faute de page faute de page le contenu de l ’adresse le contenu de l ’adresse virtuelle est en mémoire secondaire virtuelle est en mémoire secondaire (disque);(disque);
• faute de page faute de page charger la page charger la page manquante à partir du système de fichier manquante à partir du système de fichier ((swap areaswap area); );
35
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Déroulement d’un accès de mémoire Déroulement d’un accès de mémoire (suite):(suite):• chargement du contenu de l’adresse chargement du contenu de l’adresse
virtuelle de la mémoire secondaire virtuelle de la mémoire secondaire transfert immédiat dans le VAC puis dans transfert immédiat dans le VAC puis dans le processeur; le processeur;
Transfert des données de/vers le VAC Transfert des données de/vers le VAC pose un problème:pose un problème:• il peut exister deux copies d’une même il peut exister deux copies d’une même
donnée; donnée;
36
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Transfert des données de/vers le Transfert des données de/vers le VAC pose un problème (suite):VAC pose un problème (suite):• une copie dans le VAC et l’autre dans la une copie dans le VAC et l’autre dans la
mémoire;mémoire;
Pour protéger l’intégrité des Pour protéger l’intégrité des données:données:• VAC à VAC à écriture immédiateécriture immédiate ( (write-write-
throughthrough););
• VAC à VAC à écriture déféréeécriture déférée ( (write-backwrite-back).).
37
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Structures de données pour la Structures de données pour la gestion de la mémoire:gestion de la mémoire:• objets nommés objets nommés objets visibles dans objets visibles dans
le système de fichiers;le système de fichiers;
• objets anonymes objets anonymes objets invisibles objets invisibles dans le système de fichier;dans le système de fichier;
Fichiers, répertoires, Fichiers, répertoires, tuyaux nommés, les tuyaux nommés, les sockets, les sockets, les périphériques, etc.périphériques, etc.
Sémaphores, Sémaphores, verrous, mémoire verrous, mémoire partagée, segments partagée, segments « Pile », « Données « Pile », « Données non initialisées », etc.non initialisées », etc.
38
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Structures de données pour la Structures de données pour la gestion de la mémoire:gestion de la mémoire:
as
a_segs
a_hat
kas
as
a_segs
a_hat
proc
p_as
vnode
anon
vnode
anon
a_seg
a_seg
vnode
anon
a_seg
vnode
anon
a_seg
E sp ace d 'ad resses d u n o yau
E sp ace d 'ad resses d 'u tilisateur
L e M M U (H A T ) H A T (H a rdw a re A ddress T ra n sla tion )
39
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Structures de données pour la gestion Structures de données pour la gestion de la mémoire (suite):de la mémoire (suite):• vnodevnode structure de données associée à structure de données associée à
une page de mémoire (objets nommés);une page de mémoire (objets nommés);
• anonanon structure de données associée à structure de données associée à une page de mémoire (objets anonymes);une page de mémoire (objets anonymes);
• a_hata_hat structure contenant les structure contenant les paramètres matériels de MMU pour le paramètres matériels de MMU pour le processus;processus;
40
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Structures de données pour la gestion Structures de données pour la gestion de la mémoire (suite):de la mémoire (suite):• Quatre listes de pages: 1) liste des pages Quatre listes de pages: 1) liste des pages
libres; 2) liste des pages libres; 2) liste des pages vnodevnode; 3) liste de ; 3) liste de hachage; 4) liste des pages hachage; 4) liste des pages anonanon..
• pages pages anonanon espace d’échange ( espace d’échange (swap swap spacespace) paginé de la même façon que la ) paginé de la même façon que la mémoire physique;mémoire physique;
• pages pages anonanon occupe une partition occupe une partition distincte du disque rigide. distincte du disque rigide.
41
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Techniques de gestion:Techniques de gestion:• durant la vie d’un processus, des pages durant la vie d’un processus, des pages
sont réclamées et d’autres sont libérées;sont réclamées et d’autres sont libérées;
• pages réclamées pages réclamées enlevées de la liste des enlevées de la liste des pages libres;pages libres;
• pages libérées pages libérées retournées dans la liste retournées dans la liste des pages libres;des pages libres;
• Protocole Protocole LRULRU ( (Least Recently UsedLeast Recently Used) pour ) pour la réclamation et la libération des pages la réclamation et la libération des pages mémoire.mémoire.
42
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Techniques de gestion (suite):Techniques de gestion (suite):• Protocole LRU.Protocole LRU.
R éclam atio n L ib ératio nL iste d es p ages lib res
Prendre les pages libres Prendre les pages libres à la tête de la listeà la tête de la liste
Remettre les pages Remettre les pages libérées à la fin de la libérées à la fin de la liste des pages libresliste des pages libres
Les pages réclamées seront celles qui ont été Les pages réclamées seront celles qui ont été délaissées depuis longtemps.délaissées depuis longtemps.
43
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Résumé:Résumé:
vnode
vnode
L iste d es p ages lib res
T ab leau d eh ach age
anon_map
P ages d e la m ém o irean o n ym e
structure anon
L iste d es p ages d e vnode
segm en t
segm en t
44
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Gestion globale de la mémoire.Gestion globale de la mémoire. Processus effectue un adressage Processus effectue un adressage
(lecture ou écriture de la mémoire).(lecture ou écriture de la mémoire).• S.E. vérifie dans le VAC afin de trouver le S.E. vérifie dans le VAC afin de trouver le
contenu de l’adresse virtuelle demandée;contenu de l’adresse virtuelle demandée;
• S.E. vérifie dans le MMU pour savoir s’il S.E. vérifie dans le MMU pour savoir s’il dispose d ’une table de conversion valide dispose d ’une table de conversion valide pour le processus;pour le processus;
ET/OUET/OU
45
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Lors de la lecture ou l’écriture (suite):Lors de la lecture ou l’écriture (suite):• si la page n’est pas en mémoire, le S.E. si la page n’est pas en mémoire, le S.E.
vérifie la liste des pages libres;vérifie la liste des pages libres;
• si le nombre de pages libres est suffisant à si le nombre de pages libres est suffisant à la demande, le S.E. va associer une page la demande, le S.E. va associer une page libre dans l ’espace virtuel (via le libre dans l ’espace virtuel (via le vnodevnode approprié);approprié);
• s’il est insuffisant, le S.E. doit déplacer s’il est insuffisant, le S.E. doit déplacer certaines pages utilisées hors de la mémoire certaines pages utilisées hors de la mémoire puis les récupérer pour le processus puis les récupérer pour le processus demandeur.demandeur.
46
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Lors de la lecture ou l’écriture (suite):Lors de la lecture ou l’écriture (suite):• S.E. copie alors le contenu adressé dans la S.E. copie alors le contenu adressé dans la
page allouée.page allouée.
Déplacement des pages pour faire de la Déplacement des pages pour faire de la place:place:• swapperswapper (PID = 0) responsable des (PID = 0) responsable des
déplacements;déplacements;
• déplacement des pages vers le déplacement des pages vers le swap spaceswap space;;
• page daemonpage daemon (PID = 2) réalise la procédure de (PID = 2) réalise la procédure de déplacement.déplacement.
47
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Pour découvrir les pages à déplacer:Pour découvrir les pages à déplacer:• algorithme algorithme THCTHC ( (Two-handed ClockTwo-handed Clock).).
Algorithme THC:Algorithme THC:• deux variables;deux variables;
• minmin = = QMPDQMPD / 64, / 64, maxmax = = QMPDQMPD / 16; / 16;
• QMPDQMPD Quantité de Mémoire Physique Quantité de Mémoire Physique disponible. Comptabilisée lors du disponible. Comptabilisée lors du démarrage de la machine.démarrage de la machine.
48
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Algorithme THC:Algorithme THC:• but but conserver toujours la mémoire conserver toujours la mémoire
disponible à l’intérieur des limites disponible à l’intérieur des limites minmin et et maxmax;;
• quatre (4) par seconde (250 ms) quatre (4) par seconde (250 ms) algorithme THC est enclenché;algorithme THC est enclenché;
• si si MMrr + + MMdd < < maxmax alors un signal est alors un signal est envoyé au envoyé au page daemonpage daemon par le S.E. pour par le S.E. pour déplacer des pages hors de la mémoire.déplacer des pages hors de la mémoire.Quantité de mémoire réclaméeQuantité de mémoire réclamée
Quantité de mémoire Quantité de mémoire disponibledisponible
49
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Principe de l’algorithme THC:Principe de l’algorithme THC:P ages d e m ém o ire
Analogie
P o in teur B
P o in teur A
B
A
L’A
lgori
t hm
e T
HC
S’o
pèr e
L ’
Alg
ori
thm
e T
HC
S’o
père
su
r d
es
liste
s d
e p
ag
es
s ur
des
li st e
s d
e p
ag
es
50
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Paramètres de l’algorithme THC:Paramètres de l’algorithme THC:
M o
M ém o ire d u systèm e (ex cluan t la m ém o ire v erro u illée p ar le n o yau)
min max
SLOWSCANFASTSCAN
m ain ten ir la m ém o ired isp o n ib le d an s cette
zo n e
D éclen ch em en t d el'algo rith m e T H C
M ém o ire d isp o n ib le au tem p s t.
P o in teur AP o in teur B
handspreadpages
B alayage à la v itesse scanrate
51
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Si le déplacement des pages n’est pas Si le déplacement des pages n’est pas suffisant …suffisant …
Il faut déplacer les processus au complet.Il faut déplacer les processus au complet. C ’est le C ’est le swapperswapper qui en est le responsable. qui en est le responsable.
• nswappednswapped, nombre de fils déplacés;, nombre de fils déplacés;• runoutrunout, nombre de fils à remettre en mémoire;, nombre de fils à remettre en mémoire;• runinrunin, besoin de remettre en mémoire un fil , besoin de remettre en mémoire un fil
mais la mémoire physique est insuffisante;mais la mémoire physique est insuffisante;• tune_t_gpgslotune_t_gpgslo, le niveau de mémoire , le niveau de mémoire
disponible qui déclenchera le déplacement des disponible qui déclenchera le déplacement des processus.processus.
52
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Conditions pour le démarrage du Conditions pour le démarrage du swapperswapper::
M ém o ire lib re <tune_t_gpgslo ?
D ém arrage d usw a pper
O U I
L e s w a p p e r n ' e s t p a sd ém arré
N O N
R e m e t t r e l e s p r o c e s s u sd ép lacés en m ém o ire (sw a p in )
nswapped > 0 ?N O N
runout > 0 ?D ép lac em en t d es p ro c essu s v e rs l 'e sp ac ed 'échan ge (sw a p in )
V érifi catio n un e fo is p arseco n d e (1H z)
N O N
53
Processus, mémoire et ordonnancement
Étapes d’un Étapes d’un swapoutswapout::
S é l e c t i o n d e s fi l sd 'e x é c u t io n à d é p lac e rd an s l'esp ace d 'éch an ge
C h o isir le fi l ayan t la p lusb asse p rio rité
nswapped = nswapped + 1
D ép lacer la p ile d u n o yau et las t r u c t u r e L W P d u fi ld ' e x é c u t i o n d a n s l ' e s p a c ed 'éch an ge
D ern ier fi l d 'ex écutio nd u p ro cessus ?
O U I
D ép lacer to u tes les p ages d up ro cessus
N O N
54
Processus, mémoire et ordonnancement
Étapes d’un Étapes d’un swapinswapin::
S é l e c t i o n d e s fi l sd 'ex écutio n à rem ettre enm ém o ire
C h o isir le fi l ayan t la p lush aute p rio rité
nswapped = nswapped - 1
C h arger la p ile d u n o yau et las t r u c t u r e L W P d u fi ld 'ex écutio n en m ém o ire
D ern ier fi l d 'ex écutio nd u p ro cessus ?
O U I
C h arger to u tes les p ages d up ro cessus
N O N
55
Gestion de la mémoireGestion de la mémoire
Processus, mémoire et ordonnancement
Cas où le manque de mémoire Cas où le manque de mémoire physique empêche le physique empêche le swapperswapper de de remettre le processus en mémoire:remettre le processus en mémoire:
runin > 0 ?
P lace le sw ap p er d an s laliste d 'atten te d u n o yau
O U I
P o u r le m o m en t, il n 'y ap a s d e p r o c e s s u s àrem ettre en m ém o ire
N O N
runin > 0, cela sign ifi e qu 'ile x i s t e d e s p r o c e s s u s àrem ettre en m ém o ire. M ais àc au se d e l 'in su ff isan c e d e lam ém o ire , c ette o p ératio n n ep e u t ê t r e r é a l i s é e p o u r l em o m en t.
C h a r g e m e n t d e sp r o c e s s u s e n m é m o i r e(sw a p in )
56
OrdonnancementOrdonnancement
Processus, mémoire et ordonnancement
Classes d’ordonnancement:Classes d’ordonnancement:• permet aux programmeurs de déterminer le permet aux programmeurs de déterminer le
type d’ordonnancement de leurs type d’ordonnancement de leurs applications;applications;
• mieux répondre aux applications nouvelles;mieux répondre aux applications nouvelles;
• chaque classe possède des caractéristiques chaque classe possède des caractéristiques différentes;différentes;
• chaque classe chaque classe priorité, durée d’exécution; priorité, durée d’exécution;
• processus peut changer de classe par appels processus peut changer de classe par appels système.système.
57
OrdonnancementOrdonnancement
Processus, mémoire et ordonnancement
Stratégie d’ordonnancement:Stratégie d’ordonnancement:
P
P - 1
P - 2
0
Q ueue d 'ex écutio n d e p rio rité0 à P . I l ex iste un e queue p arp ro cesseur
L iste d es fi ls d 'ex écutio n . L esfi ls d e ch aque liste p o ssèd en tla m êm e p rio rité
" ch acun so n to ur" est lam éth o d e d 'o rd o n n an cem en td es fi ls d e m êm e p rio rité
58
OrdonnancementOrdonnancement
Processus, mémoire et ordonnancement
Stratégie d’ordonnancement:Stratégie d’ordonnancement:• priorité assignée initialement par le S.E. priorité assignée initialement par le S.E.
selon la classe du fil d’exécution;selon la classe du fil d’exécution;
• priorité peut varier au cous de l’existence du priorité peut varier au cous de l’existence du fil d’exécution;fil d’exécution;
• ordonnanceur choisit le premier fil le plus ordonnanceur choisit le premier fil le plus prioritaire pour passer le contrôle du prioritaire pour passer le contrôle du processeur;processeur;
• ordonnanceur remet le fil exécuté à la fin de ordonnanceur remet le fil exécuté à la fin de la queue de priorité appropriée.la queue de priorité appropriée.
59
OrdonnancementOrdonnancement
Processus, mémoire et ordonnancement
Priorités Classe
160 – 169 Interruption
100 –159 RT (Temps réel)
60 – 99 SYS (Système)
0 – 59 TS (Temps partagé)
-1 Fil d’exécution vide (IDLE Thread)
Stratégie d’ordonnancement:Stratégie d’ordonnancement:
• classe TS classe TS par défaut pour tous les par défaut pour tous les processus en mode utilisateur;processus en mode utilisateur;
• classe SYS classe SYS les fils d’exécution du noyau, les fils d’exécution du noyau, priorité fixe, n ’est pas en temps partagé priorité fixe, n ’est pas en temps partagé mais son préemptibles.mais son préemptibles.
60
OrdonnancementOrdonnancement
Processus, mémoire et ordonnancement
Stratégie d’ordonnancement:Stratégie d’ordonnancement:• classe RT classe RT priorité fixe, en temps priorité fixe, en temps
partagé, durée d’exécution en fonction partagé, durée d’exécution en fonction de leur priorité;de leur priorité;
• interruption interruption toujours plus prioritaire toujours plus prioritaire que les autres classes, préempte les que les autres classes, préempte les autres fils d’exécution, pas en temps autres fils d’exécution, pas en temps partagé.partagé.
61
OrdonnancementOrdonnancement
Processus, mémoire et ordonnancement
Stratégie d’ordonnancement sans Stratégie d’ordonnancement sans préemption:préemption:• les fils d’interruption ont toujours une priorité les fils d’interruption ont toujours une priorité
plus haute que toutes les autres fils plus haute que toutes les autres fils d’exécution;d’exécution;
• système au repos, le fil d’exécution vide (système au repos, le fil d’exécution vide (idle idle threadthread) est ordonnancé;) est ordonnancé;
• le fil d’exécution ordonnancé est celui qui le fil d’exécution ordonnancé est celui qui possède la plus haute priorité. Les fils de même possède la plus haute priorité. Les fils de même priorité sont ordonnancés selon la technique priorité sont ordonnancés selon la technique « chacun son tour ».« chacun son tour ».
62
OrdonnancementOrdonnancement
Processus, mémoire et ordonnancement
Stratégie d’ordonnancement sans Stratégie d’ordonnancement sans préemption:préemption:• le fils d’exécution est bloqué en attente le fils d’exécution est bloqué en attente
d’une ressource ou la fin d ’une d’une ressource ou la fin d ’une opération d’E/S;opération d’E/S;
• le fil d’exécution a utilisé tout son temps le fil d’exécution a utilisé tout son temps alloué (traitement en temps partagé);alloué (traitement en temps partagé);
• le fil d’exécution subi une préemption;le fil d’exécution subi une préemption;
• le fil d’exécution a terminé son travail.le fil d’exécution a terminé son travail.Engendre un changement d ’état du processus. Une nouvelle Engendre un changement d ’état du processus. Une nouvelle valeur de priorité est assignée. Cette valeur est calculée à valeur de priorité est assignée. Cette valeur est calculée à partir d ’une table associée à la classe d’ordonnancement du partir d ’une table associée à la classe d’ordonnancement du processus.processus.
63
OrdonnancementOrdonnancement
Processus, mémoire et ordonnancement
Stratégie d’ordonnancement sans Stratégie d’ordonnancement sans préemption:préemption:• 100 fois par seconde, l’ordonnanceur 100 fois par seconde, l’ordonnanceur
vérifie s’il existe des fils à exécuter dans vérifie s’il existe des fils à exécuter dans la queue d ’exécution;la queue d ’exécution;
• dans le cas positif dans le cas positif l’ordonnanceur l’ordonnanceur choisit celui qui possède la plus haute choisit celui qui possède la plus haute priorité et lui passer le contrôle du priorité et lui passer le contrôle du processeur;processeur;
64
OrdonnancementOrdonnancement
Processus, mémoire et ordonnancement
Stratégie d’ordonnancement sans Stratégie d’ordonnancement sans préemption:préemption:• si le processeur est déjà occupé:si le processeur est déjà occupé:
• une nouvelle valeur de priorité est une nouvelle valeur de priorité est assignée;assignée;
• une nouvelle durée d ’exécution est une nouvelle durée d ’exécution est donnée;donnée;
• les fils sont déplacés à la fin de leurs listes les fils sont déplacés à la fin de leurs listes de priorité respectives;de priorité respectives;
• les fils perdent le contrôle du processeur.les fils perdent le contrôle du processeur.
65
OrdonnancementOrdonnancement
Processus, mémoire et ordonnancement
Stratégie d’ordonnancement avec Stratégie d’ordonnancement avec préemption:préemption:• même stratégie que l ’ordonnancement même stratégie que l ’ordonnancement
sans préemption;sans préemption;
• placer le fil préempté à la tête de sa liste placer le fil préempté à la tête de sa liste de priorité (sa priorité inchangée).de priorité (sa priorité inchangée).