Salta al contenuto
Note per Studenti Esercizio - Spazio libero con bitmap e lista concatenata (eserciziario, esercizi 41, 98 e 120)

Esercizio - Spazio libero con bitmap e lista concatenata (eserciziario, esercizi 41, 98 e 120)

In questa pagina 4

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD).

  • Esercizio 41. Ogni riquadro rappresenta un blocco da 4 KB, con in grigio il suo indirizzo; in ogni blocco si riserva un byte per il puntatore al blocco successivo. Il contenuto di un riquadro può essere: un numero non negativo nn (il blocco è occupato dal contenuto di un file che prosegue nel blocco nn); il numero −1-1 (parte finale di un file); nulla (blocco libero). Su questo disco è memorizzato un intero file system con due file che iniziano nei blocchi 9 e 12.

    blocco 0 1 2 3 4 5 6 7 8 9 10 11
    contenuto 10 18 11 16 20 −1-1
    blocco 12 13 14 15 16 17 18 19 20 21 22 23
    contenuto 5 1 8 17 −1-1 23
    1. La rappresentazione dei blocchi del disco contiene errori? Perché?
    2. Se lo spazio libero è gestito con una bitmap (1 se il blocco è libero, 0 se occupato), qual è il contenuto della bitmap?
    3. Se lo spazio libero è allocato scandendo la bitmap da sinistra verso destra, in quali blocchi verrebbe memorizzato un nuovo file lungo 21 547 byte?

  • Esercizio 98. Disco da 16 GB diviso in blocchi da 1 KB. Due strutture per i blocchi liberi: lista concatenata e bitmap. Nel primo caso ogni elemento è un blocco che contiene indici da 32 bit, l'ultimo dei quali è riservato al blocco successivo della lista libera. Nel secondo, un bit 1 o 0 dice se il blocco è libero o utilizzato. Calcolare l'occupazione di memoria delle due strutture.

  • Esercizio 120. Un file system tiene traccia dei blocchi liberi con bitmap o lista concatenata. Il sistema ha xx blocchi di cui yy in uso; ogni eventuale puntatore a un blocco è di SS bit. Calcolare, con i passaggi, la dimensione della bitmap e della lista concatenata.

Teoria: File system - interfaccia, directory e implementazioneUn file è uno spazio di indirizzi logici contigui con attributi (nome, identificatore, tipo, posizione, dimensione, protezione, date) e operazioni (create, read, write, seek, delete, truncate, open, close); il sistema tiene una tabella dei file aperti di sistema e una per processo; l'accesso è sequenziale o diretto; le directory si organizzano a livello singolo, a due livelli, ad albero, a grafo aciclico (hard link e link simbolici) o a grafo generale; i permessi UNIX rwx per proprietario, gruppo e altri (chmod 754); il file system è a strati (file system logico, organizzazione dei file, file system di base, controllo dell'I/O), con strutture su disco (boot block, superblock, directory, FCB o inode) e in memoria; i blocchi si allocano in modo contiguo (extent), concatenato (FAT) o indicizzato (inode con puntatori diretti e indiretti, ext4 con extent); lo spazio libero con bitmap, lista, raggruppamento o conteggio; mount, VFS, file system distribuiti (NFS) e semantiche di consistenza.File system - interfaccia, directory e implementazione →.

Esercizio 41

1. Ci sono errori? Si seguono le catene dei due file:

  • file che inizia in 9: 9→16→1→10→20→−19\to16\to1\to10\to20\to-1 (fine);
  • file che inizia in 12: 12→5→18→17→8→11→−112\to5\to18\to17\to8\to11\to-1 (fine).

Il blocco 23 contiene il valore 23: punta a se stesso, ma non appartiene a nessuna delle due catene. È un errore: un blocco "occupato" che non fa parte di alcun file e che indica come successivo se stesso (un file la cui continuazione è lo stesso blocco non può terminare). Bisogna controllare anche che non ci siano blocchi formalmente occupati ma che non fanno parte di nessun file: è proprio il caso del 23.

2. La bitmap. Si assegna 1 ai blocchi liberi e 0 agli occupati. Blocchi occupati: 1, 5, 8, 9, 10, 11, 12, 16, 17, 18, 20, 23 (il 23 è marcato come occupato nella rappresentazione). I blocchi liberi sono 0, 2, 3, 4, 6, 7, 13, 14, 15, 19, 21, 22.

blocco 0 1 2 3 4 5 6 7 8 9 10 11
bit 1 0 1 1 1 0 1 1 0 0 0 0
blocco 12 13 14 15 16 17 18 19 20 21 22 23
bit 0 1 1 1 0 0 0 1 0 1 1 0

Bitmap: 101110110000 011100010110, cioè 101110110000011100010110 (la stessa della soluzione del corso).

3. Un nuovo file da 21 547 byte. In ogni blocco da 4 KB (4096 byte) uno è riservato al puntatore (o al valore speciale di fine file): restano 4095 byte per i dati. Servono

⌈21 5474095⌉=⌈5,26⌉=6 blocchi.\left\lceil\frac{21\,547}{4095}\right\rceil=\lceil5{,}26\rceil=6\ \text{blocchi}.

Scandendo la bitmap da sinistra verso destra si prendono i primi 6 bit a 1: blocchi 0, 2, 3, 4, 6, 7.

Esercizio 98

16 GB=23416\text{ GB}=2^{34} byte e blocchi da 1 KB=2101\text{ KB}=2^{10}: i blocchi sono 234/210=224=16 777 2162^{34}/2^{10}=2^{24}=16\,777\,216.

