Departament d'Arquitectura de Computadors (DAC)
Universitat Politècnica de Catalunya (UPC)

Tema 8: Memòria virtual

8.1 Introducció

8.1.1 El problema: reubicació i mida limitada

Quan es compila i s’enllaça un programa, l’enllaçador assigna adreces de memòria a les instruccions i les dades. Però en un computador modern s’executen múltiples programes simultàniament, tots compartint la mateixa memòria física. Això planteja dos problemes fonamentals:

• Reubicació. Si dos programes han estat compilats per ocupar les mateixes adreces, no poden coexistir a la memòria sense que les seves dades i instruccions col·lideixin. Cal un mecanisme que permeti que cada programa cregui que ocupa les adreces que se li han assignat en compilar-lo, però que en realitat estigui ubicat en una zona diferent de la memòria física.
• Mida limitada. El conjunt d’instruccions i dades de tots els programes en execució pot superar fàcilment la capacitat de la memòria física. Sense cap mecanisme addicional, això impossibilitaria l’execució de certs programes o combinacions de programes.

La solució a tots dos problemes és la memòria virtual.

8.1.2 Espais d’adreçament lògic i físic

La memòria virtual es fonamenta en la distinció entre dos espais d’adreçament independents.

• L’espai d’adreçament lògic (o virtual) és el conjunt d’adreces que utilitza un programa: tant en temps de compilació com en temps d’execució, la CPU treballa exclusivament amb adreces lògiques. Cada procés té el seu propi espai d’adreçament lògic, independent del dels altres, amb una mida màxima determinada pel nombre de bits d’adreça del processador (per exemple, \(2^{32}\) bytes = 4 GiB en un sistema de 32 bits; vegeu Essencial 2.5 per a la notació). Això proporciona a cada procés la il·lusió de disposar de tota la memòria per a ell sol.
• L’espai d’adreçament físic és el conjunt d’adreces de la memòria física real. La seva mida depèn de la quantitat de RAM instal·lada al sistema, i és totalment independent de l’espai d’adreçament lògic.
• La unitat de gestió de memòria (memory management unit, MMU) és el component de maquinari responsable de traduir, en temps d’execució, cada adreça lògica generada per la CPU en l’adreça física corresponent. Gràcies a aquesta traducció transparent, els programes no necessiten conèixer la seva ubicació real a la memòria física.

La Figura 8.1 il·lustra aquests tres elements amb dos processos.

Figura 8.1: Cada procés disposa d’un espai d’adreçament lògic propi i independent, de 0x00000000 a 0xFFFFFFFF, del qual només fa servir unes quantes pàgines (Secció 8.2.1), identificades amb lletres. L’MMU tradueix les adreces lògiques a adreces físiques en temps d’execució; la memòria física, de 16 KiB, té quatre marcs, i la pàgina B del procés 1 només és al disc. Al disc es dibuixen únicament les pàgines que no són a la memòria física.

8.1.3 El disc com a nivell addicional de la jerarquia

Una de les motivacions originals de la memòria virtual era donar solució al problema de no poder encabir tot un programa a la memòria física, la mida de la qual era antigament molt limitada. Tradicionalment, això s’havia solucionat mitjançant la tècnica de les superposicions (overlays): el programador divideix el programa en blocs, que va movent selectivament entre la memòria física i el disc, mantenint a la memòria únicament els blocs indispensables en cada moment. La memòria virtual funciona d’una manera semblant, ja que també fa servir el disc per emmagatzemar temporalment les parts d’un programa que no s’estan fent servir, però això ho gestiona el sistema operatiu, amb l’ajuda del maquinari, i allibera els programadors d’aquesta tasca.

En un computador amb memòria virtual, el disc (o SSD) passa a ser una capa més de la jerarquia de memòria de la Secció 7.1.4 (Figura 8.2). De la mateixa manera que la memòria cau només conté un subconjunt de les dades del nivell inferior (de la memòria principal), la memòria física d’un computador amb memòria virtual només conté un subconjunt de les dades necessàries per a l’execució d’un programa. Totes les dades són sempre al nivell inferior, el disc, que es troba a la base de la jerarquia.

Figura 8.2: Jerarquia de memòria en un computador amb memòria virtual. Els temps d’accés són ordres de magnitud orientatius, que depenen del processador, de la memòria i del dispositiu concrets (vegeu Taula 7.1 per a dades de capacitat i cost).

8.2 Paginació

8.2.1 Pàgines i marcs de pàgina

Els fonaments de la memòria virtual són els mateixos que els de les memòries cau del Capítol 7: un nivell de la jerarquia conté una part de les dades del nivell inferior, organitzades en blocs de mida fixa, i quan la dada no hi és cal anar-la a buscar. Com que els dos mecanismes tenen orígens històrics diferents, però, la terminologia canvia: els blocs s’anomenen pàgines, i les fallades, fallades de pàgina.

La memòria virtual gestiona la traducció d’adreces, doncs, en blocs de mida fixa anomenats pàgines. L’espai d’adreçament lògic de cada procés es divideix en pàgines de \(T\) bytes (habitualment \(T = 4\text{ KiB} = 2^{12}\) bytes), i cada pàgina rep un número de pàgina virtual (virtual page number, VPN), que indica la seva posició dins l’espai lògic, començant per 0. En aquest tema es tracta només la memòria virtual paginada; també existeix la memòria virtual segmentada, que divideix l’espai lògic en segments de mida variable, i que avui és residual.

Donada una adreça lògica \(A\) d’un programa, per exemple la d’una dada, es pot determinar a quin número de pàgina virtual correspon fent la divisió entera entre l’adreça i la mida de pàgina, \(\text{VPN} = \lfloor A / T \rfloor\). Si, per exemple, \(A\) = 0x10010004 i \(T = 4\text{ KiB} = 2^{12}\) bytes, \(A\) és a la pàgina virtual amb VPN = 0x10010. Com que es treballa amb valors de \(T\) que són potències de dos (\(T = 2^t\)), determinar el VPN consisteix simplement a agafar l’adreça i descartar-ne els \(t\) bits de menys pes. Aquests \(t\) bits de menys pes indiquen quina és la ubicació de la dada dins la pàgina, i s’anomenen desplaçament (page offset).

Cada computador disposa d’una determinada capacitat de memòria física, que ocupa un rang d’adreces anomenat espai d’adreçament físic, totalment independent del rang d’adreces lògiques (pot ser més petit, igual o més gran). L’espai d’adreçament físic se subdivideix en blocs de mida \(T\), la mateixa que les pàgines lògiques, anomenats marcs de pàgina (page frames), que es poden imaginar com a «contenidors» on es pot allotjar una pàgina lògica. Cada marc de pàgina té associat un número de pàgina física (physical page number, PPN), que indica la posició que ocupa dins l’espai d’adreçament físic, començant pel 0.

