Il File System

Memorizzazione delle
Informazioni

Le applicazioni su un calcolatore hanno bisogno di

memorizzare e rintracciare informazioni.

Un processo può utilizzare il suo spazio degli indirizzi per

memorizzare un quantitativo limitato di informazioni.
Permanenza delle Informazioni

Può essere necessario che le informazioni siano

memorizzate per lungo tempo.

Le informazioni memorizzate nello spazio degli indirizzi di

un processo vengono perse al termine dell’esecuzione del
processo.
Indipendenza delle Informazioni

Più processi possono aver bisogno delle stesse informazioni

contemporaneamente per cui è necessario che queste e la
loro allocazione siano indipendenti dal processo.
 I File…

Per memorizzare grandi quantità di informazioni, rendere la

memoria permanente e dare la possibilità a più processi di
accedere alle stesse informazioni è necessario registrare tali
informazioni in dischi o altri supporti in unità dette file.
 …I File…

Il sistema operativo consente la gestione dei file mediante il

modulo di gestione del File System.

Oltre al contenuto proprio del file, il file system gestisce

informazioni complementari relative al file come:

struttura; tipo di accesso;

nome; protezione, ecc.

 …I File (Denominazione)…
I file consentono di ritrovare le informazioni che
contengono mediante il proprio nome sul supporto in cui
risiedono.

Il nome del file si suddivide generalmente in:

[Link]

entrambi con un numero variabile di caratteri e varia

utilizzazione del minuscolo/maiuscolo.
 …I File (Denominazione)…
Spesso l’estensione indica un particolare tipo di file, ad
esempio:

txt per un file di tipo testo;

c per un programma in linguaggio C;

lib per un file contenente una libreria di procedure.

 …I File (Struttura)…
I file, in genere, contengono le informazioni in tre tipi di
strutture:
sequenza non strutturata di byte: consente la massima
flessibilità al programma utente. Sistemi operativi molto
diffusi come Dos e Unix utilizzano questa struttura (a);
sequenza di record a lunghezza fissa: ha perso popolarità
con il tempo (b);
albero di record con campo chiave: è ancora in uso sui
grossi mainframe usati per l’elaborazione di dati
commerciali (c).
 …I File (Struttura)…
1 Byte 1 Record

Chiave Chiave

Chiave Chiave Chiave Chiave

Chiave Chiave

(a) (b) (c)

 …I File (Tipi)…
Nel corso del tempo il modello file, per la sua comodità
d’uso, si è articolato in diversi tipi di file:

file regolari: contengono le informazioni dell’utente, un

programma eseguibile ecc.

directory: conservano la struttura del file system ed

informazioni sui file regolari;

 …I File (Tipi)…

file speciali a caratteri: sono usati per modellare unità di

input/output seriali come video, stampanti, reti, ecc;

file speciali a blocchi: sono usati per modellare unità di

input/output a blocchi come i dischi.

 …I File (Formati)…
Le informazioni nei file sono generalmente contenute in due
formati:

codice ASCII:

rappresenta caratteri quasi tutti leggibili;

i file programma sorgente ed i documenti sono

generalmente registrati in questo formato.

 …I File (Formati)…

codice Binario:

le sequenze di codici sono illeggibili;

di solito i file memorizzati in questa modalità hanno

una struttura interna.

 …I File (Formati)…

Gli esempi precedenti mostrano due file binari:

(a) rappresenta un file eseguibile Unix;

(b) rappresenta un archivio contenente procedure.

 …I File (Accesso)…

Le modalità di lettura delle informazioni in un file sono di

due tipi:

Accesso Sequenziale;

Accesso Casuale.
 …I File (Accesso)…
Accesso Sequenziale:

i byte o i record sono letti uno dopo l’altro, dall’inizio

alla fine;

i vecchi sistemi operativi consentono solo questo tipo

di accesso;

nei file speciali a caratteri si accede in questo modo.

 …I File (Accesso)…
Accesso Casuale:

l’accesso al blocco di informazioni avviene in maniera

diretta;

l’avvento dei dischi ha consentito l’introduzione di

questo metodo di accesso;

generalmente l’accesso è diretto al blocco

e
 …I File (Attributi)…

I sistemi operativi associano ai file altre informazioni come:

data e ora della creazione;

proprietario;

dimensione, ecc.

queste informazioni si definiscono attributi del file.

 …I File (Attributi)…
Campo Significato
Protezione Chi può accedere al file e in che modo
Password Parola d’ordine necessaria per accedere al file
Flag di sola lettura 0 per lettura/scrittura, 1 per sola lettura
Flag di sistema 0 per file normale, 1 per file di sistema
Flag ASCII/binario 0 per file ASCII, 1 per file binario
Lunghezza record Numero di byte in un record
Tempo di creazione Data e ora del momento in cui è stato creato il file
Dimensione attuale Numero di byte nel file
Dimensione massima Dimensione massima che il file può raggiungere

Esempi di attributi dei file

 …I File (Operazioni)…
Il sistema operativo pone a disposizione dell’utente
comandi di alto livello e chiamate di sistema per la gestione
dei file. Alcune chiamate di sistema più comuni sono:

create: creazione del file;

delete: cancellazione del file;

open: apertura del file con varie modalità (read-only,

append, ecc.);
 …I File (Operazioni)…

close: chiusura del file;

read: lettura di blocchi di dati;

write: scrittura di blocchi di dati;

append: aggiunta, in coda al file, di nuovi dati;

seek: posizionamento del puntatore all’interno del file.

…I File (Mappati in Memoria)…

Alcuni sistemi operativi (es. Unix) consentono di mappare

un file in memoria, ossia di caricarlo tutto o in parte,
assegnandogli degli indirizzi virtuali.

Questo permette ai processi di accedere in maniera

trasparente ai file che possono essere quindi contenuti in
memoria centrale per intero o per blocchi.
…I File (Mappati in Memoria)…

Questa tecnica velocizza le operazioni compiute sul file,

soprattutto quando si riferiscono a parti limitate e non
all’intero file.

Quando il processo che sta usando il file termina,

quest’ultimo viene riscritto sul disco.
…I File (Mappati in Memoria)…

La virtualizzazione dell’accesso comporta alcuni problemi

che vanno attentamente gestiti:

in caso di apertura contemporanea del file da parte di più

processi alcune informazioni possono risultare

inconsistenti;
…I File (Mappati in Memoria)

in caso di caduta del sistema alcune informazioni possono

essere perse;

sono necessarie tecniche per la rimozione delle pagine o

dei

blocchi dei file.

 Le Directory…

Per tener traccia dei file, il file system fornisce un indice

comunemente chiamato directory.

I vecchi sistemi operativi prevedevano un’unica directory in

cui confluivano tutti i file.

Questo concetto è ormai superato dai sistemi gerarchici di

directory.
 …Le Directory…
Tipicamente un elemento della directory contiene:

il nome di un file ed eventualmente include anche gli

attributi del file;

in alternativa, il nome di un file ed un puntatore ad

un’altra struttura in cui si trovano gli attributi e gli

indirizzi del disco.

 …Le Directory…
Ogni directory può contenere:

file regolari;

altre directory.

In questo modo, a partire da una directory radice (root

directory) è possibile generare un albero di directory e
subdirectory.
 …Le Directory…

Il tipo di organizzazione dell’albero delle directory dipende

dalle scelte dell’amministratore di sistema. Un tipico
esempio prevede:

la root directory include alcune directory di sistema come

etc, bin, lib, tmp, ecc.;

 …Le Directory…
la root directory include una o più directory come usr per

gli utenti;

la directory usr contiene una subdirectory per ogni

utente

ed ogni utente organizza il proprio sottoalbero nel modo

che ritiene più efficiente e comodo per il tipo di

attività
 …Le Directory…
Directory
Directory Radice
File

Subdirectory Utente File

Progetto di file system / directory

…Le Directory (I path name)…

Quando il file system è organizzato come un albero di

directory, è necessario un qualche modo per specificare i
nomi dei file. Questo può essere fatto in due diversi modi:

path name assoluto;

path name relativo.

…Le Directory (I path name)…

path name assoluto: consiste nel cammino dalla directory

radice al file. I componenti del cammino sono separati da

opportuni simboli di separazione come “ / ” in Unix e “ \ ”

in DOS.
…Le Directory (I path name)…

path name relativo: si usa congiuntamente al concetto di

directory di lavoro. Un utente può definire una directory

come directory di lavoro corrente. In questo caso tutti i

path name che non iniziano con la directory radice sono

considerati relativi alla directory di lavoro.

…Le Directory (Operazioni)…

Alcune tipiche chiamate di sistema per la gestione delle

directory sono:

create: crea una directory vuota;

delete: cancella una directory;

opendir: apre una directory per leggerne il contenuto;

…Le Directory (Operazioni)

closedir: chiude una directory;

readdir: restituisce il prossimo elemento di una directory

vuota;

rename: rinomina una directory;

link: crea un link tra un file esistente ed un pathname;

unlink: rimuove un elemento dalla directory.

Implementazione del file system
Un fattore chiave nell’implementazione della
memorizzazione dei file è tener traccia di quali blocchi del
disco associare a ciascun file.

Le modalità di allocazione dei blocchi e del relativo

reperimento sono:
Allocazione contigua

Allocazione a lista concatenata

Allocazione a lista concatenata con indice

Allocazione mediante uso di tabelle i-node

 Allocazione Contigua…

E’ lo schema di allocazione più semplice, in quanto

memorizza il file in blocchi di disco consecutivi.
 …Allocazione Contigua…
Pregi

è semplice da implementare, poiché tiene traccia del solo

indirizzo di inizio del file memorizzando, quindi, un solo

numero;

è molto efficiente perché permette di leggere l’intero

file

con una sola operazione.

 …Allocazione Contigua
Difetti

non è realizzabile senza che si conosca la dimensione

massima del file;

il disco risulta notevolmente frammentato e molto spazio

viene sprecato.
Allocazione a lista concatenata…

Ogni blocco associato al file contiene:

dati veri e propri;

il numero del blocco successivo assegnato al file.

…Allocazione a lista concatenata…
Pregi

