Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Marco Lapegna » 26.Esercitazioni 8: Il file system


Esercizio 1

Un file  dotato di una struttura a record di 512 byte ed  allocato su un disco caratterizzato da blocchi anch’essi di 512 byte.

Si considerino le tre strategie di memorizzazione del file, contigua, concatenata e indicizzata, e si supponga che le informazioni che riguardano il file (i-node), in ognuno dei tre casi, siano giˆ in memoria centrale.

Esercizio 1

Si supponga che

L’ultimo record letto dal file  il record 3,
Il prossimo record da leggere  il record 8.

Per ognuno dei tre casi, si calcoli quanti accessi a disco sono necessari per la lettura del record 8 e si motivi la risposta.

soluzione

Notiamo innanzitutto, che, date le dimensione di record e blocco sopra specificate, ogni record del file occupa esattamente un blocco del disco. Quindi:

allocazione contigua: 1 accesso alla memoria di massa permetterˆ di reperire direttamente il record 8.

soluzione

allocazione concatenata: 5 accessi alla memoria, in quanto i record che separano il terzo dall’ottavo devono essere letti sequenzialmente.

allocazione indicizzata: 2 accessi alla memoria, uno al blocco indice, se non presente in memoria centrale, per reperire il puntatore al blocco di dati richiesto, l’altro al blocco di dati.

Esercizio 2

Si consideri un file formato da 70 record e le sue possibili allocazioni su disco di tipo contigua, concatenata e con tabella indice. In ognuno di questi casi i record del file sono memorizzati uno per blocco.
Le informazioni che riguardano il file sono giˆ in memoria centrale e la tabella indice  contenuta in un unico blocco.

Si dica quanti accessi al disco (letture e/o scritture) sono necessari, in ognuna di queste situazioni, per cancellare (eliminare):
1. il primo record
2. il 40-esimo record
3. l’ultimo record

Soluzione (all. contigua)

  • per cancellare il primo record è sufficiente modificare il puntatore al blocco di inizio0 accessi al disco
  • per cancellare l’ultimo record è sufficiente modificare l’indicazione della lunghezza del file0 accessi al disco

Soluzione (all. contigua)

  • per cancellare il 40-mo record è necessario:
    • copiare il 41-mo sul 40-mo blocco
    • copiare il 42-mo sul 41-mo blocco
    • …..
    • copiare il 70-mo sul 69-mo blocco

30 accessi in lettura e 30 in scrittura


Soluzione (all. concatenata)

per cancellare il primo record è necessario modificare il puntatore del blocco di inizio con il valore che si trova nel primo blocco1 accesso al disco


Soluzione (all. concatenata)

  • per cancellare l’ultimo record è necessario modificare il puntatore del penultimo blocco68 accessi in lettura e 1 in scrittura al disco
  • per cancellare il 40-mo record sono necessari 40 in lettura per ottenere l’indirizzo del 39° e 41° blocco e 1 in scrittura per modificare l’indirizzo contenuto nel 39° blocco

Soluzione (all. indicizzata)

  • per cancellare il
    • primo record
    • l’ultimo record
    • il 40-mo record
  • è necessario modificare solo l’indice del file → 1 accesso in lettura (per accedere a tutto l’indice) e 1 in scrittura

Esercizio 3

Gli i-node di UNIX impiegano indirizzamento di 12 blocchi diretto e 1 indirizzamento indiretto singolo, doppio e triplo per localizzare i blocchi di un file fisico.

Si supponga che ciascun indirizzo occupi quattro byte.

Si calcoli la dimensione del pi grande file che pu˜ essere gestito con questo schema di indirizzamento, per dimensioni dei blocchi di 512, 1024 e 4096 byte.

Soluzione dim blocchi=512

Blocchi di 512 byte
Indirizzi di 4 byte
512/4 = 128 indirizzi per blocco

Dimensione massima per un file

  • 12 * 512 byte = 6 Kbyte +
  • 128 * 512 byte = 64 Kbyte +
  • 1282 * 512 byte = 4 Mbyte +
  • 1283 * 512 byte = 2 Gbyte

Soluzione dim blocchi=1024

Blocchi di 1 kbyte
Indirizzi di 4 byte
1024/4 = 256 indirizzi per blocco

Dimensione massima per un file

  • 12 * 1 Kbyte = 12 Kbyte +
  • 256 * 1 Kbyte = 256 Kbyte +
  • 2562 * 1 Kbyte = 64 Mbyte +
  • 2563 * 1 Kbyte = 16 Gbyte