Cada procés consta d’un cert nombre de pàgines virtuals, no totes necessàriament contigües, que ocupen unes adreces determinades en temps de compilació. Les adreces d’aquestes pàgines virtuals són totalment independents de les adreces físiques que ocuparan després, en temps d’execució. Inicialment, un procés resideix a l’emmagatzematge secundari (el disc), i durant l’execució el sistema operatiu haurà d’anar carregant del disc a la memòria física les pàgines que es vagin necessitant. Si no hi queden marcs de pàgina lliures, el sistema n’haurà de reemplaçar un d’ocupat, i possiblement haurà d’escriure’n la pàgina al disc abans de carregar-hi la nova. En un moment donat, les pàgines d’un procés que no són a la memòria física són al disc. Es deixen per a més endavant els detalls de com es llegeixen i s’escriuen les pàgines al disc. Per simplificar, se suposa que la memòria física conté un subconjunt de les pàgines d’un procés, la totalitat de les quals es troba al disc: el disc fa, respecte de la memòria física, el mateix paper que la memòria física feia respecte de la memòria cau al Capítol 7. (En un sistema real, les pàgines que un procés crea durant l’execució, com les de la pila, no tenen còpia al disc fins que el sistema operatiu no les hi ha d’escriure per fer lloc.)

La Figura 8.3 mostra una disposició possible de les pàgines de dos processos en un moment determinat. Amb adreces de 32 bits i una mida de pàgina \(T = 4\text{ KiB} = 2^{12}\) bytes, l’espai d’adreçament lògic de cada procés és de \(2^{32}\) bytes = 4 GiB, és a dir, \(2^{20}\) pàgines virtuals (\(2^{32} / 2^{12}\)). A l’exemple, però, els dos processos només fan servir dues pàgines virtuals cadascun (VPN 0 i VPN 1). La memòria física és de \(2^{14}\) bytes = 16 KiB, és a dir, 4 marcs de pàgina (\(2^{14} / 2^{12}\)): PPN 0, PPN 1, PPN 2 i PPN 3. Algunes pàgines estan carregades a la memòria física (VPN 0 del procés 1, i VPN 0 i VPN 1 del procés 2) i una altra (VPN 1 del procés 1) només és al disc. L’assignació de pàgines a marcs de pàgina la fa el sistema operatiu en funció de l’espai disponible en cada moment, de manera similar a com funciona una memòria cau completament associativa (Secció 7.3.3).

Figura 8.3: Els VPN de dos processos, a l’esquerra, i els PPN d’una memòria de 16 KiB, a la dreta. Les pàgines lògiques s’assignen als marcs de pàgina de manera completament associativa; al disc només es dibuixen les que no són a la memòria física.

8.2.2 Traducció d’adreces: VPN, PPN i desplaçament

Com que \(T\) és una potència de dos (\(T = 2^t\)), qualsevol adreça lògica es descompon naturalment en dos camps:

• Els \(t\) bits de menys pes indiquen la posició de la dada dins la pàgina: és el desplaçament (page offset).
• Els bits restants identifiquen la pàgina: és el VPN.

En un computador amb memòria virtual, el processador treballa amb adreces lògiques. Cada vegada que necessita llegir o escriure una dada de la memòria (per exemple, per fer la captura d’una instrucció), demana l’adreça lògica d’aquesta dada a l’MMU. Mitjançant un procés anomenat traducció d’adreces, l’MMU tradueix l’adreça lògica sol·licitada a l’adreça física on realment es troba la dada. Com que les dades estan agrupades en pàgines, l’únic que ha de fer el sistema de traducció és, donat el número de pàgina (VPN) a què pertany l’adreça, determinar en quin marc de pàgina (PPN) de la memòria física es troba. L’adreça física de la dada s’obté reemplaçant, a l’adreça lògica, els bits corresponents al VPN pel PPN; el desplaçament es conserva intacte. La Figura 8.4 il·lustra el mecanisme de traducció amb les dades de l’exemple anterior: adreces de 32 bits, mida de pàgina \(T = 4\text{ KiB} = 2^{12}\) bytes i memòria física de 16 KiB = \(2^{14}\) bytes.

Figura 8.4: Traducció d’una adreça lògica a una adreça física: el VPN (20 bits) es tradueix a PPN (2 bits) i el desplaçament (12 bits) es conserva.

8.3 La taula de pàgines

Per poder traduir una adreça lògica cal saber en quin marc de pàgina (PPN) es troba cada pàgina virtual (VPN). Aquesta informació la manté una estructura de dades anomenada taula de pàgines. Cada procés té la seva pròpia taula de pàgines, emmagatzemada a la memòria principal.

La taula de pàgines s’indexa pel VPN (Figura 8.5): cada fila correspon a una pàgina virtual i s’anomena entrada de la taula de pàgines (page table entry, PTE). El nombre d’entrades és igual al nombre de pàgines virtuals de l’espai d’adreçament (\(2^{20}\) entrades en l’exemple de 32 bits amb pàgines de 4 KiB).

Figura 8.5: Donat un VPN, la taula de pàgines indica si la pàgina és a la memòria física (bit V) i en quin marc de pàgina (PPN) es troba; el PPN, juntament amb el desplaçament, forma l’adreça física. El registre de taula de pàgines (Secció 8.3.2) en conté l’adreça base, i cada entrada (PTE) conté, a més, els bits D i E.

8.3.1 Estructura d’una entrada (PTE)

Cada PTE conté els camps següents:

• PPN: el número de marc de pàgina on es troba la pàgina, si és a la memòria física.
• Bit V (valid, validesa): val 1 si la PTE conté una traducció utilitzable, és a dir, si la pàgina és a la memòria física; val 0 si no hi és (perquè és al disc o perquè l’adreça no pertany a l’espai vàlid del procés).
• Bit de modificació (dirty bit), D: val 1 si la pàgina ha estat modificada des que es va carregar. Quan cal reemplaçar-la, només s’escriu al disc si D = 1.
• Bit E (escriptura): indica si el procés té permís d’escriptura sobre aquesta pàgina. Si una instrucció intenta escriure en una pàgina amb E = 0, es produeix una excepció de protecció (Secció 8.6.2).

Essencial 8.1: Estructura d’una PTE

Camp	Mida	Significat
PPN	\(p\) bits	Marc de pàgina física on es troba la pàgina
V	1 bit	1 = PTE vàlida (pàgina a memòria); 0 = pàgina al disc o adreça invàlida
D	1 bit	1 = pàgina modificada (dirty)
E	1 bit	1 = permís d’escriptura

Quan V = 0, el camp PPN no té validesa: la pàgina no és a la memòria física.

Aprofundiment 8.1: Notació: V i E a EC, P i W en altres fonts

Aquests apunts anomenen V (valid) el bit de validesa de la PTE, com fan l’ISA de RISC-V (esquema Sv32) i Harris & Harris. Alguns textos i els exàmens anteriors d’EC l’anomenen P (present), com fa l’arquitectura x86; en consultar-los, cal tenir en compte aquesta diferència de notació.

