Tema 8: Memòria virtual

26.1 Traducció d’adreces i fallada de pàgina

Exemple 26.1: Solució: paginació bàsica i traça LRU

Memòria virtual de 16 MiB ($2^{24}$ B → 24 bits d’adreça lògica), memòria física de 16 KiB ($2^{14}$ B → 14 bits d’adreça física) i pàgines de 256 B ($2^8$ B → desplaçament de 8 bits).

La descomposició VPN/desplaçament segueix la Secció 8.2.2:

VPN: $24 - 8 = 16$ bits → $2^{16} = 65\,536$ pàgines virtuals.
PPN: $14 - 8 = 6$ bits → $2^6 = 64$ marcs de pàgina.

a) La taula de pàgines té una entrada per pàgina virtual: $2^{16} = 65\,536$ entrades. Cada entrada conté el PPN (6 bits) més el bit V i el bit D:

\[6 + 1 + 1 = 8 \text{ bits} = 1 \text{ byte/entrada}\]

\[\text{Mida taula de pàgines} = 2^{16} \times 1 \text{ B} = 64 \text{ KiB}\]

b) El VPN és $\lfloor \text{adreça} / \texttt{0x100} \rfloor$ (els dos dígits hexadecimals inferiors són el desplaçament de 8 bits). Cada programa pot tenir com a màxim 3 pàgines a memòria física, amb reemplaçament LRU. Seqüència de VPN: 0, 1, 1, 2, 0, 1, 4, 5, 1.

La pila LRU s’escriu de la pàgina most recently used (MRU), la usada més recentment, a la menys recent.

Adreça	A — Pàg.	B — Fallada	C — Reempl.	Pila LRU (MRU→LRU)
`000023`	`0`	Sí	—	0
`000101`	`1`	Sí	—	1, 0
`000102`	`1`	No	—	1, 0
`000200`	`2`	Sí	—	2, 1, 0
`000010`	`0`	No	—	0, 2, 1
`000111`	`1`	No	—	1, 0, 2
`000416`	`4`	Sí	`2`	4, 1, 0
`000520`	`5`	Sí	`0`	5, 4, 1
`000101`	`1`	No	—	1, 5, 4

Hi ha 5 fallades i 4 encerts. A 000416 s’expulsa la pàgina 2 (la menys recentment usada, desplaçada pels encerts a 0 i 1); a 000520 s’expulsa la pàgina 0.

Exemple 26.2: Solució: taula de pàgines de dos nivells

Enunciat: Problema 17.2.

Adreces de 32 bits, pàgines de 4 KiB ($2^{12}$ B), entrades de 4 B, dos nivells amb repartiment simètric.

a) Desplaçament: $\log_2(4\text{ KiB}) = 12$ bits. Resten $32 - 12 = 20$ bits d’índex, repartits simètricament:

\[\underbrace{10 \text{ bits}}_{\text{índex N1}} \; \underbrace{10 \text{ bits}}_{\text{índex N2}} \; \underbrace{12 \text{ bits}}_{\text{desplaçament}}\]

b) Cada taula (de qualsevol nivell) té $2^{10} = 1024$ entrades de 4 B:

\[2^{10} \times 4 \text{ B} = 4 \text{ KiB}\]

Tant la taula de primer nivell com cada taula de segon nivell ocupen 4 KiB (exactament una pàgina).

c) Cada entrada del primer nivell pot apuntar a una taula de segon nivell: com a màxim $2^{10} = 1024$ taules de segon nivell. Mida total en el pitjor cas (totes assignades):

\[\underbrace{4 \text{ KiB}}_{\text{N1}} + 1024 \times \underbrace{4 \text{ KiB}}_{\text{N2}} = 4 \text{ KiB} + 4 \text{ MiB}\]

d) Una taula de nivell únic tindria $2^{20}$ entrades de 4 B $= 4$ MiB. La jerarquia de dos nivells, en el pitjor cas, ocupa lleugerament més (4 MiB + 4 KiB: el sobrecost del directori de primer nivell).

L’avantatge apareix en el cas típic, en què el procés només usa una fracció de l’espai lògic: només cal assignar les taules de segon nivell de les regions realment utilitzades. Per exemple, un procés que toqui codi, dades i pila en 3 regions disjuntes necessita la taula de primer nivell (4 KiB) i tres de segon nivell (una per regió), és a dir, 16 KiB en lloc de 4 MiB. Amb un nivell únic, en canvi, sempre cal reservar els 4 MiB sencers encara que la majoria d’entrades siguin invàlides.

Exemple 26.3: Solució: traça de la taula de pàgines amb accés a disc

Enunciat: Problema 17.3.

Adreça lògica de 16 bits, física de 15 bits, pàgines de 8 KiB ($2^{13}$ → desplaçament de 13 bits). VPN: $16 - 13 = 3$ bits (8 pàgines); PPN: $15 - 13 = 2$ bits (4 marcs). El VPN és $\lfloor \text{adreça}/\texttt{0x2000} \rfloor$ (els 3 bits de més pes de l’adreça).

Estat inicial: PPN 0 = VPN 2, PPN 1 = VPN 3, PPN 2 = VPN 4, PPN 3 lliure. Ordre LRU (MRU→LRU): VPN 3, VPN 2, VPN 4. Cap pàgina està modificada ($D = 0$).

