Algoritme for sideutskifting - Page replacement algorithm

I en datamaskin operativsystem som bruker personsøking for virtuelt minne forvaltning , siden erstatnings algoritmer avgjøre hvilket minne sidene til side ut, noen ganger kalt bytte ut, eller skrive til disken, da en side av minnebehov som skal tildeles. Sideutskiftning skjer når en forespurt side ikke er i minnet ( sidefeil ) og en ledig side ikke kan brukes til å tilfredsstille tildelingen, enten fordi det ikke er noen, eller fordi antallet ledige sider er lavere enn noen terskel.

Når siden som ble valgt for erstatning og sidet ut, refereres til igjen, må den sides inn (leses inn fra disk), og dette innebærer å vente på I/O -ferdigstillelse. Dette bestemmer kvaliteten på sideutskiftingsalgoritmen: jo mindre tid det venter på sideinnlegg, desto bedre blir algoritmen. En sideutskiftingsalgoritme ser på den begrensede informasjonen om tilgang til sidene som er levert av maskinvare, og prøver å gjette hvilke sider som bør byttes ut for å minimere det totale antallet savnede sider, samtidig som dette balanseres med kostnadene (primærlagring og prosessortid) selve algoritmen.

Siden som erstatter problemet er et typisk online -problem fra konkurranseanalyseperspektivet i den forstand at den optimale deterministiske algoritmen er kjent.

Historie

Siden erstatningsalgoritmer var et hett tema for forskning og debatt på 1960- og 1970 -tallet. Det endte stort sett med utviklingen av sofistikerte LRU (minst nylig brukte) tilnærminger og arbeidssettalgoritmer . Siden den gang ble noen grunnleggende forutsetninger fra de tradisjonelle algoritmene for sideutskifting ugyldige, noe som resulterte i en gjenoppliving av forskning. Spesielt har følgende trender i oppførselen til underliggende maskinvare og programvare på brukernivå påvirket ytelsen til sideutskiftningsalgoritmer:

• Størrelsen på primærlageret har økt med flere størrelsesordener. Med flere gigabyte primærminne blir algoritmer som krever en periodisk sjekk av hver minne ramme mindre og mindre praktisk.
• Minnehierarkier har vokst seg høyere. Kostnaden for en CPU -cache -savning er langt dyrere. Dette forverrer det forrige problemet.
• Referanselokaliteten til brukerprogramvaren er svekket. Dette tilskrives hovedsakelig spredningen av objektorienterte programmeringsteknikker som favoriserer et stort antall små funksjoner, bruk av sofistikerte datastrukturer som trær og hashtabeller som har en tendens til å resultere i kaotiske minne-referansemønstre og fremkomsten av søppelsamling som drastisk endret seg minnetilgangsadferd for applikasjoner.

Krav til sideutskiftningsalgoritmer har endret seg på grunn av forskjeller i kjernearkitekturer i operativsystemet . Spesielt har de fleste moderne OS -kjerner enhetlig virtuelt minne og filsystembuffere, noe som krever at sideutskiftingsalgoritmen velger en side blant sidene i både brukerprogrammets virtuelle adresserom og bufrede filer. De sistnevnte sidene har spesifikke egenskaper. For eksempel kan de være låst, eller de kan ha krav til skrivebestilling ved journalføring . Siden målet med sideutskifting er å minimere total ventetid på minne, må det dessuten ta hensyn til minnekrav som stilles av andre kjernesubsystemer som tildeler minne. Som et resultat har sideutskifting i moderne kjerner ( Linux , FreeBSD og Solaris ) en tendens til å fungere på nivået til en allokert kjerneminneallokator, i stedet for på det høyere nivået i et virtuelt minne -delsystem.

Lokal vs. global erstatning

Erstatningsalgoritmer kan være lokale eller globale.

Når det oppstår en sidefeil i en prosess, velger en lokal sideutskiftingsalgoritme å erstatte noen sider som tilhører den samme prosessen (eller en gruppe prosesser som deler en minnepartisjon ). En global erstatningsalgoritme er gratis å velge hvilken som helst side i minnet.

