[PDF] 1. Introduction Pagination. La pagination est l'

View - Download 1. Introduction

Previous PDF

Next PDF

TE

ClémentMATHIEU

GuillaumeERETEO

DRAFTv1.0 16/06/2004

Cedocument àétéproduit danslecadre d'untravaild'étude aucoursde lalicence d'informatique2003/2004 del'UNSAet présentelesconcepts etméchanismes fondamentauxde lagestionmémoire danslessystèmes d'exploitation.Lesques- tionsactuelle etlesévolutions encourssont aussiabordéesafin demontrerun panoramagénéral etactuelde cedomaine.

Tableof Contents

1.Introduction ... ...................................................................................................1

2.Généralités ... ....................................................................................................2

2.1.Historique ... ...........................................................................................2

2.2.Avantages delamémoire virtuelle.. ... ... ... ...................................................3

2.3.Pagination ... ...........................................................................................3

2.4.Segmentation ... .......................................................................................7

2.5.Gestion delazone d'échange.. ... ... ... ..........................................................8

2.6.Séparation endeuxde l'espaced'adressage. ... ... ... ... ......................................9

2.7.Hiérarchie demémoirescaches ... ... ... .........................................................9

2.8.Exhausion del'espaced'adressage ... ... ... ....................................................11

2.9.L'évolution dumatériel. ... ... .....................................................................12

3.BSD ... ............................................................................................................13

4.Linux ... ..........................................................................................................13

4.1.Modèle depagination. ... ... .......................................................................13

4.2.Espace d'adressaged'unprocessus ... ... ... ....................................................14

4.3.Gestion desdéfautsde pages.. ... ... ... .........................................................18

4.4.Allocateurs mémoire.. ... ..........................................................................22

5.Sujets d'actualité.. ... ..........................................................................................23

5.1.Chez Linux.. ... ......................................................................................23

5.2.Support NX,NoeXecute, parpage. ... ... ... ... ...............................................28

Glossaire. ...........................................................................................................31

bibliographie. ......................................................................................................33

A.Comparaisons dedifférentsprocesseurs ... ... ... .......................................................36

1.Introduction

Cedocument présenteunpanorama généraldela gestionmémoire,souvent appeléeVMM(virtual memorymanagement), MMouVM, ainsiquel'état actueldesimplémentations notammentdansles systèmesde typeUNIX.

Lapremière partieseraconsacrée àprésenterles butsetles principesgénérauxde lagestion

mémoireet nenécéssitepas deconnaissancepréalable dudomaine.Toutefois uneconnaissance minimaledes principesetdu fonctionnementdessystèmes d'exploitationpeuts'avérer utilepour

comprendrele tenantetles aboutissantsdesconcepts présentés.Cettepremière partieprésentera

aussile supportoffertpar lematérielpour lagestionmémoire notammentparle biaisde l'architecturela plusrépendueactuellement leX86mais surtoutgraceà sonsuccesseur: l'AMD64

Uneseconde partieprésenterarapidement l'implémentationdesprincipes présentésgrâceà unevue

généralede cequia étéréalisédans Linux.Ilne s'agitpasd'une descriptionenprofondeur oud'un

commentairede codecettetâche ayantdéjàeffectuée avecbriopar deuxfoispar desgensbien plus 1 compétents. Enfinla dernièrepartieprésentera quelquesdomainesactifs delagestion mémoire.Etfera unzoom surquelques débatsetproblèmes récentsrencontrésdans lessystèmeUNIX.

2.Généralités

Lessystèmes d'exploitationontpour missiondefournir uneinterfaceavec lematérielaux logiciels voulants'exécuter suruneplate-forme donnée.Aucours del'histoireles noyauxn'ontcessé d'évolueret leursfonctionnalitésn'ont cessédese modifierensuivant unlienassez étroitavec

l'évolutiondu matériel.Desystèmes monoprogramméssanssécurité noussommespassés en

quelquesannées àdessystèmes multiprogramméspermettantune forteisolationentre lesprocessus.

Ainsiau coursdutemps lessystèmesd'exploitation ensontvenus àfournirune abstraction

matérielletrès élevée,lesprocessus n'ontplus(ne peuvent)àinteragir directementavectout une

