- come gestire lo spazio su disco? (rispondiamo ora a questa)
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 cercare di allocare in modo contiguo ma poi se non c’è spazio, si prendono blocchi sparsi su disco.
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
- si tiene in RAM il primo blocco libero (es. 4 byte)
- bitmap : sequenza di bit, dove ognuno rappresenta un blocco del disco (1 = occupato, 0 = libero)
- si tiene in RAM l’intera sequenza!
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?
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