[PDF] Pagination (1/3) : la mémoire

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 271 271 Pagination (1/3) : la mémoire •Lamémoireestuneress ourcedetaill efinie,le système d'exploitationvaendonner unereprésentation"logique»,lavirtualiser,pourqu'elleapparaissecommeuneressourcedisponiblesanslimitation.•Lapremièreétapedecettevirtualisationestlapagination:Lamémoireestdiviséeensous-ensemblesdemêmetaille ,appeléspage phy ique (frameenanglais)•Dansunespacemémoirepaginé,lesadressessontstructuréesenpaires:adresseenmémoirephysique(adressephysique):(NPPHI,DEP)oùNPPHIestlenumérodepage(frame)etDEPledéplacement,enoctets,danscettepage.Parexempl e,silataille despagesest de1Ko(1024octets):adressephysique2026=(1,1002)

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 272 272 Pagination (2/3) : les processus •L'espacemémoireallouéauxprocessusestluiaussidiviséenpages,appeléespage logique (pageenanglais),numérotéesde0àNprocpourchaqueprocessus.•Parexemple,soittroisprocessusPi,PjetPk,etdespagesde1Ko:ProcessusPiPjPkEspaced'adressagenécessaire(enKilooctets)835•Représentationdel'espaced'adressagedecestroisprocessus:•Danschaqueprocessus,lesadressessontstructuréesenpaires:adresseenmémoireprogramme(adresselogique):(NPL,DEP)oùNPLestlenumérodepagelogiqueetDEPledéplacementdanslapage,enoctets,danslapage.

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 273 273 Pagination (3/3) : allocation des pages •Danscetexemple,latailledespagesphysiquesestde1Ko(1024octets),lespagesphysiqueslibressontreprésentéesengrisé.•Onconstatequeleplusgrandbloclibrefait2Ko(pagephysiques16et 17contiguës) .En allocationcontiguë,sionv oulaitmaintenantchargerenmémoirelesprocessusPj(3Ko)ouPk(5Ko)ilfaudraitfairedugarbagecollecting.•Lapaginationvalevercettecontraintedecontiguïté:Dansunespac epaginé ,auxalgorithmesdeplacementsesubstituentdesalgorithmesd eremplacement:lespageslogiquessontchargéesaufuretàmesuredesbesoinssurlespagesphysiqueslibres,mêmesicesdernièresnesontpascontigües.

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 274 274 La table de pages (1/3) : rôle •CommentretrouveruneinformationsetrouvantdansunepagelogiquenumérotéeNPLquiaétéchargéesurunepagephysiqueNPPHI?•Onutiliseunetable,appeléetabledepage .Ilyaunetabledepagesparprocessus.•SoitTPcettetable,àchaquechargementd'unepagelogiqueNPLsurunepagephysiqueNPPHI,onfait:TP[NPL]=NPPHIOnaura doncpour leprocessusPKprécédent:

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 275 275 La table de pages (2/3) : exemple Soitlavariableiquiauneadresseenmémoireprogramme(adresselogique)1028:ondit qu' elleestdansl'espaced'adressagedePK.Onvoi tbienquel'exécutionde i=4neprovoquepasd'écrituredelavaleur4àl'adressephysique1028,c'est-à-diredanslapagephysique1enmémoire;eneffet,1028esticiuneadresseenmémoireprogramme(adresselogique).Enréalité, lapage logique1deP Kestchargéesurl apagephysique23!L'adressephysiqueseradon cdifférentedel'adresselogique.

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 276 276 La table de pages (3/3) : exemple •L'utilisationdelatabledepagepermetlatraductiondesadresseslogiquesenadressesphysiques:•Remarque:chaqueprocessusvoitsonpropreespaced'adressagenumérotéàpartirde0,maischaqueespaceestappliquésurunespacephysiquedifférent->i olationetprotectionauniveaudelapage(cf.Android,...)

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 277 277 Adresses virtuelles (1/4) •Lapagina tionpermetlavirtuali ationdel' espaced'adressage:1. ellepermetde chargeruneapplicationde façonnoncontigüeenmémoire,2. mais,deplus,elleautorisel'exécutiond'uneapplicationmême ilatailledel'e pacedi ponibleenmémoirephy iquee tinféri eureàcellerequi eparl'application.3. onnecha rgeenmémo irephysiquequ'uns ous-ensembledespageslogiquesdel'application,lerestedespa geslogiquespeuventêtre écritessur unautresupportcommeundisqued ur.Latable depage sindiquel'emplacementexact:c'estàdiresiunepageestenmémoirephysiqueousurunautresupportdisque.

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 278 278 Adresses virtuelles (2/4) •Exempledescénario:§ soitunprocessusPk(7Ko),unemémoireàpagesphysiquesde1Koetundisquedontlesblocsfont1Ko.Pkoccupe7blocssurledisque:n1àn7.§ Ilreste5pagesphysiquesdisponiblesenmémoire:5,11,16,20et23.§ Enco ursd'exécutionde Pk,laconfigurationpeutêtrelasuivante:•Onremarquequ'unélémentaétéajoutédanslesentréesdelatabledepagesquiperme tdedéterminerl'emplacementd'unepagelogique:un indicateur devalidité(1:pa geenmémoire,d oncl'entréedonneunnumé rodepagephysi que,0:nu mérodeblocdisqueoùsetrouvelapage)

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 279 279 Adresses virtuelles (3/4) : bilan •Commeonvient delev oir,lamémoirerequiseparun processuspeutêtre upérieureàcelledelamémoi redi ponibleL'espaced'adressaged'u nprocessusétantpotentiellementplusgrandquel'espaced'ad ressagedela mémoirephysique,o nparledoncd'espaced'adres sagevirtueletd'adressesvirtuellespourlesprocessus.:adre evirtuelle:(Numérodepagevirtuelle,déplacementdan lapage)

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 280 280 Adresses virtuelles (4/4) : bilan •L'accèsàuneinformationenmémoiresefaitcommesuit:1. découpagedesonadressee nnuméro depagevi rtuelle(NPV)etdéplacement,2. accèsàl'entrée TP[NPL]delatab ledep agesTPduprocessus:a. indicateurdevaliditéV=1èpassagedepagelogiqueenpagephysique,accèsàl'informationpartraductiondel'adresselogiqueenadressephysique,b. indicateurdevaliditéV=0èpagesurled isque,défautdepage(pagefault)• action:re mplacerunedespagesphysique(appeléeNPR)parNPV,recopierNPRsurdisquesielleaétémodifiée,mettreàjourTP[NPL]etTP[NPR].• accèsàl'informationpartraductiond'adresse

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 281 281 Virtualisation de la mémoire : illustration •L'espaced'adressaged'unprocessusestdiviséenpagesvirtuelles:• danslaplupartdescas,seulunsous-ensembledecespagesesteffectivementenmémoire,• latabledepagesindique,pourchaquepagevirtuelleutilisée,sielleest,ounon,présenteenmémoire•Surcetexemple,seules3pagesparmi6sontprésentesenmémoire.

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 282 282 Pagination et mémoire virtuelle •SoitMlatailledelamémoiredisponiblesurlamachine.SoitTlatailledel'application:• SiTM,onparledemémoirevirtuelle,deuxcassontalorspossibles:o Mestlatailledelamémoirelibreàcetinstant,o Mestlatailledetotaledelamémoire(applicationplusgrandequelamémoirephysique!)•Lamémoirevirtuelledonnel'illu ionàl'utili ateur(auproce u )qu'ildi po ed'une paced'adre ageillimité(enfait,limitéparlatailledudi que).

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 283 283 Mémoire virtuelle : Point de vue utilisateur •Lamémoirevirtuellepermetd'exécuter:• simultanémentplusieursprocessusdontlasommedesespacesd'adressageestsupérieureàlatailledelamémoirephysiques• uneapplicationdontlatailleestsupérieureàlatailledelamémoirephysique,•Latailled'uneapplicationestdonclimitéeparcelled'uneadresse:• nbitsd'adresses->232octetsd'espaced'adressage• enpratiqueunparamètresystèmelimitecettetaille

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 284 284 Passage de l'adresse virtuelle à l'adresse physique : - l'adresse d'une information est divisée en deux champs : numéro de page virtuelle et déplacement dans cette page (ici appelés p et w) - le contenu de l'entrée p de la table de pages (appelée TP) donne le numéro de page physique p' où est chargée p. Dans cette entrée, c'est à dire dans TP[p] figurent également les droits d'accès à la page en lecture, écriture et destruction, ainsi que des indications nécessaires à la pagination. Ces indications sont données par des bits, citons le bi t V (valid) qu i indique si p' est bien un numéro d e page en mémoire, le bit M (modified ou dirty bit) qui indique si la page a été modifiée. - pour trouver l'information cherchée on concatène la partie déplacement dans la page au numéro de page physique trouvé. Lorsqu'on ne trouve pas la page que l'on cherche en mémoire, on parle de défaut de page (page fault, en anglais).

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 285 285 Traduction d'une adresse virtuelle en adresse physique •Principe:•Exemple:lesadressesvirtuellesetphysiquesontsur32bits,lespagesfont1Koctets.Lapagevirtuelle4estimplantéesurlapagephysique9.Voiciles3étapesdelatraduction:

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 286 286 En allocation par partition, les stratégies sont des stratégies de placement, ici on utilise des stratégies de REMPLACEMENT, les tailles de toutes les partitions (ici des pages) étant égales. Les principales stratégies sont les suivantes : • Moins Récemment Utilisée (MRU) / Least Recently Used (LRU) : On suppose que le futur ressemblera au passé. Implique que l'on conserve une trace des dates d'accès aux pages. • Moins Fréquemmen t Utilisée (MFU) / Least Frequently Used (LFU) : On suppose que le futur ressemblera au passé. Implique que l'on conserve une trace du nombre d'accès aux pages. Problème des pages récemment chargées. • La Plus Ancienne / First In First Out (FIFO) : Implique que l'on conserve une trace de l'ordre de chargement.

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 287 287 Stratégiesderemplacement•Ce sstratégiespermettentdechoisirquellep agevirt uelledoitêtreremplacéeparlapagevirtuellecourante:-LeastRecentlyUsed (LRU),lapagelamoin srécemmentutilisée.C'estl'algorithmeleplusutilisé:leshiérarchiesdemémoiressontgéréesLRU.-LeastFrequentlyUsed (LFU),lapagel amoinsfréquemmentutilisée.-FirstInFirstOut(FIFO),laplusancienne.

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 288 288 Exemple-1: partage de code (1/5) •Contexte:• Tailledespages:1Koctets,algorithmederemplacement:LRU,• Unetabledepageparrégion(code,donnéesetpile)pourchaqueprocessus,• Ilreste6pag eslib res(P1à P6)enmémoire. Onne 'intére equ'àlage tiondelarégiondecodede proce u .

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 289 289 Exemple-1: partage de code (2/5) •Scénario:• Unprocessus,leprocessusA,exécuteunprogrammedontlatailleest3Koctets.3pagesenmémoire(P1,P2,P3)parmices6pag eslibressontutilisées pourrangerceprogramme.1. lestroispremièresentréesdelatabledepagesdeApointentdoncversP1,P2etP3.• CeprocessusAfaitappelàfork()etcréeleprocessusB:1. lestroispremièresentréesdelatabledepagesdelarégiondecodedeBp oint ent alorsverslamêmespagesmémoirequecellesutiliséesparA:P1,P2etP3(partagedecode)commeillustréci-après.

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 290 290 Exemple-1: partage de code (3/5) Etatdes tablesdepagesdesprocessusAetB:•Remarques:Cepartagedesexécutablesestmisenoeuvresystématiquement(ilestfacileàfaire:lespagesn'étantpasmodifiées,iln'yapasdeproblèmedeconcurrence):1. iln'yaqu'unseulexemplaired'unprogrammeenmémoire,l'espacequiluiestallouéestpartagépartou lesprocessusquil'utilisent2. iln'ya qu'unse ulexe mplaireenmémoired'unebibliothèquedynamique:cf .labibliot hèqued'en tréessorties(gaindeplace!)

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 291 291 Exemple-1: partage de code (4/5) •LeprocessusBfaitmaintenantappelàexec()pourchargerunfichierdontlatailleest4Koctet .C'estmaintenantquevasefairel'allocationenmémoiredespagesdecodepourleprocessusB:LestroispremièresentréesdesatabledepagessontactualiséesetpointentversP4,P5etP6,lestroisdernièrespageslibresenmémoire,Auchargementdelaquatrièmepagedufichier,ilyn'yplusdepagelibre,onappliquedoncLRUsur lest roispagesdéj àallouéese nmémoirepourleprocessusB.

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 292 292 Exemple-1: partage de code (5/5) •EtatdestablesdepagesdesprocessusAetBaprèschargementdel'exécutabletraitéparleprocessusB:•Remarques:1. L'algorithmeLRUtravaillesur lesdatesd'accè auxinformation setrouvantdanslespages,nonpassurlesdatesdechargementdespagesenmémoire,lapageLRUauraitpuêtreuneautrequelapage0.2. Lapagevirtuelleremplacéen'estrecopiéesurdisqueavantsonremplacementquesielleaétémodifiée.

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 293 293 Exemple-2: allocation d'un tableau (1/3) •Contexte:1. L'algorithmederemplacementestLRU,latailledespagesestde4Koctets,2. Onsupposequ'ilreste3pageslibresenmémoire:P10,P20etP30,3. Onnes'intéressequ'auxpagesdedonnées,4. Onneprendpasencomptelesindicesdeboucles:onsupposequ'ilssontimplantésdansdesregistres.5. LetableauTabn'estplusenmémoireavantl'exécutiondelaboucleduprogrammeci-dessous.long Tab[4096]; /* sizeof(long) = 4 octets */ ...for (i=0; i<4096; j++)Tab[i]=0;

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 294 294 Exemple-2: allocation d'un tableau (2/3) •DescriptionduchargementdutableauTabenmémoireetévolutiondelatabledepageslorsdel'exécutiondelaboucle:1. Ilfaut4pagespourimplanterletableau,eneffet:4096(212) motsde4octets=16Ko=4pages.2. Lorsdesréféren cesàTab[0], Tab[1024], Tab[2048], onchargerespectivementlespages0,1et2dutableausurlespagesphysiquesP10,P20etP30,3. LorsdelaréférenceàTab[3072],iln'yaplusdepagelibre.Lapremièrepagedutableau(rangésurlapagemémoireP10)estlapageLRU.Soncontenuestdoncrecopiéesurledisqueparcequ'elleaétémodifiée,etlapageP10estutiliséepourstockerlesvaleurssuivantesdeTab•EtatdelatabledepagesaprèschargementdudernierKodutableau:0(entréepour1/4)Numéroblocdisqueoùsetr ouvelap remièrepagedutableau.1(entréepour2/4)P202(entréepour¾)P303(entréepour4/4)P10......

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 295 295 Exemple-2: allocation d'un tableau (3/3) •Sionremplacelaboucleprécédenteparcesinstructions:for (i=0; i<4096; j++){if (i %1024 == 0) Tab[0]=0;Tab[i]=0;}•Achaquechangementdepage,onfaitaccèsàlapremièrepage.Ellen'estdoncplusLRUlorsduchargementdelaquatrièmepage.C'estladeuxièmequiestmaintenantLRU:•Etatdelatabledepagesaprèschargementcompletdutableau:0(entréepour1/4)P101(entréepour2/4)Numéroblocdisque oùsetrouve ladeuxièmepagedutableau.2(entréepour¾)P303(entréepour4/4)P10......

Ge tiondelamémoire _______________________________________ © Telecom-ParisTech BCI Informatique 296 296 Aproposdes"fautes»surlesaccèsmémoire•Défautdesegmentation(Segmentationfault):Ils'agit d'uneréférence versunead ressedontl'accèsestinterditdanslemode(lecture,écriture)demandé:• l'accèsdemandénesefaitpas.Suroccurrencedecette"faute»,les ystèmere çoituneinterruption ,qu'iltraiteenenvoyantle signalSIG SEGVauprocessus;pardéfaut,celaprovoquelaterminaisonduprocessusfautif(saufs'ilachang élecomportemen tasso ciéàSIGSEGVenutilisantlafonctionsignal).•Défautdepage(pagefault):Ils'agitd'uneréférenceàuneadressedontlemoded'accèsdemandéestautorisé,maisquisetrouvedansunepagequin'estpasprésenteenmémoire:• Ilfautallercherchercettepagesurledisque.• Unefoislapagechargéeenmémoireetfaitelamiseàjourdelatabledepage,onrecommencel'exécutiondel'instruction.