Adreça	VPN	PPN	Fallada	Lect. disc	Escr. disc	Reempl. VPN	Reempl. PPN
E `F458`	7	3	Sí	Sí	No	—	—
E `8666`	4	2	No	No	No	—	—
L `1BBF`	0	0	Sí	Sí	No	2	0
E `5C44`	2	1	Sí	Sí	No	3	1
L `6600`	3	3	Sí	Sí	Sí	7	3
L `4000`	2	1	No	No	No	—	—

Punts clau:

E F458 (VPN 7): fallada amb el marc lliure PPN 3; com que és escriptura, queda $D = 1$.
L 1BBF (VPN 0) i E 5C44 (VPN 2): cap marc lliure; s’expulsen les pàgines més antigues (VPN 2 i VPN 3), totes dues amb $D = 0$, de manera que no cal escriure-les a disc.
L 6600 (VPN 3): s’expulsa la pàgina del VPN 7, que té $D = 1$ → cal escriure-la primer a disc (única escriptura a disc de la traça).
L 4000 (VPN 2): encert, la pàgina segueix a PPN 1.

Estat final de la taula de pàgines:

VPN	V	D	PPN
0	1	0	0
1	0	0	—
2	1	1	1
3	1	0	3
4	1	1	2
5–7	0	0	—

Estat final de la memòria física: PPN 0 = VPN 0, PPN 1 = VPN 2, PPN 2 = VPN 4, PPN 3 = VPN 3.

26.2 TLB

Exemple 26.4: Solució: traça del TLB i de la taula de pàgines

Enunciat: Problema 17.5.

Pàgines de 4 KiB → $\text{VPN} = \lfloor \text{adreça}/4096 \rfloor$. TLB de 4 entrades completament associatiu, LRU (vegeu Secció 8.5). La quarta entrada ($V = 0$) és lliure i s’omple en la primera fallada; mentre n’hi hagi cap de lliure, el reemplaçament LRU no actua. Ordre LRU inicial de les vàlides (MRU→LRU): VPN 11, VPN 7, VPN 3.

a) Llista 1. VPN: 0, 7, 3, 3, 1, 1, 2.

Ref.	VPN	Fallada TLB	Fallada pàgina	PPN
4095	0	Sí	No	5
31272	7	No	No	4
15789	3	No	No	6
15000	3	No	No	6
7193	1	Sí	Sí	13
4096	1	No	No	13
8912	2	Sí	Sí	14

4095 (VPN 0): fallada de TLB; l’MMU llegeix la PTE, que té $V = 1$ (PPN 5), i la copia a l’entrada lliure, sense fallada de pàgina.
7193 (VPN 1): fallada de TLB i la PTE té $V = 0$ → fallada de pàgina; l’SO carrega la pàgina i li assigna PPN 13. En reexecutar l’accés, l’MMU copia la PTE al TLB reemplaçant l’entrada del VPN 11 (l’única no reutilitzada des de l’inici → la més antiga).
8912 (VPN 2): fallada de TLB i $V = 0$ → fallada de pàgina (PPN 14); en reexecutar, es reemplaça l’entrada del VPN 0 (la més antiga de la pila en aquest punt).

TLB final: (VPN 1, PPN 13), (VPN 7, PPN 4), (VPN 3, PPN 6), (VPN 2, PPN 14). Taula de pàgines: VPN 1 → V 1/PPN 13, VPN 2 → V 1/PPN 14. Total: 3 fallades de TLB, 2 de les quals són fallades de pàgina. Ordre LRU final, de la més recent a la més antiga: VPN 2, 1, 3 i 7.

Llista 2 (des de l’estat inicial). VPN: 2, 7, 4, 11, 9, 4, 11.

Ref.	VPN	Fallada TLB	Fallada pàgina	PPN
9452	2	Sí	Sí	13
30964	7	No	No	4
19136	4	Sí	No	9
46502	11	No	No	12
38110	9	Sí	Sí	14
17653	4	No	No	9
47480	11	No	No	12

9452 (VPN 2): fallada de TLB i $V = 0$ → fallada de pàgina (PPN 13); s’omple l’entrada lliure.
19136 (VPN 4): fallada de TLB però $V = 1$ (PPN 9) → sense fallada de pàgina. Es reemplaça l’entrada del VPN 3 (la més antiga segons l’ordre inicial 11 > 7 > 3).
38110 (VPN 9): fallada de TLB i $V = 0$ → fallada de pàgina (PPN 14); es reemplaça l’entrada del VPN 2 (la menys recentment usada).
46502 i 47480 (VPN 11): encerts, perquè l’entrada del VPN 11 era la més recent inicialment i no s’ha expulsat.

TLB final: (VPN 11, PPN 12), (VPN 7, PPN 4), (VPN 4, PPN 9), (VPN 9, PPN 14). Taula de pàgines: VPN 2 → V 1/PPN 13, VPN 9 → V 1/PPN 14. Total: 3 fallades de TLB, 2 de les quals són fallades de pàgina. Ordre LRU final: VPN 11, 4, 9 i 7.

b) Amb pàgines de 16 KiB, $\text{VPN} = \lfloor \text{adreça}/16\,384 \rfloor$ i moltes adreces que abans queien en pàgines diferents passen a compartir pàgina:

Llista 1: pàgines 0, 1, 0, 0, 0, 0, 0 → només 2 pàgines diferents (abans 5).
Llista 2: pàgines 0, 1, 1, 2, 2, 1, 2 → només 3 pàgines diferents (abans 5).