Soluzione dim blocchi=4096

Blocchi di 4 kbyte
Indirizzi di 4 byte
4096/4 = 1024 indirizzi per blocco

Dimensione massima per un file

  • 12 * 4 Kbyte = 48 Kbyte +
  • 1024 * 4 Kbyte = 4 Mbyte +
  • 10242 * 4 Kbyte = 4 Gbyte +
  • 10243 * 4 Kbyte = 4 Tbyte

Esercizio 4

Sia dato un file system dove la dimensione del blocco è B=1024 bytes e la dimensione dell’indirizzo di blocco p=2 byte.

Supponiamo che lo schema di allocazione sia indicizzato mediante indirizzamento di
10 blocchi diretti
1 blocco indiretto di primo livello
1 blocco indiretto di secondo livello
1 blocco indiretto di terzo livello

Il byte 300.000 di un file di tale file system si trova in un blocco dati diretto, indiretto, doppiamente indiretto o triplamente indirettoÊ?

Esercizio 4

Sia dato un file system dove la dimensione del blocco è B=1024 bytes e la dimensione dell’indirizzo di blocco p=2 byte.

Supponiamo che lo schema di allocazione sia indicizzato mediante indirizzamento di
10 blocchi diretti
1 blocco indiretto di primo livello
1 blocco indiretto di secondo livello
1 blocco indiretto di terzo livello

Il byte 300.000 di un file di tale file system si trova in un blocco dati diretto, indiretto, doppiamente indiretto o triplamente indirettoÊ?

Soluzione

Un file in Unix  un flusso di bytes contenuti in blocchi del file system.

300000 / 1024 = 292.96 → Il byte 300.000, in un file system di blocchi da 1024 bytes,  contenuto nel blocco 293 del file.

Nel file system in oggetto, ogni blocco pu˜ contenere 1024/2 = 512 indirizzi

Soluzione

I primi 10 blocchi (da 0 a 9) di un file sono indirizzati direttamente.
I blocchi da 10 a 521 (9+512) del file sono singolarmente indirizzati.
I blocchi da 522 a (521 + 512*512) sono doppiamente indirizzati.
I blocchi da (521 + 512*512) a (521 + 512*512 + 512*512*512) sono triplamente indirizzati.

Perci˜ il byte 300000, che si trova nel blocco 293 del file,  contenuto in uno dei blocchi singolarmente indirizzati (dal 10 al 521).

Esercizio 5

La File Allocation Table della Microsoft è un esempio di allocazione tabellare dei file. Si determini la dimensione in byte di una FAT nei casi di

un floppy disk da 1.44 Mbyte che usa blocchi da 1 Kbyte
un disco da 200 Gbyte ch
e usa blocchi da 4 Kbyte

soluzione

Floppy disk da 1.44 Mbyte

  • 1440 blocchi da 1 Kbyte
  • Necessari 11 bit (211 = 2048 indirizzi)
  • Dim tabella = 11*1440 = 15840 bit = 1980 byte

Disco da 200 Gbyte

  • ~ 50 milioni di blocchi
  • Necessari 26 bit (226 = 67108864 indirizzi)
  • Dim tabella = 26*50*106 = 1300* 106 bit ~ 130 Mbyte

Esercizio 6

Un file system può tenere traccia dei blocchi liberi mediante

  • Bitmap
  • Lista dei blocchi liberi

Supponendo che il sistema ha un totale di

  • T blocchi,
  • U dei quali sono usati
  • ogni blocco è memorizzato usando S bit,

Esercizio 6

si calcoli la dimensione in bit della bitmap e della lista dei blocchi liberi

Fissati S e T, si determini inoltre per quale valore di U l’occupazione della bitmap è inferiore a quello della lista dei blocchi liberi

soluzione

Bitmap

  • La bitmap tiene traccia di ogni blocco (sia occupato o libero) con un solo bit
  • Dimensione è sempre T (numero di blocchi totali)

Lista dei blocchi liberi

  • Tiene traccia dei blocchi liberi
  • (T-U) numero di blocchi liberi
  • S bit per ogni blocco
  • Dimensione totale S(T-U)

soluzione

fissati T e S

  • occupazione bitmap > occupazione lista se e solo se

S(T-U) < T cioè U > (ST-T)/S

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion