Systmes dexploitation Gestion de la mmoire

CHAPITRE 5 :

LA GESTION DE LA MEMOIRE

Objectifs spcifiques Connatre le principe de gestion de mmoire en monoprogrammation Connatre le principe de gestion de mmoire en multiprogrammation Connatre le principe de gestion de mmoire avec va et vient Connatre la notion de compactage Connatre la notion de mmoire virtuelle et son utilit, Connatre le concept de pagination et son principe Connatre les diffrents algorithmes de remplacement et maitriser leur application Connatre le concept de segmentation. Elments de contenu I. Introduction la gestion de la mmoire II. Gestion sans recouvrement ni pagination III. Gestion avec recouvrement sans pagination IV. Gestion avec recouvrement, avec pagination ou segmentation Volume Horaire : Cours : 4 heures 30 TD : 3 heures

5.1

Introduction

La mmoire physique sur un systme se divise en deux catgories : la mmoire vive : compose de circuit intgrs, donc trs rapide. la mmoire de masse (secondaire) : compose de supports magntiques (disque dur, bandes magntiques...), qui est beaucoup plus lente que la mmoire vive. La mmoire est une ressource rare. Il n'en existe qu'un seul exemplaire et tous les processus actifs doivent la partager. Si les mcanismes de gestion de ce partage sont peu efficaces l'ordinateur sera peu performant, quelque soit la puissance de son processeur. Celui-ci sera souvent interrompu en attente d'un change qu'il aura rclam. Si un programme viole les rgles de fonctionnement de la mmoire, il

Mlle I.Sghaier

- 29

Systmes dexploitation Gestion de la mmoire

en sera de mme. Dans ce chapitre on va mettre laccent sur la gestion de la mmoire pour le stockage des processus concurrents.

5.2
5.2.1

Gestion sans recouvrement ni pagination

La monoprogrammation : Le modle de base

La reprsentation de base, pour un systme monoprocesseur et mono tche, est montre dans figure suivante : il sagit dune partition contigu.

Figure 3 : Les trois organisations de base pour un systme mono tche.

En gnral, le systme d'exploitation se trouve au niveau des premires adresses de la zone mmoire de la RAM. Pour des systmes avec un SE embarqu (consoles de jeu, tlphones mobiles, etc) le systme se trouve souvent dans une partie non modifiable (ROM). Afin de garantir de faon transparente mais flexible, l'amorage d'un systme quelconque, on retrouve souvent une combinaison des deux approches (RAM et ROM). La ROM contient alors un systme minimal permettant de piloter les priphriques de base (clavier -- disque -- cran) et de charger le code d'amorage un endroit bien prcis. Ce code est excut lors de la mise sous tension de l'ordinateur, et le vrai systme d'exploitation, se trouvant dans la zone d'amorage sur le disque, est ensuite charg, prenant le relais du systme minimal.

5.2.2

La multipligrammation a. Multiprogrammation avec partitions fixes

i. Partition fixes de tailles gales

Cette partition peut tre faite une fois pour toute au dmarrage du systme par loprateur de la machine, qui subdivise la mmoire en partitions fixes de tailles gales. Chaque nouveau processus est plac dans une partition vide. Ceci engendrera le problme de fragmentation interne due au faite que si

Mlle I.Sghaier

- 30

Systmes dexploitation Gestion de la mmoire

la taille de partition est suprieure lespace recueilli par un certain processus le reste de cette partition restera vide ce qui cause une perte despace mmoire. Le sous systme charg de la gestion de mmoire met en place une structure des donnes appele table des partitions ayant pour rle lindication de ltat (libre ou occupe) de chaque partition en identifiant chacune soit par son adresse soit par son numro.

ii.

Partition fixes de tailles ingales