El bit E, en canvi, és una simplificació d’aquests apunts: una PTE real de Sv32 no té cap bit E, sinó tres bits de permís, R (lectura), W (escriptura) i X (execució), a més dels bits U (accessible en mode usuari), G (traducció global, comuna a tots els processos) i A (accessed, pàgina accedida). El bit E d’EC correspon al bit W de Sv32, i el bit U és el que fa inaccessible el nucli des del mode usuari: les pàgines del nucli són a la taula de pàgines de cada procés, però amb U = 0, de manera que qualsevol accés en mode U hi provoca una fallada de pàgina (Secció 8.6.1). La resta de permisos no es tracten en aquest tema. Pel que fa a V, Sv32 només estableix que, amb V = 0, la PTE és invàlida i qualsevol accés provoca una fallada de pàgina: que la pàgina sigui al disc o que l’adreça no pertanyi al procés és informació que gestiona el sistema operatiu, no el maquinari. De fet, quan V = 0 la resta de camps de la PTE no tenen cap significat per al maquinari, i el sistema operatiu els pot fer servir per recordar, per exemple, on és la pàgina al disc.

La Figura 8.6 mostra com es faria la traducció de l’adreça lògica 0x00001801 mitjançant la taula de pàgines del procés 2 de la Figura 8.3. Amb pàgines de 4 KiB, el VPN són els 20 bits de més pes de l’adreça (VPN = 1) i el desplaçament, els 12 de menys pes (0x801). L’entrada 1 de la taula té V = 1, de manera que la pàgina és a la memòria física, al marc PPN = 2 (10 en binari). L’adreça física s’obté reemplaçant el VPN pel PPN i conservant el desplaçament: 10 1000 0000 0001 = 0x2801. Com que la memòria física és de 16 KiB, l’adreça física té 14 bits: 2 de PPN i 12 de desplaçament.

Figura 8.6: Traducció de l’adreça lògica 0x00001801 mitjançant la taula de pàgines del procés 2 de la Figura 8.3.

8.3.2 El registre de taula de pàgines i el canvi de context

En un sistema multiprogramat, diversos processos s’executen de manera concurrent en una sola CPU per temps compartit (time sharing): el sistema operatiu reparteix el temps de la CPU en períodes curts (fraccions de segon) i els alterna entre els processos, de manera que semblen executar-se alhora. En cada instant només hi ha un procés actiu, i quan el sistema operatiu en canvia un per un altre ha de desar l’estat del que deixa d’executar-se i restaurar el del que passa a ser actiu: els registres de propòsit general, el PC i altres estructures de dades. Aquest estat s’anomena context del procés.

En un sistema amb memòria virtual, cada procés té la seva pròpia taula de pàgines a la memòria. Per saber on és la taula del procés actiu, el maquinari incorpora un registre de taula de pàgines que conté l’adreça base de la taula del procés actiu. L’MMU usa aquest registre per accedir a la PTE corresponent a cada VPN que cal traduir.

Quan el sistema operatiu commuta d’un procés a un altre (canvi de context), actualitza el registre de taula de pàgines perquè apunti a la taula del nou procés actiu. Aquesta operació és suficient per canviar completament l’espai d’adreçament visible: a partir d’aquell moment, totes les traduccions es fan amb la taula del nou procés, i l’espai lògic de l’anterior queda inaccessible. El valor del registre de taula de pàgines forma part, doncs, del context del procés.

8.3.3 Taules de pàgines multinivell

La taula de pàgines plana descrita fins ara ocupa una quantitat de memòria proporcional al nombre de pàgines virtuals possibles, independentment de quantes en faci servir realment el procés. En sistemes de 32 bits amb pàgines de 4 KiB i entrades de 4 bytes, això representa 4 MiB per procés en tot moment; en sistemes de 64 bits, el cost es fa inassumible. Les taules de pàgines multinivell resolen el problema assignant memòria només per a les regions de l’espai lògic que el procés utilitza realment (Figura 8.7).

Figura 8.7: Taula de pàgines de dos nivells (Sv32). Els 10 bits de més pes del VPN, VPN[1], indexen la taula de primer nivell, i els 10 següents, VPN[0], la de segon nivell. Les taules de segon nivell només s’assignen per a les regions de l’espai lògic en ús, cosa que redueix la memòria que ocupa la taula de pàgines.

Aprofundiment 8.2: Taules de pàgines multinivell

En un sistema de 32 bits amb pàgines de 4 KiB, la taula de pàgines té \(2^{20}\) entrades. Si cada entrada ocupa 4 bytes, la taula ocupa 4 MiB per procés, tots a la memòria principal. En sistemes de 64 bits el problema s’aguditza: amb adreces de 48 bits significatius i pàgines de 4 KiB, la taula tindria \(2^{36}\) entrades, cosa inviable.

La solució és estructurar la taula de pàgines en múltiples nivells. En una taula de dos nivells, els bits del VPN es divideixen en dues parts: els bits superiors indexen una taula de primer nivell (o directori de pàgines), on cada entrada apunta a una taula de segon nivell. Cada taula de segon nivell conté les PTE d’un subconjunt de l’espai lògic.

L’avantatge clau és que les taules de segon nivell només s’assignen per a les regions de l’espai lògic que el procés utilitza realment. Com que la majoria dels processos fan servir només una fracció petita dels \(2^{32}\) o \(2^{48}\) bytes d’espai lògic possible, la memòria ocupada per la taula de pàgines es redueix dràsticament. El nombre de nivells depèn de l’arquitectura i de la configuració del sistema: per exemple, a x86-64 Linux fa servir habitualment quatre nivells (cinc en els processadors que ho admeten), i a RISC-V de 64 bits, tres (Sv39), quatre (Sv48) o cinc (Sv57), segons el que admeti el processador i triï el nucli en arrencar.

Aprofundiment 8.3: L’esquema Sv32 de RISC-V

Sv32 és l’esquema estàndard de paginació de 32 bits definit per l’arquitectura privilegiada de RISC-V. Tradueix adreces lògiques de 32 bits a adreces físiques de 34 bits mitjançant una taula de pàgines de dos nivells amb pàgines de 4 KiB. Per tant, tot i que cada procés disposa d’un espai lògic de 4 GiB (\(2^{32}\) bytes), el sistema pot adreçar fins a 16 GiB (\(2^{34}\) bytes) de memòria física.

Per a sistemes de 64 bits, RISC-V defineix els esquemes Sv39, Sv48 i Sv57, amb taules de pàgines de tres, quatre i cinc nivells respectivament, que permeten espais d’adreçament molt més grans.

8.4 Fallada de pàgina

Quan la CPU accedeix a una adreça lògica i el bit V de la PTE corresponent val 0, es produeix una fallada de pàgina (page fault). Això pot succeir per dos motius: la pàgina pertany a l’espai vàlid del procés, però no és a la memòria física (és al disc), o bé l’adreça és invàlida (no pertany a cap regió reservada del procés). En el segon cas, el sistema operatiu avorta l’execució del programa (a Unix i derivats, amb un error de tipus segmentation fault).

