Algoritm de înlocuire a paginii - Page replacement algorithm

Într-un sistem de operare al computerului care folosește paginarea pentru gestionarea memoriei virtuale , algoritmii de înlocuire a paginilor decid ce pagini de memorie să se afle, uneori numite swap out sau să scrie pe disc, atunci când o pagină de memorie trebuie alocată. Înlocuirea paginii se întâmplă atunci când o pagină solicitată nu se află în memorie ( eroare de pagină ) și o pagină gratuită nu poate fi utilizată pentru a satisface alocarea, fie pentru că nu există, fie pentru că numărul de pagini gratuite este mai mic decât un anumit prag.

Când pagina care a fost selectată pentru înlocuire și paginată este referită din nou, aceasta trebuie paginată (citită de pe disc), iar aceasta implică așteptarea finalizării I / O. Aceasta determină calitatea algoritmului de înlocuire a paginii: cu cât este mai puțin timp să așteptați pagina-ins, cu atât algoritmul este mai bun. Un algoritm de înlocuire a paginii analizează informațiile limitate despre accesul la paginile furnizate de hardware și încearcă să ghicească ce pagini ar trebui înlocuite pentru a minimiza numărul total de pagini pierdute, echilibrând în același timp costurile (stocarea primară și timpul procesorului) de algoritmul în sine.

Problema de înlocuire a paginii este o problemă tipică online din perspectiva analizei competitive, în sensul că algoritmul determinist optim este cunoscut.

Istorie

Algoritmii de înlocuire a paginilor au fost un subiect fierbinte de cercetare și dezbatere în anii 1960 și 1970. Acest lucru sa încheiat în principal cu dezvoltarea unor aproximări sofisticate LRU (cel mai puțin utilizate recent) și a unor algoritmi de lucru . De atunci, unele ipoteze de bază făcute de algoritmii tradiționali de înlocuire a paginii au fost invalidate, rezultând o revigorare a cercetării. În special, următoarele tendințe în comportamentul hardware-ului subiacent și a software-ului la nivel de utilizator au afectat performanța algoritmilor de înlocuire a paginilor:

• Dimensiunea stocării primare a crescut cu mai multe ordine de mărime. Cu mai mulți gigaocteți de memorie primară, algoritmii care necesită o verificare periodică a fiecărui cadru de memorie devin din ce în ce mai puțin practice.
• Ierarhiile memoriei au crescut. Costul unei pierderi de memorie cache a procesorului este mult mai scump. Acest lucru agravează problema anterioară.
• Localitatea de referință a software-ului utilizatorului a slăbit. Acest lucru este atribuit în mare parte răspândirii tehnicilor de programare orientate pe obiecte care favorizează un număr mare de funcții mici, utilizării structurilor de date sofisticate cum ar fi copacii și tabelele hash care tind să conducă la modele de referință haotice ale memoriei și apariția colectării gunoiului care s-a schimbat drastic. comportamentul accesului la memorie al aplicațiilor.

Cerințele pentru algoritmii de înlocuire a paginii s-au schimbat din cauza diferențelor în arhitecturile nucleului sistemului de operare . În special, majoritatea nucleelor ​​de sisteme de operare moderne au memorie virtuală unificată și cache de sistem de fișiere, necesitând algoritmul de înlocuire a paginii pentru a selecta o pagină dintre paginile ambelor spații de adrese virtuale ale programului de utilizator și ale fișierelor cache. Ultimele pagini au proprietăți specifice. De exemplu, pot fi blocate sau pot avea cerințe de ordonare la scriere impuse de jurnalizare . Mai mult, întrucât scopul înlocuirii paginii este de a minimiza timpul total de așteptare a memoriei, trebuie să țină cont de cerințele de memorie impuse de alte subsisteme ale nucleului care alocă memorie. Ca urmare, înlocuirea paginilor în nucleele moderne ( Linux , FreeBSD și Solaris ) tinde să funcționeze la nivelul unui alocator de memorie nucleu de uz general, mai degrabă decât la nivelul superior al unui subsistem de memorie virtuală.

Înlocuire locală vs. globală

Algoritmii de înlocuire pot fi locali sau globali.

