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

Tema 8: Memòria virtual

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

Vegeu Secció 8.2, Secció 8.3 i Secció 8.4.

Problema 17.1 Es disposa d’un sistema amb memòria virtual paginada amb les característiques següents:

  • Mida de la memòria virtual: 16 MiB.
  • Mida de la memòria física: 16 KiB.
  • Mida de les pàgines: 256 bytes.

Cada programa pot tenir a memòria física un màxim de 3 pàgines simultàniament. En cas que calgui alliberar una pàgina, s’usa l’algorisme de reemplaçament LRU.

  1. Indiqueu les dimensions de la taula de pàgines de cada programa, tenint en compte que cada entrada té un bit de validesa (V) i un bit de modificació (D).
  2. La taula següent mostra una llista d’adreces lògiques generades pel processador. Ompliu-la indicant, per a cada adreça, el número de pàgina (columna A), si es produeix una fallada de pàgina (columna B) i, en cas de reemplaçament, el número de pàgina reemplaçada (columna C). Considereu que inicialment no hi ha cap pàgina carregada a memòria física.
Adreça (hex) A — Núm. pàgina (hex) B — Fallada de pàgina C — Pàgina reemplaçada (hex)
000023
000101
000102
000200
000010
000111
000416
000520
000101

Problema 17.2 Un sistema té adreces lògiques de 32 bits, pàgines de 4 KiB i taules de pàgines de dos nivells. Cada entrada de la taula ocupa 4 bytes.

  1. Quants bits s’usen per al desplaçament dins la pàgina, per a l’índex de primer nivell i per a l’índex de segon nivell (suposeu una divisió simètrica dels bits d’índex)?
  2. Quina és la mida d’una taula de pàgines de primer nivell? I d’una de segon nivell?
  3. Quin és el nombre màxim de taules de segon nivell que pot tenir un procés? Quina és la mida total de la jerarquia de taules en el pitjor cas?
  4. Compareu la mida total de la jerarquia de dos nivells (pitjor cas) amb la d’una taula de pàgines de nivell únic. Quin avantatge té la jerarquia en el cas típic en què un procés usa poca memòria?

Problema 17.3 Considereu un processador amb memòria virtual paginada amb les característiques següents:

  • 16 bits d’adreça lògica, 15 bits d’adreça física.
  • Mida de les pàgines: 8 KiB.
  • Reemplaçament LRU.

El contingut inicial de la taula de pàgines és:

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

El contingut inicial de la memòria física és:

PPN VPN
0 2
1 3
2 4
3 —

L’ordre d’accés recent és: PPN 1 (VPN 3) el més recent, PPN 0 (VPN 2) el segon i PPN 2 (VPN 4) el més antic.

Ompliu la taula següent per a la seqüència de referències donada (E = escriptura, L = lectura). Indiqueu també el contingut final de la taula de pàgines i de la memòria física.

Adreça lògica (hex) VPN PPN Fallada de pàgina Lectura disc Escriptura disc Pàg. reemplaçada VPN Pàg. reemplaçada PPN
E F458
E 8666
L 1BBF
E 5C44
L 6600
L 4000

Problema 17.4 Un sistema experimental gestiona la memòria virtual amb paginació i algorisme LRU. Té 64 KiB de memòria virtual, 8 KiB de memòria física i pàgines d’1 KiB. La taula de pàgines ocupa sempre l’últim marc de pàgina.

Una aplicació s’ubica a l’espai lògic de la manera següent:

  • Codi: adreces 0x0000–0x03FF.
  • Dades: adreces 0x0400–0x47FF.

Dins les dades hi ha una matriu declarada en C com:

C
short MAT[32][256];

emmagatzemada a partir de l’adreça base 0x0400. Els short es codifiquen en 16 bits (2 bytes). La resta de variables i la pila s’emmagatzemen a partir de 0x4400. El compilador reserva registres per a i i j.

Considereu el fragment de codi del Codi 17.1:

Codi 17.1: Bucles que escriuen la matriu MAT. 
C
for (i = 0; i < 32; i++)
    for (j = 0; j < 256; j++)
        MAT[i][j] = i + j;

