Systmes dexploitation des Ordinateurs

29

CHAPITRE IV : GESTION DE LA MEMOIRE

A l'origine, la mmoire centrale tait une ressource chre et de taille limite. Elle devait tre gre avec soin. Sa taille a considrablement augment depuis, puisqu'un compatible PC a souvent aujourd'hui la mme taille de mmoire que les plus gros ordinateurs de la fin des annes 60. Nanmoins, le problme de la gestion reste important du fait des besoins croissants des utilisateurs. Le but de ce chapitre est de dcrire les problmes et les mthodes de gestion de la mmoire principale.

4.1 HIERARCHIE DES MEMOIRES :

La grande varit de systmes de stockage dans un systme informatique peut tre organise dans une hirarchie (voir figure) selon leur vitesse et leur cot.

Registres (0 ns)

Mmoire cache (10 ns) Mmoires volatiles Mmoire principale (50 ns) Vitesse Mmoires non volatiles Disque magntique (10 ms)

Disque optique (500 ms)

Bandes magntiques (1 mn)

Fig. 4.1 La hirarchie mmoire

Les niveaux suprieurs sont chers mais rapides. Au fur et mesure que nous descendons dans la hirarchie, le cot par bit diminue alors que le temps daccs augmente. En plus de la vitesse et du cot des divers systmes de stockage, il existe aussi le problme de la volatilit de stockage. Le stockage volatile perd son contenu quand lalimentation lectrique du dispositif est coupe. La mmoire cache (antmmoire) :

LOUKAM Mourad

30

La mise en mmoire cache est un principe important des systmes informatiques autant dans le matriel que dans le logiciel. Quand une information est utilise, elle est copie dans un systme de stockage plus rapide, la mmoire cache, de faon temporaire. Quand on a besoin dune information particulire, on vrifie dabord si elle se trouve dans la mmoire cache, sinon on ira la chercher la source et on mmorise une copie dans la mmoire cache, car on suppose quil existe une grande probabilit quon en aura besoin une autre fois.

4.2 ADRESSAGE LOGIQUE/ADRESSAGE PHYSIQUE :

Une adresse gnre par le processeur est appele adresse logique. Tandis quune adresse vue par lunit mmoire, cest dire celle qui est charge dans le registre dadresse de la mmoire, est appele adresse physique. Il est ncessaire au moment de lexcution de convertir les adresses logiques en adresses physiques. Par exemple, imaginons un systme o une adresse physique est obtenue en ajoutant chaque adresse logique ladresse de base contenue dans un registre.

Registre de translation 14000

Adresse logique 314 Adresse physique 14314

Mmoire

Processeur

Fig. 4.2 Conversion dadresses logiques en adresses physiques par translation.

Dans ce schma, la valeur du registre de translation est additionne chaque adresse logique gnre par un processus utilisateur. Par exemple, si ladresse de base est 14000, un accs lemplacement 314 est converti lemplacement 14314. Il est noter que le programmeur naperoit en gnral pas les adresses physiques ; il manipule uniquement des adresses logiques.

4.3 ALLOCATION CONTIGU DE LA MEMOIRE :

La mmoire principale peut loger le SE et les diffrents processus utilisateurs. La mmoire est habituellement subdivise en deux partitions : une pour le SE rsident et lautre pour les processus utilisateurs

Systmes dexploitation des Ordinateurs

31

0 Systme dexploitation

Processus utilisateurs N Fig. 4.3 Partition de la mmoire

4.3.1 Allocation multi-partitions :

Dans un environnement multiprogramm, plusieurs processus logent dans la mmoire en mme temps. On doit alors prendre en charge le problme de leur allouer la mmoire disponible. Lun des schmas les plus simples revient subdiviser la mmoire en partitions de taille fixe. Chaque rpartition peut contenir exactement un processus. Ainsi le degr de la multiprogrammation est limit par le nombre de partitions. Quand une partition devient libre, on slectionne un processus de la file dattente des processus prts et on le charge dans la partition libre. Quand le processus se termine, la partition devient libre pour un autre processus. Cette technique a t implmente sur le OS/360 dIBM, mais elle est actuellement dpasse. Une autre mthode consiste obliger le SE maintenir une table indiquant les partitions de mmoire disponibles et celles qui sont occupes. Quand un processus arrive en demandant de la mmoire, on recherche un espace suffisamment grand pour contenir ce processus. Si nous en trouvons un, nous allouons seulement la quantit de mmoire ncessaire, laissant le reste disponible pour satisfaire les futures requtes.