Lista concatenata. Ogni blocco della lista contiene 1024/4=2561024/4=256 indici da 32 bit; uno è riservato al collegamento con il blocco successivo della lista, quindi 255 indici di blocchi liberi per blocco. Nel caso peggiore (tutto il disco libero) servono

⌈224255⌉=⌈65 793,0039⌉=65 794 blocchi\left\lceil\frac{2^{24}}{255}\right\rceil=\lceil65\,793{,}0039\rceil=65\,794\ \text{blocchi}

di lista, cioè 65 79465\,794 KB ≈64,25\approx64{,}25 MB (un po' più di 64 K×1 KB=6464\text{ K}\times1\text{ KB}=64 MB).

Bitmap. Un bit per blocco: 2242^{24} bit =221=2^{21} byte =211=2^{11} KB =2 MB=\mathbf{2\ MB}, sempre (qualunque sia la quantità di spazio libero).

Confronto: la bitmap occupa 2 MB fissi, la lista fino a circa 64 MB nel caso peggiore (disco tutto libero) e quasi nulla quando il disco è pieno.

Esercizio 120

Bitmap. 1 bit per blocco: xx bit.

Lista concatenata. C'è un puntatore per ogni blocco libero; i blocchi liberi sono x−yx-y e ogni puntatore è di SS bit:

S (x−y) bit.S\,(x-y)\ \text{bit}.

Quindi la lista è più piccola della bitmap quando S(x−y)<xS(x-y)<x, cioè quando la frazione di blocchi liberi è minore di 1/S1/S (disco quasi pieno).

Esempio. x=224x=2^{24}, S=32S=32: la bitmap è 2242^{24} bit; la lista conviene solo se i blocchi liberi sono meno di 224/32=2192^{24}/32=2^{19}, cioè il 3,1% del disco.

Errori tipici

  • Non accorgersi del blocco 23 (puntatore a se stesso) nell'esercizio 41.
  • Mettere nella bitmap 1 per occupato: qui 1 significa libero.
  • Calcolare i blocchi del nuovo file con 4096 byte di dati invece di 4095.
  • Nell'esercizio 98, usare 256 indici liberi per blocco invece di 255 (uno è il collegamento).
  • Scrivere per la lista SxSx invece di S(x−y)S(x-y): solo i blocchi liberi hanno un puntatore.

Versione ripasso

41. Catene: 9→16→1→10→20→−19\to16\to1\to10\to20\to-1; 12→5→18→17→8→11→−112\to5\to18\to17\to8\to11\to-1. Errore: il blocco 23 punta a se stesso e non è in nessun file. Occupati: 1, 5, 8, 9, 10, 11, 12, 16, 17, 18, 20, 23; liberi: 0, 2, 3, 4, 6, 7, 13, 14, 15, 19, 21, 22. Bitmap (1 = libero): 101110110000011100010110. Nuovo file da 21 547 byte: 4095 byte di dati per blocco →⌈21 547/4095⌉=6\to\lceil21\,547/4095\rceil=6 blocchi →\to 0, 2, 3, 4, 6, 7.

98. 234/210=2242^{34}/2^{10}=2^{24} blocchi. Lista: 255 indici liberi per blocco (256 meno il collegamento): ⌈224/255⌉=65 794\lceil2^{24}/255\rceil=65\,794 blocchi ≈64,25\approx64{,}25 MB. Bitmap: 2242^{24} bit =2=2 MB, fissi.

120. Bitmap xx bit; lista S(x−y)S(x-y) bit (un puntatore per blocco libero). La lista conviene se S(x−y)<xS(x-y)<x.

Passaggi. Ex. 41: catene 9→16→1→10→20→−19\to16\to1\to10\to20\to-1 e 12→5→18→17→8→11→−112\to5\to18\to17\to8\to11\to-1; il blocco 23 punta a se stesso e non è in un file (errore, marcato occupato); occupati 1, 5, 8, 9, 10, 11, 12, 16, 17, 18, 20, 23; bitmap 101110110000011100010110; file da 21 547 B: ⌈21547/4095⌉=6\lceil21547/4095\rceil=6 blocchi →\to 0, 2, 3, 4, 6, 7. Ex. 98: 2242^{24} blocchi; lista ⌈224/255⌉=65 794\lceil2^{24}/255\rceil=65\,794 blocchi ≈64,25\approx64{,}25 MB; bitmap 2 MB. Ex. 120: bitmap xx bit, lista S(x−y)S(x-y) bit.

Errori tipici: non vedere il blocco 23; 1 = occupato; 4096 invece di 4095 byte di dati; 256 invece di 255 indici; SxSx invece di S(x−y)S(x-y).

Teoria: File system - interfaccia, directory e implementazioneUn file è uno spazio di indirizzi logici contigui con attributi (nome, identificatore, tipo, posizione, dimensione, protezione, date) e operazioni (create, read, write, seek, delete, truncate, open, close); il sistema tiene una tabella dei file aperti di sistema e una per processo; l'accesso è sequenziale o diretto; le directory si organizzano a livello singolo, a due livelli, ad albero, a grafo aciclico (hard link e link simbolici) o a grafo generale; i permessi UNIX rwx per proprietario, gruppo e altri (chmod 754); il file system è a strati (file system logico, organizzazione dei file, file system di base, controllo dell'I/O), con strutture su disco (boot block, superblock, directory, FCB o inode) e in memoria; i blocchi si allocano in modo contiguo (extent), concatenato (FAT) o indicizzato (inode con puntatori diretti e indiretti, ext4 con extent); lo spazio libero con bitmap, lista, raggruppamento o conteggio; mount, VFS, file system distribuiti (NFS) e semantiche di consistenza.File system - interfaccia, directory e implementazione →.

Teoria collegata