La fallada de pàgina és una excepció: la instrucció que l’ha provocat s’interromp i el processador passa el control a una rutina del sistema operatiu, que en el primer cas resol la fallada carregant la pàgina des del disc:

1. Es localitza la pàgina al disc.
2. Si hi ha un marc de pàgina lliure, s’hi carrega la pàgina. Si no n’hi ha cap de lliure, cal reemplaçar un marc ocupat: es tria una pàgina víctima, s’escriu al disc si ha estat modificada (D = 1) i es posa V = 0 a la seva PTE, perquè deixa de ser a la memòria física.
3. S’actualitza la PTE de la pàgina nova: es posa V = 1, D = 0 i s’escriu el PPN del marc assignat.
4. Es reexecuta la instrucció que ha causat la fallada, que ara troba la pàgina a la memòria.

Com que un accés al disc és centenars o milers de vegades més lent que un accés a la memòria principal (desenes de milers, o més, en el cas d’un disc magnètic), la fallada de pàgina és, amb diferència, l’incident més costós de tot el sistema de memòria. Per aquest motiu, les dades no es llegeixen ni s’escriuen mai al disc individualment, sinó sempre per pàgines senceres: primer es carrega la pàgina a la memòria física i després s’hi accedeix. Les fallades de pàgina que requereixen un accés al disc s’anomenen fallades majors (major page faults); els sistemes reals tenen també fallades menors (minor page faults), que el sistema operatiu resol sense accedir al disc (per exemple, quan la pàgina ja era a la memòria física, però encara no tenia PTE, com en una pàgina nova de la pila), i que no es consideren en aquest tema.

Essencial 8.2: Mecanisme de la fallada de pàgina

Una fallada de pàgina es produeix quan V = 0 en la PTE del VPN sol·licitat. És una excepció: si la pàgina és vàlida, el sistema operatiu la carrega des del disc (reemplaçant-ne una altra si no hi ha cap marc lliure), actualitza les PTE afectades i reexecuta la instrucció causant. Si l’adreça és invàlida, el procés s’avorta.

Quan no hi ha cap marc lliure, el sistema operatiu n’ha de reemplaçar un, seguint un algorisme de reemplaçament. A l’assignatura es fa servir l’algorisme least recently used (LRU), com a les memòries cau (Secció 7.4): es reemplaça la pàgina que fa més temps que no s’utilitza. Abans de sobreescriure el marc seleccionat, comprova el bit D de la seva PTE: si D = 1, la pàgina ha estat modificada i cal escriure-la primer al disc per no perdre els canvis; si D = 0, es pot sobreescriure directament. Aquesta política és equivalent a l’escriptura retardada amb assignació que es fa servir a les memòries cau (Secció 7.5.3). Si el processador guarda traduccions en un TLB (Secció 8.5), el sistema operatiu també n’ha d’invalidar l’entrada de la pàgina víctima, com s’explica a la Secció 8.5.4.

La zona del disc on s’emmagatzemen les pàgines reemplaçades s’anomena espai d’intercanvi (swap space).

Aprofundiment 8.4: Reemplaçament de pàgines als sistemes reals

El mecanisme descrit és el mínim que cal per fer funcionar la memòria virtual. Els sistemes operatius reals hi afegeixen diverses optimitzacions:

• LRU aproximat: als exemples i problemes d’aquest tema es fa servir un LRU exacte, que és determinista i fàcil de seguir a mà. Els sistemes operatius reals no poden mantenir l’ordre d’ús exacte de milions de pàgines, i l’aproximen amb un bit de referència (reference bit, el bit A d’una PTE de RISC-V) que el maquinari posa a 1 en cada accés i el sistema operatiu esborra periòdicament, o amb algorismes més elaborats.
• Lectura anticipada (anticipatory paging o prefetching): en resoldre una fallada de pàgina, el sistema no es limita a llegir del disc la pàgina sol·licitada, sinó que aprofita l’accés per llegir-ne algunes més de contigües, amb l’expectativa que el programa les necessiti aviat (localitat espacial).
• Reemplaçament global o local: la pàgina víctima es pot triar entre totes les pàgines residents de tots els processos (global page replacement, el que fa Linux) o només entre les del procés que ha causat la fallada (local page replacement), que acota la memòria que pot ocupar cada procés.
• Neteja anticipada (precleaning): en lloc d’esperar que una pàgina modificada sigui triada com a víctima per escriure-la al disc, el sistema aprofita els moments en què el disc està desocupat per escriure-hi les pàgines amb D = 1 i posar-les a D = 0; així, quan calgui reemplaçar-les, no caldrà esperar l’escriptura.

8.5 Traducció ràpida: el TLB

La taula de pàgines és a la memòria principal. Això implica que cada accés a memòria requereix, en realitat, dos accessos: un per llegir la PTE i traduir l’adreça, i un per llegir o escriure la dada (amb una taula de pàgines multinivell, encara més). Per evitar aquest cost, els processadors incorporen a l’MMU una memòria cau de traduccions anomenada translation lookaside buffer (TLB), que emmagatzema les PTE utilitzades més recentment. El TLB és una memòria cau com les del Capítol 7, però de traduccions en lloc de dades: en guarda poques (de l’ordre de desenes o centenars), s’hi accedeix en una fracció del temps d’un accés a memòria, i té els seus propis encerts i fallades.

EC 8.1: El model de TLB d’EC: canvi respecte del temari anterior (MIPS)

El TLB no forma part de l’ISA de RISC-V: l’arquitectura defineix com es tradueix una adreça amb la taula de pàgines, però deixa a cada implementació si guarda traduccions en una memòria cau, i amb quina organització. El TLB d’aquest tema és un model, el mateix per a la teoria i els problemes: completament associatiu, amb reemplaçament LRU i amb les entrades que descriu la Secció 8.5.1. L’únic que l’ISA fixa, i que aquest model respecta, és que el sistema operatiu mai no veu les fallades de TLB, i que ha d’invalidar les traduccions d’una pàgina quan en modifica la PTE; el model d’EC, a més, només hi guarda traduccions vàlides. Al temari anterior d’EC, basat en MIPS, el TLB formava part de l’ISA i podia contenir entrades de pàgines no residents (Aprofundiment 8.5).

8.5.1 Estructura i funcionament

Cada entrada del TLB conté una còpia d’una PTE vàlida (camps D, E i PPN) i el VPN al qual correspon, que fa de clau de cerca (Figura 8.8). A diferència de la taula de pàgines, que s’indexa directament pel VPN, el TLB funciona de manera completament associativa, com les memòries cau d’aquest tipus (Secció 7.3.3): per traduir una adreça, es compara el VPN amb els VPN de totes les entrades simultàniament.