Când un proces are un defect de pagină, un algoritm local de înlocuire a paginii selectează pentru înlocuirea unei pagini care aparține aceluiași proces (sau unui grup de procese care partajează o partiție de memorie ). Un algoritm global de înlocuire este liber să selecteze orice pagină din memorie.

Înlocuirea locală a paginii presupune o anumită formă de partiționare a memoriei care determină câte pagini trebuie alocate unui anumit proces sau unui grup de procese. Cele mai populare forme de partiționare sunt partiționarea fixă și algoritmii de seturi echilibrate bazate pe modelul setului de lucru . Avantajul înlocuirii paginii locale este scalabilitatea sa: fiecare proces își poate gestiona erorile de pagină independent, ducând la performanțe mai consistente pentru acel proces. Cu toate acestea, înlocuirea globală a paginilor este mai eficientă pe baza sistemului general.

Detectarea paginilor la care se face referință și se modifică

Calculatoarele moderne de uz general și unele procesoare încorporate au suport pentru memoria virtuală . Fiecare proces are propriul spațiu virtual de adrese. Un tabel de pagini mapează un subset de adrese virtuale de proces la adrese fizice. În plus, în majoritatea arhitecturilor, tabelul de pagini conține un bit de „acces” și un bit „murdar” pentru fiecare pagină din tabelul de pagini. CPU-ul setează bitul de acces atunci când procesul citește sau scrie memorie în pagina respectivă. CPU setează bitul murdar atunci când procesul scrie memorie în pagina respectivă. Sistemul de operare poate modifica accesul și biții murdari. Sistemul de operare poate detecta accesul la memorie și fișiere prin următoarele mijloace:

• Ștergând bitul de acces din paginile prezente în tabelul de pagini al procesului. După ceva timp, sistemul de operare scanează tabelul de pagini, căutând pagini care aveau bitul de acces setat de CPU. Acest lucru este rapid, deoarece bitul de acces setat automat de CPU și este inexact, deoarece sistemul de operare nu primește imediat o notificare a accesului și nici nu are informații despre ordinea în care procesul a accesat aceste pagini.
• Eliminând paginile din tabelul de pagini al procesului fără a le elimina neapărat din memoria fizică. Următorul acces la pagina respectivă este detectat imediat, deoarece provoacă o eroare a paginii . Acest lucru este lent, deoarece o eroare de pagină implică un comutator contextual către sistemul de operare, căutarea software-ului pentru adresa fizică corespunzătoare, modificarea tabelului de pagini și un comutator contextual înapoi la proces și precis, deoarece accesul este detectat imediat după ce acesta are loc.
• Direct când procesul efectuează apeluri de sistem care pot accesa memoria cache a paginii ca readși writeîn POSIX.

Curățarea prealabilă

Majoritatea algoritmilor de înlocuire returnează pur și simplu pagina țintă ca rezultat. Aceasta înseamnă că, dacă pagina țintă este murdară (adică conține date care trebuie scrise în spațiul de stocare stabil înainte ca pagina să poată fi recuperată), I / O trebuie inițiată pentru a trimite acea pagină în spațiul de stocare stabil (pentru a curăța pagina ). În primele zile ale memoriei virtuale, timpul petrecut pentru curățare nu a fost prea îngrijorător, deoarece memoria virtuală a fost implementată mai întâi pe sistemele cu canale duplex complete către stocarea stabilă, iar curățarea era de obicei suprapusă cu paginarea. Hardware-ul de marfă contemporan, pe de altă parte, nu acceptă transferurile full duplex, iar curățarea paginilor țintă devine o problemă.

Pentru a face față acestei situații, sunt implementate diverse politici de curățare . Curățarea prealabilă este mecanismul care pornește I / O pe paginile murdare care (probabil) vor fi înlocuite în curând. Ideea este că până la selectarea efectivă a paginii precurățate pentru înlocuire, I / O se va finaliza și pagina va fi curată. Curățarea presupune că este posibil să se identifice paginile care vor fi înlocuite în continuare . Curățarea prea dornică poate pierde lățimea de bandă I / O scriind pagini care reușesc să fie re-murdărite înainte de a fi selectate pentru înlocuire.

Paginare anticipativă

Unele sisteme utilizează cererea de paginare - așteaptă până când o pagină este cerută efectiv înainte de a o încărca în RAM.

