Esercizio - Inode e dimensione massima dei file (eserciziario, esercizi 63, 97, 105 e 111)

---

La struttura

L'inode contiene i puntatori ai blocchi del file:

• $D$ puntatori diretti, ciascuno a un blocco di dati;
• 1 puntatore indiretto singolo: punta a un blocco di puntatori ($n$ blocchi dati);
• 1 puntatore indiretto doppio: punta a un blocco di $n$ puntatori a blocchi di puntatori ($n^2$ blocchi dati);
• eventualmente 1 puntatore indiretto triplo ($n^3$ blocchi dati).

Se il blocco è di $B$ byte e un puntatore di $p$ byte, un blocco contiene $n=B/p$ puntatori. Il numero massimo di blocchi dati è $D+n+n^2\,(+n^3)$ e la dimensione massima è quel numero per $B$. I blocchi indice sono blocchi in più (non contano come dati): per $f$ blocchi di dati si conta quanti blocchi di puntatori servono livello per livello.

Esercizio 63

$B=4\text{ KB}$, $p=4$ byte: $n=4096/4=1024$ puntatori per blocco.

(a) I blocchi di dati sono $\lceil\text{dimensione}/4\text{ KB}\rceil$:

Per D: i primi 10 blocchi usano i diretti, i successivi $1024$ l'indiretto singolo (1 blocco indice). I restanti $5000-10-1024=3966$ vanno nel doppio: 1 blocco indice di primo livello, che punta a $\lceil3966/1024\rceil=4$ blocchi indice di secondo livello (tre pieni da 1024 e uno con $3966-3072=894$ puntatori). Blocchi di indici: $1\,(\text{singolo})+1+4\,(\text{doppio})=6$; totale $5000+6=\mathbf{5006}$. (La soluzione del corso scrive $5000+1+5=5006$.)

(b) La dimensione massima è, in blocchi,

$$10+1024+1024^2+1024^3=1\,074\,791\,434\ \text{blocchi}$$

e quindi $1\,074\,791\,434\cdot4096\approx4{,}0039\cdot2^{40}$ byte, circa 4 TB: il termine che conta è $1024^3$ blocchi $=2^{30}\cdot2^{12}=2^{42}$ byte $=4$ TB; gli altri (4 GB, 4 MB, 40 KB) sono molto più piccoli.

Esercizio 97

$n=1024/4=256$ puntatori per blocco (inode di 1 KB, 16 diretti, un indiretto singolo, un indiretto doppio):

• 16 blocchi dati diretti: $16$;
• indiretto singolo: $256$ blocchi dati (costa 1 blocco indice);
• indiretto doppio: $256\cdot256=2^{16}=65\,536$ blocchi dati (costa 1 blocco + 256 blocchi indice).

$$\text{dimensione massima}=(16+256+65\,536)\cdot1\text{ KB}=65\,808\text{ KB}\approx64{,}3\text{ MB}.$$

Esercizio 105

Blocchi dati. Un blocco da 512 byte contiene $\lfloor512/80\rfloor=6$ record (6 record occupano 480 byte; i 32 rimanenti si sprecano perché un record non può stare in due blocchi). Servono $\lceil10\,000/6\rceil=1667$ blocchi di dati.

Blocchi di indici. Un blocco indice da 512 byte con indirizzi da 4 byte contiene $512/4=128$ indirizzi.

• 12 blocchi sono indirizzati direttamente dal nodo indice principale; ne restano $1667-12=1655$.
• Con indirizzamento singolo se ne indirizzano 128: ne restano $1655-128=1527$. Serve 1 blocco di indirizzi.
• Con indirizzamento doppio: $\lceil1527/128\rceil=12$ blocchi di secondo livello (11 pieni e 1 con $1527-1408=119$ puntatori), più 1 blocco di primo livello: $1+12=13$ blocchi.

Blocchi per gestire l'allocazione: 1 (nodo indice principale) $+\ 1$ (singolo) $+\ 13$ (doppio) $=\mathbf{15}$.

Totale: $1667+15=1682$ blocchi $=1682\cdot512=861\,184$ byte $=841$ KB di occupazione totale.

Esercizio 111

Dimensione massima. Blocco da 1 KB, indici da 32 bit (4 byte): $n=256$. Con 12 diretti, 1 singolo, 1 doppio:

$$12+256+256^2=12+256+65\,536=65\,804\ \text{blocchi}=65\,804\ \text{KB}.$$

(La partizione è da 64 GB $=2^{36}$ byte, quindi $2^{36}/2^{10}=2^{26}$ blocchi: gli indici da 32 bit bastano.)

Spazio dell'inode. Per rappresentare un file che usa tutto: 1 blocco per l'inode principale, 1 per l'indirezione singola, 1 per il primo livello dell'indirezione doppia e 256 per il secondo livello:

$$1+1+(1+256)=259\ \text{blocchi}=259\text{ KB}.$$

---

Errori tipici

• Contare i blocchi indice nella dimensione massima del file: sono spazio in più.
• Dimenticare che i puntatori dell'indirezione doppia occupano $1+\lceil\text{blocchi}/n\rceil$ blocchi indice (non solo 1).
• Nell'esercizio 105, ignorare che un record non può essere diviso (6 record per blocco, non $512/80=6{,}4$).
• Confondere i puntatori per blocco $n=B/p$ con la dimensione del blocco.
• Nell'esercizio 63, non accorgersi che per il file D il singolo indiretto non basta.