Exemple : Ltat de la mmoire dun systme est dcrit par la figure suivante. Le systme a une file de travaux dcrit par le tableau suivant : Etat de la mmoire 0 Systme dexploitation 400K File dattente des travaux Processus P1 P2 P3 P4 P5 Mmoire 600 K 1000 K 300 K 700 K 500 K Temps 10 5 20 8 15

2160 K libres

2560K

Les figures suivantes montre les diffrents tats successifs de la mmoire aprs les entres et les sorties de processus.

LOUKAM Mourad

P1, P2 et P3 entrent P2 termine 0 Systme dexploitation 400K P1 1000K P2 2000K P3 2300K 2300K 2560K 2560K 2000K P3 1000K 400K P1 0 Systme dexploitation

P4 entre P1 termine 0 Systme dexploitation 400K P1 1000K 1700K 2000K P3 2300K 2300K 2560K 2560K P4 400K 0 Systme dexploitation

1000K 1700K 2000K

P4

P3

Systmes dexploitation des Ordinateurs

33

P5 entre 0 Systme dexploitation 400K 900 1000K 1700K 2000K P3 2300K P4 P5

2560K

Ainsi chaque instant, on dispose dune liste de tailles de blocs disponibles et la file dattente des processus prts. Le SE peut scheduler la file dattente selon un algorithme de scheduling. La mmoire est alloue aux processus jusqu ce quil nexiste aucun bloc de mmoire suffisamment grand pour contenir ce processus. Mais comment allouer un espace de taille n un processus partir dune liste de trous libres ?. On peut utiliser lun des trois algorithmes suivant : first-fit, best-fit, worst-fit. Algorithme First-fit (Le premier trouv) : On alloue au processus le premier trou suffisamment grand. Algorithme Best-fit (Le meilleur choix) : On alloue au processus le trou le plus petit suffisamment grand ; cest dire celui qui provoquera la plus petite miette possible. Cet algorithme ncessite le parcours de toute la liste des espaces libres. Algorithme Worst-fit (Le plus mauvais choix) : On alloue au processus le trou le plus grand. Cet algorithme ncessite le parcours de toute la liste des espaces libres.

Exemple : Ltat de la mmoire dun systme est dcrit par la figure suivante. On suppose quun processus P demande un espace mmoire de 80K.

0 400 700 900 1000 1400 2000 2100

SE P1 Trou T1 P2 Trou T2 P3 Trou T3 En fonction de lalgorithme choisi, on choisirait le trou T1, T2 ou T3. Algorithme First-Fit : trou T1. Algorithme Best-Fit : trou T3. Algorithme Worst-Fit : trou T2.

LOUKAM Mourad

4.3.2 La fragmentation :
Les algorithmes dallocation de la mmoire contigu prcdents, produisent la fragmentation de la mmoire. En effet, suite aux diffrentes entres et sorties de processus, des miettes spares se froment dans la mmoire. 0 400 700 900 1000 1400 2000 2100 P3 Si le processus P dsire entrer dans le systme en occupant 500K, il ne pourrait pas bien que lespace total disponible est de 700 K. P2 SE P1

La solution au problme de la fragmentation peut tre le compactage. Le principe est de rassembler tous les trous en un seul bloc. Avant compactage Aprs compactage 0 400 700 900 1000 1400 2000 2100 2100 P3 P2 SE P1 0 400 700 800 1400 SE P1 P2 P3

Inconvnient : Lopration de compactage est une opration trs coteuse pour le SE.

4.4 LA PAGINATION :
Une autre solution au problme de la fragmentation consiste permettre que lespace dadressage logique dun processus ne soit plus contigu, autorisant ainsi lallocation de la mmoire physique un processus l o elle est disponible. La technique de la pagination est une manire implmenter cette solution.