Alte sisteme încearcă să reducă latența ghicind ce pagini care nu sunt în RAM sunt susceptibile de a fi necesare în curând și preîncărcând astfel de pagini în RAM, înainte ca pagina respectivă să fie solicitată. (Acest lucru este adesea în combinație cu pre-curățarea, care ghicește ce pagini în prezent în RAM nu este probabil să fie necesare în curând și pre-scrierea lor în memoria de stocare).

Când apare o defecțiune a paginii, sistemele de „paginare anticipativă” nu vor aduce doar pagina de referință, ci și următoarele câteva pagini consecutive (analog cu o coadă de intrare pre-preluată într-un procesor).

De swap preaducere Mecanismul merge chiar mai departe în paginile de încărcare (chiar dacă acestea nu sunt consecutive) , care sunt susceptibile de a fi necesare în curând.

Problema de paginare (h, k)

Problema de paginare (h, k) este o generalizare a modelului problemei de paginare: Fie h, k numere întregi pozitive astfel încât . Măsurăm performanța unui algoritm cu cache de dimensiune în raport cu algoritmul teoretic optim de înlocuire a paginii . Dacă , furnizăm algoritmul optim de înlocuire a paginii cu resurse strict mai puține. ${\ displaystyle h \ leq k}$${\ displaystyle h \ leq k}$${\ displaystyle h <k}$

Problema de paginare (h, k) este o modalitate de a măsura cum funcționează un algoritm online comparându-l cu performanța algoritmului optim, în mod specific, parametrizând separat dimensiunea cache a algoritmului online și algoritmul optim.

Algoritmi de marcare

Algoritmii de marcare este o clasă generală de algoritmi de paginare. Pentru fiecare pagină, o asociem cu un bit numit marca ei. Initial, setam toate paginile ca nemarcate. În timpul unei etape de solicitări de pagină, marcăm o pagină când este solicitată prima dată în această etapă. Un algoritm de marcare este un astfel de algoritm care nu afișează niciodată o pagină marcată.

Dacă ALG este un algoritm de marcare cu un cache de dimensiunea k, iar OPT este algoritmul optim cu un cache de dimensiunea h, unde , atunci ALG este -competitiv. Deci, fiecare algoritm de marcare atinge raportul -competitiv. ${\ displaystyle h \ leq k}$${\ displaystyle {\ tfrac {k} {k-h + 1}}}$${\ displaystyle {\ tfrac {k} {k-h + 1}}}$

LRU este un algoritm de marcare, în timp ce FIFO nu este un algoritm de marcare.

Algoritmi conservatori

Un algoritm este conservator, dacă în orice secvență de cereri consecutive care conține k sau mai puține referințe de pagină distincte, algoritmul va suporta k sau mai puține erori de pagină.

Dacă ALG este un algoritm conservator cu un cache de dimensiunea k, iar OPT este algoritmul optim cu un cache de , atunci ALG este -competitiv. Deci, fiecare algoritm conservator atinge raportul -competitiv. ${\ displaystyle h \ leq k}$${\ displaystyle {\ tfrac {k} {k-h + 1}}}$${\ displaystyle {\ tfrac {k} {k-h + 1}}}$

LRU, FIFO și CLOCK sunt algoritmi conservatori.

Algoritmi de înlocuire a paginii

Există o varietate de algoritmi de înlocuire a paginilor:

Algoritmul teoretic optim de înlocuire a paginii

Algoritmul teoretic optim de înlocuire a paginii (cunoscut și ca OPT, algoritmul de înlocuire clarvăzător sau politica optimă de înlocuire a paginii lui Bélády ) este un algoritm care funcționează după cum urmează: atunci când o pagină trebuie schimbată, sistemul de operare schimbă pagina a cărei utilizare următoare va apărea cel mai îndepărtat în viitor. De exemplu, o pagină care nu va fi utilizată în următoarele 6 secunde va fi schimbată pe o pagină care va fi utilizată în următoarele 0,4 secunde.

Acest algoritm nu poate fi implementat într-un sistem de operare de uz general, deoarece este imposibil de calculat în mod fiabil cât va dura înainte ca o pagină să fie utilizată, cu excepția cazului în care toate software-urile care vor rula pe un sistem sunt fie cunoscute în prealabil și sunt supuse analiza statică a modelelor sale de referință de memorie sau doar o clasă de aplicații care permite analiza în timp de execuție. În ciuda acestei limitări, există algoritmi care pot oferi o performanță aproape optimă - sistemul de operare ține evidența tuturor paginilor la care face referire programul și folosește acele date pentru a decide ce pagini să schimbe și să iasă în cursele următoare. Acest algoritm poate oferi o performanță aproape optimă, dar nu la prima rulare a unui program și numai dacă modelul de referință al memoriei programului este relativ consistent de fiecare dată când rulează.

Analiza problemei de paginare a fost făcută și în domeniul algoritmilor online . Eficiența algoritmilor online randomizați pentru problema paginării este măsurată utilizând analize amortizate .

Nu a fost folosit recent

Algoritmul de înlocuire a paginii nu recent utilizat (NRU) este un algoritm care favorizează păstrarea paginilor în memorie care au fost utilizate recent. Acest algoritm funcționează pe următorul principiu: atunci când se face referință la o pagină, este setat un bit de referință pentru acea pagină, marcându-l ca referință. În mod similar, atunci când o pagină este modificată (scrisă în), este setat un bit modificat. Setarea biților se face de obicei de către hardware, deși este posibil să se facă și la nivel de software.

La un anumit interval de timp fix, o întrerupere a temporizatorului declanșează și șterge bitul la care se face referire pentru toate paginile, astfel încât numai paginile la care se face referire în intervalul curent al temporizatorului sunt marcate cu un bit la care se face referire. Când o pagină trebuie înlocuită, sistemul de operare împarte paginile în patru clase:

3. referențiat, modificat

2. referențiat, nemodificat

1. fără referință, modificat

0. fără referință, fără modificări

Deși nu pare posibil ca o pagină să fie modificată, dar fără referință, acest lucru se întâmplă atunci când o pagină de clasa 3 are bitul de referință șters de întreruperea temporizatorului. Algoritmul NRU alege o pagină aleatorie din cea mai mică categorie pentru eliminare. Deci, din cele patru categorii de pagini de mai sus, algoritmul NRU va înlocui o pagină fără referință și fără modificări, dacă există o astfel de pagină. Rețineți că acest algoritm implică faptul că o pagină modificată, dar fără referință (în ultimul interval de timp) este mai puțin importantă decât o pagină nemodificată care este intens referențiată.

NRU este un algoritm de marcare, deci este -competitiv. ${\ displaystyle {\ tfrac {k} {k-h + 1}}}$

First-in, first-out

Cel mai simplu algoritm de înlocuire a paginii este un algoritm FIFO. Primul algoritm de înlocuire a paginii de intrare, de ieșire (FIFO) este un algoritm low-overhead care necesită o contabilitate redusă din partea sistemului de operare . Ideea este evidentă din nume - sistemul de operare ține evidența tuturor paginilor din memorie într-o coadă, cu cea mai recentă sosire din spate și cea mai veche sosire din față. Când o pagină trebuie înlocuită, este selectată pagina din partea din față a cozii (cea mai veche pagină). În timp ce FIFO este ieftin și intuitiv, funcționează slab în aplicații practice. Astfel, este rar folosit în forma sa nemodificată. Acest algoritm experimentează anomalia lui Bélády . În cuvinte simple, la o eroare de pagină, cadrul care a fost cel mai mult în memorie este înlocuit.

Algoritmul de înlocuire a paginii FIFO este utilizat de sistemul de operare VAX / VMS , cu unele modificări. A doua șansă parțială este oferită prin omiterea unui număr limitat de intrări cu referințe valide de tabel de traducere și, în plus, paginile sunt deplasate din setul de lucru al procesului către un pool la nivel de sistem din care pot fi recuperate dacă nu sunt deja refolosite.

FIFO este un algoritm conservator, deci este -competitiv. ${\ displaystyle {\ tfrac {k} {k-h + 1}}}$

A doua șansă

