Esercizio - Dimensioni di page table e indirizzi, paginazione a più livelli (eserciziario, esercizi 66, 67, 69, 72, 76, 81, 82, 93 e 100)

---

Le formule

Con indirizzo logico di $m$ bit, pagine di $2^n$ byte, indirizzo fisico di $k$ bit:

• pagine virtuali (righe della tabella normale): $2^{m-n}$;
• frame fisici (righe della tabella invertita): $2^{k-n}$;
• bit del numero di frame: $k-n$, quindi l'ampiezza di una riga di tabella in byte è $\lceil(k-n)/8\rceil$ (si arrotonda ai byte interi);
• dimensione della tabella: righe $\times$ byte per riga.

Esercizio 66

Il frame è 8 KB $=2^{13}$ byte, quindi il numero di frame fisici è $2^{29-13}=2^{16}$: il numero di frame si scrive su 16 bit $=2$ byte per riga. In un frame entrano $2^{13}/2=2^{12}=4096$ righe. La tabella più grande ha quindi al massimo 4096 righe, cioè 4096 pagine, e lo spazio logico è

$$2^{12}\cdot2^{13}=2^{25}\text{ byte}=32\text{ MB}.$$

Esercizi 67 e 69

Il fisico è di 32 bit, lo spazio fisico è la metà del logico: lo spazio logico è di 33 bit, cioè $2^{33}$ byte.

67 (pagine da $2^{20}$ byte). Righe della tabella: $2^{33}/2^{20}=2^{13}=8192$. Frame fisici: $2^{32}/2^{20}=2^{12}$, quindi 12 bit per riga: si usano 2 byte. Dimensione massima: $2\cdot2^{13}=2^{14}=\mathbf{16\ KB}$.

69 (pagine da $2^{10}$ byte). Righe: $2^{33}/2^{10}=2^{23}$. Frame fisici: $2^{32}/2^{10}=2^{22}$, quindi 22 bit: servono 3 byte per riga. Dimensione: $3\cdot2^{23}$ byte $=24\text{ MB}$, enormemente più grande di un frame da 1 KB: la tabella non sta in un frame e la paginazione a più livelli è necessaria (si pagina la tabella stessa).

Esercizio 72

1. Pagine da 16 KB: testo $200/16=12{,}5\to13$; dati $100/16=6{,}25\to7$; stack $50/16=3{,}125\to4$ (si arrotonda per eccesso per ogni segmento). Totale 24 pagine: la tabella ha 24 righe.
2. Offset di 14 bit ($16\text{ KB}=2^{14}$), restano $32-14=18$ bit di pagina: $2^{18}=256\text{ K}$ pagine, quindi $2^{32}=\mathbf{4\ GB}$ di memoria complessiva.

Esercizio 76

L'offset è 12 bit: le pagine sono $2^{12}=\mathbf{4\ KB}$. La tabella principale ha $2^9$ righe, ognuna punta a una tabella di secondo livello con $2^{11}$ righe: le pagine virtuali sono $2^9\cdot2^{11}=2^{20}\approx10^6$.

Esercizio 81

Logico: 64 pagine ($2^6$) $\times$ 1024 parole ($2^{10}$): $6+10=\mathbf{16}$ bit. Fisico: 32 frame ($2^5$) $\times$ $2^{10}$: $5+10=\mathbf{15}$ bit.

Esercizio 82

Pagine da 2 KB $=2^{11}$. Tabella normale: $2^{21-11}=2^{10}=\mathbf{1024}$ righe. Tabella invertita: una riga per frame, $2^{16-11}=2^5=\mathbf{32}$ righe. Memoria fisica massima: $2^{16}=64$ KB.

Esercizio 93

Pagine da 4 KB $=2^{12}$. Tabella normale: $2^{32-12}=2^{20}=\mathbf{1\,048\,576}$ righe. Tabella invertita: $512\text{ MB}/4\text{ KB}=2^{29}/2^{12}=2^{17}=\mathbf{128\text{ K}=131\,072}$ righe.

Esercizio 100

Pagine da 1 KB $=2^{10}$: 10 bit di offset. 256 frame $=2^8$: 8 bit per il numero di frame. Indirizzo fisico: $8+10=\mathbf{18}$ bit. (Il fatto che il numero di pagina sia scritto su 2 byte e la tabella più grande di un frame non cambia il conto.)

---

Errori tipici

• Usare gli stessi bit per la pagina virtuale e per il frame: la riga della tabella contiene il numero di frame ($k-n$ bit), non quello di pagina.
• Dimenticare di arrotondare i byte per riga (22 bit $\to$ 3 byte) o le pagine di ogni segmento per eccesso.
• Confondere la dimensione della tabella normale ($2^{m-n}$ righe) con quella dell'invertita ($2^{k-n}$ righe).
• Dedurre il livello di paginazione senza confrontare la tabella con la dimensione del frame (se la tabella supera un frame, serve un secondo livello).