Lokal sideutskifting forutsetter en form for minnepartisjonering som bestemmer hvor mange sider som skal tilordnes en gitt prosess eller en gruppe prosesser. De mest populære partisjoneringsformene er faste partisjonerings- og balanserte settalgoritmer basert på arbeidssettmodellen . Fordelen med utskiftning av lokale sider er dens skalerbarhet: hver prosess kan håndtere sidefeilene uavhengig, noe som fører til mer konsistent ytelse for denne prosessen. Imidlertid er global sideutskiftning mer effektiv generelt sett.

Oppdager hvilke sider det refereres til og endres på

Moderne datamaskiner for generelle formål og noen innebygde prosessorer har støtte for virtuelt minne . Hver prosess har sitt eget virtuelle adresserom. En sidetabell tilordner et delsett av prosessens virtuelle adresser til fysiske adresser. I tillegg har sidetabellen i de fleste arkitekturer en "tilgang" -bit og en "skitten" bit for hver side i sidetabellen. CPUen angir tilgangsbiten når prosessen leser eller skriver minne på siden. CPUen angir den skitne biten når prosessen skriver minne på den siden. Operativsystemet kan endre tilgang og skitne biter. Operativsystemet kan oppdage tilgang til minne og filer på følgende måter:

• Ved å fjerne tilgangsbiten på sider som er tilstede i prosessens sidetabell. Etter en stund skanner operativsystemet sidetabellen på jakt etter sider som hadde tilgangsbiten angitt av CPU. Dette er raskt fordi tilgangsbiten den angav automatisk av CPU -en og unøyaktig fordi operativsystemet ikke umiddelbart får beskjed om tilgangen, og heller ikke har informasjon om rekkefølgen som prosessen åpnet disse sidene.
• Ved å fjerne sider fra prosessens sidetabell uten nødvendigvis å fjerne dem fra det fysiske minnet. Den neste tilgangen til siden oppdages umiddelbart fordi den forårsaker en sidefeil . Dette er tregt fordi en sidefeil innebærer en kontekstbryter til operativsystemet, programvareoppslag for den tilsvarende fysiske adressen, endring av sidetabellen og en kontekstbytte tilbake til prosessen og nøyaktig fordi tilgangen oppdages umiddelbart etter at den oppstår.
• Direkte når prosessen foretar systemanrop som potensielt får tilgang til sidebufferen som readog writei POSIX.

Forrensing

De fleste erstatningsalgoritmer returnerer ganske enkelt målsiden som resultatet. Dette betyr at hvis målsiden er skitten (det vil si inneholder data som må skrives til den stabile lagringen før siden kan gjenvinnes), må I/O startes for å sende den siden til den stabile lagringen (for å rense siden ). I de tidlige dagene med virtuelt minne var tid brukt på rengjøring ikke særlig bekymringsfull, fordi virtuelt minne først ble implementert på systemer med full dupleks -kanaler til den stabile lagringen, og rengjøring ble vanligvis overlappet med personsøk. Moderne varemaskinvare støtter derimot ikke full dupleksoverføring, og rengjøring av målsider blir et problem.

For å håndtere denne situasjonen implementeres ulike retningslinjer for forhåndsrensing . Forrensing er mekanismen som starter I/O på skitne sider som (sannsynligvis) snart skal byttes ut. Tanken er at når den forhåndsrensede siden faktisk er valgt for erstatning, vil I/O -en fullføres og siden være ren. Forrensing forutsetter at det er mulig å identifisere sider som vil bli erstattet neste . For forrensende rengjøring kan kaste bort I/O-båndbredde ved å skrive sider som klarer å bli tilsmusset på nytt før de blir valgt for erstatning.

Forventende personsøk

Noen systemer bruker etterspørselssøk - venter til en side faktisk blir bedt om før den lastes inn i RAM.

Andre systemer prøver å redusere ventetid ved å gjette hvilke sider som ikke er i RAM sannsynligvis vil trengs snart, og forhåndslaste slike sider i RAM, før den siden blir bedt om. (Dette er ofte i kombinasjon med forhåndsrensing, som gjetter hvilke sider som for øyeblikket er i RAM sannsynligvis ikke trengs snart, og forhåndsskriver dem til lagring).

