Salta al contenuto
Note per Studenti Esercizio - Traduzione degli indirizzi con la tabella delle pagine (eserciziario, esercizi 34, 37, 59, 62 e 86)

Esercizio - Traduzione degli indirizzi con la tabella delle pagine (eserciziario, esercizi 34, 37, 59, 62 e 86)

In questa pagina 6

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD).

  • Esercizio 37 (identico all'esercizio 59). Memoria paginata con memoria virtuale; frame da 1 KB; l'indirizzo fisico e quello logico sono di 32 bit; ogni cella di memoria è di 32 bit.

    1. Quanti bit servono per lo scostamento in una pagina?
    2. Qual è la quantità massima di memoria indirizzabile?
    3. Con la tabella delle pagine seguente (bit di validità 1 se la pagina è in memoria), cosa succede agli indirizzi logici (a) 0…0 0111 1101 0101, (b) 0…0 0100 0001 0111, (c) 0…0 1011 1101 1011? Dare gli indirizzi fisici in decimale.
    pagina validità frame
    0 1 739
    1 1 127
    2 0
    3 1 91
    4 0
    5 1 470
    6 1 2
    7 1 106
    8 1 495
    9 0

  • Esercizio 62. Memoria virtuale con paginazione su richiesta: pagine da 512 parole, 16 pagine (0-15), memoria fisica da 4 frame che contiene le pagine 4, 9, 5, 1 nei frame 0, 1, 2, 3. (a) Contenuto della tabella delle pagine. (b) Indirizzi fisici corrispondenti ai logici 1628, 851, 2700, 2432. (c) Cosa succede con 1330?

  • Esercizio 86. Spazio logico di 8 pagine da 1024 parole, mappato su 32 frame. Da quanti bit è l'indirizzo logico? E il fisico?

  • Esercizio 34. Processo con 7 pagine logiche da 1 K; tabella delle pagine e TLB (4 posizioni) come sotto. Cosa succede, e come cambiano TLB e tabella, se il processo scrive alle locazioni 4000 e 5130?

    pag. logica presente riferita modificata pag. fisica
    0 1 1 0 512
    1 0 0 0 0
    2 1 0 0 102
    3 0 0 0 0
    4 1 0 0 428
    5 1 1 0 123
    6 1 1 0 812
    posizione TLB valida modificata pag. virtuale pag. fisica
    0 1 0 5 123
    1 1 1 6 812
    2 0 0 0 0
    3 1 0 0 512

Teoria: Memoria centrale - allocazione contigua, paginazione e segmentazioneUn programma deve stare in memoria centrale per girare; la MMU traduce a ogni accesso l'indirizzo logico (virtuale) in indirizzo fisico, sommando un registro di rilocazione e controllando il limite; con l'allocazione contigua (partizioni fisse o variabili, first/best/worst fit) si hanno frammentazione interna ed esterna e serve la compattazione; la paginazione divide memoria logica in pagine e memoria fisica in frame della stessa dimensione (potenza di 2), elimina la frammentazione esterna, traduce (p, d) con la tabella delle pagine (PTBR, PTLR) e riduce il costo dei due accessi con il TLB (EAT = h * t + (1 - h) * 2t); le tabelle grandi si dividono in gerarchiche, hash o invertite; lo swapping sposta intere pagine o processi su disco; la segmentazione usa blocchi di lunghezza variabile con coppia (base, limite), eventualmente paginati; Intel IA-32 usa segmentazione con paginazione a due livelli (10+10+12 bit) e IA-64 quattro livelli su 48 bit.Memoria centrale - allocazione contigua, paginazione e segmentazione →, Memoria virtuale - paginazione su richiesta e sostituzione delle pagineLa memoria virtuale separa la memoria logica da quella fisica: basta che alcune pagine siano in RAM; con la paginazione su richiesta (demand paging) una pagina si carica solo al primo riferimento, e un riferimento a una pagina non residente (bit di validità = i) genera un page fault gestito dal sistema operativo in sei passi; EAT = (1 - p) * accesso + p * servizio del fault, con p minuscolo; copy-on-write rende economica la fork; se non ci sono frame liberi si sceglie una vittima con FIFO (anomalia di Belady), OPT (ottimo, irrealizzabile), LRU (algoritmo a stack), second chance (bit di riferimento, orologio) o la versione con bit di modifica; i frame si assegnano in modo uguale o proporzionale, con sostituzione globale o locale; se un processo non ha abbastanza frame va in thrashing; il modello del working set e la frequenza dei page fault lo evitano; considerazioni su prepaging, dimensione della pagina, TLB reach e struttura dei programmi; memoria del kernel con buddy system e slab.Memoria virtuale - paginazione su richiesta e sostituzione delle pagine →.

Il metodo

Dati la dimensione della pagina 2n2^n e un indirizzo logico aa:

p=⌊a2n⌋,d=a mod 2n,fisico=f⋅2n+d.p=\left\lfloor\frac a{2^n}\right\rfloor,\qquad d=a\bmod 2^n,\qquad \text{fisico}=f\cdot2^n+d.

Se la dimensione non è una potenza di 2 (512 è 292^9, 1024 è 2102^{10}: lo sono), si usa la divisione normale. Prima si guarda il bit di validità: se è 0 c'è un page fault (la pagina esiste ma non è in memoria) oppure, se la pagina non esiste nello spazio del processo, un indirizzo non valido (trap, il processo è abortito). Per il TLB si controlla prima la memoria associativa (vedi Memoria centrale - allocazione contigua, paginazione e segmentazioneUn programma deve stare in memoria centrale per girare; la MMU traduce a ogni accesso l'indirizzo logico (virtuale) in indirizzo fisico, sommando un registro di rilocazione e controllando il limite; con l'allocazione contigua (partizioni fisse o variabili, first/best/worst fit) si hanno frammentazione interna ed esterna e serve la compattazione; la paginazione divide memoria logica in pagine e memoria fisica in frame della stessa dimensione (potenza di 2), elimina la frammentazione esterna, traduce (p, d) con la tabella delle pagine (PTBR, PTLR) e riduce il costo dei due accessi con il TLB (EAT = h * t + (1 - h) * 2t); le tabelle grandi si dividono in gerarchiche, hash o invertite; lo swapping sposta intere pagine o processi su disco; la segmentazione usa blocchi di lunghezza variabile con coppia (base, limite), eventualmente paginati; Intel IA-32 usa segmentazione con paginazione a due livelli (10+10+12 bit) e IA-64 quattro livelli su 48 bit.Memoria centrale - allocazione contigua, paginazione e segmentazione →).

Esercizio 37 (e 59)

1. Bit di scostamento. Un frame è di 1 KB =1024=1024 byte; una cella è di 32 bit =4=4 byte. In una pagina ci sono 1024/4=256=281024/4=256=2^8 celle: 8 bit di scostamento. (L'indirizzo è di cella, non di byte.)

2. Memoria massima indirizzabile. Dei 32 bit logici, 8 sono scostamento e 24 numerano le pagine: 2242^{24} pagine da 1024 byte, cioè 224⋅210=2342^{24}\cdot2^{10}=2^{34} byte =16⋅230=16\cdot2^{30} byte =16 GB=\mathbf{16\ GB}. (Equivalente: 2322^{32} celle da 4 byte.)

3. Tre indirizzi. Si separano gli 8 bit meno significativi (scostamento) dal resto (pagina):

indirizzo pagina (24 bit alti) scostamento (8 bit) tabella risultato
(a) 0111 1101 0101 0111 = 7 1101 0101 = 213 validità 1, frame 106 fisico =106⋅256+213=27136+213=27349=106\cdot256+213=27136+213=\mathbf{27349}
(b) 0100 0001 0111 0100 = 4 0001 0111 = 23 validità 0 page fault: la pagina 4 esiste ma non è in memoria; il pager la carica
(c) 1011 1101 1011 1011 = 11 1101 1011 = 219 non c'è nella tabella (la tabella ha le pagine 0-9) indirizzo non valido: trap del gestore della memoria

Controllo con i numeri decimali: (a) vale 2005=7⋅256+2132005=7\cdot256+213, (b) 1047=4⋅256+231047=4\cdot256+23, (c) 3035=11⋅256+2193035=11\cdot256+219. Per (a) il fisico è 2734927349 celle, non byte (il frame 106 comincia alla cella 106⋅256=27136106\cdot256=27136).

Esercizio 62

(a) Tabella delle pagine. Le pagine 4, 9, 5, 1 sono nei frame 0, 1, 2, 3; le altre 12 non sono in memoria:

pagina 1 4 5 9 tutte le altre
frame 3 0 2 1 – (validità 0)
validità 1 1 1 1 0

(b) Indirizzi. Si calcola p=⌊a/512⌋p=\lfloor a/512\rfloor e d=a mod 512d=a\bmod512:

logico pp dd validità fisico
1628 3 1628−1536=921628-1536=92 0 page fault (la pagina 3 non è in memoria)
851 1 851−512=339851-512=339 1, frame 3 3⋅512+339=18753\cdot512+339=\mathbf{1875}
2700 5 2700−2560=1402700-2560=140 1, frame 2 2⋅512+140=11642\cdot512+140=\mathbf{1164}
2432 4 2432−2048=3842432-2048=384 1, frame 0 0⋅512+384=3840\cdot512+384=\mathbf{384}

(c) 1330. 1330/512=21330/512=2 con resto 306306: pagina 2, non in memoria (validità 0): page fault.

Per 1628 non c'è nessun indirizzo fisico da calcolare: la pagina 3 non è in memoria.

Esercizio 86

8=238=2^3 pagine e 1024=2101024=2^{10} parole per pagina: l'indirizzo logico ha 3+10=133+10=\mathbf{13} bit. I frame sono 32=2532=2^5 con 2102^{10} parole ciascuno: l'indirizzo fisico ha 5+10=155+10=\mathbf{15} bit.

Esercizio 34 (TLB e tabella delle pagine)

La pagina da 1 K ha 1000 (o 1024) locazioni. La soluzione del corso numera le locazioni da 1: la pagina 0 contiene le locazioni 1-1000, la 1 le 1001-2000, ecc. In entrambi i modi di contare risulta: 4000 cade nella pagina 3, 5130 nella pagina 5 (con 1024: 4000=3⋅1024+9284000=3\cdot1024+928, 5130=5⋅1024+105130=5\cdot1024+10).

Accesso in scrittura a 4000 (pagina 3).

  1. La pagina 3 non è nel TLB (le righe valide hanno le pagine 5, 6 e 0) e non è presente nella tabella delle pagine (presente = 0): page fault.
  2. Il sistema operativo carica la pagina in un frame libero, imposta la tabella: presente 1, riferita 1, modificata 1 (è una scrittura), frame = quello scelto (indicato con XXX: non si sa quale).
  3. La riga della TLB: l'unica non valida è la riga 2, che diventa valida con pagina virtuale 3, frame XXX e modificata 1.

Accesso in scrittura a 5130 (pagina 5).

  1. La pagina 5 è nel TLB (riga 0): TLB hit, nessun accesso alla tabella per tradurre; il frame è 123.
  2. Poiché è una scrittura, la riga 0 diventa modificata 1; nella tabella delle pagine il bit modificato della pagina 5 si aggiorna (nel TLB subito, nella tabella al più tardi quando la riga viene sostituita).

Stato finale: tabella: pagina 3 presente (riferita e modificata, frame XXX), pagina 5 con modificata 1. TLB: riga 0 = (valida, modificata, 5, 123), riga 2 = (valida, modificata, 3, XXX).

Errori tipici

  • Dimenticare che l'indirizzo è di cella (di 4 byte): la dimensione della pagina in celle è 256, non 1024.
  • Confondere page fault (pagina valida ma non in memoria) con indirizzo non valido (pagina fuori dallo spazio del processo).
  • Calcolare lo scostamento come a−p⋅2na-p\cdot2^n con pp sbagliato (arrotondare per eccesso invece che per difetto).
  • Usare il numero di frame come indirizzo: bisogna moltiplicare per la dimensione del frame e poi aggiungere lo scostamento.
  • In (c) dire "page fault" invece di "indirizzo non valido": la pagina 11 non esiste nella tabella.

Versione ripasso

Formule. p=⌊a/2n⌋p=\lfloor a/2^n\rfloor, d=a mod 2nd=a\bmod2^n, fisico =f⋅2n+d=f\cdot2^n+d. Validità 0: page fault (pagina esistente) o indirizzo non valido (pagina inesistente). Bit di logico =log⁡2(pagine)+n=\log_2(\text{pagine})+n; di fisico =log⁡2(frame)+n=\log_2(\text{frame})+n.

Ex. 37. Frame 1 KB, celle da 4 byte →\to 256 celle →\to 8 bit di offset; 24 bit di pagina →224⋅1024=16\to2^{24}\cdot1024=16 GB. (a) 0111|11010101: pagina 7, offset 213, frame 106 →106⋅256+213=27349\to106\cdot256+213=27349. (b) pagina 4, offset 23, validità 0 →\to page fault. (c) pagina 11 non in tabella →\to indirizzo non valido (trap).

Ex. 62. Frame 0-3 == pagine 4, 9, 5, 1 →\to pagina 1 →3\to3, 4 →0\to0, 5 →2\to2, 9 →1\to1. 1628: pagina 3 non presente →\to page fault. 851: pagina 1, offset 339 →3⋅512+339=1875\to3\cdot512+339=1875. 2700: pagina 5, offset 140 →2⋅512+140=1164\to2\cdot512+140=1164. 2432: pagina 4, offset 384 →384\to384. 1330: pagina 2 →\to page fault.

Ex. 86. 3+10=133+10=13 bit logici, 5+10=155+10=15 bit fisici.

Ex. 34. 4000 →\to pagina 3: né nel TLB né in memoria →\to page fault; si carica, tabella (presente, riferita, modificata), riga TLB libera (la 2) =(1,1,3,XXX)=(1,1,3,\text{XXX}). 5130 →\to pagina 5: TLB hit (riga 0, frame 123), riga 0 diventa modificata.

Passaggi. 37: indirizzo a 32 bit, offset 8, pagina 24: 0111 | 11010101 →\to pagina 7, offset 213, frame 106, 106⋅256+213=27349106\cdot256+213=27349; 0100 | 00010111 →\to pagina 4 non valida →\to page fault; 1011 | 11011011 →\to pagina 11 fuori tabella →\to trap. 62: p=⌊a/512⌋p=\lfloor a/512\rfloor, d=a mod 512d=a\bmod512; 851 →(1,339)→3⋅512+339=1875\to(1,339)\to3\cdot512+339=1875; 2700 →(5,140)→1164\to(5,140)\to1164; 2432 →(4,384)→384\to(4,384)\to384. 34: 4000 →\to pagina 3 (non nel TLB, non presente): fault, riga TLB 2 =(1,1,3,XXX)=(1,1,3,\text{XXX}); 5130 →\to pagina 5, hit nella riga 0, modificata.

Errori tipici: indirizzo di cella e non di byte; page fault ↔\leftrightarrow indirizzo non valido; offset con pagina sbagliata; usare il frame senza moltiplicare per la dimensione.

Teoria: Memoria centrale - allocazione contigua, paginazione e segmentazioneUn programma deve stare in memoria centrale per girare; la MMU traduce a ogni accesso l'indirizzo logico (virtuale) in indirizzo fisico, sommando un registro di rilocazione e controllando il limite; con l'allocazione contigua (partizioni fisse o variabili, first/best/worst fit) si hanno frammentazione interna ed esterna e serve la compattazione; la paginazione divide memoria logica in pagine e memoria fisica in frame della stessa dimensione (potenza di 2), elimina la frammentazione esterna, traduce (p, d) con la tabella delle pagine (PTBR, PTLR) e riduce il costo dei due accessi con il TLB (EAT = h * t + (1 - h) * 2t); le tabelle grandi si dividono in gerarchiche, hash o invertite; lo swapping sposta intere pagine o processi su disco; la segmentazione usa blocchi di lunghezza variabile con coppia (base, limite), eventualmente paginati; Intel IA-32 usa segmentazione con paginazione a due livelli (10+10+12 bit) e IA-64 quattro livelli su 48 bit.Memoria centrale - allocazione contigua, paginazione e segmentazione →.

Teoria collegata