En els dos casos el nombre de pàgines diferents accedides baixa, cosa que redueix el nombre potencial de fallades de TLB d’arrencada en fred (cold-start: una fallada per pàgina nova referenciada). No es pot donar, però, un nombre exacte de fallades comparable al de l’apartat a): l’estat inicial del TLB (VPN 11, 7, 3 vàlides) es va definir per a pàgines de 4 KiB i deixa de tenir sentit en reinterpretar-lo amb una mida de pàgina diferent — els VPN ja no designen els mateixos rangs d’adreces lògiques, de manera que no hi ha una manera coherent de «traduir» aquell estat inicial concret al nou context.

En general, augmentar la mida de pàgina redueix el nombre de pàgines diferents accedides i, per tant, les fallades de TLB d’arrencada en fred, a canvi de més fragmentació interna i transferències a disc més grans en cada fallada de pàgina.

c) Mida de la taula de pàgines (nivell únic):

\[\text{Nre. entrades} = \frac{2^{\text{bits adreça}}}{\text{mida pàgina}}, \qquad \text{Mida taula de pàgines} = \text{Nre. entrades} \times \text{mida entrada}\]

32 bits, pàgines de 4 KiB, entrades de 4 B: $\dfrac{2^{32}}{2^{12}} \times 4 = 2^{20} \times 4 = \mathbf{4 \text{ MiB}}$.
64 bits, pàgines de 16 KiB, entrades de 8 B: $\dfrac{2^{64}}{2^{14}} \times 8 = 2^{50} \times 2^3 = 2^{53} \text{ B} = \mathbf{8 \text{ PiB}}$.

El segon resultat (8 PiB per procés) és inviable i justifica les taules de pàgines multinivell de Solució 26.2.

26.3 Protecció

Exemple 26.5: Solució: bit de permís d’escriptura i excepcions

Enunciat: Problema 17.8.

Pàgines de 4 KiB → $\text{VPN} = \lfloor \text{adreça}/\texttt{0x1000} \rfloor$. Criteri: una lectura té èxit sempre que $V = 1$ (el bit E només restringeix escriptures); una escriptura requereix $V = 1$ i $E = 1$. Si $V = 0$ → fallada de pàgina; si l’escriptura troba $E = 0$ → excepció de protecció.

Accés	Adreça	VPN	V	E	Resultat
a	L `0x0FF0`	0	1	0	Èxit (la lectura no mira E); PPN 3
b	E `0x1234`	1	1	1	Èxit; PPN 7
c	L `0x2000`	2	0	—	Fallada de pàgina ($V = 0$)
d	E `0x3100`	3	1	0	Excepció de protecció (escriptura amb $E = 0$)
e	E `0x0010`	0	1	0	Excepció de protecció (escriptura amb $E = 0$)

Observació: els casos a) i e) accedeixen a la mateixa pàgina (VPN 0, només lectura). La lectura té èxit i l’escriptura provoca excepció: és el patró típic d’una pàgina de codi o de dades constants, protegida contra modificacions accidentals.

26.4 Integració del TLB i la memòria cau

Exemple 26.6: Solució: flux VIPT i condició antialiàsing

Enunciat: Problema 17.9.

Pàgines de 4 KiB, memòria cau de dades de correspondència directa amb 64 línies amb blocs de 32 B, TLB completament associatiu de 16 entrades. Adreces lògiques de 32 bits.

a) Descomposició de l’adreça lògica:

Desplaçament dins la pàgina: $\log_2(4\text{ KiB}) = 12$ bits.
VPN: $32 - 12 = 20$ bits.
Desplaçament dins el bloc: $\log_2(32) = 5$ bits.
Índex de la memòria cau: $\log_2(64) = 6$ bits.

\[\underbrace{b_{31} \cdots b_{12}}_{\text{VPN (20)}} \; \underbrace{b_{11} \cdots b_0}_{\text{desplaçament pàgina (12)}}, \qquad \underbrace{b_{31} \cdots b_{11}}_{\text{etiqueta (21)}} \; \underbrace{b_{10} \cdots b_5}_{\text{índex cau (6)}} \; \underbrace{b_4 \cdots b_0}_{\text{despl. bloc (5)}}\]

Cal notar que índex + desplaçament de bloc $= 6 + 5 = 11$ bits, tots dins dels 12 bits del desplaçament de pàgina.

b) Lectura amb encert de TLB i encert de memòria cau (esquema VIPT):

La CPU genera l’adreça lògica. En paral·lel: els bits d’índex (b10–b5, part del desplaçament) seleccionen la línia de la memòria cau, i el VPN (b31–b12) s’envia al TLB.
El TLB troba el VPN (encert) i retorna el PPN.
La memòria cau llegeix l’etiqueta i les dades de la línia indexada.
Es compara l’etiqueta física —el PPN i el bit b11, que és del desplaçament de pàgina i no canvia en traduir l’adreça— amb l’etiqueta llegida de la memòria cau → coincideixen → encert de memòria cau.
Es lliura la dada (el desplaçament de bloc, b4–b0, selecciona el byte/paraula).

Com que la traducció i la indexació es fan alhora, el temps d’accés és pràcticament el d’accedir a la memòria cau.

c) Fallada de TLB però pàgina present a memòria:

El VPN no és al TLB → fallada de TLB. Es llegeix la PTE de la taula de pàgines a memòria (adreça del registre de taula de pàgines + VPN × 4, la mida d’una PTE).
La PTE té $V = 1$ (pàgina present) → no hi ha fallada de pàgina. L’MMU copia la PTE al TLB (entrada lliure o reemplaçament LRU), sense interrompre el programa.
La traducció continua amb el PPN de la PTE: l’etiqueta física (el PPN i b11) es compara amb la de la memòria cau → encert de memòria cau → dada.