Abans d’executar el Codi 17.1, la taula de pàgines indica que només hi ha carregada a memòria física la pàgina corresponent al codi de l’aplicació.

  1. Quins elements de MAT es porten a memòria física en la primera fallada de pàgina?
  2. Indiqueu, justificant-ho, el nombre total de fallades de pàgina que es produiran.
  3. En alguns llenguatges com ara FORTRAN, les matrius s’emmagatzemen per columnes. Considerant aquest emmagatzematge, quins elements de MAT es portarien a memòria física en la primera fallada de pàgina?
  4. Considerant l’emmagatzematge per columnes, indiqueu el nombre total de fallades de pàgina que es produirien.

17.2 TLB

Vegeu Secció 8.5.

Problema 17.5 Considereu un sistema amb memòria virtual de pàgines de 4 KiB, un TLB de 4 entrades completament associatiu i reemplaçament LRU.

El contingut inicial del TLB és:

V VPN PPN
1 11 12
1 7 4
1 3 6
0 — —

(La quarta entrada és lliure.)

El contingut inicial de la taula de pàgines és:

VPN V PPN
0 1 5
1 0 —
2 0 —
3 1 6
4 1 9
5 1 11
6 0 —
7 1 4
8 0 —
9 0 —
10 1 3
11 1 12

A les pàgines que es portin a memòria física se’ls assignaran PPN correlatius a partir del primer de lliure (13, 14, etc.). Inicialment, l’ordre d’ús de les entrades vàlides del TLB, de la més recentment usada a la més antiga, és VPN 11, VPN 7, VPN 3.

  1. Per a cadascuna de les dues llistes d’adreces lògiques següents, indiqueu l’estat final del TLB i de la taula de pàgines, i per a cada referència si es produeix una fallada de TLB i si es produeix una fallada de pàgina:
    • Llista 1: 4095, 31272, 15789, 15000, 7193, 4096, 8912.
    • Llista 2: 9452, 30964, 19136, 46502, 38110, 17653, 47480.
  2. Raoneu, sense refer la traça completa, com canviaria el nombre total de fallades de TLB de cada llista si la mida de pàgina fos de 16 KiB en comptes de 4 KiB.
  3. Calculeu la mida de la taula de pàgines per als dos sistemes següents:
Mida adreces lògiques Mida pàgina Mida PTE
32 bits 4 KiB 4 bytes
64 bits 16 KiB 8 bytes

Problema 17.6 Considereu el codi assemblador RISC-V del Codi 17.2, on a l’etiqueta A li correspon l’adreça 0x10010000:

Codi 17.2: Bucle que llegeix i escriu paraules a partir de A. 
RV32I
        la      s0, A
        li      s1, 0
        li      s2, 512000
for:
        bge     s1, s2, fi
        slli    t0, s1, 2
        add     t0, s0, t0
        lw      t1, 0(t0)
        li      t3, 8192
        add     t3, t0, t3
        lw      t2, 0(t3)
        add     t2, t2, t1
        sw      t2, 0(t3)
        li      t3, 16384
        add     t3, t0, t3
        sw      t2, 0(t3)
        addi    s1, s1, 512
        j       for
fi:

Suposant pàgines de 8 KiB i un TLB de 4 entrades completament associatiu amb reemplaçament LRU:

  1. Per a cadascuna de les instruccions d’accés a dades de memòria (lw/sw) i per a les primeres 5 iteracions del bucle, indiqueu a quina pàgina de la memòria virtual s’accedeix.
  2. Indiqueu el nombre total de fallades del TLB de dades en tot el bucle (només es consideren els accessos a dades; les captures d’instruccions passen per un TLB d’instruccions a part, que no es té en compte).
  3. Responeu les mateixes preguntes suposant pàgines de 4 KiB.

Problema 17.7 Considereu el codi assemblador RISC-V del Codi 17.3, on a l’etiqueta A li correspon l’adreça 0x10010000:

Codi 17.3: Bucle que llegeix i escriu mitges paraules a partir de A. 
RV32I
        la      s0, A
        li      s1, 0
        li      s2, 4096
for:
        bge     s1, s2, fi
        add     t0, s1, s1
        add     t0, s0, t0
        lh      t1, 0(t0)
        lh      t2, 1024(t0)
        add     t2, t2, t1
        sh      t2, 1024(t0)
        li      t3, 4096
        add     t3, t0, t3
        sh      t2, 0(t3)
        addi    s1, s1, 1
        j       for