Når det oppstår en sidefeil, vil "foregående personsøkings" -systemer ikke bare bringe inn den refererte siden, men også de neste sidene på rad (analogt med en forhåndshentingskø i en CPU).

Den swap forhåndshenting mekanismen går enda lenger i lasting av sider (selv om de ikke er sammenhengende) som sannsynligvis vil være nødvendig snart.

(H, k) -søkingsproblemet

(H, k) -søkingsproblemet er en generalisering av modellen for personsøkingsproblem: La h, k være positive heltall slik at . Vi måler ytelsen til en algoritme med hurtigbuffer i forhold til den teoretisk optimale sideutskiftningsalgoritmen . Hvis , gir vi den optimale sideutskiftningsalgoritmen med strengt mindre ressurser. ${\ displaystyle h \ leq k}$${\ displaystyle h \ leq k}$${\ displaystyle h <k}$

(H, k) -sideproblemet er en måte å måle hvordan en online algoritme utfører ved å sammenligne den med ytelsen til den optimale algoritmen, spesifikt separat parametere bufferstørrelsen til online algoritmen og optimal algoritme.

Merkingsalgoritmer

Merkingsalgoritmer er en generell klasse av personsøkingsalgoritmer. For hver side assosierer vi den med litt kalt dens merke. I utgangspunktet angav vi alle sider som umerkede. I et trinn med sideforespørsler markerer vi en side når den først blir bedt om i dette stadiet. En markeringsalgoritme er en slik algoritme som aldri tar ut en merket side.

Hvis ALG er en markeringsalgoritme med en cache av størrelse k, og OPT er den optimale algoritmen med en cache av størrelse h, hvor , så er ALG -konkurrerende. Så hver markeringsalgoritme oppnår -konkurrerende forhold. ${\ displaystyle h \ leq k}$${\ displaystyle {\ tfrac {k} {k-h+1}}}$${\ displaystyle {\ tfrac {k} {k-h+1}}}$

LRU er en merkingsalgoritme mens FIFO ikke er en merkingsalgoritme.

Konservative algoritmer

En algoritme er konservativ, hvis algoritmen på en påfølgende forespørselssekvens som inneholder k eller færre distinkte sidereferanser, vil pådra k eller færre sidefeil.

Hvis ALG er en konservativ algoritme med en cache i størrelse k, og OPT er den optimale algoritmen med en cache på , så er ALG -konkurrerende. Så hver konservativ algoritme oppnår -konkurrerende forhold. ${\ displaystyle h \ leq k}$${\ displaystyle {\ tfrac {k} {k-h+1}}}$${\ displaystyle {\ tfrac {k} {k-h+1}}}$

LRU, FIFO og CLOCK er konservative algoritmer.

Sideskiftende algoritmer

Det finnes en rekke algoritmer for sideutskiftning:

Den teoretisk optimale sideutskiftningsalgoritmen

Den teoretisk optimale sideutskiftningsalgoritmen (også kjent som OPT, klarsynt erstatningsalgoritme eller Béládys optimale retningslinjer for sideutskifting) er en algoritme som fungerer som følger: Når en side må byttes inn, bytter operativsystemet ut siden hvis neste bruk vil skje lengst i fremtiden. For eksempel vil en side som ikke skal brukes de neste 6 sekundene byttes ut over en side som skal brukes i løpet av de neste 0,4 sekundene.

Denne algoritmen kan ikke implementeres i et operativsystem for generelle formål fordi det er umulig å beregne pålitelig hvor lang tid det vil ta før en side skal brukes, bortsett fra når all programvare som vil kjøre på et system enten er kjent på forhånd og er tilgjengelig for statisk analyse av minnereferansemønstre, eller bare en klasse applikasjoner som tillater kjøretidsanalyse. Til tross for denne begrensningen eksisterer det algoritmer som kan tilby nesten optimal ytelse-operativsystemet holder oversikt over alle sider som programmet refererer til, og det bruker disse dataene til å bestemme hvilke sider som skal byttes inn og ut ved påfølgende kjøringer. Denne algoritmen kan tilby nesten optimal ytelse, men ikke ved den første kjøringen av et program, og bare hvis programmets minne-referansemønster er relativt konsistent hver gang det kjøres.

