Innen datavitenskap ble den virtuelle minnemekanismen utviklet på 1960-tallet . Den er basert på bruk av on-the-fly oversettelse av (virtuelle) adresser sett av programvaren, til fysiske RAM- adresser . Virtuelt minne tillater:
James Kilburn s fjell 1962 artikkelen beskrives den første datamaskinen med en sidevekslet virtuelt-lager styresystemet som bruker en trommel som en forlengelse av ferritt- kjerneminne : den Atlas .
I dag har alle datamaskiner en virtuell minnehåndteringsmekanisme, bortsett fra noen superdatamaskiner eller sanntids innebygde systemer.
Prinsippet er som følger:
Sidetabellen indekseres av sidenummeret. Hver rad kalles en "oppføring i sidetabellen" ( sidetabelloppføring , forkortet PTE), og inneholder rammenummeret. Siden sidebordet kan plasseres hvor som helst i minne, et spesielt register (PTBR for Page Table Base Register ) holder sin adresse.
I praksis er oversettelsesmekanismen en del av en elektronisk krets kalt MMU ( memory management unit ) som også inneholder en del av sidetabellen, lagret i et assosiativt minne dannet av raske registre. Dette unngår å måtte se sidetabellen (i minnet) for hver minnetilgang.
Her er et reelt eksempel på en maskin hvis prosessor genererer 32-biters virtuelle adresser, og dermed får tilgang til 4 GiB minne. Sidestørrelsen er 4KiB . Det trekkes ut fra dette at forskyvningsfeltet opptar de 12 minst signifikante bitene , og sidetallfeltet de 20 mest betydningsfulle bitene.
Legg merke til tilstedeværelsen av et spesielt felt som tilhører hver PTE. For å forenkle har vi redusert bredden på dette feltet til en bit: gyldighetsbiten . Hvis dette er 0, betyr det at rammenummeret er ugyldig. Det er derfor nødvendig å skaffe seg en teknikk som gjør det mulig å oppdatere denne PTE for å gjøre den gyldig.
Tre tilfeller kan oppstå:
I de to siste tilfellene genereres et avbrudd - kalt standardside (eller noen ganger sidefeil , oversettelse fra engelsk sidefeil ) av materialet og gir hånden til operativsystemet. Dette er ansvarlig for å finne en tilgjengelig ramme i hovedminnet for å tildele den til prosessen som er ansvarlig for denne sidefeilen, og muligens for å laste innholdet på denne rammen på nytt med innholdet lagret i masseminnet (for øyeblikket harddisken på et område kalt bytteområde eller bytte ).
Det kan hende det ikke er flere ledige bilder i hovedminnet: dette er da 100% opptatt. I dette tilfellet en paginering algoritme er ansvarlig for å velge et “offer” side. Denne siden tilordnes umiddelbart til forespørselsprosessen, eller så blir den først lagret på harddisken, og oppføringen i sidetabellen som refererer til den blir oppdatert. Offersiden kan godt høre til prosessen som mangler plass.
Nedenfor er noen eksempler på algoritmer listet opp. Den første linjen tilsvarer kjeden av referanser , det vil si rekkefølgen prosessen vil få tilgang til sidene i. Det antas at hovedminnet består av tre rammer . Den offeret rammen vil vises understreket. De første sidefeilene telles ikke (de er identiske i antall uavhengig av algoritmen som er valgt).
7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
7 | 7 | 7 | 2 | 2 | 2 | 2 | 2 | 7 | ||||||||||||||||||||||||||||||||
0 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | |||||||||||||||||||||||||||||||||
1 | 1 | 3 | 3 | 3 | 1 | 1 |
7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
7 | 7 | 7 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 | 7 | 7 | 7 | |||||||||||||||||||||||||
0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | 1 | 1 | 0 | 0 | ||||||||||||||||||||||||||
1 | 1 | 1 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 |
7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
7 | 7 | 7 | 2 | 2 | 4 | 4 | 4 | 0 | 1 | 1 | 1 | ||||||||||||||||||||||||||||
0 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 0 | 0 | |||||||||||||||||||||||||||||
1 | 1 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 7 |
Det kan være relativt enkelt å finne patologiske tilfeller som gjør en algoritme ubrukelig. For eksempel, for LRU-algoritmen, vil dette være et program som bruker 5 sider i en løkke på en maskin som bare har 4 bilder '. Den vil først bruke de første 4 bildene sekvensielt (1, 2, 3, 4), så vil det oppstå en sidefeil, og det er side 1, den eldste som er lastet, som blir offeret. Sidene som er brukt er nå (5, 2, 3, 4). Siden programmet går, trenger det side 1 (fortsetter fra side 5). Denne gangen er offerets side side 2, erstattet av 1: (5, 1, 3, 4), deretter (5, 1, 2, 4), (5, 1, 2, 3) osv. Det genereres en sidefeil ved hver iterasjon ...
Intuitivt, hvis du øker antall siderammer (det vil si å øke hovedminnet), bør antallet sidefeil reduseres.
Belady finnes uregelmessighet (1970) er et counterexample som viser at dette ikke er helt oppfylt med FIFO- algoritmen , ja leseren vil være i stand til å verifisere for seg at sekvensen av referansene (3, 2, 1, 0, 3, 2 , 4, 3, 2, 1, 0, 4) fører til
Merk : omfanget av denne nysgjerrigheten skal ikke overdrives. Det viser absolutt at FIFO-algoritmen generelt ikke har en egenskap man ville ha forventet (å legge til minne reduserer sidefeil), men det viser ikke at den ikke har den i gjennomsnitt . Og uansett blir FIFO-algoritmen aldri brukt til utskifting av sider.
Videre kan det vises at visse siderstatningsalgoritmer ( for eksempel LRU ) ikke er underlagt denne typen anomali.
Metodene for å velge offer-siden nevnt ovenfor kan brukes enten på sidene som tilhører en prosess (vi snakker da om "lokal tildeling"), eller på alle sidene og derfor på hele minnet (i dette tilfellet er tildelingsteknikken sies å være "global").
I et globalt tildelingssystem kan gjennomføringstiden for en prosess variere sterkt fra forekomst til forekomst fordi antall sidefeil ikke avhenger av selve prosessen. På den annen side tillater dette systemet antall ledere som er tildelt en prosess å utvikle seg.
Det følgende diagrammet viser tre prosesser som kjører, for eksempel en tekstredigerer som heter Ed. De tre forekomstene er alle lokalisert på de samme virtuelle adressene (1, 2, 3, 4, 5). Dette programmet bruker to forskjellige minneområder: sidene som inneholder koden, det vil si instruksjonene som beskriver programmet, og dataområdet, filen som redigeres. Det er tilstrekkelig å beholde de samme oppføringene i sidetabellen for at de tre forekomstene kan dele kodeområdet. På den annen side er oppføringene som tilsvarer datasidene forskjellige.
Noen bitbeskyttelse legges til hver oppføring i sidetabellen. Så vi kan enkelt skille mellom sidene som er tildelt kjernen, skrivebeskyttet osv. Se eksemplet nedenfor.
Det er tre store problemer:
Oppførselen til programmer er ikke kaotisk: programmet starter, det kaller funksjoner (eller deler av kode) som igjen kaller andre osv. Hver av disse samtalene definerer en region. Det er sannsynlig at programmet kan bruke mye tid på å kjøre i noen få regioner: dette er lokalitetsprinsippet. Det samme prinsippet kan brukes på sider som inneholder data.
Med andre ord får et program ofte tilgang til et lite sett med sider, og det settet med sider endres sakte over tid.
Hvis vi klarer å huske disse ofte tilgjengelige områdene, reduserer vi sjansene for at et program begynner å søppel , det vil si å kreve sider som nettopp har blitt fjernet fra det nylig.
Den arbeidssett : arbeidsområdetVi kan definere en parameter, Δ, som er antall referanser til sidene som prosessen har tilgang til i løpet av en viss tidsperiode. Figuren nedenfor viser verdien av arbeidsområdet på to forskjellige tidspunkter:
Verdien av Δ må velges med forsiktighet: for liten dekker den ikke det nominelle arbeidsområdet til prosessen; for stor den inkluderer unødvendige sider. Hvis Δ er lik uendelig, dekker det selvfølgelig hele programmet.
For en enkelt prosess kan vi grafisk representere hvordan minnet er allokert til det, og visualisere arbeidsområdene:
“Brettene” er områder der det ikke er noen sidefeil: den tildelte plassen er stor nok til å inneholde alle rammene som prosessen trenger i relativt lang tid. Sidefeil finner sted i den stigende delen av overgangen, mens minnet frigjøres når kurven faller tilbake til neste arbeidsområde: likevekt sone.
Det er opp til operativsystemet å implementere algoritmene slik at verdien av A er optimal slik at frekvensen av multiprogrammering og bruken av sentralenheten maksimeres. Med andre ord: unngå søppel . Hvis summen av arbeidsområdene for hver prosess er større enn antall tilgjengelige rammer , vil det nødvendigvis være kollaps.
En av fordelene med virtuelt minne er å kunne starte kjøringen av et program så snart den første kodesiden er lastet inn i minnet. Prepaginasjonen vil ikke bare laste den første siden, men de neste få, som har svært stor sannsynlighet for å bli tilgjengelig.
Maskin | Adresserbar plass | Page antall felt | "Displacement" -felt |
---|---|---|---|
Atlas | 11 | 9 | |
PDP-10 | 9 | 9 | |
IBM-370 | 13 eller 12 | 11 eller 12 | |
Pentium Pro | 12 eller 20 | 20 eller 12 | |
Alpha 21064 | 1. 3 | 30 |
Feltene M, U, N og NDP er bare gyldige hvis V-biten er på 1. Når V er 0, inneholder NDP-feltet adressen på harddisken der siden ligger.
Verdi | Beskyttelse |
---|---|
0000 | Ingen adgang |
1000 | Lesing for kjernen |
1100 | Les / skriv for kjernen |
1010 | Bruker og kjerne lest |
1110 | Brukerlesning, kjernelese / skrive |
1111 | Bruker og kjerne lese / skrive |
Bit 24, N ( N skjult), betyr at siden ikke er hurtigbufret og systemet skal lese eller skrive direkte fra eller til minnet.
The M ( M odified) bit blir modifisert ved maskinvaren hvis innholdet på siden er modifisert.
Bit U ( U tilisée) indikerer om siden har blitt lest eller skrevet av en prosess. Det er nyttig, i samarbeid med de andre, for å bestemme arbeidssettet til en prosess (se ovenfor).
Segmentering gir et syn på minne som er mer konsistent med brukerens. Faktisk anser denne ikke (eller sjelden!) Minnet som en serie sider, men snarere som mellomrom, eller regioner, ment for en bestemt bruk for eksempel: koden til et program, dataene, stabelen, et sett med underrutiner, moduler, en matrise, etc. Segmenteringen gjenspeiler denne organisasjonen.
Hvert logiske objekt vil bli utpekt av et segment. I et segment vil adresseringen bli gjort ved hjelp av en forskyvning. Dreiemomentet (segment, forskyvning) vil bli oversatt til en minneadresse ved hjelp av en segmenttabell som inneholder to felt, grense og base . Basen er startadressen til segmentet, og begrenser den siste adressen til det samme segmentet:
Paginerte systemer har et internt fragmenteringsproblem : plass er bortkastet på slutten av en side. Segmenterte systemer har et eksternt fragmenteringsproblem : mellomrom mellom segmentene er for små til å imøtekomme nye fragmenter, slik at plassen blir bortkastet.
Det er mulig å gjenopprette det ved å komprimere minnet, det vil si ved å flytte segmentene - mens de gjenspeiler disse modifikasjonene i tabellene til segmentene - slik at de er sammenhengende. Imidlertid er denne operasjonen kostbar.
Det er mulig å dele segmenter mellom prosesser, som vist i figuren nedenfor, der to prosesser Ed1 og Ed2 deler samme kodesegment (program), men har usammenhengende datasegmenter av forskjellige størrelser.
Denne beskyttelsen vil bli sikret av tilleggsbiter lagt til i segmenttabellen, på samme måte som for et sidesystem.
Det mest kjente eksemplet er Intel 8086 og dets fire registre:
Etterfølgerne til 8086 er også segmentert:
Det er mulig å blande de to foregående modusene:
Noen ganger er det nødvendig å slette alle sider eller segmenter av en prosess fra hovedminnet. I dette tilfellet vil prosessen sies å byttes , og alle dataene som tilhører den vil bli lagret i masseminnet. Dette kan skje i lange sovende prosesser når operativsystemet må tildele minne til aktive prosesser. Sidene eller kodesegmentene (programmet) vil aldri bli byttet ut , men ganske enkelt tildelt på nytt, fordi de finnes i filen som tilsvarer programmet ( den kjørbare filen ). Av denne grunn forbyr operativsystemet skrivetilgang til en kjørbar fil som er i bruk; symmetrisk er det ikke mulig å starte kjøringen av en fil mens den holdes åpen for skrivetilgang av en annen prosess.
Komprimering av virtuelt minne kan forbedre ytelsen til et virtuelt minnesystem. Denne virtuelle minnestyringsteknikken bruker datakomprimering for å redusere størrelsen eller antallet personsøkeforespørsler til og fra hjelpelagring.
I et komprimeringssystem for virtuelt minne blir sider komprimert og lagret i fysisk minne, vanligvis RAM , eller sendt komprimert til hjelpelagring, for eksempel en harddisk eller SSD . I begge tilfeller er rekkevidden til det virtuelle minnet hvis innhold ble komprimert utilgjengelig, så forsøk på å få tilgang til de komprimerte sidene utløser sidefeil og reverserer komprimeringsprosessen (gjenvinning av ekstra lagring og dekomprimering). Det sidede datafotavtrykket reduseres av komprimeringsprosessen, og det frigjorte RAM-minnet returneres til det tilgjengelige fysiske minnepoolen. Hvis de komprimerte sidene holdes i RAM-minne, bruker de komprimerte sidene åpenbart mindre plass enn originalsidene. I tilfelle at de komprimerte sidene oppbevares i ekstra lagring, blir RAM-minnet fullstendig frigjort, og skrive- og leseoperasjonene på hjelpeminnet er raskere enn om sidene ikke hadde blitt komprimert.