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
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
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