Dans ce cas la mmoire est subdivise en partitions de tailles ingales. Chaque nouveau processus est plac dans la file dattente de la plus petite partition qui peut le contenir. Cette faon de faire peut conduire faire attendre un processus dans une file, alors quune autre partition pouvant le contenir est libre. Il existe deux mthodes de gestion : on cre une file d'attente par partition. Chaque nouveau processus est plac dans la file d'attente de la plus petite partition pouvant le contenir. Inconvnients : on perd en gnral de la place au sein de chaque partition il peut y avoir des partitions inutilises (leur file d'attente est vide) Ds qu'une partition se libre, on lui affecte la premire tche de la file qui peut y tenir. Inconvnient : on peut ainsi affecter une partition de grande taille une petite tche et perdre beaucoup de place Ds qu'une partition se libre, on lui affecte la plus grande tche de la file qui peut y tenir. Inconvnient : on pnalise les processus de petite taille. Lalternative cette approche consiste nutiliser quune seule file dattente : ds quune partition se libre, le systme y place le premier processus de la file qui peut y tenir. Cette solution rduit la fragmentation interne de la mmoire.

on cre une seule file d'attente globale. Il existe deux stratgies :

b. Multiprogrammation avec partitions variables

Au lancement du systme, on cre une seule zone libre de taille maximale. Lorsqu'on charge un programme, on le place dans une zone libre suffisante, et on lui alloue exactement la mmoire ncessaire. Le reste devient une nouvelle zone libre. Lorsqu'un programme s'achve, sa partition redevient libre, et peut ventuellement grossir une zone libre voisine. Il n'y a donc ce quon appelle fragmentation externe.

Mlle I.Sghaier

- 31

Systmes dexploitation Gestion de la mmoire

Figure 4: Principe d'allocation de partitions de taille variable.

La solution la plus flexible est d'adopter un systme avec des partitions de taille variable et un systme de va-et-vient qui permet d'utiliser le disque comme mmoire secondaire et d'y stocker un nombre de processus inactifs ou en attente.

5.3

Gestion avec recouvrement sans pagination

Ds que le nombre de processus devient suprieur au nombre de partitions, il faut pouvoir simuler la prsence en mmoire centrale (MC) de tous les processus pour pouvoir satisfaire au principe d'quit et minimiser le temps de rponse des processus. La technique du recouvrement permet de stocker temporairement sur disque des images de processus afin de librer de la MC pour d'autres processus. On pourrait utiliser des partitions fixes, mais on utilise en pratique des partitions de taille variable, car le nombre, la taille et la position des processus peuvent varier dynamiquement au cours du temps. On n'est plus limit par des partitions trop grandes ou trop petites comme avec les partitions fixes. Cette amlioration de l'usage de la MC ncessite un mcanisme plus complexe d'allocation et de libration.

5.3.1

Le va et vient

Conceptuellement le va-et-vient, ou swap, se comporte exactement comme la mmoire vive, la diffrence prs qu'on ne peut y excuter des processus (pour excuter un processus sur le swap, il faut le charger en mmoire vive), ainsi que quelques considrations lies au mdium de stockage, qui impose un accs et un stockage par blocs, mais que l'on peut ngliger. Un processus qui est inactif (soit bloqu, soit prt) peut donc tre plac dans le swap. Les stratgies de choix des processus crire sur disque sont sensiblement identiques celles mises en uvre pour l'ordonnancement des processus. Il est noter qu'il existe deux types de solution : soit on alloue une place fixe dans le swap, pour chaque processus cr, soit on utilise le swap comme une grande zone de stockage dans laquelle les processus sont crits selon les besoins et un endroit dtermin en fonction de l'occupation au moment de l'criture.

Mlle I.Sghaier

- 32

Systmes dexploitation Gestion de la mmoire

Figure 5 : Gestion de la mmoire avec va et vient

5.3.2

Oprations sur la mmoire

Le compactage de la mmoire permet de regrouper les espaces inutiliss. Trs coteuse en temps UC, cette opration est effectue le moins souvent possible. S'il y a une requte d'allocation dynamique de mmoire pour un processus, on lui alloue de la place dans le tas (heap) si le SE le permet, ou bien de la mmoire supplmentaire contigu la partition du processus (agrandissement de celle-ci). Quand il n'y a plus de place, on dplace un ou plusieurs processus : soit pour rcuprer par ce moyen des espaces inutiliss, soit en allant jusqu'au recouvrement. A chaque retour de recouvrement (swap), on rserve au processus une partition un peu plus grande que ncessaire, utilisable pour l'extension de la partition du processus venant d'tre charg ou du processus voisin. Il existe trois faons de mmoriser l'occupation de la mmoire : les tables de bits (bits maps), les listes chanes et les subdivisions (buddy). Comme on le voit sur le schma suivant on distingue trois mthodes de compactage : La premire consiste tout simplement recopier de mmoire mmoire le programme dplacer. Elle monopolise le processeur pour effectuer la copie ; La seconde effectue une copie du programme dplacer vers le disque, puis une seconde copie du disque vers la mmoire au nouvel emplacement. Curieuse a priori, cette mthode s'explique et se justifie si le transfert de mmoire disque et de disque mmoire est effectu par un canal d'E/S, processeur spcialis dans les changes, qui laisse donc le processeur libre pendant les transferts. La recopie cote toutefois un certain ralentissement du processeur, par vol de cycles. La dernire mthode est encore plus curieuse, mais se dduit de la seconde. On utilise deux canaux d'E/S, et on les boucle. L'utilisation de deux canaux est plus coteuse que l'usage

Mlle I.Sghaier

- 33

Systmes dexploitation Gestion de la mmoire

d'un disque, mais la copie est plus rapide. Il faut tout de mme noter que les deux canaux vont voler des cycles au processeur de calcul, et l'un l'autre, ce qui ralentit un peu. Rq : Quelle que soit la mthode choisie, le compactage est coteux.

Figure 6 : Diffrentes stratgies de compactage

5.3.3

Gestion de la mmoire par table de bits

On divise la MC en units d'allocations de quelques octets quelques Ko. A chaque unit, correspond un bit de la table de bits : valeur 0 si l'unit est libre, 1 sinon. Cette table est stocke en MC. Plus la taille moyenne des units est faible, plus la table occupe de place. A un retour de recouvrement (swap), le gestionnaire doit rechercher suffisamment de 0 conscutifs dans la table pour que la taille cumule de ces units permette de loger le nouveau processus implanter en MC, avec le choix entre trois algorithmes dallocation possibles : First-fit : la premire zone libre : en parcourant la liste libre, on retient la premire zone suffisante ; on alloue la partie suffisante pour le programme, et le reste devient une nouvelle zone libre plus petite. Best-fit : le meilleur ajustement, on recherche dans la liste la plus petite zone possible. Cette mthode est plus coteuse et peut crer ainsi de nombreuses petites units rsiduelles inutilisables (fragmentation ncessitant un compactage ultrieur), mais vite de couper inutilement une grande zone. worst fit : le plus grand rsidu, on recherche la zone qui laissera le plus petit rsidu avec le risque de fractionnement regrettable des grandes units.

5.3.4

Gestion de la mmoire par liste chane

On utilise une liste chane des zones libres en MC. On applique :

Mlle I.Sghaier

- 34

Systmes dexploitation Gestion de la mmoire

soit l'un des algorithmes prcdents, soit un algorithme de placement rapide (quick fit) : on cre des listes spares pour chacune des tailles les plus courantes, et la recherche est considrablement acclre.

A l'achvement d'un processus ou son transfert sur disque, il faut du temps (mise jour des listes chanes) pour examiner si un regroupement avec ses voisins est possible pour viter une fragmentation excessive de la mmoire. En rsum, les listes chanes sont une solution plus rapide que la prcdente pour l'allocation, mais plus lente pour la libration.

5.3.5

Gestion de la mmoire par subdivisions (ou frres siamois)

Cet algorithme utilise l'existence d'adresses binaires pour acclrer la fusion des zones libres adjacentes lors de la libration d'units. Le gestionnaire mmorise une liste de blocs libres dont la taille est une puissance de 2 (1, 2, 4, 8 octets, ...., jusqu' la taille maximale de la mmoire). Par exemple, avec une mmoire de 1 Mo, on a ainsi 251 listes. Initialement, la mmoire est vide. Toutes les listes sont vides, sauf la liste 1 Mo qui pointe sur la zone libre de 1 Mo :