Cada entrada té també un bit de validesa V, amb el mateix paper que el bit de validesa d’una línia de memòria cau: val 1 si l’entrada conté una traducció i 0 si és lliure. En engegar el processador totes les entrades tenen V = 0; una entrada torna a quedar lliure quan el sistema operatiu la invalida (Secció 8.5.4). No s’ha de confondre amb el bit V de la PTE: al TLB només s’hi copien PTE amb V = 1, de manera que tota entrada vàlida del TLB correspon a una pàgina resident a la memòria física.

Essencial 8.3: Estructura d’una entrada del TLB

Camp	Significat
V	1 = l’entrada conté una traducció; 0 = entrada lliure
VPN	Identificador de la pàgina virtual (clau de cerca)
D	1 = pàgina modificada (dirty), copiat de la PTE
E	1 = permís d’escriptura, copiat de la PTE
PPN	Marc de pàgina física corresponent, copiat de la PTE

El TLB només guarda traduccions de pàgines residents: una PTE amb V = 0 no es copia mai al TLB.

Figura 8.8: El TLB emmagatzema una còpia de les entrades de la taula de pàgines utilitzades més recentment, i cada entrada inclou el VPN com a clau de cerca. Són les dades inicials de Exemple 8.2.

8.5.2 Encert de TLB

Quan cal traduir una adreça, l’MMU extreu el VPN i el cerca entre les entrades vàlides del TLB. Si en troba una amb aquest VPN, es produeix un encert de TLB (TLB hit): la pàgina és resident, i la traducció es completa directament amb el PPN d’aquella entrada, sense accedir a la taula de pàgines a la memòria. El cost de la traducció es redueix al temps d’accés al TLB, que és molt inferior al d’un accés a memòria.

Abans d’acabar l’accés, l’MMU comprova els permisos amb els bits de l’entrada: si la instrucció és una escriptura i E = 0, es produeix una excepció de protecció (Secció 8.6.2); si és una escriptura i D = 0, és la primera vegada que s’escriu a la pàgina i cal posar D a 1, tant a l’entrada del TLB com a la PTE de la taula de pàgines (Secció 8.5.5).

8.5.3 Fallada de TLB

Si el VPN no es troba en cap entrada vàlida del TLB, es produeix una fallada de TLB (TLB miss). L’MMU inclou un circuit, el recorregut de la taula de pàgines (page-table walker), que llegeix la PTE corresponent de la taula de pàgines a la memòria principal (a partir del registre de taula de pàgines i del VPN) sense interrompre el programa: la fallada de TLB és transparent per al programari, igual que una fallada de memòria cau. Segons el bit V de la PTE llegida:

• Si V = 1, la pàgina és resident. La PTE es copia en una entrada del TLB —una de lliure (V = 0) si n’hi ha, o la que triï l’algorisme de reemplaçament (LRU, aleatori, FIFO, etc.) si totes són ocupades— i la traducció continua com en un encert.
• Si V = 0, la pàgina no és a la memòria física. No es copia res al TLB i es genera l’excepció de fallada de pàgina (Secció 8.4), que resol el sistema operatiu. Quan la instrucció es reexecuta, torna a fallar al TLB, però ara el recorregut troba la PTE amb V = 1 i la instal·la.

El cost d’una fallada de TLB és, doncs, el dels accessos a memòria necessaris per llegir la PTE: un amb la taula de pàgines plana d’aquest tema, i un per nivell amb una taula multinivell.

Essencial 8.4: Encert i fallada de TLB

Encert de TLB (TLB hit): el VPN és en una entrada vàlida del TLB. La pàgina és resident i la traducció es completa amb el PPN de l’entrada, sense accedir a la memòria principal.

Fallada de TLB (TLB miss): el VPN no és al TLB. L’MMU llegeix la PTE de la taula de pàgines. Si V = 1, la copia al TLB (entrada lliure o reemplaçament) i la traducció continua. Si V = 0, es produeix una fallada de pàgina i no es copia res.

Aprofundiment 8.5: El TLB gestionat per programari: el model de MIPS

A RISC-V, a x86 i a ARM, la fallada de TLB la resol el maquinari, com s’ha explicat, i el sistema operatiu només intervé en les fallades de pàgina. L’arquitectura MIPS, en què es basaven els apunts anteriors d’EC, seguia un model diferent, el del TLB gestionat per programari (software-managed TLB): el TLB formava part de l’ISA, amb instruccions per llegir-ne i escriure’n les entrades, i la fallada de TLB era una excepció. El sistema operatiu executava una rutina que llegia la PTE de la taula de pàgines i la copiava al TLB —encara que tingués V = 0—, i reexecutava la instrucció; si la PTE copiada tenia V = 0, l’encert següent al TLB provocava la fallada de pàgina. En aquell model, doncs, el TLB podia contenir entrades de pàgines no residents, i el bit V d’una entrada del TLB era una còpia del bit V de la PTE.

Cal tenir-ho en compte en consultar exàmens i problemes antics d’EC: hi apareixen encerts de TLB amb V = 0, que en el model d’aquests apunts no poden passar. Els resultats observables (fallades de pàgina, escriptures al disc i adreces físiques) són els mateixos en tots dos models; el que canvia és el contingut del TLB en cada moment.

RISC-V permet que una implementació resolgui les fallades de TLB per programari, però com una extensió del mode màquina (M) invisible per al sistema operatiu: el nucli, que s’executa en mode supervisor (S), només veu fallades de pàgina. El Tema 9 (Secció 9.7) presenta la rutina de fallada de pàgina del nucli amb codi RISC-V.

8.5.4 Entrades lliures i invalidació del TLB

Una entrada del TLB pot estar lliure (V = 0) per dos motius: perquè no s’ha fet servir mai des que s’ha engegat el processador, o perquè el sistema operatiu l’ha invalidat.

El TLB és una còpia parcial de la taula de pàgines, i cal mantenir-les coherents. Quan el sistema operatiu modifica una PTE —en reemplaçar una pàgina, en canviar-ne els permisos o en canviar de procés—, les entrades del TLB que en tinguin una còpia queden obsoletes, i el maquinari no ho pot detectar, perquè el TLB no observa les escriptures a la taula de pàgines. Per això el sistema operatiu, després de modificar la PTE, ha d’invalidar les entrades afectades del TLB (a RISC-V, amb la instrucció sfence.vma, que presenta el Tema 9 a Secció 9.7.3), posant-les a V = 0. En el cas del reemplaçament de pàgina, l’entrada de la pàgina víctima queda lliure, i és la primera candidata a rebre la traducció de la pàgina nova. En el canvi de context, com que la taula de pàgines canvia sencera, s’invaliden totes les entrades (tret que cada entrada del TLB identifiqui el procés a què pertany, com permet el camp ASID del registre satp de RISC-V; vegeu RISC-V 9.15).

8.5.5 El bit D: consistència amb la taula de pàgines

El bit D és l’únic camp del TLB que l’execució del programa pot modificar: quan una instrucció d’escriptura (sw, fsw, etc.) accedeix a una pàgina amb D = 0, el bit D s’ha de posar a 1, i la taula de pàgines ho ha de saber, perquè el sistema operatiu consulta la PTE quan ha de reemplaçar la pàgina.

