Domanda Free-list nei file system

[mattstack]

Salve, sto studiando la teoria dei sistemi operativi e attualmente sono al capitolo sul file system. Non riesco a capire il funzionamento della free-list per tener traccia dei blocchi logici cui viene suddiviso un disco. Ho capito che consiste in una lista di blocchi liberi che deve essere consultata ogni volta che il OS deve trovare un blocco nel quale memorizzare un file, ma non capisco né il perché sia necessaria una lista per fare ciò e né come funziona la memorizzazione di questa free-list nei blocchi liberi stessi così da consumare meno spazio possibile.
Inoltre, data la grande dimensione della free-list, il libro spiega che questa non può essere memorizzata completamente in memoria centrale, e di conseguenza ne viene caricata in memoria solamente una piccola parte mentre la restante rimane sul disco. La parte memorizzata in memoria centrale verrà poi riportata sul disco quando completamente piene o vuota. Ciò comporta un numero troppo elevato di operazione sul disco e quindi un calo di prestazioni, che il libro propone di risolvere memorizzando in memoria, quando possibile, una parte della free-list per metà piena così da diminuire in media il numero di accessi al disco. Non capisco però come facciano ad esserci delle parti della free-list piene per metà, ciò non è impossibile?

 

[demtor]

Sarebbe da vedere l'interpretazione che il libro dà di "free list". Di base la free list è una delle possibile strutture dati che possono essere usate per la gestione dello spazio libero in un file system. Un'altra struttura dati comune che può essere usata per questo scopo è la bitmap (utilizzata nei file system unix). Penso che gli autori dei libri di sistemi operativi, con free list, intendano l'uso di una linked list per creare una catena di puntatori che puntano ai blocchi liberi del disco.

Una possibile free list può essere (la più naive delle free list sicuramente): viene salvato tra le strutture dati del file system il puntatore al primo blocco libero (la testa della lista); dopodiché una parte dei blocchi liberi (fai gli ultimi 4 byte per esempio) viene utilizzata per memorizzare un puntatore al blocco libero successivo. In questo modo finisci per avere una linked list cui nodi sono contenuti nei blocchi liberi stessi e l'unico overhead spaziale sono 4 byte per la testa della lista (nota: i 4 byte all'interno di ogni blocco libero non vengono considerati perché sono liberi per definizione, una volta allocati non servono più). Questo però è poco carino per più motivi. L'accesso casuale è inefficiente e il carico di operazioni di I/O è terribilmente alto: dal momento che i nodi della lista sono sparsi per il disco, quest'ultimo è soggetto a continui seek quando andiamo a scannerizzare la lista alla ricerca di uno spazio libero.

Un'altra possibile free list (più comune e in cui si integra bene): il file system FAT mantiene una tabella (può essere visto come un array di puntatori) con un numero di elementi pari al numero di blocchi (o cluster) disponibili nel disco; ogni elemento è indicizzabile attraverso l'indirizzo di un blocco e il contenuto dell'elemento è un puntatore al blocco successivo. Gli elementi di questa tabella possono essere utilizzati come puntatori per formare una linked list, una per file, basta salvarsi a parte la testa della lista: un puntatore all'elemento della tabella che identifica il primo blocco del file. Oltre a una linked list per file, è possibile implementare una linked list dei blocchi liberi (la free list), dove sempre la testa sarà un puntatore all'elemento della tabella che identifica il primo blocco libero. Sarà poi il contenuto degli elementi della tabella a creare la catena di puntatori che ci serve.

La prima implementazione che ho fornito è ovviamente impossibile da memorizzare in memoria, bisogna necessariamente accedere al disco ogni volta, infatti è altamente inefficiente. La seconda implementazione invece, dal momento in cui tutta l'organizzazione del disco viene compattata in un array di puntatori (File Allocation Table), questa può essere memorizzata in memoria parzialmente o interamente.