non implica spreco di spazio perché i blocchi vengono

allocati dinamicamente;

nell’elemento della directory viene memorizzato solo

l’indirizzo del primo blocco.

…Allocazione a lista concatenata
Difetti

la lettura sequenziale del file è semplice, ma l’accesso

diretto ai blocchi è estremamente lento;

la quantità di dati nel blocco non corrisponde più ad una

potenza di due.
Allocazione a lista concatenata
con indice…
Assegna ai file:

blocchi di disco non necessariamente contigui;

mantiene l’elenco dei blocchi assegnati mediante una

tabella in memoria.

Questo tipo di allocazione è utilizzata nel sistema operativo

MS-DOS.
…Allocazione a lista concatenata
con indice…
Pregi

l’intero blocco è disponibile per i dati;

l’accesso diretto ad un blocco è molto più rapido;

l’elemento della directory contiene solo il numero del

primo blocco.
…Allocazione a lista concatenata
con indice…
Difetti

lo svantaggio principale consiste nel fatto che ad un gran

numero di blocchi di disco corrisponde una tabella grande

che occupa molto spazio in memoria centrale.

 …Allocazione a lista concatenata
con indice…
File 1 File 2

0 0
Blocco Blocco Blocco Blocco Blocco Blocco Blocco
0 1 2 0 1 2 3
Del file Del file Del file Del file Del file Del file Del file
2 5 3 Blocco Fisico 1 8 7 10

La prima parola di ogni blocco è usata come puntatore al

prossimo blocco.

Memorizzazione di un file come lista concatenata

…Allocazione a lista concatenata
con indice
Blocco Fisico
0
1 8 Inizio File 2
2 5 Inizio File 1
3 0
4
5 3
6 Blocco Inutilizzato
7 10
8 7
9
10 0

Allocazione a lista concatenata che usa una tabella in memoria

 Allocazione mediante uso di
tabelle i-node…

Questo tipo di allocazione è utilizzata nel sistema operativo

Unix.

Gli i-node sono piccole tabelle che contengono:

gli attributi del file;

gli indirizzi dei primi dieci blocchi assegnati al file;

…Allocazione mediante uso di
tabelle i-node…

tre campi che consentono l’indirizzamento dei blocchi

successivi mediante:
blocco a singola indirezione
blocco a doppia ed a tripla indirezione
Gli i-node sono in posizione definita all’interno del file
system.
…Allocazione mediante uso di
tabelle i-node…
Pregi
l’elemento di directory contiene solo il nome del file ed il
numero di i-node;
consente di mantenere in memoria gli i-node dei file
aperti
sprecando poco spazio;
consente di indirizzare un numero enorme di blocchi di
disco;
per i file di piccole dimensioni consente di reperire
rapidamente l’indirizzo dei primi blocchi di disco.
…Allocazione mediante uso di
tabelle i-node…
I-node

Attributi
Blocco a
Indirizzi del disco

singola indirezione

I-node
 …Allocazione mediante uso di
tabelle i-node…
I-node
Indirizzi dei blocchi dei dati
Attributi
Blocco a
Indirizzi del disco

doppia indirezione

I-node
 …Allocazione mediante uso di
tabelle i-node
I-node

Attributi
Blocco a
Indirizzi del disco

tripla indirezione

Indirizzi dei blocchi

dei dati

I-node
 Struttura delle directory

Il file system, mediante il pathname fornito dall’utente:

localizza l’elemento della directory;

estrae le informazioni necessarie per trovare i blocchi di

disco assegnati al file.

Implementazione delle directory
in MS-DOS…
L’elemento di directory del DOS è di 32 byte, contiene:

il nome del file;

l’estensione del file;

tutti gli attributi;

l’indirizzo del primo blocco del disco assegnato al file.

 …Implementazione delle
directory in MS-DOS
Le directory DOS possono contenere elementi che fanno
riferimento a blocchi contenenti altre sub-directory, e
pertanto in DOS è implementata una struttura gerarchica
delle directory.

8 3 1 10 2 2 2 4
Nome del file Dimensione

Numero del
Ampiezza Attributi Riservato Ora Data primo blocco

Elemento della directory MS-DOS

Implementazione delle directory
in Unix
La struttura delle directory Unix è estremamente semplice ed
è composta da:
nome del file;
relativo numero di i-node;
Tutte le informazioni relative al file sono contenute nell’i-
node. Byte 2
Nome del file
Numero di i-node

Elemento della directory Unix

 Unix: Ricerca di una directory
nell’albero
Il blocco 406 è
L’i-node 6 Il blocco 132 è L’i-node 26 la directory
Directory Radice per /usr la directory /usr per /usr/ast /usr/ast
1 • modo 6 • modo 26 •
1 •• dimensione 1 •• dimensione 6 ••
4 bin tempi 19 dick tempi 64 grants
7 dev 132 30 erik 406 92 books
14 lib 51 jim 60 mbox
9 etc 26 ast 81 minix
6 usr L’i-node 6 45 bal L’i-node 26 17 src
8 tmp stabilisce che /usr/ast stabilisce che /usr/ast/mbox
/usr è nel è l’i-node 26 /usr/ast è nel è l’i-node 60
La ricerca di usr
blocco 132 blocco 406
restituisce l’i-node 6
Gestione dello spazio su disco…