A EC se suposa que l’actualització del bit D la fa el maquinari, sense cap excepció ni intervenció del sistema operatiu: l’MMU segueix una política d’escriptura immediata i, a la primera escriptura en una pàgina (D = 0 al TLB), posa D = 1 simultàniament a l’entrada del TLB i a la PTE de la taula de pàgines. Això requereix un accés addicional a la memòria principal, però només succeeix la primera vegada que s’escriu en cada pàgina, no en cada instrucció d’escriptura. És una de les dues opcions que admet RISC-V per actualitzar els bits A i D de la PTE; l’altra, que ho faci el sistema operatiu a través d’una excepció, no es fa servir, i s’explica a l’aprofundiment Aprofundiment 9.7 del Tema 9.

8.5.6 Flux complet de traducció

La Figura 8.9 resumeix totes les situacions possibles durant la traducció d’una adreça en un sistema amb TLB i memòria virtual. Les dues columnes de l’esquerra, l’encert i la fallada de TLB, les resol el maquinari (l’MMU) sense interrompre el programa; la de la dreta, la fallada de pàgina, és una excepció que resol el sistema operatiu i acaba reexecutant la instrucció.

Figura 8.9: Flux complet de traducció d’una adreça en un sistema amb TLB i memòria virtual. A l’esquerra, l’encert de TLB; al centre, la fallada de TLB, que resol l’MMU sense interrompre el programa, i a la dreta, la fallada de pàgina, una excepció que resol el sistema operatiu.

Aprofundiment 8.6: TLB shootdown en sistemes multinucli

En un processador amb múltiples nuclis, cada nucli disposa del seu propi TLB. Quan el sistema operatiu modifica una PTE de la taula de pàgines d’un procés (per exemple, en reemplaçar una pàgina o revocar un permís d’escriptura), qualsevol nucli que tingui una còpia d’aquella entrada al seu TLB passa a tenir informació obsoleta.

Per garantir la coherència, el sistema operatiu ha d’invalidar les entrades afectades als TLB de tots els nuclis que puguin tenir-les, no només al nucli on s’executa (la instrucció sfence.vma de RISC-V només actua sobre el TLB del nucli que l’executa). La manera habitual de fer-ho és enviar una interrupció entre processadors (inter-processor interrupt, IPI) a cadascun dels nuclis implicats perquè invalidin l’entrada corresponent, tot i que algunes plataformes ofereixen mecanismes d’invalidació remota que ho estalvien. Aquest procés s’anomena TLB shootdown.

El cost del TLB shootdown és significatiu: cada nucli afectat ha d’interrompre l’execució, processar la interrupció i invalidar l’entrada. En sistemes amb molts nuclis i processos que comparteixen memòria, el TLB shootdown pot convertir-se en un coll d’ampolla de rendiment rellevant, i és una de les raons per les quals la gestió eficient de la memòria virtual en sistemes multinucli (multicore) és un problema de recerca actiu.

8.6 Protecció i compartició

Una de les funcions més importants de la memòria virtual és permetre que múltiples processos comparteixin la memòria física de manera segura. Això requereix mecanismes que garanteixin que cap procés pugui accedir a l’espai d’adreçament d’un altre de manera no autoritzada.

8.6.1 Protecció entre processos

El mecanisme de traducció d’adreces proporciona protecció entre processos de manera natural: com que cada procés té la seva pròpia taula de pàgines, i l’MMU usa exclusivament la taula del procés actiu per a totes les traduccions, un procés no pot generar cap adreça física que correspongui a una pàgina assignada a un altre procés, tret que el sistema operatiu ho hagi volgut així (Secció 8.6.3). L’aïllament no requereix cap comprovació addicional en cada accés: és conseqüència del contingut de la taula de pàgines.

Perquè aquest mecanisme sigui efectiu, cal que cap procés pugui modificar la seva pròpia taula de pàgines ni el registre de taula de pàgines. Per garantir-ho, les taules de pàgines es troben a la zona de memòria reservada al nucli del sistema operatiu (kernel), accessible només quan el processador opera en un mode privilegiat. A RISC-V, els programes d’usuari s’executen en mode usuari (U) i el nucli del sistema operatiu en mode supervisor (S): en mode U, qualsevol intent d’accedir a la zona del nucli provoca una fallada de pàgina; el sistema operatiu, en tractar-la, detecta que l’adreça no és vàlida per al procés i l’avorta (segmentation fault), com en qualsevol accés a una adreça invàlida (Secció 8.4). Qualsevol intent d’escriure el registre de taula de pàgines (satp) o d’invalidar el TLB (sfence.vma), en canvi, provoca una excepció d’instrucció il·legal. El Tema 9 descriu amb més detall els modes d’execució (Secció 9.2.1) i el mecanisme d’excepcions.

8.6.2 Protecció contra escriptura

A més de l’aïllament entre processos, la memòria virtual permet controlar el tipus d’accés permès sobre cada pàgina individual mitjançant el bit E de la PTE i del TLB. Si una instrucció intenta escriure en una pàgina amb E = 0, l’MMU genera una excepció de protecció (a RISC-V, una fallada de pàgina d’escriptura, store page fault) i el sistema operatiu, en el model d’aquest tema, avorta el procés amb un error de violació de protecció.

Aquest mecanisme té diverses aplicacions pràctiques:

• Protecció del codi: les pàgines que contenen instruccions es marquen habitualment com a només de lectura (E = 0), de manera que un error de programació no pugui sobreescriure el codi en execució.
• Detecció d’errors: marcar com a només de lectura pàgines que no haurien de ser modificades permet detectar errors de programació que d’altra manera passarien desapercebuts.
• Compartició segura: permet compartir pàgines entre processos amb permisos asimètrics (un procés pot escriure-hi i un altre només llegir-hi), com es veurà a la secció següent.

8.6.3 Compartició de pàgines

Hi pot haver situacions en què un procés (per exemple, P1) vulgui permetre a un altre (per exemple, P2) accedir al seu espai d’adreçament. El sistema operatiu, a petició de P1, pot habilitar la compartició simplement escrivint una entrada a la taula de pàgines del procés P2 que assigni una pàgina lògica de P2 a la mateixa pàgina física que P1 vol compartir (Figura 8.10). A petició del procés P1, la pàgina compartida pot tenir permís d’escriptura o no per al procés P2: només cal que el sistema operatiu inicialitzi adequadament el bit E de la pàgina lògica de P2.

Exemple 8.1: Compartició de pàgines

El procés P1 vol compartir la seva pàgina VPN = 0x00000 (carregada al marc PPN = 0x02) amb el procés P2 en mode escriptura. El sistema operatiu escriu una entrada a la taula de pàgines de P2 que assigna VPN = 0x00001 al mateix PPN = 0x02, amb E = 1.

A partir d’aquell moment, quan P2 accedeix a VPN = 0x00001 i P1 accedeix a VPN = 0x00000, tots dos llegeixen i escriuen els mateixos bytes de la memòria física: el que un dels dos hi escrigui, l’altre ho llegirà, sense cap còpia pel mig.