4.4.1 Le principe de la pagination :

La pagination consiste dcouper la mmoire physique en blocs de taille fixe, appels cadres physiques ou cadres de pages. La mmoire physique est galement subdivise en blocs de la mme

Systmes dexploitation des Ordinateurs

35

taille appele pages. Quand on doit excuter un processus, on charge ses pages dans les cadres de pages partir de la mmoire auxiliaire. Adresse logique Processeur P d f Adresse physique d Mmoire Physique

d f

Table de pages Fig. 4.4 Principe de la pagination.

On divise chaque adresse gnre par le processeur en deux parties : numro de page P et dplacement dans la page D.

On utilise le numro de page comme indice une table de pages. La table de pages contient ladresse de base de chaque page dans la mmoire physique. Cette adresse de base est combine avec le dplacement dans la page afin de dfinir ladresse physique. La taille de la table de page est une puissance de 2 variant entre 512 octets et 8192 octets, selon larchitecture de lordinateur. Le choix dune puissance de 2 comme taille de page facilite la traduction dune adresse logique en un numro de page et un dplacement dans la page. Si la taille de lespace m n adresse logique est de 2 et la taille de la page est de 2 units dadressage (mots ou octets), les m-m bits de poids forts dune adresse logique dsignent le numro de page et les n bits de poids faible dsignent le dplacement dans la page.

P m-n

d m

Lexemple suivant montre un systme ayant une mmoire logique de 4 pages et une mmoire physique de 8 pages.

LOUKAM Mourad

36

Mmoire logique Page 0 Page 1 Page 2 Page 3 0 1 2 3

Table de pages 1 4 3 7 0 1 2 3 4 5 6 7

Mmoire physique

Page 0 Page 2 Page 1

Page3

Les cadres de pages sont allous comme des units. Si les besoins en mmoire dun processus ne tombent pas sur les limits des pages, le dernier cadre de page peut ne pas tre plein. Par exemple, si les pages sont de 2048 octets, un processus de 72766 octets aura besoin de 35 pages, plus 1086 octets. On lui allouera donc 36 cadres de pages, en provoquant une fragmentation de 2048-1086=962 octets. Dans le pire des cas, un processus demandera n pages plus un octet. On lui allouera n+1 cadres de pages, provoquant ainsi une fragmentation de presque une page entire. Cette considration suggre quil est souhaitable davoir des pages de petites tailles. Cependant, il existe une surcharge due chaque entre de la table de pages et elle est rduite si la taille de la page augmente. De nos jours, les pages sont gnralement dune taille de 2 4 Ko. Un aspect important de la pagination est la sparation nette entre la vue de lutilisateur de la mmoire et la mmoire physique relle. Le programme utilisateur conoit cette mmoire comme un espace unique contigu, mais en ralit le programme utilisateur est clat dans toute la mmoire physique qui contient ventuellement dautres programmes.

4.4.2 Structure dune table de pages :

Chaque SE possde sa propre mthode pour stocker la table de pages. La plupart allouent une table de page pour chaque processus. On stocke un pointeur sur la table de pages avec les autres valeurs des registres dans le PCB. Lors dune commutation de contexte, et quand le processus redmarre, sa table de pages est recharge.

4.4.3 Protection :
La protection de la mmoire dans un environnement pagin est accomplie avec des bits de protection associs chaque cadre de page. Normalement, ces bits sont stocks dans la table de pages. Un bit peut dfinir que lon accde une page en lecture et criture, ou en lecture seulement. Mmoire logique Page 0 Page 1 Page 2 Page 3 0 1 2 3 Table de pages 1 4 3 7 1 1 0 1 0 1 2 3 4 5 6 7 Mmoire physique

Page 0 Page 2 Page 1

Bit de protection

Page3

Fig. 4.5 Protection des pages.

Systmes dexploitation des Ordinateurs

37

4.4.4 Pagination multiniveaux :