I file sono generalmente memorizzati su disco, pertanto la

gestione dello spazio su disco è uno dei problemi
fondamentali nell’implementazione del file system.
È ormai quasi unanime la modalità di registrazione dei file
su disco in blocchi non necessariamente adiacenti.
…Gestione dello spazio su disco…

Questo perché memorizzando un file come una sequenza

contigua di byte si presenta l’ovvio problema che se il file
aumenta di dimensione molto probabilmente dovrà essere
spostato nel disco. Lo stesso problema si ha per i segmenti
in memoria, con la differenza che muovere un segmento in
memoria è un operazione relativamente veloce rispetto allo
spostare un file da una posizione del disco a un’altra.
…Gestione dello spazio su disco…
(Dimensione dei blocchi)

Il primo problema da risolvere è la scelta della dimensione

dei blocchi. La scelta di un blocco molto grande rende più
veloce il tempo di lettura ma provoca maggior spreco di
spazio. Mentre la scelta di un blocco molto piccolo causa
numerosi accessi ai blocchi per leggere i dati ma consente
una gestione più efficiente dello spazio.
…Gestione dello spazio su disco…
(Dimensione dei blocchi)

L’efficienza nel tempo e nello spazio sono intrinsecamente

in conflitto nella scelta della dimensione delle unità di
allocazione. Confrontando la velocità di trasferimento dei
dati e l’efficienza dello spazio su disco si può vedere che a
una buona utilizzazione dello spazio corrisponde una bassa
percentuale di dati e viceversa.
…Gestione dello spazio su disco…
(Dimensione dei blocchi)

Un compromesso si raggiunge scegliendo la dimensione del

blocco di allocazione di: 512 byte, 1 K, 2 K.
Considerando che il settore è la minima unità fisica
leggibile dal disco avremo che la dimensione del settore sul
disco è generalmente di 512 byte e la lettura di un blocco di
allocazione di 1 K causerà sempre la lettura consecutiva di
due settori di disco.
…Gestione dello spazio su disco…
(Gestione dei blocchi liberi)
Il problema successivo alla scelta della dimensione del
blocco è quello della gestione dei blocchi liberi.
I metodi usati comunemente sono due:
lista concatenata di blocchi che contengono gli indirizzi
dei blocchi liberi nel disco;
mappa di bit: un disco di n blocchi richiede una mappa di
n bit. I blocchi liberi si rappresentano con 1 sulla mappa,
i blocchi allocati con 0 (o viceversa).
…Gestione dello spazio su disco…
(Gestione dei blocchi liberi)

Un esempio di lista concatenata può essere ottenuto

consideriamo un blocco di 1 K con un numero di blocco del
disco di 16 bit, ogni blocco sulla lista libera contiene i
numeri di 511 blocchi liberi. Mentre per esempio un disco
di 20Mbyte richiede 20Kbit per la mappa che corrisponde a
soli 3 blocchi.
 …Gestione dello spazio su disco…
(Gestione dei blocchi liberi)
Blocchi di disco liberi: 16, 17, 18
42 230 86 1001101101101100
136 162 234 0110110111110111
210 612 897 1010110110110110
97 342 422 0110110110111011
41 214 140 1110111011101111
63 160 223 1101101010001111
21 664 223 0000111011010111
48 216 160 1011101101101111
262 320 126 1100100011101111

310 180 142 0111011101110111

516 482 141 1101111101110111
Un blocco del disco di 1 K può contenere Una mappa di bit
512 numeri di blocchi di disco di 16 bit
…Gestione dello spazio su disco…
(Gestione dei blocchi liberi)

Il metodo della lista concatenata è più efficiente se il disco è

quasi pieno, poiché il numero di blocchi è molto limitato.
Inoltre in queste condizioni, la mappa di bit potrebbe
risultare spesso piena e richiedere continui accessi ad altre
parti di mappa per assegnare blocchi liberi. Se c’è
abbastanza memoria principale per contenere la mappa di
bit, è generalmente preferibile quest’ultimo metodo.
 Affidabilità del file system…

Il file system può contenere dati che non possono essere

persi poiché di difficile o costoso recupero.
L’affidabilità del file system va perseguita spesso anche a
scapito dell’efficienza o di economie.
 …Affidabilità del file system…
(Gestione dei blocchi fuori uso)

I dispositivi di memorizzazione presentano spesso blocchi

inutilizzabili:
difetti di fabbricazione;
usura;
urti violenti.
I blocchi inutilizzabili non devono essere assegnati a nessun
file, necessità quindi una gestione appropriata.
 …Affidabilità del file system…
(Gestione dei blocchi fuori uso)

Le soluzioni per la gestione dei blocchi danneggiati possono

essere di due tipi:
soluzione hardware;
soluzione software.
 …Affidabilità del file system…
(Gestione dei blocchi fuori uso)

