Sistemi operativi GC

IMPLEMENTAZIONE DEL FILE SYSTEM

Struttura del file system

Struttura dei file

- Unità logica di memoria (file)

- Collezione di informazioni correlate

Un file è memorizzato e trasferito a blocchi.

Il file system risiede su memoria secondaria (dischi).

Il file system è organizzato a livelli funzionali.

Livelli di un file system

Quattro strati software dove ognuno comunica con il precedente e con il successivo.

Gli utenti interagiscono con il file system tramite il file system logico.

I driver dei dispositivi sono i programmi che gestiscono i dispositivi di I/O.

File Control Block

File Control Block: struttura di memoria contenente un insieme di informazioni riguardanti un file.

Nei file system basati su UNIX si chiama inode (index node)

Il File Control Block è gestito dal file system logico.

Il File Control Block dice anche dove si trova fisicamente il file sul disco.

Strutture del file system in memoria

La Figura (a) descrive l’operazione di apertura di un file (open).

- Accesso alla directory in memoria

- Accesso alla directory sul disco (se necessario)

- Accesso al file control block su disco

La Figura (b) descrive l’operazione di lettura (read) di un file.

- Accesso alle tabelle dei file in memoria

- Accesso al file control block su disco

- Accesso ai blocchi dati dei file.

File system virtuali

Alcuni sistemi operativi, come UNIX, permettono di gestire in maniera integrata diversi tipi di file system.

Questo è fatto tramite un Virtual File System (VFS) che fornisce una rappresentazione object-oriented del

file system.

Un VFS permette di usare una stessa interfaccia (API) per differenti tipi di file system.

L’interfaccia opera verso il VFS che “nasconde” i diversi tipi di file system sottostanti.

Posso avere nello stesso computer due o tre file system. Se voglio utilizzare questi file system con la stessa

interfaccia, basta installare la VFS e utilizzare questi file system con le operazioni di VFS.

IMPLEMENTAZIONE DEL FILE SYSTEM

Implementazione delle directory

La scelta del metodo di allocazione e gestione delle directory ha un impatto sull’efficienza e sull’affidabilità

del file system. Due sono i metodi principali:

Lista lineare dei nomi dei file con i puntatori ai blocchi dei dati (ogni elemento ha il contenuto del file)

- semplice da programmare

- non molto efficiente nella ricerca (lineare)

Tabella hash – lista lineare con struttura hash per la ricerca (quando c’è un numero elevato di file).

- Diminuisce il tempo di ricerca

- Collisioni – situazioni dove due nomi di file portano alla stessa locazione della tabella.

- Dimensione fissata legata alla funzione hash.

Metodi di allocazione

Un metodo di allocazione si occupa di come allocare sulla memoria secondaria i blocchi di un file.

Tre metodi principali:

- Allocazione contigua

- Allocazione concatenata (non contigua)

- Allocazione indicizzata (non contigua)

Allocazione contigua

Ogni file occupa un insieme contiguo di blocchi sul disco.

È necessario conoscere la locazione di partenza (indirizzo del primo blocco) e la lunghezza (numero di

blocchi).

Supporta l’accesso diretto.

Spreco di spazio (perché se alloco i file in maniera contigua possono esserci buchi nel disco nei quali non

entrano altri file e quindi se sommate le dimensioni di questi buchi possono contenere molto più di un file).

Occorre trovare lo spazio sufficiente (problema di allocazione dinamica di memoria).

In determinati casi, i file non possono crescere di dimensione.

Esempio

Mapping da indirizzo logico (LA) a indirizzo fisico, con una dimensione dei blocchi di 512 words:

Blocco da accedere = Q + indirizzo di partenza

Spiazzamento nel blocco = R

Esempio:

- LA= 864

- Q = 1 (Blocco)

- R = 352 (Spiazzamento nel Blocco)

Allocazione contigua modificata

Alcuni sistemi operativi usano uno schema modificato dell’allocazione contigua

Se al file non basta lo spazio di memoria contigua allocata si alloca un ulteriore spazio contiguo (extent) su

una parte libera del disco.

Un file, quindi, può essere composto da uno o più extent.

È necessario avere un contatore degli extent e l’indirizzo del primo extent.

Allocazione concatenata

Ogni file è gestito tramite una lista concatenata di blocchi di disco: i blocchi non devono essere

necessariamente contigui e quindi possono trovarsi in punti diversi del disco.

Da ogni blocco deve partire un collegamento del prossimo blocco.

Seguire questa catena vuol dire fare tanti accessi sul disco (rallenta l’operazione di ricerca).

Esempio:

Semplice: serve solo l’indirizzo di partenza.

Non c’è spreco di spazio

Non supporta l’accesso diretto (solo accesso sequenziale) (devo seguire i puntatori).

I file possono crescere.

Mapping (con blocco di 512 word):

- Il blocco a cui accedere è il Q-esimo nella lista concatenata di blocchi che rappresenta il file.

- Spiazzamento nel blocco = R + 1

Una variante usata in MS-DOS e OS/2 è la File Allocation Table (FAT):

- Tabella con tanti elementi per quanti sono i blocchi sul disco (conservata o in parte o tutta in RAM

-> accesso più veloce).

- Ogni elemento contiene l’indice del prossimo blocco.

File Allocation Table

Utilizzando la FAT si va nella sua posizione 217. Qui trova il blocco successivo (618). Alla posizione 618 della

FAT trova il prossimo indirizzo (339). Infine, va alla posizione 339 e qui trova la fine del file. Da qui vado sul

