Esercizio - Allocazione dei file con metodo contiguo, concatenato, indicizzato e FAT (eserciziario, esercizi 42, 53, 65, 71, 104, 108, 113 e 119)

---

Esercizio 42 (FAT)

La FAT. Ogni riga $i$ della tabella contiene il blocco che segue il blocco $i$ nel suo file. Seguendo le catene (con la correzione del corso: $f_0$ è 5, 9, 19, 4, 11, 7, perché la soluzione del corso include anche il blocco 9; nel testo l'elenco salta il 9):

• $f_0$: $5\to9\to19\to4\to11\to7$ (e 7 è l'ultimo: $-2$);
• $f_1$: $18\to12\to13\to1\to6\to15\to10$ (10 è l'ultimo: $-2$).

I blocchi liberi ($-1$) sono 0, 2, 3, 8, 14, 16, 17: 7 blocchi.

Dimensione massima di un nuovo file. Un file può usare tutti i blocchi liberi: $7\cdot4\text{ KB}=28\text{ KB}=28\,672$ byte.

Se si seguisse il testo alla lettera (senza il blocco 9 in $f_0$, con $5\to19$) anche il blocco 9 risulterebbe libero e i blocchi liberi sarebbero 8, cioè 32 KB. La soluzione del corso (28 KB) corrisponde alla lista con il 9.

Esercizio 53

Il disco ha 1 GB e il 10% è occupato: circa 100 MB. Metà (50 MB) è occupata da file piccoli. Un file, anche se più piccolo di 2 KB, occupa comunque un intero cluster da 2 KB. Quindi il numero di file piccoli è

$$N_{\text{small}}\approx\frac{50\ \text{MB}}{2\ \text{KB}}=25\,000.$$

(Con 1 GB $=1000$ MB; con le potenze di 2 il conto dà circa 26 200.) Sugli altri file non si può dedurre nulla: non si sa quanti sono né quanto sono grandi.

Esercizio 65

Ogni blocco contiene 1020 byte di dati e 4 di puntatore al blocco successivo. Il file è di $2^{15}=32\,768$ byte:

$$\left\lceil\frac{32\,768}{1020}\right\rceil=\lceil32{,}13\rceil=33\ \text{blocchi}.$$

(Se si usasse un blocco intero per i dati, $2^{15}/2^{10}=32$ blocchi; ma 4 byte per blocco sono puntatori, quindi 33.) Con allocazione concatenata, per arrivare all'ultimo blocco si devono leggere tutti i blocchi in sequenza: servono i puntatori dei primi 32 blocchi più il contenuto del 33°. Il numero di accessi è 33. (Il numero del primo blocco è già in RAM, quindi non si legge nessun'altra struttura.)

Esercizio 71

Spiegazioni:

• Contigua, 40-esimo: i record dal 41° al 70° (30 record) vanno spostati di una posizione: si legge e si riscrive ciascuno: 30 + 30.
• Concatenata, ultimo: per modificare il puntatore del penultimo blocco bisogna arrivare fino a lui seguendo la catena; la soluzione del corso conta 68 letture e 1 scrittura. (Se si conta anche la lettura del penultimo blocco stesso, cioè la lettura-modifica-scrittura di un blocco, sono 69 letture e 1 scrittura.)
• Concatenata, 40-esimo: servono 40 letture per ottenere gli indirizzi del 39° e del 41° blocco, e 1 scrittura nel blocco 39 per fargli puntare il 41°.
• Indicizzata: si modifica solo il blocco indice: 1 lettura (per accedere a tutto l'indice) e 1 scrittura (per riscriverlo), qualunque sia il record: i blocchi dati non si spostano e non si toccano.

Esercizio 104

FAT-15 significa che un indice di blocco ha 15 bit: $2^{15}=32\,768$ blocchi. Come in FAT-16, i blocchi sono al massimo da 32 KB $=2^{15}$ byte. La dimensione massima di partizione è

$$2^{15}\text{ blocchi}\times2^{15}\text{ B/blocco}=2^{30}\text{ B}=\mathbf{1\ GB},$$

cioè la metà di quella di FAT-16 ($2^{16}\cdot2^{15}=2$ GB). La dimensione massima di un file è la stessa, 1 GB (un file può occupare l'intera partizione, trascurando la FAT).

Esercizio 108

La chiavetta ha $2\text{ GB}/4\text{ KB}=2^{31}/2^{12}=2^{19}=524\,288$ blocchi. I file occupano $100\cdot1000=100\,000$ blocchi.

(a) Minima frammentazione: tutti i blocchi sono contigui e uno dopo l'altro. Si leggono $100\,000$ blocchi a 100 $\mu$s: $100\,000\cdot100\ \mu\text{s}=10$ s (la soluzione ammette anche 10 s più i 5 ms iniziali per il primo blocco). Se i file fossero separati fra loro (ogni file contiguo ma con un salto fra un file e l'altro): ogni file costa $1000\cdot100\ \mu\text{s}=100$ ms, più 5 ms di salto: $100\cdot105\text{ ms}=10{,}5$ s.

(b) Massima frammentazione: poiché i blocchi liberi sono $524\,288-100\,000>100\,000$, ogni blocco di dato può essere separato dal successivo da almeno un blocco libero. Ogni lettura costa quindi un salto più la lettura:

$$100\,000\cdot(5\ \text{ms}+100\ \mu\text{s})=100\,000\cdot5{,}1\ \text{ms}=510\ \text{s}=8\ \text{min }30\ \text{s}.$$

Il caso peggiore è 51 volte più lento del migliore (510 s contro 10 s): ogni accesso non contiguo costa 50 volte più del trasferimento del blocco.

Esercizio 113

Il record è di 512 byte e il blocco è di 512 byte: un record per blocco.

• Contigua: il record 8 è all'indirizzo base $+\,7$ blocchi: si calcola subito, 1 accesso.
• Concatenata: il record 3 è appena stato letto (e con lui il puntatore al blocco 4): per arrivare all'8 si leggono i blocchi 4, 5, 6, 7, 8: 5 accessi.
• Indicizzata: il blocco indice è in memoria (è un'ipotesi): si legge direttamente il blocco 8: 1 accesso.

Esercizio 119

Una partizione da 200 GB con blocchi da 4 KB ha $200\cdot2^{30}/2^{12}=52\,428\,800$ blocchi (circa 50 milioni). Si ha $2^{25}=33\,554\,432<52\,428\,800\le2^{26}=67\,108\,864$, quindi ogni indice di blocco richiede almeno 26 bit.

---

Errori tipici

• Dimenticare di togliere dai blocchi della concatenata lo spazio del puntatore (1020 e non 1024 byte di dati).
• Nella concatenata, contare solo il blocco da raggiungere e non tutti i blocchi precedenti da leggere.
• Nell'esercizio 42, non contare il blocco 9 o i blocchi liberi (indicati con $-1$) e quelli di fine file ($-2$).
• Dimenticare che un file piccolo occupa comunque un cluster intero (esercizio 53).
• Nel caso di massima frammentazione dell'esercizio 108, contare i 5 ms una volta sola invece che a ogni blocco.