La plupart des SE modernes supportent un espace adresse logique trs grand (2 2 ). Dans un tel environnement, la table de pages elle-mme devient excessivement grande. Par exemple, si lespace 32 12 adresse est de 2 , et si la taille dune page est de 4Ko (2 ), alors la table de pages peut possder 32 12 jusqu 1 million dentre (2 /2 ). Il convient alors de subdiviser la table de pages en parties plus petites. Par exemple, on peut utiliser un schma de pagination 2 niveaux, dans lequel la table de pages elle-mme est pagine. Mmoire physique 0 Table de pages externe
32 64

0 100 500 550 800 900

100

500 550

800

900

Fig. 4.6 Pagination 2 niveaux

Dans un systme de pagination 2 niveaux, une adresse logique a la forme suivante :

P1 N de page

P2 N de page

d Dplacement dans la page

P1 est le numro de la table de pages interne. P2 est le dplacement dans la page de la table de page externe. La traduction dune adresse logique en adresse physique dans un systme pagin 2 niveaux est prsente par le schma suivant :

P1

P2

LOUKAM Mourad

38

P1

P2 d Table de pages externe Page de la table de page Page dsire Fig. 4.7 Traduction dadresses pour une architecture de pagination 2 niveaux.

4.4.5 Pages partages :

Un autre avantage de la pagination est la possibilit de partager du code commun. Cette caractristique est particulirement importante dans un environnement partag. Imaginons un systme qui supporte 40 utilisateurs, chacun deux excutant un diteur de textes. Si lditeur est constitu de 150 Ko de code et 50 Ko de donnes, on aura besoin de 8000 Ko pour satisfaire les 40 utilisateurs. Cependant si le code est rentrant, il peut tre partag comme le montre le schma suivant : Ed1 Ed2 Ed3 Donnes1 Processus P1 Ed1 Ed2 Ed3 Donnes2 Processus P2 Ed1 Ed2 Ed3 Donnes3 Processus P3

3 4 6 1 Table de pages de P1

3 4 6 7 Table de pages de P2

0 1 2 3 4 5 6 7

Donnes1 Donnes 3 Ed1 Ed2 Ed3 Donnes 2

3 4 6 2 Table de pages de P3

Mmoire physique

Fig. 4.8 Partage de code dans un environnement de pagination. Le schma prcdant montre que les 3 pages de code de lditeur de textes sont partages par les 3 processus. Chaque processus, par contre, possde sa propre page de code.

Systmes dexploitation des Ordinateurs

39

Le code rentrant (encore appel code pur) est un code invariant ; cest dire quil ne change jamais pendant lexcution. Ainsi, deux ou plusieurs processus peuvent excuter le mme code en mme temps. Chaque processus possde sa propre copie de registres et son stockage de donnes. On doit maintenir en mmoire physique une seule copie de lditeur. La table de pages de chaque processus correspond la mme structure physique de lditeur, mais les cadres de pages sont transforms des cadres de pages diffrents. Ainsi, pour supporter 40 utilisateurs nous navons besoin que dune copie de lditeur (ie 150 Ko), plus 40 copies de lespace de donnes de 50 Ko par utilisateur. Lespace requis est donc de 2150 Ko au lieu de 8000 Ko.

4.5 LA SEGMENTATION :
La segmentation rejoint la pagination pour consacrer un principe important dans les SE actuels, savoir la sparation entre la vue de lutilisateur de la mmoire et la mmoire physique. La vue de lutilisateur de la mmoire nest pas le mme que la mmoire physique relle ; le SE se charge de convertir lune dans lautre. Il est admis que le programmeur nimagine pas la mmoire comme un tableau linaire doctets. Il prfre voir la mmoire comme un ensemble de segments de taille variable, sans quil y ait un ordre entre les segments.

Programme principal

Procdure P1 Procdure Pi

Fonction F1 Fonction Fj

Fig. 4.9 Exemples de segments.

La segmentation consiste dcouper lespace logique en un ensemble de segments. Chacun des segments est de longueur variable ; la taille dpend de la nature du segment dans le programme. Chaque segment possde un numro et une longueur. Pour cibler une zone mmoire spcifique, on doit donc dsigner deux paramtres : un numro de segment et un dplacement. : Numro de segment dplacement