Figura 8.10: Compartició d’una pàgina física entre dos processos (Exemple 8.1): P1 la té assignada a VPN = 0x00000 i P2, a VPN = 0x00001, totes dues al marc PPN = 0x02 i amb E = 1. La figura mostra el moment en què P2 és en execució: el registre de taula de pàgines apunta a la taula de P2, i el TLB només conté traduccions de la taula de P2.

La compartició de pàgines té dues aplicacions principals:

• Comunicació entre processos: dos processos poden intercanviar dades escrivint i llegint una pàgina compartida, sense necessitat de còpies.
• Biblioteques compartides: si múltiples processos usen simultàniament el codi d’una mateixa biblioteca, el sistema operatiu pot mantenir una sola còpia de les pàgines de codi a la memòria física i assignar-les (en mode només de lectura, E = 0) a l’espai lògic de cada procés, estalviant memòria física de manera significativa.

8.7 Integració del TLB i la memòria cau

En un sistema amb memòria virtual, cada accés a memòria implica dos passos: traduir l’adreça lògica a física (amb el TLB) i accedir a la dada (a la memòria cau). La manera com s’organitzen aquests dos passos determina el temps d’accés efectiu i la complexitat del disseny.

8.7.1 Memòria cau indexada físicament

L’esquema més senzill és la memòria cau indexada i etiquetada físicament (physically indexed physically tagged, PIPT): primer es tradueix l’adreça lògica amb el TLB i, un cop obtinguda l’adreça física, s’accedeix a la memòria cau amb aquesta adreça (Figura 8.11).

Figura 8.11: Memòria cau indexada físicament (PIPT), amb un TLB completament associatiu, dibuixat com la memòria cau de la Figura 7.11 (una entrada només encerta si té V = 1), i una memòria cau de correspondència directa (Figura 7.8): el PPN de l’entrada del TLB que encerta i el desplaçament de pàgina formen l’adreça física, que es parteix en etiqueta, índex i desplaçament de bloc. La traducció i l’accés a la memòria cau es fan en sèrie. A sota, el temps d’accés: el del TLB i el de la memòria cau, un darrere l’altre.

L’avantatge és la simplicitat: no hi ha ambigüitat possible, ja que cada adreça física identifica unívocament una dada. L’inconvenient és el temps d’accés: la memòria cau no pot començar a operar fins que el TLB hagi acabat la traducció, de manera que els dos accessos es fan en sèrie.

8.7.2 Memòria cau indexada i etiquetada virtualment

Una memòria cau indexada i etiquetada virtualment (virtually indexed virtually tagged, VIVT) redueix la latència perquè usa l’adreça lògica directament, sense esperar la traducció (Figura 8.12). Si hi ha encert, la dada s’obté sense necessitat de la traducció; només cal el TLB en cas de fallada, per anar a buscar el bloc a la memòria principal amb l’adreça física.

Figura 8.12: Memòria cau indexada i etiquetada virtualment (VIVT): l’adreça lògica indexa la memòria cau i en dona l’etiqueta; el TLB només intervé en una fallada, per obtenir l’adreça física del bloc. A sota, el temps d’accés amb encert, a la mateixa escala que a la Figura 8.11.

El problema és l’aliàsing (aliasing): si dos processos (o dues pàgines lògiques d’un mateix procés) comparteixen una mateixa pàgina física (Secció 8.6.3), el mateix bloc pot ocupar dues línies diferents de la memòria cau, una per a cada adreça lògica. Una escriptura feta a través d’una adreça lògica pot no ser visible quan es llegeix a través de l’altra, cosa que trenca la coherència.

L’altre problema són els homònims: la mateixa adreça lògica de dos processos correspon a dades físiques diferents. Per això, en cada canvi de context, cal invalidar la memòria cau sencera o afegir a cada etiqueta l’identificador del procés, com fa l’ASID amb el TLB (Secció 8.5.4).

8.7.3 VIPT: la solució habitual

La solució més habitual als processadors actuals, per a la memòria cau de primer nivell, és la memòria cau indexada virtualment i etiquetada físicament (virtually indexed physically tagged, VIPT). La idea clau és que l’índex per accedir a la memòria cau i la traducció del TLB es poden fer en paral·lel (Figura 8.13):

• L’índex de la memòria cau s’extreu de l’adreça lògica. Si només fa servir bits del desplaçament de pàgina (els \(t\) bits de menys pes; és la condició de més avall), coincideix exactament amb el de l’adreça física, perquè el desplaçament no es tradueix.
• Mentre la memòria cau llegeix les etiquetes i els blocs de dades corresponents a aquest índex, el TLB tradueix el VPN i obté el PPN.
• Un cop acabats els dos accessos en paral·lel, es compara l’etiqueta física de l’adreça —el PPN obtingut del TLB, més els bits del desplaçament de pàgina que l’índex i el desplaçament de bloc no fan servir, si n’hi ha— amb les etiquetes llegides de la memòria cau per determinar si hi ha encert.

Figura 8.13: Memòria cau VIPT: la indexació de la memòria cau i la traducció del TLB es fan en paral·lel, i, com que l’índex només fa servir bits del desplaçament, no hi ha aliàsing. A sota, el temps d’accés, a la mateixa escala que a la Figura 8.11.

La condició perquè VIPT funcioni sense aliàsing és que l’índex de la memòria cau usi exclusivament bits del desplaçament (és a dir, bits que no canvien amb la traducció). En una memòria cau amb \(N_C = 2^{n_c}\) conjunts i blocs de \(B = 2^b\) bytes (Essencial 7.1), l’índex ocupa els \(n_c\) bits que hi ha per sobre dels \(b\) del desplaçament dins del bloc. Perquè tots siguin del desplaçament de pàgina (els \(t = \log_2 T\) bits de menys pes), cal que \(n_c + b \le t\), és a dir:

\[N_C \cdot B \leq T\]

on \(T\) és la mida de pàgina. El producte \(N_C \cdot B\) és la mida d’una via, la capacitat de la memòria cau dividida pel grau d’associativitat \(N\): cap via no pot ser més gran que una pàgina. Per exemple, amb pàgines de 4 KiB i 4 vies, la memòria cau L1 pot tenir fins a 16 KiB sense aliàsing. És una condició suficient per evitar l’aliàsing en una memòria cau VIPT, no una equivalència amb la PIPT en tots els aspectes, i els dissenys de L1 l’acostumen a respectar: una L1 més gran obliga a augmentar l’associativitat en la mateixa proporció.

Essencial 8.5: Comparació dels esquemes d’integració TLB–memòria cau

Esquema	Indexació	Etiqueta	Avantatge	Inconvenient
PIPT	Física	Física	Simple, sense aliàsing	TLB i MC en sèrie
VIVT	Virtual	Virtual	Ràpid (sense TLB en els encerts)	Aliàsing i homònims
VIPT	Virtual	Física	Ràpid i sense aliàsing	Restricció de mida