Analyse av personsøkingsproblemet har også blitt gjort innen elektroniske algoritmer . Effektiviteten av randomiserte elektroniske algoritmer for personsøkingsproblemet måles ved hjelp av amortisert analyse .

Ikke nylig brukt

Den ikke nylig brukte (NRU) side erstatningsalgoritmen er en algoritme som favoriserer å beholde sider i minnet som nylig har blitt brukt. Denne algoritmen fungerer etter følgende prinsipp: Når en side refereres, settes en referert bit for den siden, og markerer den som referert. På samme måte, når en side endres (skrives til), settes en modifisert bit. Innstillingen av bitene gjøres vanligvis av maskinvaren, selv om det er mulig å gjøre det også på programvarenivå.

Ved et bestemt tidsintervall utløser og sletter et tidsavbrudd den refererte biten på alle sidene, så bare sider som det refereres til i det nåværende tidsintervallet er merket med en referert bit. Når en side må byttes, deler operativsystemet sidene i fire klasser:

3. referert, modifisert

2. referert, ikke endret

1. ikke referert, modifisert

0. ikke referert, ikke endret

Selv om det ikke ser ut til å være mulig for en side å bli endret, men som det ikke er referert til, skjer dette når en klasse 3 -side får sin refererte bit fjernet av tidsavbruddet. NRU -algoritmen velger en tilfeldig side fra den laveste kategorien for fjerning. Så av de fire sidekategoriene ovenfor vil NRU-algoritmen erstatte en side som ikke er referert til, ikke-modifisert hvis en slik side eksisterer. Vær oppmerksom på at denne algoritmen innebærer at en modifisert, men ikke referert (innenfor det siste tidsintervallet) siden er mindre viktig enn en ikke-modifisert side som er intens referert til.

NRU er en merkingsalgoritme, så den er -konkurrerende. ${\ displaystyle {\ tfrac {k} {k-h+1}}}$

Først inn først ut

Den enkleste side-erstatningsalgoritmen er en FIFO-algoritme. Den først inn, først ut (FIFO) side erstatningsalgoritmen er en lav overhead algoritme som krever lite bokføring fra operativsystemets side . Ideen er åpenbar fra navnet - operativsystemet holder oversikt over alle sidene i minnet i en kø, med den siste ankomsten på baksiden, og den eldste ankomsten foran. Når en side må byttes ut, velges siden foran i køen (den eldste siden). Selv om FIFO er billig og intuitiv, fungerer den dårlig i praktisk bruk. Dermed blir den sjelden brukt i sin umodifiserte form. Denne algoritmen opplever Béládys anomali . Med enkle ord, på en sidefeil, erstattes rammen som har vært lengst i minnet.

FIFO side erstatningsalgoritme brukes av operativsystemet VAX/VMS , med noen modifikasjoner. Delvis ny sjanse gis ved å hoppe over et begrenset antall oppføringer med gyldige oversettelsestabellreferanser, og i tillegg blir sider flyttet fra prosessarbeidssett til et systemomfattende basseng hvorfra de kan gjenopprettes hvis de ikke allerede er gjenbrukt.

FIFO er en konservativ algoritme, så den er -konkurrerende. ${\ displaystyle {\ tfrac {k} {k-h+1}}}$

Ny sjanse

En modifisert form for FIFO-sideutskiftningsalgoritmen, kjent som Second-chance-sideutskiftningsalgoritmen, går relativt bedre enn FIFO til en liten kostnad for forbedringen. Det fungerer ved å se på forsiden av køen som FIFO gjør, men i stedet for å bla ut siden umiddelbart, sjekker den om den refererte biten er angitt. Hvis den ikke er angitt, byttes siden ut. Ellers slettes den refererte biten, siden settes inn på baksiden av køen (som om det var en ny side) og denne prosessen gjentas. Dette kan også tenkes som en sirkulær kø. Hvis alle sidene har sin refererte bit satt, på det andre møtet på den første siden i listen, vil denne siden byttes ut, siden den nå har fjernet sin refererte bit. Hvis alle sidene har sin referansebit ryddet, degenererer andre sjanse -algoritmen til ren FIFO.

Som navnet antyder, gir Second-chance hver side en "andre sjanse"-en gammel side som det er referert til er sannsynligvis i bruk, og bør ikke byttes ut over en ny side som ikke har blitt referert.