O formă modificată a algoritmului de înlocuire a paginii FIFO, cunoscut sub numele de algoritmul de înlocuire a paginii cu a doua șansă, este relativ mai bună decât FIFO cu un cost mic pentru îmbunătățire. Funcționează uitându-se la partea din față a cozii așa cum o face FIFO, dar în loc să pagineze imediat acea pagină, verifică dacă bitul său de referință este setat. Dacă nu este setată, pagina este schimbată. În caz contrar, bitul de referință este șters, pagina este inserată în spatele cozii (ca și cum ar fi o pagină nouă) și acest proces se repetă. Acest lucru poate fi, de asemenea, gândit ca o coadă circulară. Dacă toate paginile au bitul de referință setat, la a doua întâlnire a primei pagini din listă, acea pagină va fi schimbată, deoarece are acum bitul de referință șters. Dacă toate paginile au bitul de referință șters, atunci algoritmul de a doua șansă degenerează în FIFO pur.

După cum sugerează și numele, Second-chance oferă fiecărei pagini o „a doua șansă” - o pagină veche la care s-a făcut referire este probabil utilizată și nu ar trebui schimbată pe o pagină nouă care nu a fost făcută referință.

Ceas

Ceasul este o versiune mai eficientă a FIFO decât a doua șansă, deoarece paginile nu trebuie împinse în mod constant în spatele listei, dar îndeplinește aceeași funcție generală ca a doua șansă. Algoritmul ceasului păstrează o listă circulară de pagini în memorie, cu „mâna” (iterator) îndreptată către ultimul cadru de pagină examinat din listă. Când apare o eroare de pagină și nu există cadre goale, atunci bitul R (la care se face referire) este inspectat la locația mâinii. Dacă R este 0, noua pagină este plasată în locul paginii către care indică „mâna”, iar mâna este avansată cu o poziție. În caz contrar, bitul R este șters, apoi mâna ceasului este incrementată și procesul se repetă până când o pagină este înlocuită. Acest algoritm a fost descris pentru prima dată în 1969 de FJ Corbató .

Variante de ceas

• GCLOCK: algoritm de înlocuire a paginii de ceas generalizat.
• Clock-Pro păstrează o listă circulară de informații despre paginile cu referință recentă, inclusiv toate paginile M din memorie, precum și cele mai recente pagini M care au fost paginate. Aceste informații suplimentare pe paginile paginate, cum ar fi informațiile similare întreținute de ARC , îl ajută să funcționeze mai bine decât LRU pe bucle mari și scanări unice.
• WSclock. Prin combinarea algoritmului Clock cu conceptul unui set de lucru (adică, setul de pagini care se așteaptă să fie utilizat de acel proces pe parcursul unui anumit interval de timp), performanța algoritmului poate fi îmbunătățită. În practică, algoritmul „îmbătrânire” și algoritmul „WSClock” sunt probabil cei mai importanți algoritmi de înlocuire a paginilor.
• Ceasul cu înlocuire adaptivă (CAR) este un algoritm de înlocuire a paginilor care are o performanță comparabilă cu ARC și care depășește substanțial atât LRU, cât și CLOCK. Algoritmul CAR se auto-reglează și nu necesită parametri magici specificați de utilizator.

CLOCK este un algoritm conservator, deci este -competitiv. ${\ displaystyle {\ tfrac {k} {k-h + 1}}}$

Cel puțin folosit recent

Algoritmul de înlocuire a paginii cel mai recent utilizat (LRU), deși similar ca nume cu NRU, diferă prin faptul că LRU ține evidența utilizării paginii într-o perioadă scurtă de timp, în timp ce NRU doar privește utilizarea în ultimul interval de ceas. LRU lucrează la ideea că paginile care au fost cele mai utilizate în ultimele instrucțiuni sunt cel mai probabil utilizate și în următoarele instrucțiuni. În timp ce LRU poate oferi o performanță aproape optimă în teorie (aproape la fel de bună ca memoria cache de înlocuire adaptivă ), este destul de costisitoare de implementat în practică. Există câteva metode de implementare pentru acest algoritm care încearcă să reducă costul, dar păstrează cât mai mult din performanță posibil.

Cea mai scumpă metodă este metoda listei legate, care folosește o listă legată care conține toate paginile din memorie. În spatele acestei liste se află cea mai recent utilizată pagină, iar în partea din față este cea mai recent utilizată pagină. Costul acestei implementări constă în faptul că articolele din listă vor trebui mutate în fiecare referință de memorie, care este un proces care necesită mult timp.