Soluzione hardware:
una parte di disco è riservata per tenere traccia dei
blocchi rovinati e contiene dei blocchi di riserva;
in fase di inizializzazione il controllore del dispositivo
legge questi blocchi e li sostituisce con blocchi di
riserva, memorizzandone l’avvenuta sostituzione;
questa soluzione è trasparente al file system.
 …Affidabilità del file system…
(Gestione dei blocchi fuori uso)

Soluzione software:
l’utente o il file system tiene traccia dei blocchi rovinati
assegnandoli tutti ad un file speciale da non utilizzare;
nelle operazioni di backup è necessario porre attenzione
per evitare la lettura di questo file.
 …Affidabilità del file system…
(Gestione dei blocchi fuori uso)

Consideriamo come esempio il comportamento del sistema

operativo MS-DOS:
marca questi blocchi con un codice speciale ‘888’ nella
File Allocation Table;
il file system ignora questi blocchi che non saranno mai
assegnati a nessun file e mai letti o scritti.
 …Affidabilità del file system…
(Copie di backup)

Il metodo per ridurre le perdite di dati in caso di crash del

file system o del disco è effettuare le copie di backup.
Nella pianificazione delle operazioni di backup vanno
valutati principalmente:
la frequenza con cui effettuare le copie di backup;
i file che presentano la maggior necessità di essere
copiati;
la tecnica migliore per effettuare il backup.
 …Affidabilità del file system…
(Copie di backup)

Frequenza: la scelta va pianificata in base alla quantità di

lavoro svolta nel tempo ed al costo di ripristino.
Generalmente la frequenza è di tipo:
giornaliero;
settimanale;
mensile;
annuale (solo per archivi storici).
 …Affidabilità del file system…
(Copie di backup)
Scelta dei file: la scelta va pianificata in base al contenuto
dei file ed al costo di ripristino. Ad esempio:
i file critici potrebbero essere raggruppati in directory
dedicate delle quali si effettua copia con maggiore
frequenza;
la duplicazione di alcuni file critici può essere opportuna
se il quantitativo di memoria sprecato è giustificabile.
Limita i danni da problemi locali.
 …Affidabilità del file system…
(Copie di backup)
Tecnica di backup: la scelta va pianificata in base al tempo
disponibile ed al costo sopportabile per i supporti. Le
tecniche di backup possono essere:
backup su nastri dell’intero file system;
backup incrementale (copia solo dei file nuovi o
modificati dall’ultimo backup);
duplicazione incrociata dei dati su due dispositivi: metà di
ogni disco contiene i propri dati e l’altra metà contiene i
dati dell’altro disco.
 …Affidabilità del file system…
(Consistenza del file system)
Nel corso della vita del file system può succedere che la sua
consistenza venga a mancare a causa:
crash;
programmi che non rispettano le regole di allocazione;
altro.
La maggior parte dei sistemi operativi prevede un
programma di servizio per la verifica della consistenza del
file system e la correzione degli errori.
 …Affidabilità del file system…
(Consistenza del file system)

Ad esempio i controlli di consistenza di UNIX sono di due

tipi:
sui blocchi;
sui file.
…Affidabilità del file system…
(Consistenza del file system)

Nell’effettuare il controllo di consistenza sui blocchi UNIX

usa una tabella con due contatori per ogni blocco:
il primo registra quante volte il blocco è presente in un
file;
il secondo quante volte il blocco è presente nella lista
libera.
 …Affidabilità del file system…
(Consistenza del file system)
Il test consiste nella scansione degli i-node, per individuare
blocchi assegnati e la scansione della lista dei blocchi liberi.
Al termine del check si possono verificare i seguenti casi:
Caso normale: un blocco è presente una sola volta nella
lista xor in un file;
Blocco mancante: un blocco non è presente nella lista
libera e non è assegnato a nessun file, viene assegnato
alla lista libera;
…Affidabilità del file system…
(Consistenza del file system)
Blocco duplicato nella lista libera: il doppio riferimento
viene cancellato;
Blocco assegnato a due file: è il caso più grave perché è
sintomo di possibili dati alterati. Il contenuto del blocco è
copiato in un altro blocco ed ognuno dei blocchi
assegnato ad un file;
Blocco presente nella lista libera ed assegnato ad un file:
viene eliminato dalla lista libera.
 …Affidabilità del file system…
(Consistenza del file system)
Numero di blocco Numero di blocco
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1101011110011100 Blocchi in uso 1101011110011100

0010100001100011 Blocchi liberi 0010100001100011
(a) (b)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1101011110011100 Blocchi in uso 1101021110011100

0010200001100011 Blocchi liberi 0010100001100011
(c) (d)
…Affidabilità del file system…
(Consistenza del file system)

UNIX quando effettua il controllo di consistenza sui file

tiene conto che file distribuiti su diverse directory possono
puntare allo stesso file fisico, e quindi allo stesso i-node (file
di tipo link) in tal caso il contatore di link dell’i-node è > 1.
Nel test l’albero delle directory viene interamente percorso
e un contatore temporaneo per ogni i-node indica quanti file
fanno riferimento ad ogni i-node.
…Affidabilità del file system…
(Consistenza del file system)

I risultati che si possono verificare sono:

risultato normale: contatore temporaneo=contatore i-
node;
contatore temporaneo < del contatore di link: anche se
tutti i file
vengono rimossi, l’i-node resta bloccato. Al valore del
link viene assegnato il valore del contatore;
…Affidabilità del file system…
(Consistenza del file system)
contatore temporaneo > del contatore di link:
se alcuni file vengono rimossi, il valore dei link si
azzera;
l’i-node viene reso libero;
i blocchi da esso riferiti vengono assegnati alla lista
libera;
alcuni file puntano erroneamente all’i-node e i dati
vengono persi;
il contatore di link viene aggiornato al valore attuale.
…Affidabilità del file system…
(Prestazioni del file system)
L’accesso al disco è un operazione notevolmente più lenta
della lettura in memoria. Molti file system prevedono
tecniche per ridurre il numero di accessi al disco come:
caching;
riduzione dei movimenti del braccio del disco
(soluzione soft);
riduzione dei movimenti del braccio del disco
(soluzione hard).
…Affidabilità del file system…
(Prestazioni del file system)

Una delle tecniche usate più comunemente è il block cache

in cui un certo numero di blocchi in memoria vengono
riservati per contenere blocchi di disco. La quantità dei
blocchi riservati va scelta in funzione:
della memoria utilizzata;
del miglioramento delle prestazioni richieste.
…Affidabilità del file system…
(Prestazioni del file system)

I principi operativi che la regolano sono:

ad ogni richiesta di un blocco viene scandita la tabella dei
blocchi in memoria per verificarne la presenza;
se non è presente il blocco viene caricato dal disco,
copiato nella chache e poi reso disponibile alle richieste;
la lista può essere gestita con normali algoritmi di
rimpiazzamento delle pagine come FIFO e LRU;
…Affidabilità del file system…
(Prestazioni del file system)

i blocchi critici vengono immediatamente riscritti sul

disco quando modificati;
per gli altri blocchi si può decidere di riscriverli subito
oppure con una determinata frequenza.
…Affidabilità del file system…
(Prestazioni del file system)

UNIX,ad esempio , ogni 30 secondi riscrive tutti i blocchi

modificati su disco (oppure a richiesta dell’utente), mentre
MS-DOS riscrive immediatamente ogni blocco modificato.
…Affidabilità del file system…
(Prestazioni del file system)
La riduzione dei movimenti del braccio del disco (soluzione
soft) avviene nei seguenti passi:
raggruppamento di blocchi in uso. Andando a stimare i
blocchi a cui si accede con maggiore probabilità in
sequenza (o il più vicino possibile), al fine di ridurre i
movimenti della testina. Si può osservare che :
con la gestione mediante mappa di bit è più facile
scegliere un blocco libero vicino al blocco precedente;
con la gestione mediante lista è più difficoltoso.
…Affidabilità del file system…
(Prestazioni del file system)

posizione dell’indice dei blocchi . Tenendo conto che

la lettura di un file richiede comunque almeno 2 accessi
uno all’i-node ed uno al blocco e che il posizionamento
degli i-node o della tabella di allocazione dei file al
centro del disco per ridurre la distanza tra questi ed i
blocchi a cui questi fanno riferimento (fattore 2) ;
…Affidabilità del file system…
(Prestazioni del file system)

partizioni aperte. Si tende ad avvicinare il più possibile

gli i-node ai blocchi cui fanno riferimento nel seguente
modo (Fig.2):
divisione del disco in gruppi di cilindri, ognuno con i
propri i-node e la propria lista dei blocchi liberi;
quando una partizione esaurisce i blocchi, un blocco
può essere allocato in una partizione diversa.
…Affidabilità del file system…
(Prestazioni del file system)

Gli i-node sono collocati Il cerchio è diviso in gruppi di

vicino all’inizio del disco Cilindro ognuno con i suoi
proprietari

Gruppo di cilindro
(a) Posizione dell’indice dei blocchi (b) Partizioni aperte
…Affidabilità del file system…
(Prestazioni del file system)

interleave: un processo richiede un tempo tb per richiedere

e recuperare un blocco. In situazioni (frequenti) di

richieste consecutive di blocchi sequenziali può accadere
che:
il blocco richiesto può essere già passato sotto la
testina;
bisogna attendere una rotazione intera.
…Affidabilità del file system…
(Prestazioni del file system)

La tecnica di interleaving alloca i blocchi fisici del disco in

ordine non sequenziale stretto, ma sequenziale con salti
(fattore di interleaving).

Sia tr il tempo di rotazione del disco avremo che:

fattore di interleaving = [tr / tb ] + 1

…Affidabilità del file system…
(Prestazioni del file system)
Consideriamo il seguente esempio:

tr = 16.67 msec , tb = 4 msec

fattore di interleaving : ¼ di giro

2 4
3 1 1 7

43 42 41
4 8
44 40 0 0

45 49
5 9 5 3
46 47 48

6 8 2 6
7 9
(a) Senza interallacciamento (b) Con interallacciamento
…Affidabilità del file system…
(Prestazioni del file system)
La riduzione dei movimenti del braccio del disco (soluzione
hard) avviene mediante la schedulazione del braccio del
disco. Il tempo necessario per leggere un blocco di disco
dipende da:
seek time: spostamento della testina sul cilindro;
latency time: tempo di rotazione per raggiungere il settore
richiesto;
transfer time: tempo di trasferimento.
 …Affidabilità del file system…