partiedu matérielmaisutilise lacouched'abstraction qu'estlesystème d'exploitation.Cettecouche d'abstractionnécessite quelesystème fournissedesprimitives pourrépondreaux besoinsdespro- cessus.Un desbesoinsfondamentaux estlamémoire. Toutprogrammepour s'exécuteràbesoin de mémoirepour contenirsoncode etsesdonnées. Nousallonsnous intéresseràcomment unsystème d'exploitationgère lamémoirephysique disponiblepourl'utiliser etpermettreaux processusde l'utiliser.Pour celanousallons commencerparfaire unbrefrappel historiqueretraçantles différentesgrandes étapesdela gestionmémoire.

2.1.Historique

Lespremiers systèmesn'offraientque trèspeud'abstraction aveclematériel etlesprogrammes

étaientsouvent développésavecune trèsbonneconnaissance dumatérielcaché derrière.Nous

sommesau tempsdessystèmes monoprogrammés;unseul processuspeuts'exécuter àlafois. Un desproblèmes majeursestque lamémoireprincipale faitbiensouvent défaut;unprogramme etses donnéesne peuventtenirentièrement dedans,lesystème n'offrantaucuneaide. Leprocessusest al- orsfortement coupléàla machinesurlequel ilestdéveloppé. Eneffetle programmeurdoit s'occuperlui mêmededécouper sonprogrammeen segments(modules)indépendants etdemettre enplace lemécanismepermettant lereplacementde cessegmentsde l'exécution.Cettefaçon de procéderà beaucoupd'inconvénientsen voiciquelquesuns. Toutd'abordil fautquetout lesseg- mentssoient pluspetitsque lamémoireprincipale disponible,ainsile programmeestdéveloppé pourune machinedonnée;le découpageensegments complexifiebeaucouple développement puisqueles structuresdedonnées etlesalgorithmes doiventêtrepensés pournejamais fairede référenceà desdonnéesqui nesontpas danslesegment actueletsurtout chaqueprogramme implémentesa proprefaçonde chargersesdonnées etdeles sauvegarderdansla mémoiredemasse. Enplus ducaractèrefastidieux delachose ons'aperçoitque toutlesprogrammes réinvententlaroue etle résultatfinaln'est absolumentpasportable d'unemachineà l'autre.Comblede lachosele pro- grammerésultant estdeuxà troisfoisplus grosàcause delagestion dessegments! Noussommes alorsdans lesannées50 etlesconcepteurs despremierssystèmes d'exploitationrêventd'une chose: automatiserla gestiondela mémoirepourque lesprogrammesn'aient plusàgérer leswapin etle swapout dessegments.

Cerêve estréaliséquelques annéesplustard audébutdes années60et lerésultatse nomme

mémoirevirtuelle ;la premièreimplémentationdate de1959par l'universitédeManchester. Cequi

correspondà lamémoirevirtuelle estappelé"one-level storagesystem"l'idée derrièrecenom est

simplemais trèsefficaceet consisteentrois points: •Construire unmatérielpermettant detransformerune adressepasséepar leprocesseuren laposi- tionactuelle desdonnéescorrespondant àcetteadresse. •Ajouter unemécanismede paginationà lademande.Lorsque lematérielindique quel'adresse demandéen'est pasenmémoire principalecemécanisme permetchargerles donnéesman- quantes,par exempledansla zoned'échangeou encorenonchargées. Silamémoire principale estsaturée ilfautaussi déporterdespages verslazone d'échange. TE 2 •Développer unalgorithmede remplacementquipermet dechoisirla zonemémoireà sélectionnerpour ladéportersur ledisque. Derrièreces troisconceptssimples secacheun idéeincroyablementpuissante; lesadresses manipuléespar lesprogrammesne décriventplusl'emplacement physiquedesinformations mais

leuremplacement logiquequiest géréparune coopérationdusystème d'exploitationetdu matériel.

Lamémoire estdevenuevirtuelle pourleprocessus ! Cettevoie serafortementétudiée parlemonde universitairede1965 à1975.De nombreuxsystèmes reprennentce principe,lesfondeurs depucesincorporent lagestionmémoire danslesprocesseurs et lemilieu delarecherche s'occupedetrouver desalgorithmesde remplacementainsique derésoudre diversesproblème commeletrashingtouten étudiantleprincipede localité. Dansle mêmetempsles systèmesmultiprogrammésfont leurapparitionet permettentd'exécuter plusieursprocessus demanièrepseudo concurrenteouconcurrente selonlescaractéristiques du