De ce point de vue , la segmentation est diffrente de la pagination, puisque dans la pagination, lutilisateur ne spcifie quune seule adresse qui est dcode par le SE en un numro de page et un dplacement. En segmentation la conversion dune adresse logique en une adresse physique est faite grce une table de segments. Chaque entre de la table de segment possde deux valeurs : La base : cest ladresse de dbut du segment en mmoire. La limite : spcifie la taille du segment. S Limite
LOUKAM Mourad

Base

40

Table des segments

@ logique Processeur S d Oui < Mmoire physique

@ physique Non Droutement : erreur dadressage

Fig. 4.10 Conversion dadresse logique en adresse physique cas de la segmentation

Une adresse logique est constitue de 2 parties : un numro de segment S et un dplacement dans ce segment d. On utilise le numro de segment comme indice dans la table de segments. Le dplacement d de ladresse logique doit se trouver entre 0 et la limite du segment. Si ce nest pas le cas, il y a un droutement vers le SE pour tentative dadressage hors limite. Si le dplacement est correct, on ladditionne la base du segment pour calculer ladresse physique de lemplacement dsir. Exemple : Soit un espace dadressage logique contenant quatre segments.
0 1400

Programme principal Segment 0 Procdure 1 Segment 1 Limite 1000 400 400 1100 Base 1400 6300 4300 3200

Segment 0
2400

Procdure 2 Segment 2

0 1 2 3

3200

Segment 3
4300

Segment 2
4700 6300

Segment 1 Fonction 1 Segment 3

6700

Espace dadressage logique

Mmoire physique

Faisons la conversion des adresses logiques suivantes en adresses physiques :

Systmes dexploitation des Ordinateurs

41

Adresse logique N de segment Dplacement 2 53 3 852 0 1222

Adresse physique 4300+53=4353 3200+852=4052 Provoque un droutement vu que le dplacement est hors limite

4.6 MEMOIRE VIRTUELLE :

Les techniques de gestion de la mmoire vue prcdemment possdent le mme objectif : maintenir plusieurs processus en mmoire simultanment afin de permettre la multiprogrammation. Cependant, elles tendent demander que le processus se trouve en mmoire dans sa totalit avant de pouvoir tre excut. La mmoire virtuelle est une technique autorisant lexcution de processus pouvant ne pas tre compltement en mmoire. Le principal avantage de ce schma est que les programmes peuvent tre plus grand que la mmoire physique. Le concept de mmoire virtuelle a t mis au point aprs que lon a constat que dans de nombreux cas, on na pas besoin dun programme dans sa totalit. Exemples : Les programmes possdent souvent du code pour manipuler des situations exceptionnelles. Ce code nest alors que trs rarement excut. On alloue souvent aux tables et tableaux plus de mmoire que ce dont ils ont rellement besoin. On peut dclarer un tableau 100x100, alors quon nutilise que 10x10 lments.

Ainsi la possibilit dexcuter un programme se trouvant partiellement en mmoire prsenterait plusieurs bnfices : Un programme nest plus limit par la quantit de mmoire physique disponible. Les utilisateurs pourront crire des programmes pour un espace adresse virtuel extrmement grand, simplifiant ainsi la tche de programmation. Comme chaque programme utilisateur pourrait occuper moins de mmoire physique, il serait possible dexcuter plus de programme en mme temps.

L mmoire virtuelle fournit donc un espace dadressage extrmement grand alors que la mmoire physique est limite. Cela est possible en utilisant une mmoire auxiliaire comme espace de travail pour charger et dcharger les diffrentes pages par le SE.

Table de page Mmoire logique

Mmoire physique

Mmoire auxiliaire

Fig. 4.11 Mmoire virtuelle plus grande que la mmoire physique

4.6.1 Pagination la demande :

LOUKAM Mourad

42

