Riprendiamo le domande che ci eravamo poste :
- come memorizzare i file?
- come implementare le directory?
- come gestire lo spazio su disco? (rispondiamo ora a questa)
- come garantire le prestazioni del file system?
- come garantire l’affidabilità del file system?
I file sono memorizzati su disco e ci sono 2 modi principali per farlo (come abbiamo già detto in Implementazione file) :
- allocazione contigua : file salvato come una sequenza di byte
- suddivisione in blocchi non contigui (sparsi) : file viene “spezzettato” in blocchi di dimensione fissa, che possono essere sparsi ovunque nel disco
Con l’allocazione contigua abbiamo il problema che se il file cresce, non ci potrebbe essere abbastanza spazio, obbligando il OS a spostarlo per intero (operazione lenta). Quindi si preferisce usare la seconda tecnica a blocchi “sparsi”.
Il compromesso della dimensione dei blocchi sta tra velocità e spazio :
- blocchi grandi :
- trasferimento veloce
- spreco di spazio
- blocchi piccoli :
- disco deve fare molta fatica per fare ricerche e ritardi di rotazione per andare a leggere i vari blocchi
- no spreco di spazio Il compromesso storico è di 4 KB, ma siccome oggi abbiamo dischi dell’ordine dei Terabyte, si cerca di avere blocchi grandi accettando lo spreco di spazio.
Traccia dei blocchi liberi
Come facciamo a tenere traccia dei blocchi liberi?
Esistono due metodi :
- lista concatenata : si utilizzano gli stessi blocchi liberi per “scriverci dentro” gli indirizzi di altri blocchi liberi e un puntatore al prossimo blocco della lista
- efficiente in termini di spazio solo quando il disco è quasi pieno (pochi blocchi liberi)
- bitmap : sequenza di bit, dove ognuno rappresenta un blocco del disco (1 = occupato, 0 = libero)
- richiede meno spazio rispetto alla lista concatenata
Per esempio se avessimo blocchi da 1 KB e indirizzi da 32 bit, allora :
- lista concatenata : ogni blocco può contenere 255 indirizzi di blocchi liberi (256 - 1 per il puntatore)
- per un disco da 1 TB avremo bisogno di circa 4 milioni di blocchi (per coprire tutti i blocchi liberi)
- bitmap : con un disco da 1 TB serve una bitmap da 1 miliardo di bit (128 MB - fai il calcolo se non ci credi 🧐)
Modifica tecnica della lista concatenata
Per migliorare l’efficienza della lista concatenata, invece di elencare l’indirizzo di ogni singolo blocco, è possibile fornire solo l’indirizzo di inizio di una serie di blocchi liberi contigui e aggiungere il conteggio di quanti sono.
Questo diventa efficiente quando il disco è vuoto (tanti spazi contigui liberi), ma diventa un problema quando il disco è frammentato, che porterebbe ad un maggiore overhead. Why?
La sfida nella progettazione dei OS è infatti la scelta della struttura dati ottimale senza sapere se l’utente finale terrà il disco ordinato o frammentato.
Gestione dei blocchi liberi con lista di puntatori (lista concatenata - free list)
Il OS tiene in RAM un “pezzo” (blocco) della lista concatenata (free list), in modo che quando crea un file e ha bisogno di sapere dove deve andare a scrivere, consulta quel blocco (di puntatori - indirizzi) in RAM senza andare sul disco a cercare.
- se si crea un file si prendono gli indirizzi necessari dal blocco in RAM
- se si rimuove un file gli indirizzi liberati dal file vengono aggiunti al blocco in RAM
Il problema è quando vengono creati e cancellati file rapidamente (file temporanei) :
- se il blocco in RAM è quasi pieno e si cancella un file, gli indirizzi aggiunti al blocco potrebbero riempirlo completamente
- il blocco in RAM deve essere salvato su disco e sostituito con uno nuovo
- vedi figura sotto (a) (b)
- se subito dopo creiamo un file (quindi utilizzo gli indirizzi in quello appena messo), il blocco (nuovo) in RAM si svuota
- bisogna prendere un altro blocco dal disco (non ha senso avere un blocco vuoto di indirizzi)
(le entry in grigio sono gli indirizzi a blocchi del disco liberi)
Quindi la soluzione per evitare di fare frequenti operazioni di I/O sul disco sarebbe quella di dividere il blocco pieno in RAM, in modo da tenere in RAM sempre un blocco “mezzo pieno” (vedi figura sotto).
Quota del disco in sistemi multiutente
Nei OS multiutente, per evitare che un singolo utente occupi tutto lo spazio disco, l’amministratore di sistema può configurare a ciascun utente un limite massimo di blocchi e di file che può possedere (quota).
Il OS controlla queste quote attraverso due tabelle che tiene in memoria, infatti quando viene aperto un file :
- i dati finiscono nella tabella dei file aperti, dove esiste un puntatore che collega il file al suo owner nella tabella delle quote
- ogni volta che il file cresce (aggiungendo blocchi), il sistema aggiorna la tabella delle quote
Esistono due tipi di limiti :
- soft : si può temporaneamente superare il limite, ma va consolidato prima del log-out (altrimenti restrizione accesso)
- hard : non si può mai superare il limite