Klokke

Clock er en mer effektiv versjon av FIFO enn Second-chance fordi sider ikke trenger å skyves konstant bak på listen, men den utfører samme generelle funksjon som Second-Chance. Klokkealgoritmen holder en sirkulær liste over sider i minnet, med "hånden" (iteratoren) som peker på den siste undersøkte siderammen i listen. Når det oppstår en sidefeil og det ikke finnes tomme rammer, blir R (referert) biten inspisert på håndens plassering. Hvis R er 0, settes den nye siden i stedet for siden som "hånden" peker til, og hånden avanseres en posisjon. Ellers fjernes R -biten, deretter økes klokkeviseren og prosessen gjentas til en side er byttet ut. Denne algoritmen ble først beskrevet i 1969 av FJ Corbató .

Varianter av klokke

• GCLOCK: Generalisert algoritme for utskifting av klokkesider.
• Clock-Pro holder en sirkulær liste over informasjon om nylig refererte sider, inkludert alle M-sidene i minnet, så vel som de siste M-sidene som har blitt oversatt. Denne ekstra informasjonen på sider som er slått ut, i likhet med lignende informasjon som ARC vedlikeholder , hjelper den til å fungere bedre enn LRU på store sløyfer og engangssøk.
• WSclock. Ved å kombinere klokke -algoritmen med konseptet om et arbeidssett (dvs. settet med sider som forventes brukt av denne prosessen i løpet av et tidsintervall), kan ytelsen til algoritmen forbedres. I praksis er "aldring" -algoritmen og "WSClock" -algoritmen sannsynligvis de viktigste sideutskiftningsalgoritmene.
• Clock with Adaptive Replacement (CAR) er en sideutskiftningsalgoritme som har ytelse som er sammenlignbar med ARC , og som er vesentlig bedre enn både LRU og CLOCK. Algoritmen CAR er selvjusterende og krever ingen brukerspesifikke magiske parametere.

CLOCK er en konservativ algoritme, så den er -konkurrerende. ${\ displaystyle {\ tfrac {k} {k-h+1}}}$

Minst nylig brukt

Den minst brukte sideløsningsalgoritmen (LRU), selv om den ligner NRU, skiller seg fra det faktum at LRU holder oversikt over sidebruk over en kort periode, mens NRU bare ser på bruken i det siste klokkeintervallet. LRU jobber med ideen om at sider som har vært mest brukt i de siste instruksjonene, mest sannsynlig vil bli brukt mye i de neste instruksjonene også. Selv om LRU kan gi nesten optimal ytelse i teorien (nesten like god som adaptiv erstatningsbuffer ), er det ganske dyrt å implementere i praksis. Det er noen få implementeringsmetoder for denne algoritmen som prøver å redusere kostnadene, men beholder så mye av ytelsen som mulig.

Den dyreste metoden er metoden for koblet liste, som bruker en koblet liste som inneholder alle sidene i minnet. Bak på denne listen er siden som er minst brukt, og foran er den sist brukte siden. Kostnaden for denne implementeringen ligger i det faktum at elementene på listen må flyttes rundt hver minnereferanse, noe som er en svært tidkrevende prosess.

En annen metode som krever maskinvarestøtte er som følger: Anta at maskinvaren har en 64-biters teller som økes ved hver instruksjon. Når en side åpnes, får den verdien som er lik telleren på tidspunktet for sidetilgang. Når en side må byttes, velger operativsystemet siden med den laveste telleren og bytter den ut.

På grunn av implementeringskostnader kan man vurdere algoritmer (som de som følger) som ligner på LRU, men som tilbyr billigere implementeringer.

En viktig fordel med LRU -algoritmen er at den kan motta full statistisk analyse. Det er for eksempel bevist at LRU aldri kan resultere i mer enn N-ganger flere sidefeil enn OPT-algoritmen, hvor N er proporsjonal med antall sider i det administrerte bassenget.