matériel.Certain systèmessontde typecoopératif(on retrouvedessystèmes decetype jusqu'àassez

récemmentpar exempleavecles MacOS7,8,9) oupremptif.Les systèmesmultiprogrammésre- posenttous surl'abstractionintroduite parlamémoire virtuelleetselon l'usagequien estfaitune réelleisolation desdifférentsprocessus estatteinte.

Jusqu'àassez récemmentlessystèmes grandpubliqueétaient incapablesd'utilisercorrectement les

notionsintroduites desannéesplus tôt(Win9x etMacOS parneciter qu'eux).Ainsiaucune isola-

tiondes espacesd'adressagedes différentsprocessusn'était réaliséecequi posedegraves problèmes

desécurité etdestabilité. Toutefoisdesannées plustôtces problèmesétaientparfaitement maîtrisés

parde nombreuxsystèmes,ainsi MULTICSétaitdoté d'unedesgestions mémoirelesplus évoluées

jamaisimplémentée; lessystèmespost MULTICStelque lesUNIXen reprenantgénéralementles conceptsde manièresimplifié. Denos jourslessystèmes courantssontde typesmultitachespréemptifs onpeutainsi noterLinux, *BSD,Solaris, MacOSX, Win2k/XP.Sur cessystèmesl'espace d'adressagedechaque processus n'estmodifiable queparle processusluimême etlenoyau estprotégéen lectureetécriture.

2.2.Avantages delamémoire virtuelle

Parmisles avantagesapportéspar lamémoirevirtuelle ontrouve:

•Contribue àl'écriturede codeindépendantde lamachine.Portabilité, réutilisabilité.

•Gestion automatiquedela zoned'échange.Les programmespeuventutiliser plusdemémoire qu'iln'y ademémoire principale •Optimisation del'utilisationde lamémoire.Les pagesnonutiles engendréesparerreurs deges- tionmémoire commelesfuites oulesallocation inutilesseretrouverons danslazone d'échange etlibérerons descadresde pagepourdes donnéesutiles.

•Possibilité d'utiliserdesbibliothèques partagées.Optimisationde l'utilisationmémoire

•Permet d'implémenterdessystèmes multiprogrammésdemanière sûre. •Optimisation del'utilisationmémoire etdesperformances grâceàdes techniquescommela copieà l'écritureetla paginitionàla demande.

2.3.Pagination

Lapagination estl'unedes deuxtechniques(qui peuventêtrecombinée) delamémoire virtuelle.Le principeest dediviserl'espace d'adressageenblocs detaillefixée parleprocesseur; lataillede ces blocsvarie de4KBà 64KBvoir4MB danscertainscas. Chacundeces blocspeutêtre déplacédans lamémoire physique.Lesystème d'exploitationavecla coopérationdumatériel doitmaintenirune

listequi permetdelocaliser l'emplacementdechaque bloc,quipeut éventuellementêtredéplacé sur

ledisque. TE 3

L'avantagede cetteapprocheest lasimplicitédes opérationsassociéesà desdonnéesdont lataille

estconnue d'avance.Introduiredes blocsdetailles variablesimpliqueraitl'utilisation d'algorithmes deplacement coûteuxetcomplexes.

Aveccette adresselaméthode pourretrouveroù sesituenos donnéesestfacile ilsuffitde découper

uneadresse virtuelleendeux parties.Lesbits depoidsforts indiquentlapage àlaquellenous faisons

référencealors quelesbits depoidsfaibles représententledécalage danslapage. Lorsqu'unead-

ressevirtuelle estprésentéeà laMMUelle extraitlesbits depoidsfort etcommenceà rechercher l'adresseréelle delapage. Sicettepage n'estpastrouvable alorsundéfaut depagese produitetest

signaléau systèmed'exploitationpar leprocessus.La tâchedecelui-ci estalorsde savoirquoifaire

selonle contexteassociéau défautdepage (voirSection4, "Linux").Si lapageest trouvéealorsles permissionssont vérifiéesetsi celles-cisontcorrectes l'adressephysiqueest envoyéesurle bus mémoire;si lespermissionssont faussesundéfaut depagese produit.

Traductiond'adresse parlapagination

Notonsque dansceschéma dèsquela MMUrencontreun problèmepourfaire latraduction

d'adresseun défautdepage estremontéau systèmed'exploitationce quiluidélègue lestâches

suivantes •Aller chercherlapage manquantedansla zonedezone etlamettre enmémoireprincipale •Implémenter unalgorithmede remplacementdepage quichoisijudicieusement lespagesà

évincer

•Gérer lesdéfautsde pagegénérésvolontairement pardesmécanismes telquela copieà

l'écriture(COW),qui permetderetarder lepluspossible laduplicationde page. Cecilaisse unegrandeliberté auxsystèmesd'exploitation pourimplémenterdes fonctionnalités

avancéesou émulerdemanière logicielledesfonctionnalités nonprésentesmatériellement.

Ledécoupage enblocsde taillefixemalgré lasimplificationdes opérationsintroduitune fragmenta-

tioninterne. Dansunsystème paginélesprotections portentsurune pageainsisi deuxdonnéesne doiventpas êtreprotégéesde lamêmemanière celle-cidoiventse trouverdansdeux pages différentesce quipeutmener àdespages partiellementremplies.Plus latailledes pagesestpetite plusla fragmentationinternesera faiblemaisd'un autrecôtéplus lesstructuresde donnéesdunoyau serontnombreuses pourgérerla mêmequantitéde mémoire.Actuellementla plupartdesproces- seursoffres despagesde 4KBetl'on sedirigevers despagesun peuplusgrande, puisquela mémoireprincipale necessede grossiret4KB commenceàêtre problématiquepourles noyaux. Certainsprocesseurs telqueles X86fournissentaussi despagesde 4MBicila fragmentationinterne peutêtre trèsimportante! Lesprocesseursalpha permettentdechoisir despagesde 8à64K. TE 4 Lemécanisme detraductiond'adresse peutreposersur deuxprincipes.Soit untabledes pagesmulti- niveauxsoit unetabledes pagesinversée.Nous allonsprésenterrapidement cesdeuxtechniques.

2.3.1.Table depagesmulti-niveaux

Lastructure laplussimple pourunetable depageest unsimpleindex ouchaqueentrée contientson emplacementmémoire etquelquesbits pourstockerles informationsutiles.

Tablede pageàun niveau

Trouverl'adresse physiqueesttrès simpleilsuffit alorsderemplacer lesbitsde poidsfortdécrivant lapage virtuelleparla pagephysique.On peutdifficilementfaire plusrapide;cependant cette méthodea unénormeinconvénient latailleoccupée parlastructure. Imaginonsdesadresses sur32 bitsavec despagesde 4KB.Les12 bitsdepoids faiblescorrespondentdonc audécalagedans la pageet les20bits depoidsfort aunumérode lapagevirtuelle. Cecidonne2^20 entréesdansla ta- bledes pages.Uneentréede tabledepage occuperaen moyenne32bits (20bitsd'adresse et12bits designification diverse).Ainsiune seuletablede pageoccupe2^20 *32= 32MB;sachantqu'il ya unetable depagepar processuslaconsommation mémoireesténorme etsurles machinespeupour- vuesen mémoireprincipalela consommationmémoiredu telletablede pagepeutexcéder la mémoirephysique présente! Pourcontrer ceproblèmeon aintroduitles tablesdepages multiniveaux.Lebut estmultiple;tout