(Prestazioni del file system)

Il ritardo predominante è dato dal seek time, per cui vari

algoritmi sono stati ideati per ottimizzare il movimento del
braccio delle testine. Alcuni esempi sono:
algoritmo FCFS (First Come First Served):
serve le richieste nell’ordine in cui giungono;
non richiede nessun specifico supporto hardware o
software;
…Affidabilità del file system…
(Prestazioni del file system)

è l’algoritmo più corretto nei riguardi delle richieste

ma non ottimale;
costringe il braccio del disco ad un superlavoro.
…Affidabilità del file system…
(Prestazioni del file system)

algoritmo SSF (Shortest Seek First):

mantenendo in tabella tutte le richieste pendenti,
l’SSF
si sposta sempre sulla richiesta più vicina a quella
appena servita;
riduce di circa la metà gli spostamenti sul disco
rispetto al FCFS;
presenta un problema di localizzazione delle richieste.
 …Affidabilità del file system…
(Prestazioni del file system)

Posizione iniziale Richieste precedenti

x x xx x x x
0 5 10 15 20 25 30 35 Cilindro

Tempo

Sequenza di spostamenti

Algoritmo SSF per la schedulazione

dei movimenti del braccio
…Affidabilità del file system…
(Prestazioni del file system)

algoritmo dell’ascensore:
mantiene in tabella le richieste pendenti;
un bit up/down indica la direzione attuale del braccio
del disco;
serve le richieste più vicine proseguendo sempre nella
stessa direzione;
…Affidabilità del file system…
(Prestazioni del file system)

cambia direzione quando raggiunge l’estremità o

quando non ci sono più richieste nella direzione
attuale;
la quantità massima di cilindri di cui deve essere
spostato il braccio per servire le richieste pendenti è
fisso: due volte il numero dei cilindri;
concilia meglio equità di servizio con efficienza.
 …Affidabilità del file system…
(Prestazioni del file system)

Posizione iniziale

x x xx x x x
0 5 10 15 20 25 30 35 Cilindro

Tempo
Sequenza di spostamenti

Algoritmo dell’ascensore
 …Affidabilità del file system
(Prestazioni del file system)

Alcuni driver di disco evoluti permettono di conoscere il

numero di settore attualmente in lettura. Ciò consente al
software di I/O di “inserire” prima delle altre una eventuale
richiesta per un settore della stessa traccia o di altra traccia
dello stesso cilindro che stà per passare sotto la testina.
 …Modelli di protezione…

Gli utenti operano sugli archivi per mezzo dei processi di

loro proprietà: le operazioni eseguibili dal generico processo
sono quindi limitate dai diritti di accesso attribuiti al suo
proprietario.
Le politiche che regolano l’attribuzione dei diritti di accesso
agli utenti competono al sistema operativo oppure agli utenti
medesimi.
 …Modelli di protezione

Spetta invece esclusivamente al sistema operativo (file

system) realizzare i meccanismi di protezione che
impediscono agli utenti di superare i limiti dei propri diritti
di accesso.
 Dominio di protezione…

Un modello generale di questi meccanismi è basato sul

concetto di dominio di protezione. Un dominio di protezione
è un insieme di coppie del tipo (Oggetto, DirittiDiAccesso).
Ad esempio:
(Fi , {r,w}) esprime il possesso del diritto di lettura e di
quello di scrittura sull’archivio Fi ;
(Dj , {r,x}) esprime il possesso del diritto di lettura e
quello di ricerca del repertorio Dj .
 …Dominio di protezione…

Il modello basato sui domini consente di formalizzare il

concetto della migrazione dei processi in un dominio di
protezione diverso da quello di appartenenza (ad esempio
per consentire ad un proprietario P di migrare nel dominio di
protezione di P’ solo durante l’esecuzione di un particolare
programma che richiede operazioni non consentita a P ed
invece consentite a P’).
 …Dominio di protezione…
Per formalizzare la facoltà di migrare da un dominio
all’altro è sufficiente considerare anche i domini come
oggetti, ai quali è associata la sola operazione di ingresso
(in).
Ad esempio:
(Δ3 , {in}) esprime la facoltà di migrare nel dominio Δ3.
Una volta migrato in un nuovo dominio, l’utente o il
processo proveniente da un altro dominio non ha la
possibilità di migrare ulteriormente.
…Dominio di protezione…

Δ1
D3, {r,w,x}
D4, {r,w,x}
D1, {r,w,x} F2, {x} D5, {r,w}
D2, {r,w,x} F1, {r,w,x}
F3, {r,w}
F4, {r,w} Δ2

F1, {r,x}
Esempio di domini di protezione
D6, {r,w,x} Δ3
F2, {r,w}
F5, {r,w,x}
 …Dominio di protezione…

Tabella 10.8 Rappresentazione dei domini di protezione sotto forma di matrice

D1 D2 D3 D4 D5 D6 F1 F2 F3 F4 F5