VIPT és l’esquema habitual als processadors actuals per a la memòria cau L1. Les memòries cau L2 i L3, menys crítiques en latència, usen habitualment PIPT. Cap dels tres esquemes no és un requisit de l’ISA: l’organització de les memòries cau és una decisió de cada implementació.

8.8 Exemple pràctic

Aquesta secció recorre un exemple complet: una seqüència de cinc accessos a memòria en un sistema amb TLB, amb la traducció de cada adreça, les fallades de TLB i de pàgina, el reemplaçament i el bit D, seguint el flux de la Figura 8.9.

Exemple 8.2: Traducció amb TLB

Considerem un sistema amb adreces lògiques de 32 bits, pàgines de 4 KiB (\(t = 12\)), una memòria física de 16 KiB (4 marcs de pàgina, adreces físiques de 14 bits) i un TLB de 4 entrades, completament associatiu, amb reemplaçament LRU, tant per al TLB com per a les pàgines. L’estat inicial és:

TLB (estat inicial)

V	VPN	D	E	PPN
1	0x00003	1	1	0x00
1	0x00000	0	1	0x01
1	0x00002	0	1	0x02
0	—	—	—	—

La taula de pàgines (entrades rellevants) és:

Taula de pàgines (entrades rellevants)

VPN	V	D	E	PPN
0x00000	1	0	1	0x01
0x00001	0	0	1	—
0x00002	1	0	1	0x02
0x00003	1	1	1	0x00
0x00004	0	0	1	—
0x00005	0	0	1	—

Sabem que només tres dels quatre marcs de pàgina estan ocupats (PPN = 0x03 és lliure), i que els tres darrers accessos han estat a VPN = 0x00003, VPN = 0x00000 i VPN = 0x00002, en aquest ordre (de més antic a més recent). Les tres pàgines residents tenen entrada al TLB, de manera que l’ordre LRU del TLB i el de les pàgines coincideixen.

Accés 1: escriptura a 0x00002A0B → VPN = 0x00002.

Encert de TLB. Com que és una escriptura amb E = 1 i D = 0, s’aplica la política d’escriptura immediata descrita a la Secció 8.5.5: es posa D = 1 al TLB i a la PTE. PPN = 0x02. Adreça física (14 bits): 0x2A0B. VPN 2 passa a ser la pàgina més recent (ja ho era).

Accés 2: lectura a 0x00001F21 → VPN = 0x00001.

Fallada de TLB. L’MMU llegeix la PTE de VPN 1: V = 0, fallada de pàgina; no es copia res al TLB. El sistema operatiu troba el marc lliure (PPN = 0x03), hi carrega la pàgina des del disc i actualitza la PTE (V = 1, D = 0, PPN = 0x03). En reexecutar la lectura, torna a fallar el TLB, però ara la PTE té V = 1 i l’MMU la copia a l’entrada lliure. PPN = 0x03. Adreça física: 0x3F21. Ordre LRU: VPN 3, 0, 2, 1.

Accés 3: lectura a 0x0000420C → VPN = 0x00004.

Fallada de TLB i, en llegir la PTE, fallada de pàgina. Cap marc lliure: el sistema operatiu tria la víctima LRU, VPN 3 (al marc 0x00), que té D = 1 i que cal escriure primer al disc. Posa V = 0 a la PTE de VPN 3 i n’invalida l’entrada del TLB, que queda lliure. Carrega VPN 4 al marc 0x00 i actualitza la seva PTE (V = 1, D = 0, PPN = 0x00). En reexecutar la lectura, l’MMU copia la PTE de VPN 4 a l’entrada que acaba de quedar lliure. PPN = 0x00. Adreça física: 0x020C. Ordre LRU: VPN 0, 2, 1, 4.

Accés 4: lectura a 0x00003001 → VPN = 0x00003.

Fallada de TLB (l’entrada de VPN 3 s’ha invalidat a l’accés 3) i fallada de pàgina. La víctima LRU és VPN 0 (al marc 0x01), amb D = 0: no cal escriure-la al disc. V = 0 a la seva PTE i entrada del TLB invalidada. Es carrega VPN 3 al marc 0x01 (PTE: V = 1, D = 0, PPN = 0x01; en tornar del disc la pàgina ja no està modificada) i, en reexecutar, s’instal·la a l’entrada lliure. PPN = 0x01. Adreça física: 0x1001. Ordre LRU: VPN 2, 1, 4, 3.

Accés 5: lectura a 0x00005120 → VPN = 0x00005.

Fallada de TLB i fallada de pàgina. La víctima LRU és VPN 2 (al marc 0x02), que té D = 1 des de l’accés 1: s’escriu al disc. V = 0 a la seva PTE i entrada del TLB invalidada. Es carrega VPN 5 al marc 0x02 (PTE: V = 1, D = 0, PPN = 0x02) i s’instal·la al TLB. PPN = 0x02. Adreça física: 0x2120. Ordre LRU: VPN 1, 4, 3, 5.

Resum dels cinc accessos

	Adreça lògica	VPN	Fallada TLB	Fallada pàg.	Pàg. víctima	Escr. disc	PPN	Adreça física
E	0x00002A0B	0x00002	no	no	—	no	0x02	0x2A0B
L	0x00001F21	0x00001	sí	sí	— (marc lliure)	no	0x03	0x3F21
L	0x0000420C	0x00004	sí	sí	0x00003	sí (VPN 3)	0x00	0x020C
L	0x00003001	0x00003	sí	sí	0x00000	no	0x01	0x1001
L	0x00005120	0x00005	sí	sí	0x00002	sí (VPN 2)	0x02	0x2120

A la columna «Fallada TLB» es compta una fallada per accés: quan la instrucció es torna a executar després d’una fallada de pàgina, la segona consulta del TLB no compta com una fallada nova.

En acabar, la memòria física conté VPN 4 (0x00), VPN 3 (0x01), VPN 5 (0x02) i VPN 1 (0x03), totes amb D = 0, i el TLB té exactament aquestes quatre traduccions. Fixa’t que, amb tants marcs com entrades de TLB, el reemplaçament LRU del TLB no arriba a actuar mai: mentre hi ha marcs lliures, també hi ha entrades lliures. Quan el TLB és ple, hi són totes les pàgines residents; per tant, una fallada de TLB és sempre una fallada de pàgina, i en invalidar l’entrada de la víctima se n’allibera una. El reemplaçament del TLB només entra en joc quan hi ha més pàgines residents que entrades, com a Exercici 17.5. La Figura 8.14 mostra l’estat del TLB i de la memòria física després de cada accés.

Figura 8.14: Traça dels cinc accessos de Exemple 8.2: l’estat inicial i, per a cada accés, el TLB i la memòria física després de resoldre’l, amb les entrades i els marcs que han canviat amb vora gruixuda. A la versió en HyperText Markup Language (HTML), el navegador de passos mostra també la taula de pàgines després de cada accés.