d'abordseule latabledes pagesdeplus hautniveauà besoind'êtrerésidente enmémoireles autres

peuventelles mêmeêtredéplacées versl'espaced'échange, deplustoutes lestablesde pagesn'ont

pasbesoin d'existertantqu'elles nesontpas nécessaires.Onévite doncd'utiliserde lamémoire inutilement.Les tablesdepages rencontréesfontgénéralement deuxniveaux(X86)ou troisniveaux (alpha).Plus deniveauxd'indirection commencentafaire sentirunepénalité àl'exécution. Prenonsl'exemple desprocesseursX86 quiprésententune tabledespages àdeuxniveaux, unes- paced'adressage de32bits etdespages de4KB(nous laissonsdecôté PAEetPSE.Chaque entrée detable depage(PTE) fait4octets. Ilya donc2^20PTEs àréférencer.Au lieud'utiliserune simple tablenous utilisonsplusieursniveaux detable.La tabledeplus hautniveaucontient 1024entrées quipointent vers1024tables depagesde niveau1.Ainsi chaqueentréede latablede niveau0ad- resse4MB demémoire.Les tablesdeniveau 1contiennent1024 PTEquiindiquent lapositionde la pagevirtuelle. Onconstate quenonseulement cettereprésentationdemande moinsdemémoire quela représentationà unniveau,4MB +4KBcontre 20MB,maisen plusles4MB peuventêtrepaginés et