Non ho mai affrontato la gestione della memoria di cui parli alla fine, come ho anticipato il libro potrebbe averti fornito una implementazione di free list diversa da quelle che ti ho proposto (e che conosco) io. Però intuitivamente mi verrebbe da pensare che si stia riferendo a qualcosa di simile all'array di puntatori che ho descritto. La free list quindi è una catena di puntatori che puntano agli elementi di una tabella che non include solo i blocchi liberi ma anche blocchi occupati dai file. Quindi idealmente puoi andare a segmentare la tua tabella per assicurarti di avere in memoria elementi della tabella che sono più liberi che occupati.

 

[mattstack]

Il libro per free-list intende una lista di blocchi del disco dove ogni elemento è composto da un insieme di blocchi liberi.
Se per esempio il disco è da 500GB e la dimensione dei blocchi logici è di 4KB, ogni blocco logico potrà contenere 1024 puntatori a blocchi liberi (si hanno 131.072.000 blocchi logici nel disco, quindi utilizziamo un puntatore a 32 bit).
Adesso quando viene allocato un blocco questo viene rimosso dalla free-list, perché è stato occupato e quindi non è più libero. Quando invece viene deallocato un blocco viene aggiunto nella free-list, perché il blocco si è liberato.
Per occupare meno memoria possibile il libro consiglia di allocare la free-list nei blocchi logici stessi dedicati ai file e aggiungere questi blocchi alla free-list quando si libereranno, ovvero quando un elemento della free-list si svuoterà. Praticamente non occupando spazio.
Più che non aver capito, volevo trovare delle conferme. Avendo fatto solo delle ipotesi sul suo funzionamento volevo che qualcuno, per l'appunto, le confermasse.
Ho visto che questa tecnica viene anche chiamata Grouping.

 

[demtor]

Il libro per free-list intende una lista di blocchi del disco dove ogni elemento è composto da un insieme di blocchi liberi.
Se per esempio il disco è da 500GB e la dimensione dei blocchi logici è di 4KB, ogni blocco logico potrà contenere 1024 puntatori a blocchi liberi (si hanno 131.072.000 blocchi logici nel disco, quindi utilizziamo un puntatore a 32 bit).

Quindi prendi x blocchi del disco e dentro a gruppi di 4 byte ci scrivi gli indirizzi dei blocchi liberi? Quindi un array di puntatori a blocchi liberi. Mi viene difficile da immaginare per l'inefficienza delle operazioni di lookup, insert e deletion.

Mi sembra tutto abbastanza confuso. Nome del libro? Magari posso darci un'occhiata.

 

[mattstack]

Quindi prendi x blocchi del disco e dentro a gruppi di 4 byte ci scrivi gli indirizzi dei blocchi liberi? Quindi un array di puntatori a blocchi liberi. Mi viene difficile da immaginare per l'inefficienza delle operazioni di lookup, insert e deletion.

Mi sembra tutto abbastanza confuso. Nome del libro? Magari posso darci un'occhiata.

Si proprio così. Il libro è "I moderni sistemi operativi di tenenbaum" 3^a edizione.

 

[demtor]

Ah ok, adesso mi è più chiaro, è una gestione dello spazio libero di cui non avevo mai sentito parlare. L'idea quindi è quella di avere un pool di indirizzi che puntano ai blocchi liberi. Provo a rispondere alle tue domande.

ma non capisco né il perché sia necessaria una lista per fare ciò e né come funziona la memorizzazione di questa free-list nei blocchi liberi stessi così da consumare meno spazio possibile

Conviene usare una lista perché l'alternativa, che sarebbe allocare una sequenza contigua di blocchi (e quindi un array di puntatori e non più una lista), potrebbe causare frammentazione esterna e non permetterebbe l'efficienza spaziale di cui parli (o meglio è meno scalabile). Più blocchi vengono allocati per i file, meno blocchi servono per mantenere il pool di indirizzi di blocchi liberi, e tutti questi blocchi che non vengono più usati diventano loro stessi blocchi liberi allocabili per un file. Assumi che il disco passi da un utilizzo dello spazio alto (e.g. 90%) a un utilizzo basso (e.g. 20%), avrai bisogno a questo punto di allocare nuovi blocchi per mantenere il tuo pool di indirizzi di blocchi liberi: nel caso in cui utilizzi un array di puntatori questo è fattibile ma dovresti stare attento a non ritrovarti dei file sui blocchi che ti servono per espandere la tua sequenza contigua (situazione in cui non vorresti trovarti), oppure decidi proprio di rendere non allocabili i blocchi necessari per coprire la gestione dello spazio libero di tutto il disco a costo di una efficienza spaziale peggiore; invece con la lista puoi allocare qualsiasi blocco del disco e mantenere la tua free-list dinamicamente, togliendo blocchi quando questi non ti servono più e aggiungendone quando ti servono.