O altă metodă care necesită suport hardware este următoarea: să presupunem că hardware-ul are un contor pe 64 de biți care este incrementat la fiecare instrucțiune. Ori de câte ori este accesată o pagină, aceasta dobândește valoarea egală cu contorul în momentul accesării paginii. Ori de câte ori trebuie înlocuită o pagină, sistemul de operare selectează pagina cu cel mai mic contor și o schimbă.

Din cauza costurilor de implementare, se pot lua în considerare algoritmi (precum cei care urmează) care sunt similari cu LRU, dar care oferă implementări mai ieftine.

Un avantaj important al algoritmului LRU este că este supus unei analize statistice complete. S-a dovedit, de exemplu, că LRU nu poate avea niciodată mai multe defecte de N-ori decât algoritmul OPT, unde N este proporțional cu numărul de pagini din pool-ul gestionat.

Pe de altă parte, slăbiciunea LRU este că performanța sa tinde să degenereze sub multe tipare de referință destul de comune. De exemplu, dacă există N pagini în grupul LRU, o aplicație care execută o buclă peste matrice de N + 1 pagini va provoca o eroare de pagină la fiecare acces. Deoarece buclele peste matrice mari sunt comune, s-a depus mult efort în modificarea LRU pentru a funcționa mai bine în astfel de situații. Multe dintre modificările LRU propuse încearcă să detecteze modelele de referință în buclă și să treacă la algoritmul de înlocuire adecvat, cum ar fi Most Recent Used (MRU).

Variante pe LRU

1. LRU-K evacuează pagina al cărei acces K-th cel mai recent este cel mai îndepărtat în trecut. De exemplu, LRU-1 este pur și simplu LRU, în timp ce LRU-2 evacuează paginile în funcție de momentul penultimului lor acces. LRU-K se îmbunătățește foarte mult cu LRU în ceea ce privește localitatea în timp.
2. ARC Algoritmul se extinde LRU prin menținerea unei istorii de pagini recent evacuate și folosește această preferinței schimbare de acces recent sau frecvent. Este deosebit de rezistent la scanările secvențiale.

O comparație a ARC cu alți algoritmi (LRU, MQ, 2Q, LRU-2, LRFU, LIRS ) poate fi găsită în Megiddo & Modha 2004.

LRU este un algoritm de marcare, deci este -competitiv. ${\ displaystyle {\ tfrac {k} {k-h + 1}}}$

Aleatoriu

Algoritmul de înlocuire aleatorie înlocuiește o pagină aleatorie din memorie. Aceasta elimină costurile generale ale urmăririi referințelor la pagină. De obicei, se descurcă mai bine decât FIFO, iar pentru referințele de memorie în buclă este mai bun decât LRU, deși, în general, LRU funcționează mai bine în practică. OS / 390 utilizează aproximarea globală LRU și revine la înlocuirea aleatorie atunci când performanța LRU degenerează, iar procesorul Intel i860 a folosit o politică de înlocuire aleatorie (Rhodehamel 1989).

Nu se utilizează frecvent (NFU)

Algoritmul de înlocuire a paginilor care nu este utilizat frecvent (NFU) necesită un contor și fiecare pagină are un contor propriu, care este setat inițial la 0. La fiecare interval de ceas, toate paginile care au fost referite în intervalul respectiv vor avea contorul crescut cu 1. De fapt, contoare țin evidența frecvenței utilizării unei pagini. Astfel, pagina cu cel mai mic contor poate fi schimbată atunci când este necesar.

Principala problemă cu NFU este că ține evidența frecvenței de utilizare, indiferent de intervalul de timp de utilizare. Astfel, într-un compilator cu mai multe treceri, paginile care au fost puternic utilizate în timpul primei treceri, dar care nu sunt necesare în cea de-a doua trecere vor fi favorizate față de paginile care sunt comparabil ușor utilizate în a doua trecere, deoarece au contoare de frecvență mai mari. Acest lucru are ca rezultat performanțe slabe. Există și alte scenarii comune în care NFU va funcționa în mod similar, cum ar fi un boot-up al sistemului de operare. Din fericire, există un algoritm similar și mai bun, iar descrierea acestuia urmează.