Δ1 {rwx}{rwx} {rx} {x} {rw} {rw}

Δ2 {rwx}{rwx} {wx} {rwx} {x}

Δ3 {rwx} {rx} {rw} {rwx}

 …Dominio di protezione

Tabella 10.9 Una matrice di protezione che rappresenta la possibilità

di migrazione tra domini
D1 D2 D3 D4 D5 D6 F1 F2 F3 F4 F5 Δ3

Δ1 {rwx}{rwx} {rx} {x} {rw} {rw} {in}

Δ2 {rwx}{rwx} {wx} {rwx} {x}

Δ3 {rwx} {rx} {rw} {rwx}

Strutture dati per la protezione…

La matrice di protezione è tipicamente molto grande e

sparsa. Una struttura più efficiente è ottenuta rappresentando
le stesse informazioni attraverso:
liste di controllo degli accessi;
liste associate ai domini.
…Strutture dati per la protezione…
(Liste di controllo degli accessi )

Ogni lista è associata ad un oggetto ed i suoi elementi sono

coppie del tipo (dominio, insieme di diritti di accesso).
Ciascuna lista elenca tutti i diritti di accesso sull’oggetto che
competono ad un certo dominio.
Piuttosto che ai domini di protezione, gli elementi delle liste
di controllo degli accessi sono spesso riferite agli utenti.
…Strutture dati per la protezione…
(Liste di controllo degli accessi )

Gli utenti sono identificati con una coppia del tipo (gruppo,
nome), dove i nomi degli utenti sono locali ai gruppi (uno
stesso nome può essere attribuito a più utenti, purché
appartenenti a gruppi diversi).
Comunque siano codificate, le liste di controllo degli accessi
sono attribuiti dagli archivi (o dei repertori).
…Strutture dati per la protezione
(Liste associate ai domini )

In questo caso ogni lista è associata ad un dominio e i suoi

elementi sono coppie del tipo (oggetto, Insieme Di Diritti di
accesso). Ogni elemento della lista esprime la facoltà
(capability) dell’utente di accedere ad un dato oggetto con i
diritti compresi in un certo insieme. Ogni lista viene perciò
chiamata C-list (capability list) ed è un attributo degli utenti
e dei loro processi.
Protezione nel sistema operativo
UNIX…

I meccanismi di protezione degli archivi adottati in UNIX si

basano sulle liste di controllo degli accessi. Ogni utente è
identificato da una coppia del tipo (gruppo, nome).
Dato che ogni processo è attribuito a un utente proprietario
(chiamato anche proprietario reale), l’identificazione degli
utenti si propaga ai loro processi.
 …Protezione nel sistema
operativo UNIX…
Ogni descrittore di archivio contiene invece una struttura
dati simile, dal punto di vista del contenuto informativo a
una lista di controllo degli accessi. Essa consiste di tre
codici:
DirittiProprietario;
DirittiGruppo;
DirittiAltriUtenti.
 …Protezione nel sistema
operativo UNIX…

Che esprimono i diritti di lettura, scrittura ed esecuzione

rispettivamente:
all’utente proprietario;
ai rimanenti utenti del gruppo;
agli utenti dei rimanenti gruppi.
 …Protezione nel sistema
operativo UNIX…
Se ad esempio:
DirittiProprietario, DirittiGrtuppo, DirittiAltriUtenti

registrati nel descrittore dell’archivio Fi hanno

ordinatamente i valori 111,101 e 001 si intende che:

il proprietario dell’archivio Fi ha tutti i diritti di accesso;
gli altri utenti del suo gruppo possiedono i diritti di lettura
ed esecuzione;
i rimanenti utenti del sistema possiedono esclusivamente
il diritto di esecuzione.
 …Protezione nel sistema
operativo UNIX…

Questa convenzione non permette di discriminare tra utenti

dello stesso gruppo del proprietario ne tra quelli
appartenenti a gruppi diversi da quello del proprietario. A
questa minore generalità rispetto alle liste di controllo degli
accessi corrispondenti una maggiore compattezza dei dati.
 Identificazione degli utenti…

I meccanismi di protezione degli archivi sono basati sul

presupposto della sicura identificazione degli utenti.
Nei sistemi interattivi multi-utente, il progenitore di tutti i
processi di un generico utente è quello che viene generato
quando esso si connette al sistema attraverso un terminale.
 …Identificazione degli utenti…

Per ogni processo diverso dal progenitore, la responsabilità

di definire il proprietario spetta esclusivamente al sistema
operativo, che assegna il figlio allo stesso utente che risulta
proprietario del processo padre.
L’identificazione del proprietario del figlio è sicura se lo è
quella del padre.
 …Identificazione degli utenti…

In conclusione, la sicurezza degli archivi è fondata sulla

corretta definizione del proprietario del processo
progenitore, che a sua volta dipende dalla sicura
identificazione dell’utente che si connette attraverso il
terminale.
 …Identificazione degli utenti

La tecnica comunemente usata è quella della parola d’ordine

(password), che l’utente deve trasmettere attraverso il
terminale, insieme al nome con il quale è registrato nel
sistema, ogni volta che si connette.