Non capisco però come facciano ad esserci delle parti della free-list piene per metà, ciò non è impossibile?

È possibile non vedo perché no. Se si considerano blocchi da 4KiB e architettura a 32 bit abbiamo che ogni elemento della lista può contenere fino a 4096/4-1 indirizzi che puntano ai blocchi liberi. L'idea quindi è quella di mantenere alcuni elementi della lista (tipicamente in testa o in coda) che non sono piene fino all'orlo di indirizzi in modo da diminuire le operazioni di I/O.

 

[mattstack]

Quindi dovrei portarli sul disco quando vuoti per metà. Così da ottenere poi un lista di soli elementi mezzi pieni e gestire meglio l'I/O sul disco. Inoltre data l'efficenza spaziale e temporale di questa tecnica conviene al posto di una bitmap?
Lo so che quando possibile sarebbe meglio allocare più blocchi contigui allo stesso file, cosa che con la bitmap viene garantita, ma visto che poi i blocchi vengono memorizzati nella cache software del sistema operativo non diventa un po' inutile combattere per avere i file in blocchi contigui?

 

[demtor]

Quindi dovrei portarli sul disco quando vuoti per metà. Così da ottenere poi un lista di soli elementi mezzi pieni e gestire meglio l'I/O sul disco

Si, l'idea sembra questa. Dal momento che il pool di indirizzi può crescere e decrescere, è preferibile tenere in memoria un blocco pieno a metà per diminuire le operazioni di I/O che si potrebbero verificare nei due casi limite (blocco quasi vuoto e blocco quasi pieno).

Inoltre data l'efficenza spaziale e temporale di questa tecnica conviene al posto di una bitmap?

Quando una politica è efficiente da una parte, c'è sempre la fregatura dall'altra. L'implementazione di questa free list proposta da Tanenbaum è sicuramente molto efficace da un punto di vista didattico visto che aiuta a ragionare sui vari problemi di cui tenere conto e di come tutto sia un trade-off continuo, ma è ben lontana dalla realtà. Ha infatti un problema fondamentale: gli indirizzi dei blocchi liberi non sono ordinati, e la natura della struttura dati non permette di imporre alcun ordinamento, questo implica: frammentazione e molta inefficienza nel lookup di blocchi contigui per un nuovo file.

Personalmente risponderei dipende alla tua domanda (ovviamente). Le free list in alcuni contesti può essere una buona scelta, per esempio la natura del file system FAT che ho descritto brevemente prima permette una buona integrazione del concetto di free list. La bitmap invece, utilizzata dai maggiori file system unix, permette di avere una panoramica dei blocchi ordinata e operazioni di lookup di blocchi contigui abbastanza efficienti (e che possono essere ulteriormente migliorate). File system più moderni tendono ad usare strutture dati più sofisticate come qualche forma di Btree, sia per la gestione dello spazio libero che occupato (vedi per esempio XFS).

Lo so che quando possibile sarebbe meglio allocare più blocchi contigui allo stesso file, cosa che con la bitmap viene garantita, ma visto che poi i blocchi vengono memorizzati nella cache software del sistema operativo non diventa un po' inutile combattere per avere i file in blocchi contigui?

Se intendi la memoria cache, questa ha una capacità di memorizzazione drasticamente inferiore rispetto alle due memorie (si parla dell'ordine dei KiB / MiB). Difficilmente ci trovi i blocchi che compongono un file a suo interno. Più probabile che tu possa trovarci invece una directory entry (le directory sono file e vengono consultate di continuo per quasi ogni operazione effettuata su un file regolare, specialmente quelle meno annidate, come la root directory).

 

[mattstack]

Ok grazie. Tutto chiaro.