seulela tableracinea besoind'êtrerésidente. Latraductiond'adresse sefaitaisément delamanière

suivante. TE 5

Tablede pageàdeux niveau

Onextrait toutd'abordles 10bitsde poidsfort,a l'entréecorrespondantedans latablede pagera- cineon obtientuneadresse quicorrespondà latablede pagecontenantle PTErecherché.On extrait alorsles 10bitsde poidsfortsuivants. Àl'indicecorrespondant delatable despagesde niveau1se trouvele PTEassociéà notreadressevirtuelle. Iln'ya plusqu'àcombiner les20bits d'adressecon- tenusdans lePTEavec les12bits dedéplacementde l'adressevirtuelle. Desprocesseurs telquele PowerPCoule PA-Riscimplémententcette recherchedemanière unpeu différentesi bienquedans certaincason n'estpasobligé desuivretoutes lesindirectionspour ret-

rouverl'adresse physique.Pourplus dedétailson seréféreraà ladocumentationde cesprocesseurs.

Endépit desasimplicité cetteapprocheà quelquesinconvénients.La tailledesdonnées croitavecla

taillede l'espaced'adressageet nonavecla tailledela mémoireprincipale.De plusplusieurs niveauxd'indirections sontnécessairesce quiralentila recherche.Enfince nombred'indirections augmenteavec desespacesd'adressages conséquentscommeceux de64bits. Ellerestetoutefois employéedans beaucoupdeprocesseurs.

2.3.2.Table depagesinversée

Latable depagemultiniveaux estuneapproche intuitiveetpuissante cependantellea l'inconviénent degaspiller unequantiténon négligeabledemémoire, toutd'abordpar cequela tailled'untable de pagecroit enfonctionde lataillede l'espaced'adressagevirtuel; maisaussipar cequechaque pro- cessusdispose desapropre table. Ilexiste unedeuxièmeapproche nettementmoinsconsommatrice demémoire,mais moinsintuitive etsemblant nepaspermettre lepartagedes pages.Ils'agit destablesde pageinversées.Le principe estle suivant.Ondispose d'uneuniquetable pourlesystème quiapour taillelenombre decadredu pagedu système.L'indicede cetableaucorrespond aunumérode cadredepage. Uneadressevir-

tuelleest constituéedetrois parties alorsqu'uneentrée dans

latable despagescontient . L'approchela plusbasiquequand ondisposed'une adressevirtuelleest deparcourirla tabledes pagesà larecherchedu coupleprocessus/adressevirtuelle correspondant. TE 6

Traductiond'adresse partablede pageinversée

Cependantcette méthoden'estpas applicable,onconstate quifauten moyenne nombre_de_cadres_de_page/ 2accèsmémoire pourtraduireune adressevirtuelle! Pourrésoudrese problèmeon ajouteunetable dehachagepour réduirelenombre d'adressemémoireà consulter. Cettetechnique estassezpeu employéeetje nevoispersonellement pascommentpartager des pagesavec cettetechnique(possible ?).

Enplus desdeuxprocédés présentésilexiste unpetitnombre devariantes.Certaines approches,bi-

enque nonimplémentéesactuellement, ontétéétudiées pardiverschercheurs; onpeutnotamment

citerles travauxdeJochen Liedtkesurune sortedetable depagemulti-niveaux maisnonbalancée

évitantainsi degâcherde l'espacepourdes espacesd'adressageclairsemés. Sonimplémentationin-

troduitplus deniveauxd'indirections qu'unetablede pagesà3 niveauxclassiquemais cecipourrait

êtrecompensable àl'aided'un cachepourstocker lespointsd'entrer lesplusutilisés danslatable des

pages.On sereporteranotamment à[LIE94 ]et[ LIE]pour plusd'informationssur cettethéorie intéressante.On ytrouveraaussi unecritiquedes deuxautresapproches.

2.4.Segmentation

D'unpoint devueconceptuel lasegmentationest àl'opposéde lapagination.Là oùl'onpositionnait

