Gestion de Mémoire (PDF)

Gestion de mémoire SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Résultat Stratégie d'allocation...

Gestion de mémoire SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Résultat Stratégie d'allocation de la mémoire ⮚ Savoir quelles zones sont libres et quelles zones sont utilisées. ⮚ Règles d'allocation : qui obtient de la mémoire, combien, quand, etc. ⮚ Techniques d'allocation – choix des lieux d'allocation et mises à jour des informations d'allocation. ⮚ Règles de désallocation : à qui reprendre de la mémoire, quand, etc. SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Résultat Stratégie d'allocation de la mémoire ⮚ Savoir quelles zones sont libres et quelles zones sont utilisées. ⮚ Règles d'allocation : qui obtient de la mémoire, combien, quand, etc. ⮚ Techniques d'allocation – choix des lieux d'allocation et mises à jour des informations d'allocation. ⮚ Règles de désallocation : à qui reprendre de la mémoire, quand, etc. SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Résultat Stratégie d'allocation de la mémoire La mémoire est le lieu ou se trouvent les programmes en cours d’exécution (Processus). La taille continuellement grandissante des programmes ==> insuffisance de mémoire. La gestionnaire de la mémoire est la partie qui se charge de : Connaitre les parties libres de la mémoire. Récupérer la mémoire libérée. Offrir au processus des services de mémoire virtuelle. Mémoire du cache: volatile, rapide, chère Mémoire centrale: volatile, moins rapide, moins chère Mémoire de masse - disque: non volatile, lente, moins chère SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire Mono-programmation Monopolisation de la mémoire par un seul processus. Gestion simple de la mémoire (seulement deux zones). SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire Mono-programmation Système de gestion simple La mémoire est divisée entre le SE et les processus utilisateur. Le SE est protégé des programmes de l'utilisateur (pour éviter que l'utilisateur n'écrive sur le code du SE). Avantages : ⮚ Simplicité ⮚ SE très réduit Inconvénients : ⮚ Mauvaise utilisation de la mémoire (un seul processus) et du processeur (attente des E/S). ⮚ Manque de flexibilité : les programmes sont limités à la mémoire existante. SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire Processus 3 Multi-programmation Processus 2 Présence de plusieurs processus en mémoire. o Maximiser le degré de multiprogrammation. Processus 1 o Meilleure utilisation de la mémoire et du CPU. SE Deux problèmes : o Réallocation. Partition 3 o Protection. Partition 2 Partition 1 SE SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire Méthodes d’allocation Pour un espace donné on peut choisir deux modes d’allocation : ▪ Allocation contiguë : consiste à placer la totalité d’un programme à des adresses consécutives ▪ Allocation non contiguë : consiste à fractionner le programme et à placer les différents fragments à des adresses dispersées SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire Techniques de gestion Divers types de gestion de la mémoire ont été utilisés. Dans l'allocation contiguë Partitionnement statique ⮚ Partitions fixes Partitionnement dynamique ⮚ Partitions variable Dans l’allocation non contiguë Segmentation Pagination simple Pagination à la demande Les systèmes récents utilisent la mémoire virtuelle SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire Partitionnement statique Partition 7 Méthode la plus simple : Partition 6 o La mémoire est partagé en plusieurs partitions de la même taille. Partition 5 o Chaque partition peut contenir un processus (limite du nombre de processus au Partition 4 nombre de partitions). Partition 3 o Quand une partition est libérée, un autre processus est choisi. Partition 2 Partition 1 SE SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire Partition 7 Partition 6 Partitionnement statique Partition 5 Deuxième organisation de l'allocation contiguë : o Les partitions sont soit de même taille ou de tailles inégales Partition 4 o N’importe quel programme peut être affecté à une partition qui soit suffisamment Partition 3 grande Partition 2 Partition 1 SE SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire Processus 3 Multi-programmation Processus 2 Présence de plusieurs processus en mémoire. Partitionnement statique Processus 1 o Division de l'espace mémoire en plusieurs partitions de tailles fixes SE o Nombre et tailles des partitions fixes a la génération du système. o Problème de fragmentation interne. Partition 3 Programmes absolus : Partition 2 Liaison statique entre les objets du programme et les adresse mémoire. Gestion de plusieurs files d'attente. Partition 1 SE SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire Programmes relogeables : Liaison dynamique entre les objets du programme et les adresse mémoire. SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire Partitionnement dynamique Partitions en nombre et tailles variables Chaque processus est alloué exactement la taille de mémoire requise Probablement des trous inutilisables se formeront dans la mémoire: c’est la fragmentation externe SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire Partitionnement dynamique SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation Partitionnement dynamique de la mémoire Partitionnement dynamique selon la demande ==> Taille Processus Elimination de la fragmentation interne. Partition Libre 1 Question : Ou loger le nouveau Processus F? Partition Libre 2 Réponse : plusieurs stratégies de placement existant SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation Partitionnement dynamique de la mémoire Partition Libre 1 Question : Ou loger le nouveau Processus F? Partition Libre 2 Réponse : plusieurs stratégies de placement existant SYSTÈME D’EXPLOITATION I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire First Fit A (Premier qui convient) Best Fit B (Meilleur qui convient) C Worst Fit (Pire qui convient) SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire First Fit (Premier qui convient) : Placer le processus dans la première partition libre de taille suffisante o Avantage : Rapidité o Inconvénient : ne prend pas en considération les autres partitions libres. Best Fit (Meilleur qui convient) : Placer le processus dans la plus petite partition libre de taille suffisante. o Avantage : Eviter le partitionnement des partitions libres de tailles importantes o Inconvénient : parcours de toute la liste des partitions libres (Couteuse en temps). Worst Fit (Pire qui convient) : Placer le processus dans la plus grande partition libre de taille suffisante. o Avantage : Eviter le partitionnement de minuscules trous mémoire. o Inconvénient : parcours de toute la liste des partitions libres (Couteuse en temps). SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire Quel est le meilleur? Critère principal: diminuer la probabilité de situations où un processus ne peut pas être servi, même s’il y a assez de mémoire... La simulation montre qu’il ne vaut pas la peine d’utiliser les algorithmes les plus complexes “Best-fit”: cherche le plus petit bloc possible: l’espace restant est le plus petit possible la mémoire se remplit de trous trop petits pour contenir un programme “Worst-fit”: les allocations se feront souvent à la fin de la mémoire et donc trop de temps... D’où le first fit SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire Types de fragmentation : o Fragmentation interne : Espace de partition inutilisable par le processus et ne pouvant pas être alloue a d'autres processus. o Fragmentation externe : Espace libre suffisant découpé en plusieurs partitions libres. SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation Mémoire virtuelle : Le va-et-vient de la mémoire o Problème : Que faire si la taille du processus est supérieure a la taille de la mémoire ? o Solution : Découper le processus en plusieurs parties et utiliser le Sawp-In / Sawp-Out Mémoire centrale Mémoire secondaire Question : Comment effectuer le découpage?? Réponse : techniques de la mémoire virtuelle SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation Mémoire virtuelle : Le va-et-vient de la mémoire Principe Taille programme + données + pile peut être > Taille mémoire disponible → Le SE conserve les parties en cours d’utilisation en mémoire et le reste sur disque. Quand un programme attend le chargement d’une partie de lui-même → il est en attente d’E/S pouvoir exécuter des processus sans qu'ils soient entièrement chargés en mémoire. Sans la mémoire virtuelle, un processus doit être entièrement chargé à des adresses contiguës. Avec la mémoire virtuelle, un processus peut être chargé dans des pages ou des segments non contigus. SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation Mémoire virtuelle : Le va-et-vient de la mémoire Pagination: Les adresses générées par un programme s’appellent des adresses virtuelles, et forment l’espace d’adressage virtuel. La MMU (Memory Management Unit, unité de gestion mémoire) fait la correspondance entre les adresses virtuelles et les adresses physiques. Espace d’adressage virtuel est divisé en pages. Les unités correspondantes dans la mémoire physique sont appelées cadres de pages (page frame). SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation Mémoire virtuelle : Le va-et-vient de la mémoire Pagination: SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation Mémoire virtuelle : Le va-et-vient de la mémoire Pagination: Dans l'exemple précédent, les pages ont une taille de 4 Ko. L'adresse virtuelle 12292 correspond à un déplacement de 4 octets dans la page virtuelle 3 (car 12292 = 12288 + 4 et 12288 = 12 * 1024). La page virtuelle 3 correspond à la page physique 2. L'adresse physique correspond donc à un déplacement de 4 octets dans la page physique 2, soit : (8 * 1024) + 4 = 8196. Par contre, la page virtuelle 2 n'est pas mappée. Une adresse virtuelle comprise entre 8192 et 12287 donnera lieu à un défaut de page. Il y a défaut de page lorsqu'il y a un accès à une adresse virtuelle correspondant à une page non mappée. En cas de défaut de page, un déroutement se produit (trap) et le processeur est rendu au système d'exploitation (SE). Le système doit alors effectuer les opérations suivantes : déterminer la page à décharger (page victime) ; déterminer la page à charger sur le disque pour libérer un cadre ; lire sur le disque la page à charger ; modifier la table des bits et la table des pages. SYSTÈME La sélection de la page à évincer est réalisée D’EXPLOITATION par les algorithmes de remplacement. Le principe de fonctionnement de la  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire Ex. Application: Un ordinateur dispose de 32 Mo de mémoire vive. Le système d'exploitation (OS) occupe 16 Mo. Chaque processus utilisateur nécessite 4 Mo. Questions : 1.Déterminer le niveau de multiprogrammation maximal. 2.Déterminer le taux d'utilisation du CPU si les processus sont indépendants et qu'un processus passe 80 % de son temps en attente d'E/S. 3.Combien peut-on améliorer ce taux si on ajoute 16 Mo de mémoire ? SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire Solutions: 1. Niveau de multiprogrammation maximal: La mémoire totale disponible pour les processus utilisateurs est : 32 Mo−16 Mo=16 Mo. Chaque processus utilisateur nécessite 4 Mo. Donc, le nombre maximum de processus qui peuvent être en mémoire (niveau de multiprogrammation) est : Niveau de multiprogrammation max=Mémoire disponible/ Mémoire par processus=16 Mo/4 Mo=4 SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire Solutions: 2. Taux d’utilisation du CPU Un processus passe 80 % de son temps en attente d’E/S, ce qui signifie qu'il n'utilise le CPU que 20 % du temps. Si le niveau de multiprogrammation est n, le taux d'utilisation du CPU est donné par : où : p est le pourcentage d'utilisation du CPU par un processus (p=0,2), n=4 (nombre maximum de processus en mémoire). Substituons les valeurs : Le taux d’utilisation du CPU est donc : SYSTÈME D’EXPLOITATION  I II III IV Gestion de mémoire V VI Introduction Stratégie d'allocation de la mémoire 3. Amélioration du taux d’utilisation du CPU avec 16 Mo supplémentaires  I II III IV Gestion de mémoire V VI Introduction Algo de remplacement de pages Algo NRU (Not Recently Used) Défaut de page Chercher une page à évincer, pour faire de la place pour la page à charger en mémoire. Si le bit M de la page à évincer = 1, la page doit être sauvée sur disque. Algo. optimal Question de performances, afin d’éviter le rechargement de pages, la page à évincer doit être peu utilisée. Étiquetage des pages : Chaque page en mémoire reçoit une "étiquette" qui indique combien de temps avant que cette page ne soit de nouveau utilisée. Par exemple, une page avec une étiquette de "10" signifie qu'elle sera utilisée après 10 étapes, tandis qu'une page avec une étiquette de "1" sera utilisée très bientôt. Evincer la page dont l’étiquette est la + grande (on repousse ainsi le défaut de page aussi tard que possible) Cet algo est irréalisable, le SE ne sait pas si la page serait référencée ou pas ultérieurement. (dans un système réel, vous ne savez pas à l'avance quels seront les prochains accès mémoire)  I II III IV Gestion de mémoire V VI Introduction Algo de remplacement de pages Algo NRU (Not Recently Used) Cet algorithme utilise les bits R et M associés à chaque page pour déterminer les pages non récemment utilisées. Le bit R est positionné à 1 chaque fois qu’une page est référencée. Il est remis à 0 à chaque interruption d’horloge. Le bit M est positionné à 1 lorsque la page est modifiée (elle n’est plus identique à sa copie sur le disque). Lorsqu’un défaut de page se produit, l’algorithme NRU (Not Recently Used) sélectionne la page à retirer en procédant comme suit : 1.Pages non référencées et non modifiées (R = 0 et M = 0) : Si de telles pages existent, l’algorithme sélectionne l’une d’entre elles et la retire. 2.Pages non référencées mais modifiées (R = 0 et M = 1) : Si aucune page de la première catégorie n’est trouvée, l’algorithme recherche ces pages. Si elles existent, il sélectionne l’une d’entre elles, la sauvegarde sur le disque (car elle est modifiée), puis la retire. 3.Pages référencées mais non modifiées (R = 1 et M = 0) : Si aucune page des deux premières catégories n’est trouvée, l’algorithme recherche ces pages. Si elles existent, il sélectionne l’une d’entre elles et la retire. 4.Pages référencées et modifiées (R = 1 et M = 1) : Si aucune autre page ne correspond aux catégories précédentes, l’algorithme sélectionne l’une de ces pages, la sauvegarde sur le disque, puis la retire.  I II III IV Gestion de mémoire V VI Introduction Algo de remplacement de pages Algo FIFO (1st In, 1st out) la page qui est en mémoire depuis le plus longtemps est la première à être évincée en cas de défaut de page. Cet algorithme est basé sur l'ordre d'arrivée des pages en mémoire, sans tenir compte de leur fréquence d'utilisation ou de leur importance. File d'attente des pages : Les pages en mémoire sont gérées comme une file d'attente. La première page insérée est celle qui sera retirée en premier. Ajout de nouvelles pages : Si la mémoire est pleine, la page située à l'avant de la file (la plus ancienne) est évincée pour faire de la place à la nouvelle page. Processus de remplacement : À chaque défaut de page, l'algorithme vérifie si la page demandée est en mémoire : Oui : Aucun remplacement n'est effectué. Non : La page la plus ancienne est retirée, et la nouvelle page est ajoutée à la file.  I II III IV Gestion de mémoire V VI Introduction Algo de remplacement de pages Algo. seconde chance Variante de FIFO avec une optimisation basée sur un bit d'utilisation. Si une page est sur le point d'être remplacée, mais que son bit d'utilisation est activé, elle obtient une "seconde chance" et le pointeur passe à la page suivante. Décision basée sur R :R = 1 : Conserver, déplacer à la fin de la liste et réinitialiser R.R = 0 : Remplacer, car la page est ancienne et inutilisée. Limitation : Les déplacements fréquents des pages dans la liste peuvent ralentir le processus. Exemple: Mémoire avec 3 emplacements (capacité 3 pages). Séquence des pages demandées : 1,2,3,4,1,2,5,1,2,3,4,5  I II III IV Gestion de mémoire V VI Introduction Algo de remplacement de pages Algo. seconde chance  I II III IV Gestion de mémoire V VI Introduction Algo de remplacement de pages Algo LRU (Least Recently Used) L'objectif de LRU est d'évincer la page qui n'a pas été utilisée depuis le plus longtemps, car elle est supposée être la moins probable d'être réutilisée bientôt. Chaque page en mémoire est suivie pour déterminer son dernier usage.  I II III IV Gestion de mémoire V VI Introduction Algo de remplacement de pages La segmentation L'espace d'adressage d'un processus est divisé en segments, générés lors de la compilation. Chaque segment est identifié par son numéro S et sa longueur variable L. Un segment est un ensemble d'adresses virtuelles contiguës Contrairement à la pagination, la segmentation est "connue" du processus : une adresse n'est plus donnée de façon absolue par rapport au début de l'adressage virtuel; une adresse est donnée par un couple (S , d), où S est le n° du segment et d le déplacement dans le segment, d € [0 , L [. Pour calculer l'adresse physique, on utilise une table des segments :  I II III IV Gestion de mémoire V VI Introduction Algo de remplacement de pages La segmentation La segmentation permet de gérer plus facilement les objets qui peuvent changer de taille dynamiquement. Par exemple, si des objets sont stockés dans des segments distincts et que la taille de ces objets change, il est plus simple de réorganiser ou redimensionner ces segments sans perturber l'ensemble du processus. Cela rend la gestion de la mémoire plus flexible, contrairement à une approche de "partitionnement" statique B : adresse de base (adresse physique de début du segment) L : longueur du segment ou limite p : protection du segment L'adresse physique correspondant à l'adresse virtuelle (S, d) sera donc : adresse physique = B + d, si d