La mmoire virtuelle est communment implmente avec la pagination la demande. Quand un processus doit tre transfr en mmoire, la routine de pagination devine quelles pages seront utilises avant que le processus soit mis en mmoire axilliaire de nouveau. Au lieu de transfrer en mmoire un processus complet, la routine de pagination ramne seulement les pages qui lui sont ncessaires. Ainsi, elle vite que lon charge en mmoire des pages qui ne seront jamais employes, en rduisant le temps de swaping et la quantit de mmoire dont on a besoin. Avec cette technique, le SE doit disposer de moyens pour distinguer les pages qui sont en mmoire, et celles qui sont sur disque. Par exemple, on peut utiliser dans la table des pages un bit valide/invalide pour dcrire si la page est charge en mmoire ou non.
Cadre de page

Bit valide /invalide

A B C D E F G H

Mmoire logique

0 1 2 3 4 5 6 7

4 6

1 0 1 0 0 1 0 0

Table de pages

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

A C

A D

B E

C F

Mmoire physique Fig. 4.12 Mmoire pagine avec certaines pages en mmoire.

Disque

Que se passe-t-il si un processus essaie dutiliser une page qui nest pas en mmoire ?. Laccs une page marque invalid provoque un dfaut de page. En essayant daccder cette page, il y a un droutement vers le SE. La procdure permettant de traiter ce dfaut de page est la suivante : Sassurer que la rfrence de la page est correcte. Sassurer que la page dsire est bien en mmoire auxilliare. Trouver un cadre de page libre et charger la page. 3 SE 1
Charger la page P

2 0 4
Cadre de page libre

Fig. 4.13 Procdure de traitement dun dfaut de page.

Lgende : 1 : on fait rfrence la page P qui nexiste pas en mmoire.

Systmes dexploitation des Ordinateurs

43

2 : Il y a un droutement vers le SE. 3 : Le SE vrifie si la page existe bien en mmoire auxilliare. 4 : Le SE vrifie sil y a un cadre de page libre, auquel cas il y charge la page absente. 5 : Le SE met jour la table de page. 6 : Redmarrer linstruction du processus qui a provoqu le dfaut de page.

4.6.2 Remplacement de pages :

Lorsque le SE se rend compte au moment de charger une page quil nexiste aucun cadre de page disponible, il peut faire recours un remplacement de page. Ainsi le code complet dune procdure de traitement dun dfaut de pages est le suivant : 1. Trouver lemplacement de la page dsire sur disque. 2. Trouver un cadre de page libre. Sil existe un cadre de pages libre, lutiliser, sinon utiliser un algorithme de remplacement de pages pour slectionner un cadre de page victime. 3. Enregistrer la page victime dans le disque et modifier la table de page. 4. Charger la page dsire dans le cadre de page rcemment libr et modifier la table de pages. 5. Redmarrer le processus utilisateur.

P V

0 1

4 Victime 2

Fig. 4.14 Remplacement de pages.

Lgende : 1 : Swap out de la page victime. 2 : Mettre le bit de la page invalide 3 : Swap in de la page dsire. 4 : Mettre le bit de la page valide

4.6.3 Algorithmes de remplacement de pages :

Il existe plusieurs algorithmes diffrents de remplacement de pages. En gnral, on souhaite celui qui provoquera le taux de dfauts de pages le plus bas. On value un algorithme en lexcutant sur une squence particulire de rfrences mmoires et en calculant le nombre de dfauts de page. Cette chane est appele : chane de rfrences.

Afin de dterminer le nombre de dfauts de pages pour une chane de rfrences et un algorithme de remplacement particulier, on doit galement connatre le nombre de cadres de pages disponibles.

LOUKAM Mourad

44

Evidemment, au fur et mesure que le nombre de cadres de pages augmente, le nombre de dfauts de pages doit diminuer, comme le montre la figure suivante :

Nombre de dfauts de pages

Nombre de cadres de pages

Fig. 4.15 Dfauts de pages et cadres de pages

4.6.3.1 Algorithme FIFO :