desdonnées dansdesblocs detaillefixe facilementdéplacable,la segmentationproposede re- grouperun ensemblehomogènede donnéesdansun blocmémoirede tailleappropriée.Les informa- tionssont alorsaccessiblespar rapportàl'adresse dedébutd'un segmentdonné;une adressedevient doncun couple(numérode segment,déplacement).La positionréelled'une telledonnéeest donc modifiableen changeantl'adressedu débutdusegment, leprogrammelui nevoitrien. Cependantle calculentre desadressesn'appartenant pasàun mêmesegmentn'a dèslorsaucun sens. L'avantageapporté parlasegmentation estdepas avoiràdupliquer d'informationscommedans la pagination(disposer desprotectionssur 2^20pagesest pluscoûteuxque protégerunsegment) etde nepas introduiredefragmentation interne.Demême partagerunsegment entreplusieursutilisateurs estplus simplequede maintenirdesensembles depagescohérents. Lecalculde l'adressephysique correspondantà uneadressevirtuel estplussimple quepourla paginationetse faitdela manière suivante TE 7

Traductiond'adresse parlasegmentation

Cependantmalgré lefaitque leprincipede lasegmentations'énonce simplementellen'est pasla réponseà toutlesproblèmes etintroduitune plusgrandecomplexité danslaconception des systèmeset nesimplifiepas vraimentlesalgorithmes !Sila paginationintroduisaitune fragmenta- tioninterne (lesblocssont detaillefixe maislesdonnées peuventêtreplus petites)lasegmentation introduitun fragmentationexterne.Les segmentssontde taillevariableet peuventêtredéplacés dansl'espace d'adressagececiimplique detrouverune zonelibrede taillesuffisantepour placerles segmentsce quipeutêtre coûteux.Demême ledéplacementvers lazoned'échange d'unsegment s'effectuepar segment.L'avantageétant qu'ondéplaceun ensemblelogiqueservant peu(quià donc peude chancesderesservir) maislapagination permettaitdedéplacer despagesinutiles dansunen- sembledonné (erreursd'allocationpar exemple). Lenombre desegmentsétant limité(2^13sur X86)celapeut aussiposerdes problèmesside très

nombreuxsegments doiventêtrecréés. Ceciàd'ailleurs étéproblématiquedans Linux2.2et

empêchaitde créerplusde 2^12processus. Certainsystèmes commeMULTICSont implémentéunmodèle mémoirebasésur delasegmenta- tionpaginée combinantlesavantages desdeuxméthodes. Ceciàpermis lamiseen placedeprotec-

tionstrès finesettoujours peuégaléesdans lessystèmesactuels (lesanneauxde protectionontété

remplacéspar dessystèmesplus rudimentaires).Cependantla complexitédela VMMétaittrès im-

portanteet lessystèmesUNIX ontreprisles bonnesidéesde MULTICStouten lessimplifiantnot- ammenten mettantdecoté lasegmentationqui nesertpratiquement plusaujourd'hui.D'ailleurs l'AMD64ne disposeplusd'unité desegmentationen mode64bits.

2.5.Gestion delazone d'échange

L'undes rôlesdusystème d'exploitationestde gérerdemanière transparentelazone d'échange.

L'utilisationdu disquedurcomme zonededélestage temporairedela mémoireprincipalerepose sur leprincipe delocalité.Des étudessurle comportementdesprogrammes ,notamentde P.J.Denning [DEN70],[DEN72],[DEN68 ],[DEN68b]et[DEN96],montrent quegénéralementlesaccès

mémoiresuivent unprincipede localité.C'est-à-direqu'à uninstantdonné seuleunepartie de

l'espaced'adresse d'unprocessusest utilisée,cettepartie estappeléeensemble detravail.Les études

statistiquesmontre quecetensemble detravailn'évolue quelentementau coursdel'exécution d'un

programme;si uneréférencemémoire aétéfait àl'adresseX àl'instantT ilya degrandechance

quecette adresseresservedans unfuturproche. Inversementsiune adressen'apas étéutilisée depuislongtemps, ilya peudechance quel'onen aitbesoin. Lesalgorithmesde remplacementtirentparti deceprincipe pourenleverdes pagesquiont lemoins

deprobabilité d'êtreutiliséesdans unfuturproche. Ilexisteun petitnombred'algorithmes quisont

notammentdécrit dans[TAN ],nousn'aborderons pascesalgorithmesdanscedocument. TE 8

2.6.Séparation endeuxde l'espaced'adressage

Surles systèmesutilisantla paginationl'espaced'adressage desprocessusest généralementséparé