Algoritmul de înlocuire a paginii care nu este utilizat frecvent generează mai puține erori de pagină decât algoritmul de înlocuire a paginii cel mai recent utilizat atunci când tabelul de pagini conține valori nule ale indicatorului.

Îmbătrânire

Algoritmul de îmbătrânire este un descendent al algoritmului NFU, cu modificări pentru a-l face conștient de intervalul de timp de utilizare. În loc de a crește doar contoare de pagini la care se face referire, punând accent egal pe referințele de pagină indiferent de timp, contorul de referință de pe o pagină este mai întâi deplasat la dreapta (împărțit la 2), înainte de a adăuga bitul de referință la stânga acelui număr binar. De exemplu, dacă o pagină are biți de referință 1,0,0,1,1,0 în ultimele 6 bifuri de ceas, contorul de referință va arăta astfel: 10000000, 01000000, 00100000, 10010000, 11001000, 01100100. până în prezent au un impact mai mare decât referințele de pagină de demult. Acest lucru asigură faptul că paginile la care se face referire mai recent, deși mai puțin frecvent menționate, vor avea prioritate mai mare față de paginile la care se face referință mai frecvent în trecut. Astfel, atunci când o pagină trebuie schimbată, va fi aleasă pagina cu cel mai mic contor.

Următorul cod Python simulează algoritmul de îmbătrânire. Contoare sunt inițializate cu${\ displaystyle V_ {i}}$0 și actualizat așa cum este descris mai sus prin , utilizând operatori de schimbare aritmetică . ${\ 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])))

În exemplul dat de biți R pentru 6 pagini peste 5 bifuri de ceas, funcția imprimă următoarea ieșire, care listează biții R pentru fiecare bifă de ceas t și valorile contorului individual pentru fiecare pagină în reprezentare binară . ${\ 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]

Rețineți că îmbătrânirea diferă de LRU în sensul că îmbătrânirea poate ține evidența referințelor doar în cele mai recente 16/32 (în funcție de dimensiunea de biți a numărului întreg al procesorului) intervale de timp. În consecință, este posibil ca două pagini să fi făcut referință la contoare de 00000000, chiar dacă o pagină a fost trimisă cu 9 intervale în urmă și cealaltă cu 1000 de intervale în urmă. În general vorbind, cunoașterea utilizării în ultimele 16 intervale este suficientă pentru a lua o decizie bună cu privire la ce pagină să se schimbe. Astfel, îmbătrânirea poate oferi performanțe aproape optime la un preț moderat.

Algoritmul de înlocuire a paginii cu cea mai mare distanță (LDF) page

Ideea de bază din spatele acestui algoritm este Localitatea de referință utilizată în LRU, dar diferența este că în LDF, localitatea se bazează pe distanță nu pe referințele utilizate. În LDF, înlocuiți pagina care se află pe cea mai mare distanță de pagina curentă. Dacă două pagini sunt la aceeași distanță, atunci pagina care este lângă pagina curentă în rotație anti-ceas va fi înlocuită.

Detalii de implementare

Tehnici pentru hardware fără bit de referință

Multe dintre tehnicile discutate mai sus presupun prezența unui bit de referință asociat fiecărei pagini. Unele hardware nu au un astfel de bit, astfel încât utilizarea sa eficientă necesită tehnici care funcționează bine fără unul.

Un exemplu remarcabil este hardware-ul VAX care rulează OpenVMS . Acest sistem știe dacă o pagină a fost modificată, dar nu neapărat dacă a fost citită o pagină. Abordarea sa este cunoscută sub numele de cache de pagină secundară. Paginile eliminate din seturile de lucru (memoria proces-privat, în general) sunt plasate pe liste cu destinație specială, în timp ce rămân în memoria fizică pentru o perioadă de timp. Eliminarea unei pagini dintr-un set de lucru nu este tehnic o operațiune de înlocuire a paginii, ci identifică în mod eficient acea pagină ca fiind un candidat. O pagină al cărei magazin de rezervă este încă valabil (al cărui conținut nu este murdar sau altfel nu trebuie păstrat) este plasat pe coada listei de pagini gratuite. O pagină care necesită scriere în magazinul de rezervă va fi plasată pe lista de pagini modificate. Aceste acțiuni sunt de obicei declanșate atunci când dimensiunea listei de pagini gratuite scade sub un prag reglabil.