Lalgorithme de remplacement FIFO (First In First Out) est le plus simple raliser. Avec cet algorithme, quand on doit remplacer une page, cest la plus ancienne quon doit slectionner. Exemple : Considrons un systme mmoire pagine ayant 3 cadres de pages (pages physiques), et soit la chane de rfrences suivante : 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1. Quel est le nombre de dfauts de pages si lalgorithme de remplacement choisi est lalgorithme FIFO ?. Pour rpondre cette question, faisons un droulement qui fait ressortir les tats successifs du systme et en marquant les diffrents dfauts de pages. Chane de rfrence 7 7 Cadres de page 0 7 0 1 7 0 1 Dfauts de page 0 0 2 3 X Nombre de dfauts de pages : 15. Lalgorithme de remplacement FIFO est simple implmenter mais ses performances ne sont pas toujours bonnes. X 3 0 2 3 X 2 0 2 3 X 1 0 1 3 X 2 2 0 1 X 2 0 1 2 X 0 0 1 2 0 2 0 1 3 2 3 1 X 1 0 1 2 0 2 3 0 X 7 7 1 2 X 4 4 3 0 X 0 7 0 2 X 2 4 2 0 X 1 7 0 1 X 3 4 2 3 X

Systmes dexploitation des Ordinateurs

45

Afin dillustrer les problmes rencontrs avec un algorithme de remplacement FIFO, on peut envisager la chane de rfrences suivantes : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. La figure suivante montre le nombre de dfauts de pages en fonction des cadres de pages disponibles.

14 12 10 8 6 4 2 0 1 2 3 4 5 6

Cadres de pages 1 2 3 4 5 6

Dfauts de pages 12 12 9 10 6 6

Fig. 4.16 Anomalie de Belady On remarque que le nombre de dfauts de pages pour 4 cadres de pages (ie : 10) est suprieur au nombre de dfauts de pages pour 3 cadres de pages (ie : 9) !. Ce rsultat fort inattendu est connu sous le nom de lanomalie de Belady. Elle dcrit une situation o le taux de dfauts de pages augmente au fur et mesure que le nombre de cadres de pages augmente, contrairement la rgle gnrale.

4.6.3.2 Algorithme optimal :

Lalgorithme de remplacement optimal fournit le taux de dfauts de pages le plus bas de tous les autres algorithmes, de plus il ne souffre pas de lanomalie de Belady. Son principe est de remplacer la page qui mettra le plus de temps tre de nouveau utilise. Exemple : Reprenons la mme chane de rfrences que lalgorithme FIFO prcdent, et calculons le nombre de dfauts de pages avec cet algorithme. Chane de rfrence 7 7 Cadres de page 0 7 0 1 7 0 1 Dfauts de page 0 2 0 3 X Nombre de dfauts de pages : 09. X 3 2 0 3 X 2 2 0 3 X 1 2 1 0 X 2 2 0 1 X 2 2 0 1 0 2 0 1 0 2 0 1 3 2 0 3 X 1 2 0 1 7 7 0 1 X 0 2 0 3 4 2 4 3 X 0 7 0 1 1 7 0 1 2 2 4 0 3 2 4 3

Malheureusement, lalgorithme optimal est difficile mettre en uvre car il requiert une connaissance future de la chane de rfrences. Il est utilis essentiellement pour faire des tudes comparatives.

LOUKAM Mourad

46

4.6.3.3 Algorithme LRU :

Lalgorithme LRU (Least Recently Used) slectionne pour le remplacement dune page victime, la page la moins rcemment utilise. Cest dire quon doit remplacer une page, lalgorithme slectionne la page qui na pas t utilise pendant la plus grande priode de temps. Exemple : Reprenons la mme chane de rfrences que lalgorithme FIFO prcdent, et calculons le nombre de dfauts de pages avec cet algorithme. Chane de rfrence 7 7 Cadres de page 0 7 0 1 7 0 1 Dfauts de page 0 2 3 2 X Nombre de dfauts de pages : 12. X 3 0 3 2 X 2 0 3 0 X 1 1 3 2 X 2 2 0 1 X 2 1 3 2 0 1 0 2 X 0 2 0 1 3 2 0 3 X 1 1 0 2 7 1 0 7 X 0 2 0 3 4 4 0 3 X 0 1 0 7 2 4 0 2 X 1 1 0 7 3 4 3 2 X

4.6.3.4 Algorithmes bass sur le comptage :