El cost addicional respecte de b) és un accés a memòria per llegir la PTE (amb la taula de pàgines plana del tema; amb una taula multinivell, un per nivell).

d) Com s’explica a Secció 8.7.3, perquè una memòria cau VIPT no pateixi aliàsing (aliasing) (i es comporti, pel que fa a la selecció de la línia, com una PIPT), l’índex de la memòria cau ha d’usar només bits del desplaçament de pàgina (bits que no canvien en la traducció). Això equival a:

\[N_C \cdot B \leq T\]

on $N_C$ és el nombre de conjunts, $B$ la mida del bloc (el producte és la mida d’una via) i $T$ la mida de pàgina. Aquí, la memòria cau és de correspondència directa, amb $N_C = 64$ conjunts d’una línia, $B = 32$ bytes i $T = 4 \text{ KiB}$:

\[64 \times 32 = 2 \text{ KiB} \leq 4 \text{ KiB} \quad \checkmark\]

es compleix (índex + desplaçament de bloc = 11 bits $\leq$ 12 bits de desplaçament de pàgina), de manera que la memòria cau no pateix aliàsing: l’índex selecciona la mateixa línia amb l’adreça lògica que amb la física.

Exemple 26.7: Solució: fallades de memòria cau i TLB per files vs. columnes

Enunciat: Problema 17.10.

Enters de 4 B. MC: 4 vies × 64 conjunts × 32 B/bloc $= 8$ KiB; un bloc conté $32/4 = 8$ enters. TLB de 32 entrades, pàgines de 8 KiB (2048 enters per pàgina; cada fila d’A ocupa 1024 enters $= 4$ KiB, és a dir, mitja pàgina). La matriu A[128][1024] ocupa $512$ KiB $= 64$ pàgines $= 16\,384$ blocs.

Adreça de l’element A[i][j]: byte $= (i \cdot 1024 + j) \cdot 4 = i \cdot 4096 + j \cdot 4$.

Conjunt d’MC: $\left\lfloor \dfrac{i \cdot 4096 + j \cdot 4}{32} \right\rfloor \bmod 64 = \left(i \cdot 128 + \lfloor j/8 \rfloor\right) \bmod 64 = \lfloor j/8 \rfloor \bmod 64$ → depèn només de $j$.
Pàgina: $\left\lfloor \dfrac{i \cdot 4096 + j \cdot 4}{8192} \right\rfloor = \lfloor i/2 \rfloor$ → depèn només de $i$.

Versió A (recorregut per files, accés seqüencial en memòria):

MC: cada bloc de 8 enters es carrega un cop i s’aprofita 8 vegades. Fallades $= 16\,384$ blocs $= \mathbf{16\,384}$ (1 de cada 8 accessos).
TLB: es recorren les 64 pàgines en ordre, una fallada per pàgina $= \mathbf{64}$.

Versió B (recorregut per columnes, stride de 4096 B):

MC: per a un $j$ fix, els 128 elements A[0..127][j] són blocs diferents que mapen tots al mateix conjunt ($\lfloor j/8 \rfloor \bmod 64$, independent de $i$). Amb només 4 vies, els 128 blocs s’expulsen entre ells abans de poder-se reutilitzar a la iteració següent de $j$. Cap reutilització: totes les referències fallen $= 128 \times 1024 = \mathbf{131\,072}$.
TLB: per a cada $j$, el bucle intern recorre A[0..127][j], que toca les pàgines $\lfloor i/2 \rfloor = 0, 0, 1, 1, \ldots, 63, 63$: 64 pàgines diferents, una fallada cadascuna (la segona visita, $i$ senar, encerta). Són 64 fallades per cada valor de $j$: $64 \times 1024 = \mathbf{65\,536}$.

	Fallades d’MC	Fallades de TLB
Versió A (per files)	16 384	64
Versió B (per columnes)	131 072	65 536

La versió B multiplica per 8 les fallades d’MC i per 1024 les de TLB. El recorregut per columnes no només destrueix la localitat espacial (cada accés toca un bloc i una pàgina nous), sinó que a més pateix un conflicte de conjunt sistemàtic: com que l’stride entre files (4096 B) és múltiple del nombre de conjunts per la mida de bloc, totes les files competeixen pel mateix conjunt de l’MC.