Paginile pot fi selectate pentru eliminarea setului de lucru într-un mod esențial aleatoriu, cu așteptarea că, dacă se face o alegere slabă, o referință viitoare poate prelua acea pagină din lista Gratuită sau Modificată înainte de a fi scoasă din memoria fizică. O pagină la care se face referire în acest fel va fi eliminată din lista Gratuită sau Modificată și plasată din nou într-un set de lucru de proces. Lista de pagini modificate oferă în plus o oportunitate de a scrie pagini în magazinul de rezervă în grupuri de mai multe pagini, sporind eficiența. Aceste pagini pot fi apoi plasate pe Lista de pagini gratuite. Secvența de pagini care merge spre capul listei de pagini gratuite seamănă cu rezultatele unui mecanism LRU sau NRU, iar efectul general are similitudini cu algoritmul de a doua șansă descris anterior.

Un alt exemplu este folosit de kernel-ul Linux pe ARM . Lipsa funcționalității hardware este compensată prin furnizarea de tabele de două pagini - tabelele de pagini native pentru procesor, fără biți de referință și nici biți murdari , și tabele de pagini întreținute de software cu biții necesari prezenți. Biții emulați în tabelul gestionat de software sunt setați prin defecțiuni de pagină. Pentru a obține defecțiunile paginii, ștergerea biților emulați în al doilea tabel revocă unele dintre drepturile de acces la pagina corespunzătoare, care este implementată prin modificarea tabelului nativ.

Memoria cache a paginii în Linux

Linux utilizează un cache de pagină unificat pentru

• brkși mmaped -regiuni anonime . Aceasta include grămada și stiva de programe spațiu utilizator . Este scris pentru a schimba când este afișat.
• mmapRegiuni ed non-anonime (susținute de fișiere) . Dacă este prezentă în memorie și nu este modificată în mod privat, pagina fizică este partajată cu memoria cache sau cu bufferul de fișiere.
• Memorie partajată dobândită prin shm_open.
• Sistemul de fișiere în memorie tmpfs ; scris pentru a schimba când este paginat.
• Memoria cache a fișierelor, inclusiv; scrise în stocarea blocului de bază (eventual trecând prin buffer, vezi mai jos) când sunt paginate.
• Cache-ul dispozitivelor de bloc , denumit „buffer” de Linux (nu trebuie confundat cu alte structuri numite și tampoane precum cele utilizate pentru țevi și tampoane utilizate intern în Linux); scrise în spațiul de stocare subiacent când sunt paginate.

Memoria cache de pagină unificată funcționează pe unități cu cea mai mică dimensiune de pagină acceptată de CPU (4 KiB în ARMv8 , x86 și x86-64 ), cu unele pagini de următoarea dimensiune mai mare (2 MiB în x86-64 ) numite „pagini uriașe” de Linux. Paginile din memoria cache a paginilor sunt împărțite într-un set „activ” și un set „inactiv”. Ambele seturi păstrează o listă de pagini LRU. În cazul de bază, atunci când o pagină este accesată de un program de spațiu utilizator, aceasta este plasată în capul setului inactiv. Când este accesat în mod repetat, este mutat pe lista activă. Linux mută paginile din setul activ în setul inactiv, după cum este necesar, astfel încât setul activ să fie mai mic decât setul inactiv. Când o pagină este mutată în setul inactiv, aceasta este eliminată din tabelul de pagini al oricărui spațiu de adrese de proces, fără a fi paginat din memoria fizică. Când o pagină este eliminată din setul inactiv, aceasta este paginată din memoria fizică. Dimensiunea listei „activ” și „inactiv” poate fi interogată din /proc/meminfocâmpurile „Activ”, „Inactiv”, „Activ (anon)”, „Inactiv (anon)”, „Activ (fișier)” și „Inactiv” (fişier)".

Set de lucru

Setul de lucru al unui proces este setul de pagini care se așteaptă să fie utilizat de acel proces într-un anumit interval de timp.

„Modelul setului de lucru” nu este un algoritm de înlocuire a paginii în sens strict (este de fapt un fel de programator pe termen mediu )

Referințe

Lecturi suplimentare