fi:

Suposant pàgines d’1 KiB i un TLB completament associatiu de 4 entrades amb reemplaçament LRU:

  1. Indiqueu el nombre de pàgines diferents accedides per a cadascuna de les quatre instruccions d’accés a dades de memòria (lh/sh).
  2. Calculeu el nombre de fallades del TLB de dades en tot el bucle (només es consideren els accessos a dades, no les captures d’instruccions).
  3. Es vol redissenyar el TLB, mantenint el reemplaçament LRU, per minimitzar el nombre de fallades en aquest programa. Indiqueu quin és el nombre mínim de fallades assolible i quin és el nombre mínim d’entrades de TLB necessàries per obtenir-lo.
  4. Repetiu els apartats anteriors considerant pàgines de 4 KiB.

17.3 Protecció

Vegeu Secció 8.6.

Problema 17.8 Un sistema de memòria virtual amb pàgines de 4 KiB disposa, a cada entrada de la taula de pàgines, d’un bit de validesa (V), un bit de modificació (D) i un bit de permís d’escriptura (E: 1 = lectura i escriptura; 0 = només lectura).

VPN V D E PPN
0 1 0 0 3
1 1 1 1 7
2 0 0 1 —
3 1 0 0 5

Per a cada accés de la llista següent, indiqueu si té èxit, provoca una fallada de pàgina o provoca una excepció de protecció:

  1. Lectura de l’adreça lògica 0x0FF0.
  2. Escriptura a l’adreça lògica 0x1234.
  3. Lectura de l’adreça lògica 0x2000.
  4. Escriptura a l’adreça lògica 0x3100.
  5. Escriptura a l’adreça lògica 0x0010.

Nota: en aquest problema, excepcionalment, les adreces lògiques s’escriuen en format reduït, amb 4 dígits hexadecimals. Amb pàgines de 4 KiB, els 3 dígits de menys pes són el desplaçament dins de la pàgina i el de més pes és el VPN, i totes les adreces són de les pàgines 0–3 de la taula: els dígits de l’esquerra, que valen zero, no hi aporten res.

17.4 Integració del TLB i la memòria cau

Vegeu Secció 8.7.

Problema 17.9 Un sistema amb adreces lògiques de 32 bits té pàgines de 4 KiB, una memòria cau de dades indexada virtualment i etiquetada físicament (VIPT), de correspondència directa, amb 64 línies amb blocs de 32 bytes, i un TLB de dades completament associatiu de 16 entrades.

  1. Indiqueu quants bits de l’adreça lògica s’usen per al desplaçament dins la pàgina, quants per al VPN, quants per a l’índex de l’MC i quants per al desplaçament dins el bloc.
  2. Expliqueu el flux complet de traducció i accés a dades per a una lectura amb encert al TLB i encert a l’MC.
  3. Per al mateix accés, quin és el flux si hi ha fallada de TLB, però la pàgina és present a memòria física?
  4. En una MC indexada físicament (PIPT), la traducció ha de completar-se abans d’accedir a l’MC. En canvi, en VIPT, les dues operacions poden fer-se alhora. Sota quina condició una MC VIPT no presenta problemes d’aliàsing?

Problema 17.10 Considereu un processador RISC-V amb una memòria cau de dades de 4 vies, 64 conjunts i 32 bytes per bloc (algorisme LRU), i un TLB de dades completament associatiu de 32 entrades, amb pàgines de 8 KiB i algorisme LRU. Considereu la memòria cau i el TLB inicialment buits.

S’executen dues versions d’una mateixa aplicació:

C
int A[128][1024]; // emmagatzemada a partir de l'adreça 0

// Versió A
sumA = 0;
for (i = 0; i < 128; i++)
    for (j = 0; j < 1024; j++)
        sumA = sumA + A[i][j];

// Versió B
sumA = 0;
for (j = 0; j < 1024; j++)
    for (i = 0; i < 128; i++)
        sumA = sumA + A[i][j];

Suposant que i, j i sumA estan en registres, indiqueu quantes fallades hi ha a la memòria cau i al TLB per a cada versió.