Un processus A demande 70 Ko : la mmoire est fragmente en deux compagnons (buddies) de 512 Ko; l'un d'eux est fragment en deux blocs de 256 Ko; l'un d'eux est fragment en deux blocs de 128 Ko et on loge A dans l'un d'eux, puisque 64 < 70 < 128 :

Un processus B demande 35 Ko : l'un des deux blocs de 128 Ko est fragment en deux de 64 Ko et on loge B dans l'un d'eux puisque 32 < 35 < 64 :

Un processus C demande 80 Ko : le bloc de 256 Ko est fragment en deux de 128 Ko et on loge C dans l'un d'eux puisque 64 < 80 < 128 :

A s'achve et libre son bloc de 128 Ko. Puis un processus D demande 60 Ko : le bloc libr par A est fragment en deux de 64 Ko, dont l'un logera D :

B s'achve, permettant la reconstitution d'un bloc de 128 Ko :

D s'achve, permettant la reconstitution d'un bloc de 256 Ko , etc...

Mlle I.Sghaier

- 35

Systmes dexploitation Gestion de la mmoire

L'allocation et la libration des blocs sont trs simples. Mais un processus de taille 2n + 1 octets utilisera un bloc de 2n+1 octets ! Il y a beaucoup de perte de place en mmoire. Dans certains systmes, on n'alloue pas une place fixe sur disque aux processus qui sont en mmoire. On les loge dans un espace de va et vient (swap area) du disque. Les algorithmes prcdents sont utiliss pour l'affectation.