endeux parties.Unepremière partiecontientles donnéesduprocessus etunedeuxième partie, identiquepour touslesprocessus, contientlamémoire dunoyau. Lebut decettetechnique estdeminimiser lecoûtdes appelssystèmespuisque lamémoirese trouve directementaccessible maisprotegéepar lematérielet iln'ya pasàvider leTLBàchaque fois.De

mêmeil estalorstrès faciledetransférer desdonnéesde l'espaceutilisateurvers l'espacenoyau.Pour

êtreefficace lenoyauà souventbesoind'avoir danssonespace d'adressagetoutela mémoire physique.Cela s'effectuesimplementlorsque l'espaced'adressageest assezgrandmais pose problèmesur lesarchitectures32 bits.Eneffet siunemachine disposede3GB demémoireprincip- aleon nepeutraisonablement pasréserver3GB demémoirepour lenoyau,les processusnepour- raientalors aumaximumadresser qu'unGBde mémoire! Ainsigénéralement oneffectueun découpagedetaille fixe;courament3/1 surlesarchitectures 32 bits.Le noyaunedispose qued'unGB etnepeut doncpasdirectement accèderàtoute lamémoire. Celaest effectuéparune astucequiconsiste àreserverune partiedece GBpoureffectuer desmap- pingtemporaires. Onchangela tabledespages pourpouvoiraccèder àl'informationintéressante. Cependantune partiedesdonnées dunoyaudoit absolumentêtreadressable directementetdoit donc demandermoins d'unGBde mémoire.

2.7.Hiérarchie demémoirescaches

Jusqu'icinous n'avonsparléque detroistypes demémoire: lamémoirede masseconstituéedes disquesdur, deslecteursde bandesouoptiques etc.,lamémoire principaleetenfin lesregistresdu processeurs. Cestrois catégoriessontséparées paraumoins unordrede grandeurtantau niveaudela tailleque destemps d'accèsetdébit; voiciquelqueschiffres : Mémoirede masse:Capacité: de100GBà quelquesTB,Temps d'accès:une dizainede ms,Débit :50MB/s Mémoireprincipale: Capacité:de 256MBàquelques GB,Tempsd'accès :del'ordre de ladizaine denanoseconde(133Mhz pourdela SDRAM)

Hiérarchiemémoire desmachinesactuelles

Encomparant cesordresde grandeuràceux d'unprocesseuron peutconstaterque nonseulemental- TE 9 lerchercher unedonnéesur ledisqueprend uneéternité,n'oublions pasqueles processeursactuels ontune fréquencedel'ordre duGhz,mais allerchercherune donnéeenRAM n'apasun coût négligeablenon plus.Sinous revenonssurle principedetable depageque nousavonsintroduit on constateque pourfairela traductiond'uneadresse virtuelleenune adressephysiqueil fautconsulter latable despages.Cette tabledepage setrouveelle mêmeenRAM etpourune tableà2 niveauxil faut3 accèsmémoirepour obtenirl'adressephysique !Cecireprésente uncoûtgigantesque à

l'exécution;l'introduction delamémoire virtuelleralentiraitalors énormémentlamachine pourtant

celane seproduitpas pouruneraison simple.Lamémoire d'unordinateuractuel estconstituéed'une hiérarchiede mémoires.Ainsion aintroduitdes cachesmatérielsà diversesendroitsqui

représentaientdes goulotsd'étranglement.Ainsi lesdisquesdurs sontéquipésd'un cached'unetaille

dequelques MBquipermet d'éviterd'avoirà déplacerlatête delecturesi ladonnéesest encore

présentedans lecache. Demême descachesont étéintroduitsentre lamémoireprincipale etleprocesseur. Descachesde niveauL1, L2,voirL3 ontétéintroduits pourgarderun petitnombrede donnéesenmémoire etles rendreaccessibles trèsrapidement.Plus lamémoireest procheduprocesseur pluselleest rapide maisplus elleestpetite carcoûteuse.Le butdujeux étantd'essayerde maintenirdansles cachesles plusrapides lesinformationsaccédées leplusfréquemment. Toutcescaches sebasentsur leprin-

cipede localitéetimplémentent diversesméthodesde remplacementdontl'étude sortducadre dece

document. Toutefoisil existeuncache spécifiquequinous intéresseicile TLB,translationlookaside buffer.Le TLBàpour rôledegarder enmémoireun petitensemblede correspondancesadresse virtuelle/adressephysique +détailsde lapage.Encore unefoisle TLBsebase surleprincipe de