På den annen side er LRUs svakhet at ytelsen har en tendens til å degenerere under mange ganske vanlige referansemønstre. For eksempel, hvis det er N -sider i LRU -bassenget, vil et program som kjører en loop over array med N + 1 -sider forårsake en sidefeil på hver tilgang. Siden sløyfer over store matriser er vanlige, har det blitt lagt mye arbeid på å endre LRU for å fungere bedre i slike situasjoner. Mange av de foreslåtte LRU -modifikasjonene prøver å oppdage looping -referansemønstre og bytte til passende erstatningsalgoritme, som Most Used Used (MRU).

Varianter på LRU

1. LRU-K fjerner siden hvis K-th siste tilgang er lengst tidligere. For eksempel er LRU-1 ganske enkelt LRU, mens LRU-2 kaster ut sider i henhold til tidspunktet for den nest siste tilgangen. LRU-K forbedrer seg sterkt på LRU med hensyn til lokalitet i tide.
2. Den ARC algoritmen utvider LRU ved å opprettholde en historie med nylig kastet ut sider og bruker dette til å endre innstillingen til nylig eller hyppig tilgang. Den er spesielt motstandsdyktig mot sekvensielle skanninger.

En sammenligning av ARC med andre algoritmer (LRU, MQ, 2Q, LRU-2, LRFU, LIRS ) finnes i Megiddo & Modha 2004.

LRU er en markeringsalgoritme, så den er -konkurrerende. ${\ displaystyle {\ tfrac {k} {k-h+1}}}$

Tilfeldig

Tilfeldig erstatningsalgoritme erstatter en tilfeldig side i minnet. Dette eliminerer overheadkostnaden for å spore sidehenvisninger. Vanligvis går det bedre enn FIFO, og for sløyfe -minnehenvisninger er det bedre enn LRU, selv om LRU generelt fungerer bedre i praksis. OS/390 bruker global LRU -tilnærming og faller tilbake til tilfeldig erstatning når LRU -ytelsen degenererer, og Intel i860 -prosessoren brukte en tilfeldig erstatningspolicy (Rhodehamel 1989).

Ikke ofte brukt (NFU)

Den ikke ofte brukte (NFU) sideutskiftningsalgoritmen krever en teller, og hver side har en egen teller som i utgangspunktet er satt til 0. Ved hvert klokkeintervall vil alle sider som det er referert til innenfor dette intervallet, ha sin teller økt med 1. Tellerne holder faktisk oversikt over hvor ofte en side har blitt brukt. Dermed kan siden med den laveste telleren byttes ut når det er nødvendig.

Hovedproblemet med NFU er at den holder orden på bruksfrekvensen uten hensyn til brukstid. I en multipass-kompilator vil sider som ble mye brukt under den første passeringen, men som ikke er nødvendig i den andre passeringen, bli foretrukket fremfor sider som er relativt lett brukt i den andre passeringen, ettersom de har tellere med høyere frekvens. Dette resulterer i dårlig ytelse. Andre vanlige scenarier eksisterer der NFU vil utføre på samme måte, for eksempel en OS-oppstart. Heldigvis eksisterer en lignende og bedre algoritme, og beskrivelsen følger.

Den ikke ofte brukte side-erstatningsalgoritmen genererer færre sidefeil enn den sidst brukte algoritmen for sidebytte når sidetabellen inneholder nullpekerverdier.

Aldring

Aldringsalgoritmen er en etterkommer av NFU -algoritmen, med modifikasjoner for å gjøre den oppmerksom på brukstiden. I stedet for å bare øke tellerne til sider det refereres til, og legge like stor vekt på sidereferanser uavhengig av tid, blir referansetelleren på en side først flyttet til høyre (delt med 2), før du legger den refererte biten til venstre for det binære tallet. For eksempel, hvis en side har referert til bitene 1,0,0,1,1,0 i de siste 6 klokkene, vil den refererte telleren se slik ut: 10000000, 01000000, 00100000, 10010000, 11001000, 01100100. Sidereferanser nærmere til nå har mer innvirkning enn sidereferanser for lenge siden. Dette sikrer at sider det refereres til mer nylig, men sjeldnere referert til, vil ha høyere prioritet enn sider som er referert hyppigere tidligere. Når en side må byttes ut, vil siden med den laveste telleren bli valgt.