Il existe de nombreux algorithmes de remplacement de pages bass sur le comptage du nombre de rfrences effectues chaque page. Pour cela, on utilise un compteur pour chaque numro de page. A. Lalgorithme LFU : Lalgorithme de remplacement LFU (Least Frequently Used) requiert que lon remplace la page la moins frquemment utilise ; cest dire celle ayant le compteur le plus petit. La raison de cette slection est quune page activement utilise devrait avoir un grand compte de rfrences. Exemple : En reprenant la mme chane de rfrences que lalgorithme FIFO prcdent, le nombre de dfauts de pages trouv avec cet algorithme est de 11. Cet algorithme prsente un problme quand une page est trs utilise pendant la phase initiale dun programme, mais quelle nest plus employe nouveau par la suite. Comme elle a t amplement utilise, elle possde un grand compte et reste donc en mmoire mme si elle nest pas utilise. B. Lalgorithme MFU : Lalgorithme de remplacement MFU (Most Frequently Used) requiert que lon remplace la page la plus frquemment utilise. La raison de cette slection est que la page ayant le compte le plus petit vient probablement dtre ramene en mmoire et doit encore tre utilise. Exemple : En reprenant la mme chane de rfrences que lalgorithme FIFO prcdent, le nombre de dfauts de pages trouv avec cet algorithme est de 14.

Systmes dexploitation des Ordinateurs

47

4.6.4 Allocation de cadres de pages :

Comment allouer la quantit de mmoire libre entre les diffrents processus ?. par exemple, si on dispose de 93 cadres de pages libres et 2 processus, combien de cadres de pages obtient chacun deux ?. La manire la plus simple de rpartir m cadres de page entre n processus est de donner chacun des portions gales, cest dire m/n cadres de pages. Par exemple, si on possde 93 cadres de pages et 5 processus, chaque processus obtiendra 18 cadres de pages. Les 3 cadres de pages restant pourraient faire partie dun pool de buffers de cadres de pages libres. Ce schma est appel allocation quitable. Il existe une autre mthode qui admet que les processus ont des besoins diffrents et demandent des quantits diffrentes de mmoires. Par exemple, nous disposons dune mmoire compose de 62 cadres de pages et de deux processus diffrents : un processus utilisateur qui demande 10 Ko et un processus de Bases de donnes qui demande 127 Ko. Cette seconde mthode utilise lallocation proportionnelle, cest dire quelle affecte la mmoire disponible entre les processus en fonction de leur besoin. Soit Si la taille de la mmoire virtuelle dun processus Pi. On a : S= Si Si le nombre total de cadres de pages disponibles est m, on alloue ai cadres de pages au processus Pi , o : ai = (si / S) * m Ainsi, le nombre de cadres de pages affects chaque processus de notre exemple est : Processus utilisateur : (10/137)*62=4 cadres de pages. Processus Base de donnes : (127/137)*62=57 cadres de pages.

4.6.5 Ecroulement :
Si la quantit de cadres de pages alloue un processus de basse priorit descend en dessous du nombre minimum requis par larchitecture de lordinateur, nous devons arrter lexcution de ce processus. Nous devrions ensuite transfrer les pages restantes sur disque, librant ainsi tous les cadres de pages qui lui ont t allous. En fait, on peut envisager le cas dun processus ne possdant pas suffisamment de cadres de pages. Bien quil soit techniquement possible de rduire le nombre de cadres de pages allous au minimum, il existe un nombre de pages (suprieur) en utilisation active. Si le processus ne possde pas ce nombre de cadres de pages, il produira trs rapidement des dfauts de pages. A ce moment l, il doit remplacer une page. Cependant comme toutes ses pages sont en utilisation active, il devra nouveau remplacer une page ncessaire tout de suite aprs. Il produira donc trs rapidement un dfaut de pages nouveau, et ainsi de suite. Le processus continuera produire des dfauts de pages, en remplaant des pages dont il aura besoin tout de suite aprs. Cette haute activit de pagination est appele croulement. Un processus scroule sil passe plus de temps paginer qu sexcuter.

LOUKAM Mourad