localitépour êtreeffectif.Sur lesprocesseurs80486 celui-ciavaitune taillede32 entréesquià été

élargieà 64entréesdepuis lesPentiumIII. Ainsiavecune tailledepage de4Kole taillegardeen mémoire64 *4= 256Kodetraduction enmémoireaccessible enmoinsd'un cycleCPU.Ainsi on

peutéviter danslaplupart descasle surcoûtentraînépar lapaginationen évitantd'avoirà consulter

latable depage. Cheminsuivit pouraccéderaux donnéesdansla plupartdesprocesseurs modernes.Àchaque étape

onessai decourscircuiter l'étagedudessous enregardantsi ladonnéen'est pasdéjàdans uncache

plusrapide. LeTLB neprésenteque desavantagespuisqu'au mieuxilpermet defairela traductionenmoins d'uncycle CPUetautrement lapénalitépour un"cachemissis" estdel'ordre de50cycles CPU;la MMUira alorsconsulterla tabledespages etplacerala valeurtrouvéedans leTLB. Ilest anotéque chaqueprocessusdisposant desonpropre espaced'adressageà chaquechangement

decontexte leTLBdoit êtrevidéet celaàdonc uncoûtà l'exécution.Deplus selonlesprocesseurs

TE 10 lagestion duTLBest matérieloulogiciel etlesystème d'exploitationàalors latachede defairela recherchedans latabledes pagesetde chargerl'informationcorrespondante àl'adressevirtuelle dansle TLB.Cecià pouravantagede laisserlesystème choisirlastructure dedonnéepour ses tablesde pagelematériel n'imposantrienà l'avance.Cependantle principalinconvénientest qu'il fautalors ilfautalors desinstructionspour parcourirlatable depages,généralement entre10et 100. Deplus ilestpossible quecesinstructions nesoientpas danslecache d'instructionalorsla pénalité àl'exécution estplusque conséquenteparrapport àuneprocédure câblée. Lechoix del'uneou l'autredesapproches sefaiten observantlafréquence des"cachemiss" etdonc lecoût induitpartel outelchoix. Nousprésenteronsen annexelessolutions proposéespartel outel processeur.

2.8.Exhausion del'espaced'adressage

Undes butsetune desconséquencesde lamémoirevirtuelle estdepouvoir adresserplusd'espace mémoireque demémoireprincipale n'estdisponible.Bien entenducommenous l'avonsvucela sup- poseque l'espacedetravail resteluiplus petitouégal quelamémoire principalelecontraire entraînantinévitablement dutrashing. Cependantl'espace constituédela mémoireprincipaleet deszonesde swapsurle disqueconstitue luiaussi unensemblede tailleborné.Il peutarriverque lesystèmearrive àcourtde mémoireetne puisseplus satisfairelesdemandes d'allocationmémoire.Cette partiedela gestionmémoireest souventappelée OOMpour"out ofmemorymanagement". Undesprincipaux problèmesquise

poseest commentgérerde manièreoptimalela situation.Àce problèmedifférentessolutions ontété

proposéesaucunes n'estsatisfaisantenous allonsenprésenter quelquesunesen pointantleursavant- ageset leursinconvénients.

Lapolitique optimalen'estréalisable quepartl'administrateur quisaitévaluer lasituationet choisir

l'actionqui auralemoins deconséquence.Évidement untelalgorithme n'estpasconcevables ainsi toutles algorithmesprésentésprésentent aumoinsun caspathologiqueou ilprendla mauvaise décision. Lapremière solutionetla plussimpleest denerien faire.Enfait ilsuffitde faireéchouerles de- mandesd'allocation mémoireetd'attendre quel'administrateursystème intervienne.Aucunequotesdbs_dbs44.pdfusesText_44

[PDF] difference entre pagination et segmentation

[PDF] conversion adresse logique adresse physique

[PDF] pagination et segmentation pdf

[PDF] pagination systeme d'exploitation

[PDF] telecharger un livre de grammaire pdf

[PDF] larousse conjugaison pdf

[PDF] telecharger larousse difficultés grammaticales pdf

[PDF] larousse grammaire francais

[PDF] larousse orthographe pdf

[PDF] larousse livre de bord orthographe pdf

[PDF] introduction grammaire generative

[PDF] chomsky théorie

[PDF] chomsky linguistique pdf

[PDF] aspects de la théorie syntaxique pdf

[PDF] grammaire grecque ancien