5.4
5.4.1

Gestion avec recouvrement, avec pagination ou segmentation

Notion de mmoire virtuelle

La taille d'un processus doit pouvoir dpasser la taille de la mmoire physique disponible, mme si l'on enlve tous les autres processus. Afin dassurer une extension de la mmoire il existe 2 manires : En dcoupant un programme en une partie rsidente en mmoire vive et une partie charge uniquement en mmoire lorsque l'accs ces donnes est ncessaire. En utilisant un mcanisme de mmoire virtuelle, consistant utiliser le disque dur comme mmoire principale et stocker uniquement dans la RAM les instructions et les donnes utilises par le processeur. Le systme d'exploitation ralise cette opration en crant un fichier temporaire (appel fichier SWAP, traduit "fichier d'change") dans lequel sont stockes les informations lorsque la quantit de mmoire vive n'est plus suffisante. Cette opration se traduit par une baisse considrable des performances, tant donn que le temps d'accs du disque dur est extrmement plus faible que celui de la RAM. Lors de l'utilisation de la mmoire virtuelle, il est courant de constater que la LED du disque dur reste quasiment constamment allume et dans le cas du systme Microsoft Windows qu'un fichier appel "win386.swp" d'une taille consquente, proportionnelle aux besoins en mmoire vive, fait son apparition. La Mmoire Virtuelle est une mmoire idale, dont les adresses commencent 0, et de capacit non limite ; elle a pour but principal de pouvoir excuter des processus sans qu'ils soient logs en mmoire en leur totalit ; sans recours la mmoire virtuelle, un processus est entirement charg des adresses contigus ; avec le recours la mmoire virtuelle, un processus peut tre charg dans des pages ou des segments non contigus. On appelle Espace Virtuel l'ensemble des adresses possibles ; il est fix par le nombre de bits qui constitue une adresse virtuelle. On parlera d'adresse relle et d'adresse virtuelle. Toute la difficult consiste traduire une adresse virtuelle (A.V.) en une adresse relle (A.R.) accessible sur la machine.

Mlle I.Sghaier

- 36

Systmes dexploitation Gestion de la mmoire

5.4.2

La pagination

L'espace d'adressage d'un processus est divis en petites units de taille fixe appeles pages. La MC est elle aussi dcoupe en units physiques de mme taille appeles cadres. Les changes entre MC et disques ne portent que sur des pages entires. De ce fait, l'espace d'adressage d'un processus est potentiellement illimit (limit l'espace mmoire total de la machine). On parle alors d'adressage virtuel. Pour un processus, le systme ne chargera que les pages utilises. Mais la demande de pages charger peut tre plus leve que le nombre de cadres disponibles. Une gestion de l'allocation des cadres libres est ncessaire. Dans un SE sans mmoire virtuelle, la machine calcule les adresses physiques en ajoutant le contenu d'un registre de base aux adresses relatives contenues dans les instructions du processus. Dans un SE pagination, un sous-ensemble insr entre l'UC et la MC, la MMU (Memory Management Unit ou unit de gestion de la mmoire) traduit les adresses virtuelles en adresses physiques. La MMU mmorise : les cadres physiques allous des processus (sous forme d'une table de bits de prsence) les cadres mmoire allous chaque page d'un processus (sous forme d'une table des pages ) On dira qu'une page est mappe ou charge si elle est physiquement prsente en mmoire.

Mlle I.Sghaier

- 37

Systmes dexploitation Gestion de la mmoire

adresses virtuelles 0-4 K 4-8K 8-12 K 12-16 8-12 K K 16-20 K 20-24 K 24-28 K 28-32 K 32-36 K 36-40 K 40-44 K 44-48 K

n page 0 1 2 3 4 5 6 7 8 9 10 11