Følgende Python -kode simulerer aldringsalgoritmen. Tellere initialiseres med${\ displaystyle V_ {i}}$0 og oppdatert som beskrevet ovenfor via , ved hjelp av aritmetiske skiftoperatører . ${\ displaystyle V_ {i} \ leftarrow (R_ {i} \ ll (k-1)) | (V_ {i} \ gg 1)}$

from collections.abc import Sequence

def simulate_aging(Rs: Sequence, k: int) -> None:
    """Simulate aging."""
    print(' t  |  R-bits (0-{length})        |  Counters for pages 0-{length}'.format(length=len(Rs)))
    Vs = [0] * len(Rs[0])
    for t, R in enumerate(Rs):
        Vs[:] = [R[i] << k - 1 | V >> 1
                 for i, V in enumerate(Vs)]
        print('{:02d}  |  {}  |  [{}]'.format(t, R,
                                              ', '.join(['{:0{}b}'.format(V, k)
                                                         for V in Vs])))

I det gitte eksemplet på R-bits for 6 sider over 5 klokkemerker, skriver funksjonen ut følgende utgang, som viser R-bitene for hver klokkekryss t og de individuelle tellerverdiene for hver side i binær representasjon. ${\ displaystyle V_ {i}}$

>>> Rs = [[1,0,1,0,1,1], [1,1,0,0,1,0], [1,1,0,1,0,1], [1,0,0,0,1,0], [0,1,1,0,0,0]]
>>> k = 8
>>> simulate_aging(Rs, k)
 t  |  R-bits (0-5)        |  Counters for pages 0-5
00  |  [1, 0, 1, 0, 1, 1]  |  [10000000, 00000000, 10000000, 00000000, 10000000, 10000000]
01  |  [1, 1, 0, 0, 1, 0]  |  [11000000, 10000000, 01000000, 00000000, 11000000, 01000000]
02  |  [1, 1, 0, 1, 0, 1]  |  [11100000, 11000000, 00100000, 10000000, 01100000, 10100000]
03  |  [1, 0, 0, 0, 1, 0]  |  [11110000, 01100000, 00010000, 01000000, 10110000, 01010000]
04  |  [0, 1, 1, 0, 0, 0]  |  [01111000, 10110000, 10001000, 00100000, 01011000, 00101000]

Vær oppmerksom på at aldring skiller seg fra LRU i den forstand at aldring bare kan holde orden på referansene i det siste 16/32 (avhengig av bitstørrelsen til prosessorens heltall) tidsintervaller. Følgelig kan to sider ha refererte tellere til 00000000, selv om en side ble referert for 9 intervaller siden og den andre for 1000 intervaller siden. Generelt er det tilstrekkelig å kjenne til bruken innen de siste 16 intervallene for å ta en god beslutning om hvilken side som skal byttes ut. Dermed kan aldring tilby nesten optimal ytelse til en moderat pris.

Lengste distanse først (LDF) side erstatningsalgoritme

Den grunnleggende ideen bak denne algoritmen er Referanselokalitet som brukt i LRU, men forskjellen er at i LDF er lokalitet basert på avstand, ikke på de brukte referansene. I LDF erstatter du siden som er på lengst avstand fra den gjeldende siden. Hvis to sider er på samme avstand, vil siden som er ved siden av gjeldende side i klokkerotasjon bli erstattet.

Gjennomføringsdetaljer

Teknikker for maskinvare uten referansebit

Mange av teknikkene som er diskutert ovenfor antar tilstedeværelsen av en referansebit som er knyttet til hver side. Noe maskinvare har ingen slik bit, så effektiv bruk krever teknikker som fungerer godt uten en.

Et bemerkelsesverdig eksempel er VAX -maskinvare som kjører OpenVMS . Dette systemet vet om en side er blitt endret, men ikke nødvendigvis om en side har blitt lest. Tilnærmingen er kjent som Secondary Page Caching. Sider fjernet fra arbeidssett (vanligvis prosess-privat minne) blir plassert på spesiallister mens de forblir i fysisk minne en stund. Å fjerne en side fra et arbeidssett er teknisk sett ikke en side-erstatningsoperasjon, men identifiserer siden effektivt som en kandidat. En side hvis støttelager fortsatt er gyldig (hvis innholdet ikke er skittent eller på annen måte ikke trenger å bevares) er plassert på halen på listen over gratis sider. En side som krever å skrive til en lagringsplass, blir plassert på den endrede sidelisten. Disse handlingene utløses vanligvis når størrelsen på gratis sideliste faller under en justerbar terskel.