--- number-sections: true language: crossref-exr-title: "Problema" crossref-exr-prefix: "Problema" --- # {{< var tema8 >}} {#sec-tema-mv-solucions} ## Traducció d'adreces i fallada de pàgina ::: {#sol-t8-mv-paginacio-basica .callout-tip} ## Solució: paginació bàsica i traça LRU **Enunciat**: @exr-t8-mv-paginacio-basica. Memòria virtual de 16 MiB ($2^{24}$ B → 24 bits d'adreça lògica), memòria física de 16 KiB ($2^{14}$ B → 14 bits d'adreça física) i pàgines de 256 B ($2^8$ B → desplaçament de 8 bits). La descomposició VPN/desplaçament segueix la @sec-mv-traduccio: - VPN: $24 - 8 = 16$ bits → $2^{16} = 65\,536$ pàgines virtuals. - PPN: $14 - 8 = 6$ bits → $2^6 = 64$ marcs de pàgina. **a)** La taula de pàgines té una entrada per pàgina virtual: $2^{16} = 65\,536$ entrades. Cada entrada conté el PPN (6 bits) més el bit V i el bit D: $$6 + 1 + 1 = 8 \text{ bits} = 1 \text{ byte/entrada}$$ $$\text{Mida taula de pàgines} = 2^{16} \times 1 \text{ B} = 64 \text{ KiB}$$ **b)** El VPN és $\lfloor \text{adreça} / \texttt{0x100} \rfloor$ (els dos dígits hexadecimals inferiors són el desplaçament de 8 bits). Cada programa pot tenir com a màxim 3 pàgines a memòria física, amb reemplaçament LRU. Seqüència de VPN: 0, 1, 1, 2, 0, 1, 4, 5, 1. La pila LRU s'escriu de la pàgina *most recently used* (MRU), la usada més recentment, a la menys recent. | Adreça | A — Pàg. | B — Fallada | C — Reempl. | Pila LRU (MRU→LRU) | | :---: | :---: | :---: | :---: | :---: | | `000023` | `0` | **Sí** | — | 0 | | `000101` | `1` | **Sí** | — | 1, 0 | | `000102` | `1` | No | — | 1, 0 | | `000200` | `2` | **Sí** | — | 2, 1, 0 | | `000010` | `0` | No | — | 0, 2, 1 | | `000111` | `1` | No | — | 1, 0, 2 | | `000416` | `4` | **Sí** | `2` | 4, 1, 0 | | `000520` | `5` | **Sí** | `0` | 5, 4, 1 | | `000101` | `1` | No | — | 1, 5, 4 | : {tbl-colwidths="[18,14,16,16,36]" .striped} Hi ha **5 fallades** i 4 encerts. A `000416` s'expulsa la pàgina 2 (la menys recentment usada, desplaçada pels encerts a 0 i 1); a `000520` s'expulsa la pàgina 0. ::: ::: {#sol-t8-mv-multinivell .callout-tip} ## Solució: taula de pàgines de dos nivells **Enunciat**: @exr-t8-mv-multinivell. Adreces de 32 bits, pàgines de 4 KiB ($2^{12}$ B), entrades de 4 B, dos nivells amb repartiment simètric. **a)** Desplaçament: $\log_2(4\text{ KiB}) = 12$ bits. Resten $32 - 12 = 20$ bits d'índex, repartits simètricament: $$\underbrace{10 \text{ bits}}_{\text{índex N1}} \; \underbrace{10 \text{ bits}}_{\text{índex N2}} \; \underbrace{12 \text{ bits}}_{\text{desplaçament}}$$ **b)** Cada taula (de qualsevol nivell) té $2^{10} = 1024$ entrades de 4 B: $$2^{10} \times 4 \text{ B} = 4 \text{ KiB}$$ Tant la taula de primer nivell com cada taula de segon nivell ocupen **4 KiB** (exactament una pàgina). **c)** Cada entrada del primer nivell pot apuntar a una taula de segon nivell: com a màxim $2^{10} = 1024$ taules de segon nivell. Mida total en el **pitjor cas** (totes assignades): $$\underbrace{4 \text{ KiB}}_{\text{N1}} + 1024 \times \underbrace{4 \text{ KiB}}_{\text{N2}} = 4 \text{ KiB} + 4 \text{ MiB}$$ **d)** Una taula de **nivell únic** tindria $2^{20}$ entrades de 4 B $= 4$ MiB. La jerarquia de dos nivells, en el pitjor cas, ocupa lleugerament **més** (4 MiB + 4 KiB: el sobrecost del directori de primer nivell). L'avantatge apareix en el **cas típic**, en què el procés només usa una fracció de l'espai lògic: només cal assignar les taules de segon nivell de les regions realment utilitzades. Per exemple, un procés que toqui codi, dades i pila en 3 regions disjuntes necessita la taula de primer nivell (4 KiB) i tres de segon nivell (una per regió), és a dir, **16 KiB** en lloc de 4 MiB. Amb un nivell únic, en canvi, sempre cal reservar els 4 MiB sencers encara que la majoria d'entrades siguin invàlides. ::: ::: {#sol-t8-mv-taula-referencies .callout-tip} ## Solució: traça de la taula de pàgines amb accés a disc **Enunciat**: @exr-t8-mv-taula-referencies. Adreça lògica de 16 bits, física de 15 bits, pàgines de 8 KiB ($2^{13}$ → desplaçament de 13 bits). VPN: $16 - 13 = 3$ bits (8 pàgines); PPN: $15 - 13 = 2$ bits (4 marcs). El VPN és $\lfloor \text{adreça}/\texttt{0x2000} \rfloor$ (els 3 bits de més pes de l'adreça). Estat inicial: PPN 0 = VPN 2, PPN 1 = VPN 3, PPN 2 = VPN 4, PPN 3 lliure. Ordre LRU (MRU→LRU): VPN 3, VPN 2, VPN 4. Cap pàgina està modificada ($D = 0$). | Adreça | VPN | PPN | Fallada | Lect. disc | Escr. disc | Reempl. VPN | Reempl. PPN | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | E `F458` | 7 | 3 | **Sí** | Sí | No | — | — | | E `8666` | 4 | 2 | No | No | No | — | — | | L `1BBF` | 0 | 0 | **Sí** | Sí | No | 2 | 0 | | E `5C44` | 2 | 1 | **Sí** | Sí | No | 3 | 1 | | L `6600` | 3 | 3 | **Sí** | Sí | **Sí** | 7 | 3 | | L `4000` | 2 | 1 | No | No | No | — | — | : {tbl-colwidths="[12,8,8,12,13,13,17,17]" .striped} Punts clau: - `E F458` (VPN 7): fallada amb el marc lliure PPN 3; com que és escriptura, queda $D = 1$. - `L 1BBF` (VPN 0) i `E 5C44` (VPN 2): cap marc lliure; s'expulsen les pàgines més antigues (VPN 2 i VPN 3), totes dues amb $D = 0$, de manera que no cal escriure-les a disc. - `L 6600` (VPN 3): s'expulsa la pàgina del VPN 7, que té $D = 1$ → **cal escriure-la primer a disc** (única escriptura a disc de la traça). - `L 4000` (VPN 2): encert, la pàgina segueix a PPN 1. Estat final de la taula de pàgines: | VPN | V | D | PPN | | :---: | :---: | :---: | :---: | | 0 | 1 | 0 | 0 | | 1 | 0 | 0 | — | | 2 | 1 | 1 | 1 | | 3 | 1 | 0 | 3 | | 4 | 1 | 1 | 2 | | 5–7 | 0 | 0 | — | : {.striped} Estat final de la memòria física: PPN 0 = VPN 0, PPN 1 = VPN 2, PPN 2 = VPN 4, PPN 3 = VPN 3. ::: ## TLB ::: {#sol-t8-tlb-estat .callout-tip} ## Solució: traça del TLB i de la taula de pàgines **Enunciat**: @exr-t8-tlb-estat. Pàgines de 4 KiB → $\text{VPN} = \lfloor \text{adreça}/4096 \rfloor$. TLB de 4 entrades completament associatiu, LRU (vegeu @sec-mv-tlb). La quarta entrada ($V = 0$) és lliure i s'omple en la primera fallada; mentre n'hi hagi cap de lliure, el reemplaçament LRU no actua. Ordre LRU inicial de les vàlides (MRU→LRU): VPN 11, VPN 7, VPN 3. **a) Llista 1.** VPN: 0, 7, 3, 3, 1, 1, 2. | Ref. | VPN | Fallada TLB | Fallada pàgina | PPN | | :---: | :---: | :---: | :---: | :---: | | 4095 | 0 | **Sí** | No | 5 | | 31272 | 7 | No | No | 4 | | 15789 | 3 | No | No | 6 | | 15000 | 3 | No | No | 6 | | 7193 | 1 | **Sí** | **Sí** | 13 | | 4096 | 1 | No | No | 13 | | 8912 | 2 | **Sí** | **Sí** | 14 | : {.striped} - 4095 (VPN 0): fallada de TLB; l'MMU llegeix la PTE, que té $V = 1$ (PPN 5), i la copia a l'entrada lliure, sense fallada de pàgina. - 7193 (VPN 1): fallada de TLB i la PTE té $V = 0$ → **fallada de pàgina**; l'SO carrega la pàgina i li assigna PPN 13. En reexecutar l'accés, l'MMU copia la PTE al TLB reemplaçant l'entrada del VPN 11 (l'única no reutilitzada des de l'inici → la més antiga). - 8912 (VPN 2): fallada de TLB i $V = 0$ → fallada de pàgina (PPN 14); en reexecutar, es reemplaça l'entrada del VPN 0 (la més antiga de la pila en aquest punt). TLB final: (VPN 1, PPN 13), (VPN 7, PPN 4), (VPN 3, PPN 6), (VPN 2, PPN 14). Taula de pàgines: VPN 1 → V 1/PPN 13, VPN 2 → V 1/PPN 14. Total: 3 fallades de TLB, 2 de les quals són fallades de pàgina. Ordre LRU final, de la més recent a la més antiga: VPN 2, 1, 3 i 7. **Llista 2** (des de l'estat inicial). VPN: 2, 7, 4, 11, 9, 4, 11. | Ref. | VPN | Fallada TLB | Fallada pàgina | PPN | | :---: | :---: | :---: | :---: | :---: | | 9452 | 2 | **Sí** | **Sí** | 13 | | 30964 | 7 | No | No | 4 | | 19136 | 4 | **Sí** | No | 9 | | 46502 | 11 | No | No | 12 | | 38110 | 9 | **Sí** | **Sí** | 14 | | 17653 | 4 | No | No | 9 | | 47480 | 11 | No | No | 12 | : {.striped} - 9452 (VPN 2): fallada de TLB i $V = 0$ → fallada de pàgina (PPN 13); s'omple l'entrada lliure. - 19136 (VPN 4): fallada de TLB però $V = 1$ (PPN 9) → sense fallada de pàgina. Es reemplaça l'entrada del VPN 3 (la més antiga segons l'ordre inicial 11 > 7 > 3). - 38110 (VPN 9): fallada de TLB i $V = 0$ → fallada de pàgina (PPN 14); es reemplaça l'entrada del VPN 2 (la menys recentment usada). - 46502 i 47480 (VPN 11): encerts, perquè l'entrada del VPN 11 era la més recent inicialment i no s'ha expulsat. TLB final: (VPN 11, PPN 12), (VPN 7, PPN 4), (VPN 4, PPN 9), (VPN 9, PPN 14). Taula de pàgines: VPN 2 → V 1/PPN 13, VPN 9 → V 1/PPN 14. Total: 3 fallades de TLB, 2 de les quals són fallades de pàgina. Ordre LRU final: VPN 11, 4, 9 i 7. **b)** Amb pàgines de 16 KiB, $\text{VPN} = \lfloor \text{adreça}/16\,384 \rfloor$ i moltes adreces que abans queien en pàgines diferents passen a compartir pàgina: - Llista 1: pàgines 0, 1, 0, 0, 0, 0, 0 → només **2 pàgines diferents** (abans 5). - Llista 2: pàgines 0, 1, 1, 2, 2, 1, 2 → només **3 pàgines diferents** (abans 5). En els dos casos el nombre de pàgines diferents accedides baixa, cosa que **redueix el nombre potencial de fallades de TLB d'arrencada en fred** (*cold-start*: una fallada per pàgina nova referenciada). No es pot donar, però, un nombre exacte de fallades comparable al de l'apartat a): l'estat inicial del TLB (VPN 11, 7, 3 vàlides) es va definir per a pàgines de 4 KiB i deixa de tenir sentit en reinterpretar-lo amb una mida de pàgina diferent — els VPN ja no designen els mateixos rangs d'adreces lògiques, de manera que no hi ha una manera coherent de «traduir» aquell estat inicial concret al nou context. En general, augmentar la mida de pàgina **redueix el nombre de pàgines diferents** accedides i, per tant, les fallades de TLB d'arrencada en fred, a canvi de més fragmentació interna i transferències a disc més grans en cada fallada de pàgina. **c)** Mida de la taula de pàgines (nivell únic): $$\text{Nre. entrades} = \frac{2^{\text{bits adreça}}}{\text{mida pàgina}}, \qquad \text{Mida taula de pàgines} = \text{Nre. entrades} \times \text{mida entrada}$$ - 32 bits, pàgines de 4 KiB, entrades de 4 B: $\dfrac{2^{32}}{2^{12}} \times 4 = 2^{20} \times 4 = \mathbf{4 \text{ MiB}}$. - 64 bits, pàgines de 16 KiB, entrades de 8 B: $\dfrac{2^{64}}{2^{14}} \times 8 = 2^{50} \times 2^3 = 2^{53} \text{ B} = \mathbf{8 \text{ PiB}}$. El segon resultat (8 PiB **per procés**) és inviable i justifica les taules de pàgines multinivell de @sol-t8-mv-multinivell. ::: ## Protecció ::: {#sol-t8-mv-proteccio .callout-tip} ## Solució: bit de permís d'escriptura i excepcions **Enunciat**: @exr-t8-mv-proteccio. Pàgines de 4 KiB → $\text{VPN} = \lfloor \text{adreça}/\texttt{0x1000} \rfloor$. Criteri: una **lectura** té èxit sempre que $V = 1$ (el bit E només restringeix escriptures); una **escriptura** requereix $V = 1$ **i** $E = 1$. Si $V = 0$ → fallada de pàgina; si l'escriptura troba $E = 0$ → excepció de protecció. | Accés | Adreça | VPN | V | E | Resultat | | :---: | :---: | :---: | :---: | :---: | :--- | | a | L `0x0FF0` | 0 | 1 | 0 | **Èxit** (la lectura no mira E); PPN 3 | | b | E `0x1234` | 1 | 1 | 1 | **Èxit**; PPN 7 | | c | L `0x2000` | 2 | 0 | — | **Fallada de pàgina** ($V = 0$) | | d | E `0x3100` | 3 | 1 | 0 | **Excepció de protecció** (escriptura amb $E = 0$) | | e | E `0x0010` | 0 | 1 | 0 | **Excepció de protecció** (escriptura amb $E = 0$) | : {tbl-colwidths="[8,14,8,8,8,54]" .striped} Observació: els casos a) i e) accedeixen a la **mateixa pàgina** (VPN 0, només lectura). La lectura té èxit i l'escriptura provoca excepció: és el patró típic d'una pàgina de codi o de dades constants, protegida contra modificacions accidentals. ::: ## Integració del TLB i la memòria cau ::: {#sol-t8-mv-tlb-cau .callout-tip} ## Solució: flux VIPT i condició antialiàsing **Enunciat**: @exr-t8-mv-tlb-cau. Pàgines de 4 KiB, memòria cau de dades de correspondència directa amb 64 línies amb blocs de 32 B, TLB completament associatiu de 16 entrades. Adreces lògiques de 32 bits. **a)** Descomposició de l'adreça lògica: - Desplaçament dins la pàgina: $\log_2(4\text{ KiB}) = 12$ bits. - VPN: $32 - 12 = 20$ bits. - Desplaçament dins el bloc: $\log_2(32) = 5$ bits. - Índex de la memòria cau: $\log_2(64) = 6$ bits. $$\underbrace{b_{31} \cdots b_{12}}_{\text{VPN (20)}} \; \underbrace{b_{11} \cdots b_0}_{\text{desplaçament pàgina (12)}}, \qquad \underbrace{b_{31} \cdots b_{11}}_{\text{etiqueta (21)}} \; \underbrace{b_{10} \cdots b_5}_{\text{índex cau (6)}} \; \underbrace{b_4 \cdots b_0}_{\text{despl. bloc (5)}}$$ Cal notar que índex + desplaçament de bloc $= 6 + 5 = 11$ bits, tots dins dels 12 bits del desplaçament de pàgina. **b) Lectura amb encert de TLB i encert de memòria cau** (esquema VIPT): 1. La CPU genera l'adreça lògica. **En paral·lel**: els bits d'índex (b10–b5, part del desplaçament) seleccionen la línia de la memòria cau, i el VPN (b31–b12) s'envia al TLB. 2. El TLB troba el VPN (encert) i retorna el PPN. 3. La memòria cau llegeix l'etiqueta i les dades de la línia indexada. 4. Es compara l'etiqueta física —el PPN i el bit b11, que és del desplaçament de pàgina i no canvia en traduir l'adreça— amb l'etiqueta llegida de la memòria cau → coincideixen → **encert de memòria cau**. 5. Es lliura la dada (el desplaçament de bloc, b4–b0, selecciona el byte/paraula). Com que la traducció i la indexació es fan alhora, el temps d'accés és pràcticament el d'accedir a la memòria cau. **c) Fallada de TLB però pàgina present a memòria**: 1. El VPN no és al TLB → **fallada de TLB**. Es llegeix la PTE de la taula de pàgines a memòria (adreça del registre de taula de pàgines + VPN × 4, la mida d'una PTE). 2. La PTE té $V = 1$ (pàgina present) → **no hi ha fallada de pàgina**. L'MMU copia la PTE al TLB (entrada lliure o reemplaçament LRU), sense interrompre el programa. 3. La traducció continua amb el PPN de la PTE: l'etiqueta física (el PPN i b11) es compara amb la de la memòria cau → encert de memòria cau → dada. El cost addicional respecte de b) és **un accés a memòria** per llegir la PTE (amb la taula de pàgines plana del tema; amb una taula multinivell, un per nivell). **d)** Com s'explica a @sec-mv-vipt, perquè una memòria cau **VIPT** no pateixi **aliàsing** (*aliasing*) (i es comporti, pel que fa a la selecció de la línia, com una **PIPT**), l'índex de la memòria cau ha d'usar **només bits del desplaçament de pàgina** (bits que no canvien en la traducció). Això equival a: $$N_C \cdot B \leq T$$ on $N_C$ és el nombre de conjunts, $B$ la mida del bloc (el producte és la mida d'una via) i $T$ la mida de pàgina. Aquí, la memòria cau és de correspondència directa, amb $N_C = 64$ conjunts d'una línia, $B = 32$ bytes i $T = 4 \text{ KiB}$: $$64 \times 32 = 2 \text{ KiB} \leq 4 \text{ KiB} \quad \checkmark$$ es compleix (índex + desplaçament de bloc = 11 bits $\leq$ 12 bits de desplaçament de pàgina), de manera que la memòria cau no pateix aliàsing: l'índex selecciona la mateixa línia amb l'adreça lògica que amb la física. ::: ::: {#sol-t8-mv-cache-tlb .callout-tip} ## Solució: fallades de memòria cau i TLB per files vs. columnes **Enunciat**: @exr-t8-mv-cache-tlb. Enters de 4 B. MC: 4 vies × 64 conjunts × 32 B/bloc $= 8$ KiB; un bloc conté $32/4 = 8$ enters. TLB de 32 entrades, pàgines de 8 KiB (2048 enters per pàgina; cada fila d'`A` ocupa 1024 enters $= 4$ KiB, és a dir, mitja pàgina). La matriu `A[128][1024]` ocupa $512$ KiB $= 64$ pàgines $= 16\,384$ blocs. Adreça de l'element `A[i][j]`: byte $= (i \cdot 1024 + j) \cdot 4 = i \cdot 4096 + j \cdot 4$. - Conjunt d'MC: $\left\lfloor \dfrac{i \cdot 4096 + j \cdot 4}{32} \right\rfloor \bmod 64 = \left(i \cdot 128 + \lfloor j/8 \rfloor\right) \bmod 64 = \lfloor j/8 \rfloor \bmod 64$ → **depèn només de $j$**. - Pàgina: $\left\lfloor \dfrac{i \cdot 4096 + j \cdot 4}{8192} \right\rfloor = \lfloor i/2 \rfloor$ → **depèn només de $i$**. **Versió A** (recorregut per files, accés seqüencial en memòria): - MC: cada bloc de 8 enters es carrega un cop i s'aprofita 8 vegades. Fallades $= 16\,384$ blocs $= \mathbf{16\,384}$ (1 de cada 8 accessos). - TLB: es recorren les 64 pàgines en ordre, una fallada per pàgina $= \mathbf{64}$. **Versió B** (recorregut per columnes, *stride* de 4096 B): - MC: per a un $j$ fix, els 128 elements `A[0..127][j]` són blocs diferents que mapen **tots al mateix conjunt** ($\lfloor j/8 \rfloor \bmod 64$, independent de $i$). Amb només 4 vies, els 128 blocs s'expulsen entre ells abans de poder-se reutilitzar a la iteració següent de $j$. **Cap reutilització**: totes les referències fallen $= 128 \times 1024 = \mathbf{131\,072}$. - TLB: per a cada $j$, el bucle intern recorre `A[0..127][j]`, que toca les pàgines $\lfloor i/2 \rfloor = 0, 0, 1, 1, \ldots, 63, 63$: **64 pàgines diferents**, una fallada cadascuna (la segona visita, $i$ senar, encerta). Són 64 fallades per cada valor de $j$: $64 \times 1024 = \mathbf{65\,536}$. | | Fallades d'MC | Fallades de TLB | | :--- | :---: | :---: | | Versió A (per files) | 16 384 | 64 | | Versió B (per columnes) | 131 072 | 65 536 | : {tbl-colwidths="[40,30,30]" .striped} La versió B multiplica per 8 les fallades d'MC i per 1024 les de TLB. El recorregut per columnes no només destrueix la localitat espacial (cada accés toca un bloc i una pàgina nous), sinó que a més pateix un **conflicte de conjunt** sistemàtic: com que l'*stride* entre files (4096 B) és múltiple del nombre de conjunts per la mida de bloc, totes les files competeixen pel mateix conjunt de l'MC. :::