prsence MMU table des pages x 0 1 x x 2 3 4 4 5 x 2 8

adresses physiques 0-4 K 4-8 K 8-12 K 12-16 K 16-20 K 20-24 K 24-28 K 28-32 K 32-36 K

Dans l'exemple prcdent, les pages ont une taille de 4 Ko. L'adresse virtuelle 12292 correspond un dplacement 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 dplacement de 4 octets dans la page physique 2, soit : (8*1024) + 4 = 8196. Par contre, la page virtuelle 2 n'est pas mappe. Une adresse virtuelle comprise entre 8192 et 12287 donnera lieu un dfaut de page. Il y a dfaut de page quand il y a un accs une adresse virtuelle correspondant une page non mappe. En cas de dfaut de page, un droutement se produit (trap) et le processeur est rendu au SE. Le systme doit alors effectuer les oprations suivantes : dterminer la page charger (page victime) dterminer la page dcharger sur le disque pour librer un cadre lire sur le disque la page charger modifier la table de bits et la table de pages

La slection de page est ralise par les algorithmes de remplacement. Le principe de fonctionnement de la majorit de ces algorithmes repose sur le principe de localit. Ces algorithmes sont en gnral diviss en deux grandes catgories :

les algorithmes dpendants de l'utilisation des donnes: LRU, LFU, etc les algorithmes indpendants de l'utilisation des donnes : alatoire, FIFO.

Ci-dessous sont lists quelques d'algorithmes. Mlle I.Sghaier - 38

Systmes dexploitation Gestion de la mmoire

a. Algorithme optimal Cet algorithme, utilise la mmoire cache de manire optimale : il retire la page qui sera rfrence le plus tard possible. Cet algorithme doit connatre pour chaque page le nmbre dinstructions excuter avant quelle ne soit rfrence cause pour laquelle set algorithme est irralisable. Cet algorithme constitue nanmoins un excellent moyen afin de mesurer l'efficacit d'un algorithme de remplacement en fournissant une rfrence. b. NRU (not recently used) Le SE rfrence chaque page par deux bits R (le plus gauche) et M initialiss 0. A chaque accs en lecture une page, R est mis 1. A chaque accs en criture, M est mis 1. A chaque interruption d'horloge, le SE remet R 0. En cas de dfaut de page, on retire une page au hasard dans la catgorie non vide de plus petit index (RM). c. FIFO ( first in, first out) Le SE indexe chaque page par sa date de chargement et constitue une liste chane, la premire page de la liste tant la plus anciennement charge et la dernire la plus rcemment charge. Le SE replacera en cas de ncessit la page en tte de la liste et chargera la nouvelle page en fin de liste. Deux critiques cet algorithme : ce n'est pas parce qu'une page est la plus ancienne en mmoire qu'elle est celle dont on se sert le moins l'algorithme n'est pas stable : quand le nombre de cadres augmente, le nombre de dfauts de pages ne diminue pas ncessairement. d. LRU (least recently used) En cas de ncessit, le SE retire la page la moins rcemment rfrence. Pour cela, il indexe chaque page par le temps coul depuis sa dernire rfrence et il constitue une liste chane des pages par ordre dcroissant de temps depuis la dernire rfrence. L'algorithme est stable. Mais il ncessite une gestion coteuse de la liste qui est modifie chaque accs une page. 5.4.3 La segmentation

Dans cette solution, l'espace d'adressage d'un processus est divis en segments, gnrs la compilation. Chaque segment est repr par son numro S et sa longueur variable L. Un segment est un ensemble d'adresses virtuelles contigus.

Mlle I.Sghaier

- 39

Systmes dexploitation Gestion de la mmoire

Contrairement la pagination, la segmentation est "connue" du processus : une adresse n'est plus donne de faon absolue par rapport au dbut de l'adressage virtuel; une adresse est donne par un couple (S , d), o S est le n du segment et d le dplacement dans le segment, d [0 , L [ . Pour calculer l'adresse physique, on utilise une table des segments :
S d

............. B ............ table des segments L p

descripteur de segment

B : adresse de base (adresse physique de dbut du segment) L : longueur du segment ou limite p : protection du segment L'adresse physique correspondant l'adresse virtuelle (S , d) sera donc B + d, si d <= L La segmentation simplifie la gestion des objets communs (rangs chacun dans un segment), notamment si leur taille volue dynamiquement.

Mlle I.Sghaier

- 40