Sider kan velges for fjerning av arbeidssett på en i hovedsak tilfeldig måte, med forventning om at hvis et dårlig valg blir gjort, kan en fremtidig referanse hente siden fra listen Gratis eller endret før den fjernes fra det fysiske minnet. En side som refereres til på denne måten, vil bli fjernet fra gratis eller endret liste og plassert tilbake i et prosessarbeidssett. Den endrede sidelisten gir i tillegg en mulighet til å skrive ut sider til en backing -butikk i grupper på mer enn én side, noe som øker effektiviteten. Disse sidene kan deretter plasseres på listen over gratis sider. Sekvensen av sider som går til hodet på gratis sideliste, ligner resultatene av en LRU- eller NRU-mekanisme, og den generelle effekten har likhet med Second-Chance-algoritmen beskrevet tidligere.

Et annet eksempel brukes av Linux -kjernen på ARM . Mangelen på maskinvarefunksjonalitet blir gjort opp ved å tilby to sidetabeller-prosessor-native sidetabeller, med verken refererte biter eller skitne biter , og programvare-vedlikeholdte sidetabeller med de nødvendige bitene til stede. De emulerte bitene i tabellen som vedlikeholdes av programvaren, angis av sidefeil. For å få sidefeil, tilbakekall sletting av emulerte biter i den andre tabellen, noen av tilgangsrettighetene til den tilsvarende siden, som implementeres ved å endre den opprinnelige tabellen.

Sidebuffer i Linux

Linux bruker en enhetlig sidebuffer for

• brkog anonym mmaped -regions. Dette inkluderer den haug og stabelen av bruker plass programmer. Det er skrevet for å bytte når det skrives ut.
• Ikke-anonyme (filstøttede) mmaped-områder. Hvis den finnes i minnet og ikke er privat endret, deles den fysiske siden med filbuffer eller buffer.
• Delt minne ervervet gjennom shm_open.
• De tmpfs i minnet filsystem; skrevet for å bytte når den slås ut.
• Filbufferen inkluderer; skrevet til den underliggende blokklagringen (muligens å gå gjennom bufferen, se nedenfor) når den skrives ut.
• Cachen til blokkenheter , kalt "buffer" av Linux (for ikke å forveksle med andre strukturer som også kalles buffere som de som brukes for rør og buffere som brukes internt i Linux); skrevet til den underliggende lagringen når den er slått ut.

Den enhetlige sidebufferen opererer på enheter med den minste sidestørrelsen som støttes av CPU (4 KiB i ARMv8 , x86 og x86-64 ) med noen sider av den neste større størrelsen (2 MiB i x86-64 ) kalt "enorme sider" av Linux. Sidene i sidebufferen er delt inn i et "aktivt" sett og et "inaktivt" sett. Begge settene holder en LRU -liste over sider. I det grunnleggende tilfellet, når en side får tilgang til et brukerromsprogram, settes den i hodet på det inaktive settet. Når den åpnes flere ganger, flyttes den til den aktive listen. Linux flytter sidene fra det aktive settet til det inaktive settet etter behov, slik at det aktive settet er mindre enn det inaktive settet. Når en side flyttes til det inaktive settet, blir den fjernet fra sidetabellen for ethvert prosessadresserom, uten å bli fjernet fra det fysiske minnet. Når en side fjernes fra det inaktive settet, blir den fjernet fra det fysiske minnet. Størrelsen på listen "aktiv" og "inaktiv" kan søkes /proc/meminfoi feltene "Aktiv", "Inaktiv", "Aktiv (anon)", "Inaktiv (anon)", "Aktiv (fil)" og "Inaktiv (fil)".

Arbeidssett

Arbeidssettet for en prosess er settet med sider som forventes å bli brukt av denne prosessen i løpet av et tidsintervall.

"Arbeidssettmodellen" er ikke en sideutskiftningsalgoritme i streng forstand (det er faktisk en slags mellomtidsplanlegger )

Referanser

Videre lesning