disco.

Allocazione indicizzata

Mantiene tutti i puntatori ai blocchi dei file in un’unica struttura: il blocco indice (index table).

Vista logica:

Esempio:

Il Blocco indice occupa spazio.

Supporta l’accesso diretto.

Non c’è frammentazione esterna.

Mapping da indirizzo logico a indirizzo fisico nel caso in cui il blocco indice sia contenuto in un solo blocco:

Q = spiazzamento nel blocco indice

R = spiazzamento nel blocco del file

Ad esempio, se Q=3 e R=176 devo andare nel blocco indice e accedere alla posizione 3, ad esempio nella

posizione 3 c’è 1. Accedo al blocco 1 del file e prendo la word 176.

Se un blocco non è sufficiente a contenere il blocco indice di un file, per i blocchi indice si possono

utilizzare:

- schema concatenato

- schema multilivello

- schema combinato

Schema concatenato

L’ultima parte di un blocco indice contiene un puntatore ad un altro blocco indice (se il file è molto grande).

Mapping: (512 -> dimensione del blocco)

Q = blocco della index table (blocco indice)

1

R è usato come segue:

1

Q = spiazzamento nel blocco della index table

2

R = spiazzamento nel blocco del file

2

Allocazione indicizzata: schema a due livelli

Ogni elemento del blocco indice del primo livello, mi da un puntatore che punta ad un blocco indice di

secondo livello. Qui c’è un altro puntatore che punta al blocco dei dati.

3

Mapping (dimensione massima del file 512 )

Q = spiazzamento nell’indice di primo livello (indirizzo iniziale del blocco indice di secondo livello)

1

R è usato come segue:

1

Q = spiazzamento nel blocco della index table (di secondo livello)

2

R = spiazzamento nel blocco del file

2

Schema combinato: Inode di Unix (4k per blocco)

FCB

(Blocchi diretti) Contiene una serie di indirizzi a blocchi di dati, ad esempio 12.

Se il file è più grande di 512x12 il 13 indirizzo punta ad un blocco indice (indiretto singolo). Se questo non

bastasse, c’è un indiretto doppio, il quale punto anch’esso ad un blocco indice di primo livello e a sua volta

ad un blocco indice di secondo livello. Se non dovesse bastare ancora si passa ad un indiretto triplo fino

quindi ad arrivare a blocchi indici di terzo livello.

Questo permette di avere file grandi ma di dimensione piccola oppure gradi file che occupano tutto il disco.

Gestione dei blocchi liberi

Per memorizzare i blocchi liberi si usa il vettore di bit (n bit per n blocchi)

Calcolo del numero del primo blocco libero usando le word:

(numero di bit per word) * (numero di word con valore 0) + offset del primo bit 1

La bit map richiede uno spazio che potrebbe non essere tutto in memoria. Esempio:

12

dim. blocco = 2 byte

30

dim. disco = 2 byte (1 gigabyte)

30 12 18

n = 2 /2 = 2 bit (o 32K byte)

Soluzione alternativa

Lista concatenata (lista blocchi liberi)

- Bassa efficienza nella ricerca

- Non c’è spreco di spazio

Raggruppamento di blocchi per migliorare le prestazioni. Si memorizza l’indirizzo di n blocchi liberi nel

primo blocco libero e nell’ultimo blocco l’indirizzo dei prossimi n blocchi liberi.

Lista concatenata dei blocchi liberi

GESTIONE DELLA MEMORIA SECONDARIA

Dischi magnetici

I dischi magnetici (sono veri e propri dischi) forniscono grandi quantità di storage secondario nei moderni

computer

I dischi contiene farli girare continuamente nel computer poiché avviarlo ci mette qualche secondo, così da

non pagare il tempo della rotazione all’avvio.

- I drive ruotano tra 60 e 200 volte al secondo

- Il transfer rate è la velocità alla quale i dati vengono trasferiti dal drive al computer (dal disco alla

memoria principale)

- Il tempo di accesso è il tempo necessario a muovere il braccio sul cilindro desiderato, più quello

necessario al settore desiderato a ruotare sotto la testina

- Un head crash si verifica quando la testina tocca la superficie del disco (causa una rottura del

disco) [poiché le testine, una sopra e una sotto, leggono i dati tramite induzione magnetica, senza

toccare il disco]

I dischi possono essere rimovibili

I drive si collegano al computer attraverso l’I/O bus

- Esistono diversi tipi di bus, tra cui EIDE, ATA, SATA, USB, Fibre Channel, SCSI

- L’host controller nel computer usa il bus per comunicare con il disk controller che si trova

all’interno del drive (ogni dispositivo del computer ha un controller, che sono dei piccoli chip

dedicati a controllare questi dispositivi, si parlano tra di loro con degli interrupt)

Quando colleghiamo ad esempio il mouse si installa un driver a livello software.

Nastri magnetici

- Nastro magnetico

- È stato uno dei primi supporti di memoria secondaria

- Relativamente permanente e in grado di contenere grandi quantità di dati

- Tempo di accesso elevato (accesso sequenziale)

- Accesso casuale ~ 1000 volte più alto di quello del disco

- Dopo che i dati sono sotto la testina, la velocità di trasferimento è paragonabile a quella di

un disco

Principalmente usato per il backup, per archiviazione di dati utilizzati di rado, e per il trasferimento di dati

tra sistemi

Dischi ottici

Lettura ottica basata sulla riflessione (o sul