6.3 La gestione dei processi
stallo 9
void filosofo_i_esimo(){
while (1) {
// medita
wait(mutex);
wait(f[i]);
wait(f[(i+1)%5]);
signal(mutex);
// mangia
signal(f[i]);
signal(f[(i+1)%5]);
}
}
Sistema Operativo
soluzione corretta
si utilizzano un
semaforo per ogni
forchetta (f[1..5]) per
evitare che venga
utilizzata da più
filosofi, ed un
semaforo per la mutua
esclusione (mutex) al
momento del prelievo
delle forchette
Architettura degli elaboratori 1 - A. Memo
373
6.4 La gestione della memoria
generalità


nei SO multitasking dobbiamo far coesistere più
processi nella memoria principale
il SO deve gestire la memoria
– virtualizzando la dimensione della memoria fisica
ed adeguandola allo spazio logico di più processi
– caricando i programmi in memoria (loader)
– assegnando e recuperando la memoria ai vari
processi (allocation e de-allocation)
– rimpiazzando gli spazi opportuni in base alle
richieste (replacement)
– realizzando opportuni schemi di protezione
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
374
6.4 La gestione della memoria
manipolazione degli indirizzi
file
sorgente
... ;
char x = 0;
... ;
identificatore
indirizzo
assoluto
rilocabile
COMPILER
LINKER
xxxx3A
indirizzo
rilocabile
indirizzo
fisico
Sistema Operativo
12B5
file obj
LOADER
indirizzo
file exe
memoria
secondaria
S.O.
CPU/MMU
890E
C3B5
variabile indirizzo logico
Architettura degli elaboratori 1 - A. Memo
swap
C:8
P:1
S:2
375
6.4 La gestione della memoria
loader 1

caricamento dinamico
– al fine di minimizzare l’occupazione di
memoria, si carica solo la parte necessaria del
programma, e poi si attivano swap opportuni

linking dinamico
– caricamento dinamico delle librerie alla loro
occorrenza (Dynamic Link Libraries o Shared
Object)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
376
6.4 La gestione della memoria
loader 2

overlay
– divisione del programma tra moduli che devono
risiedere sempre in memoria e moduli autonomi
che svolgono funzioni specifiche
– caricamento stabile dei moduli fissi e
caricamento alternato dei moduli specifici
– adottato nei SO che non adottano il principio
della memoria virtuale, la gestione è a carico
dell’applicazione
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
377
6.4 La gestione della memoria
allocazione della memoria 1

a singola partizione
– la memoria è condivisa tra l’unico programma
utente ed il SO
– per evitare conflitti si utilizzano due registri:
base, utilizzato anche per la rilocazione, che
punta all’inizio dell’area di memoria del
proceso utente, e limite, che contiene la
dimensione massima dello spazio utente
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
378
6.4 La gestione della memoria
allocazione della memoria 2
CPU
Indirizzo Logico
?
utente
limite
SI
IL<limite
indirizzo
illegale
NO
S.O.
Sistema Operativo
base
+
Architettura degli elaboratori 1 - A. Memo
Indirizzo Fisico
379
6.4 La gestione della memoria
allocazione della memoria 3

a partizioni multiple
– la memoria è condivisa da più programmi utente
e dal SO
– ad ogni processo viene assegnata una partizione
fissa, di dimensione prestabilita (molto poco
efficiente) o in base alle esigenze del processo
– si inducono problemi analoghi a quelli della
paginazione (tecniche di allocazione e frammentazione interna) (compattazione)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
380
6.4 La gestione della memoria
allocazione della memoria 4

paginazione
– tecnica già affrontata nell’analisi delle CPU
perché la tendenza è di gestirne il meccanismo
sempre più con modalità hardware (più veloci)
– si divide la memoria in blocchi di dimensioni
uguali (frame in memoria fisica, page in
memoria logica)
– ai processi vengono assegnate le pagine
necessarie, anche non consecutive
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
381
6.4 La gestione della memoria
allocazione della memoria 5

paginazione (segue)
– l’indirizzo si scompone in due campi, e la
traduzione da PageL a PageF avviene mediante
una page table, normalmente implementata
tramite TLB
– nella page table si possono aggiungere anche bit
per la protezione
– la paginazione permette anche la condivisione in
sola lettura (programmi condivisi e dati distinti)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
382
6.4 La gestione della memoria
allocazione della memoria 6

segmentazione
– la memoria è vista come un insieme di segmenti di
diverse dimensioni
– un indirizzo è composto dall’indirizzo di inizio del
segmento (o da un indice che lo identifica) e
dall’offset del dato dentro al segmento
– la traduzione da indirizzo logico (segmento più
offset) in indirizzo fisico avviene mediante tabelle,
normalmente complete di bit di protezione
– si induce frammentazione esterna
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
383
6.4 La gestione della memoria
memoria virtuale 1

già trattata nell’analisi delle CPU
– consente di eseguire programmi più grandi della
memoria fisica a disposizione
– consente di caricare in memoria solo le parti più
utilizzate del programma
– è più facile da programmare rispetto agli overlay o
tecniche analoghe perché indipendente dal sistema
– aumenta il tasso di multitasking della CPU
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
384
6.4 La gestione della memoria
memoria virtuale 2


può essere implementata sia tramite demand
paging che con demand segmentation
demand paging
– un processo è costituito da un insieme di pagine
poste in memoria secondaria e solo quella
necessaria è presente anche in memoria principale
– si può anche tentare di prevedere quali saranno le
prossime pagine ed anticiparne il caricamento
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
385
6.4 La gestione della memoria
memoria virtuale 3

demand paging (sequenza operativa)
– dato l’indirizzo logico, mediante funzione di
traduzione si perviene all’indirizzo fisico
– si controlla il bit di validità nella tabella:
se bit=1 vuol dire che la pagina è in memoria
principale, e quindi si procede al recupero del dato
 se bit=0 la pagina è su disco, e si produce page fault

– si controlla se l’operazione richiesta è consentita

Sistema Operativo
in caso contrario viene ancora prodotto un page fault
Architettura degli elaboratori 1 - A. Memo
386
6.4 La gestione della memoria
memoria virtuale 4

demand paging (page fault)
– se è dovuto ad accesso illegale, il processo viene
fatto terminare e le sue pagine rilasciate
– altrimenti si cerca un frame libero
se cè’ lo si alloca
 se non c’è, si rimpiazza uno già utilizzato (replacement)
eventualòmente salvando le pagine modificate (dirty bit)

– si aggiorna la page table in base al nuovo stato
– si riparte dall’istruzione che ha causato il page fault
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
387
6.4 La gestione della memoria
memoria virtuale 5

demand paging (politiche di rimpiazzo 1)
– FIFO, First In First Out, implementata con una
lista degli ingressi o con l’orario di arrivo (?),
facile ma poco efficiente
– LRU, Least Recently Used, si sostituisce la
pagina che è rimastata inutilizzata da più tempo,
richiede l’orario dell’ultimo impiego (?); si
adottano tecniche più semplici quali il contatore
di accessi alla pagina (LFU) o tramite stack
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
388
6.4 La gestione della memoria
memoria virtuale 6

demand paging (politiche di rimpiazzo 2)
– LRU a bit di accesso, ad ogni accesso si setta
il bit relativo alla pagina, e periodicamente si
azzerano tutti i bit, semplice ma inefficace
– LRU a bit multipli di accesso, invece di
azzerarli, i bit di accesso vengono memorizzati
in un byte shiftando il contenuto preesistente
(rappresenta una storia della pagina negli ultimi
8 cicli di clock)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
389
6.4 La gestione della memoria
memoria virtuale 7

demand paging (assegnazione dei frame)
– all’avvio di un processo vanno attribuiti allo
stesso un certo numero di frame
– il numero di frame posseduti influenza la
probabilità di page fault
– vengono attribuiti in base alla priorità del
processo ed alla sua dimensione
– il rimpiazzo di una pagina è bene venga limitato
ai frame posseduti da quel processo
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
390
6.4 La gestione della memoria
memoria virtuale 8

demand paging (working-set model)
– se le pagine richieste in una certa attività sono
note a priori (working-set). possono essere
caricate preventivamente, al fine di eliminare o
minimizzare i page fault
– è il SO che memorizza i working-set delle
applicazioni in uso e li riutilizza alla prossima
esecuzione
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
391
6.5 La gestione dell’I/O
generalità 1


la gestione dell’I/O è la parte più monotona,
meno impegnativa e più consistente dei SO
i dispositivi di I/O sono molto diversi tra di
loro come modalità d’uso e prestazioni:
dischi (a livello logico, come estensione della memoria principale, sono anche una risorsa)
terminali video (testuali o grafici)
dispositivi d’ingresso (tastiera, mouse, bar reader)
stampanti
nastri magnetici
schede di rete
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
392
6.5 La gestione dell’I/O
generalità 2


l’obiettivo dei moderni SO è di gestire con
le medesime modalità, ove possibile, tutti i
dispositivi di I/O
l’organizzazione generale prevede almeno
tre componenti:
– il gestore della risorsa
– il controllore della risorsa
– la risorsa
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
393
6.5 La gestione dell’I/O
generalità 3
richiesta
utilizzo
Gestore della risorsa
verifica
accesso
accesso
negato
device
azioni
driver
elementari
risultato
processi utilizzo
utente
controllore
della risorsa risorsa
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
394
6.5 La gestione dell’I/O
gestore della risorsa

i compiti del gestore della risorsa sono:
– verificare se il processo richiedente ha i diritti
necessari per effettuare l’operazione richiesta
– accodare la richiesta nella coda delle richieste e
predisporre gli eventuali ed opportuni buffer
– scomporre le richieste pervenute nelle singole
attività necessarie, passando dalla visione astratta
e generalizzata della risorsa a quella reale
– utilizzare il driver della risorsa per accedervi
– intercettare e gestire le interruzioni della risorsa
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
395
6.5 La gestione dell’I/O
controllore della risorsa

il controllore della risorsa, il più delle volte
implementato con dispositivi hardware
programmabili, deve
– pilotare direttamente l’interfaccia della risorsa,
accedendovi a livello fisico
– è quasi sempre dipendente dal particolare tipo
di dispositivo di I/O gestito e qundi totalmente
privo di standard
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
396
6.5 La gestione dell’I/O
esempio: lo spooling



la stampante è una delle periferiche di uscita
più lente e con tempi di risposta altamente
variabili
fa normalmente uso di un buffer di stampa,
ma inevitabilmente presenta un comportamento a burst
Simultaneous Peripherical Operation On
Line (SPOOL) sostituisce il buffer con un
file in memoria secondaria
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
397
6.5 La gestione dell’I/O
esempio: il disco magnetico




ammettendo una coda di richieste, è utile
schedularle secondo politiche appropriate:
FCFS, First Come First Served, esegue le
richieste così come sono arrivate
SSTF, Shortest Seek Time First, si esegue
prima la richiesta più vicina
SCAN, si eseguono le richieste più vicine,
mantenendo la direzione di scansione
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
398
6.5 La gestione dell’I/O
disco: politica FCFS
0
5
10
15
20
25
30
35
40
TFCFS = 4 + 2 + 22 + 32 + 15 = 75
molto semplice ma poco efficiente
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
399
6.5 La gestione dell’I/O
disco: politica SSTF
0
5
10
15
20
25
30
35
40
TSSTF = 2 + 2 + 7 + 15 + 32 = 58
efficiente, ma usura maggiormente i cilindri centrali
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
400
6.5 La gestione dell’I/O
disco: politica SCAN
0
5
10
15
20
25
30
35
40
TSCAN = 3 + 17 + 22 + 2 + 8 = 52
efficiente e con trattamento paritetico
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
401
6.6 File system e protezione
generalità



Il File System (FS) garantisce l’accesso e
l’organizzazione della memoria secondaria
il FS permette di vedere più dischi fisici
come lo stesso volume logico oppure più
volumi logici sullo tsesso disco fisico
la sua gestione si integra facilmente con
quella della protezione e della sicurezza
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
402
6.6 File system e protezione
file




un file è un’insieme di informazioni caratterizzate
da un nome comune e memo-rizzate in memoria
secondaria
è una struttura logica mappata in un dispositivo
fisico
il formato viene scelto alla sua creazione
le caratteristiche dei file sono:
attributi
struttura
operazioni ammesse
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
403
6.6 File system e protezione
attributi 1

gli attributi che caratterizzano un file sono
–
–
–
–
–
–
nome (da 8 a 256 caratteri, case sensitive o no)
estensione o tipo (eseguibile, oggetto, sorgente)
dimensione
istanti di creazione e modifica
parentela (processo padre ed eventuali figli)
schemi di protezione (lettura, scrittura, modifica)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
404
6.6 File system e protezione
attributi 2
Protezione
Chi e come può accedere ad un file
Password
Creator
Owner
Read-only flag
Hidden flag
Codice necessario per accedere al file
ID dell’utente che ha creato il file
utilizzatore corrente del file
0 - lettura/scrittura
1 - sola lettura
0 - normale
1 - non visibile
System flag
Archive flag
ASCII/binary flag
Random access flag
0 - normal e
0 - salvato (back up)
0 - ASCII
0 - sequenziale
Temporary flag
Lock flags
Record length
0 - normale
1 - eliminare al termine
0 -libero
n - bloccato
Numero di byte in un record
Sistema Operativo
1 - file di sistema
1 - non salvato
1 - binario
1 - casuale
Architettura degli elaboratori 1 - A. Memo
405
6.6 File system e protezione
struttura 1


Un file ha una struttura fisica composta da
blocchi di dati (cluster), mentre a livello
logico è visto come un’insieme di byte o di
record. Il SO le mette in relazione.
le possibili strutture logiche di un FS sono:
– a flusso di byte
– a record di lunghezza fissa
– a record di lunghezza variabile
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
406
6.6 File system e protezione
struttura 2

a flusso di byte (byte stream)
– il SO non sa come interpretare il contenuto del
file, lo sa solo l’utente
– il SO utilizza un puntatore relativo all’inizio del
file per accedere ai dati cercati
– massima flessibilità per il SO
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
407
6.6 File system e protezione
struttura 3

a record di lunghezza variabile
– delimitati da indicatori di fine record
– ogni record è contraddistinto univocamente da
una chiave
– tutte le chiavi sono raccolte in una tabella a
parte, ordinata secondo la chiave, contenente
anche i puntatori all’inizio del record nel file
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
408
6.6 File system e protezione
struttura 4

a record di lunghezza fissa
– gli spazi vuoti sono riempiti da caratteri NULL
o SPACE
– il SO conosce la struttura del file
– puntatore al record corrente
– meno utilizzati dei precedenti
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
409
6.6 File system e protezione
operazioni ammesse 1





creare un file
 posizionamento interno
scrivere un file
 eliminare un file
leggere un file
 troncare un file
rinominare un file  spostare un file
altre operazioni più complesse si ottengono
con opportune combinazioni delle precedenti
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
410
6.6 File system e protezione
operazioni ammesse 2

apertura file
– per accedere ad un file, bisogna prima aprirlo,
cioè far si che il SO predisponga un’opportuno
strumento di accesso a quel file (handle)
– al termine dell’uso di un file, questo dovrà essere
chiuso
– il SO multiutente UNIX ha una tabella dei file
aperti a due livelli, nel primo ci sono le
informazioni del file comuni a tutti i processi, nel
secondo i dati specifici del particolare processo
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
411
6.6 File system e protezione
metodi di accesso ai file 1

accesso sequenziale
– viene gestito un record (o un byte) alla volta
– il SO utilizza un puntatore al record/byte
corrente, e ad ogni lettura lo fa avanzare
– il file può essere letto solo in ordine crescente,
una rilettura richiede la ripartenza dall’inizio
– ad ogni scrittura il record/byte viene aggiunto
in coda e si aggiorna il puntatore
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
412
6.6 File system e protezione
metodi di accesso ai file 2

accesso diretto
– si può leggere un record/byte posto in posizione
qualsiasi
– la posizione del record nel file è calcolata rispetto
al suo inizio (offset = 0)

accesso indicizzato (ISAM)
– un file di chiavi ordinate contenente gli offset dei
rispettivi record nel file, posto in RAM
– ricerca binaria sul file chiavi e poi accesso diretto
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
413
6.6 File system e protezione
esempio d’uso di un file in C
#include <stdio.h>
#include <stdlib.h>
if ((fp=fopen(argv[1],”w”))==NULL){
printf(“Impossibile aprire file”);
exit(1);
}
do {
dato = getchar();
if (EOF == putc (dato, fp)) {
printf(“Errore nel file.\n”);
break;
}
} while (dato!=ESCAPE);
fclose(fp);
#define BUF_SIZE 4096
#define MODE 0666
void main(int argc, char *argv[]){
FILE *fp;
char dato;
if (argc != 2) {
printf(
“Manca il nome del file.”);
exit (1);
}
Sistema Operativo
}
Architettura degli elaboratori 1 - A. Memo
414
6.6 File system e protezione
file mappati in memoria


il SO può mappare in memoria virtuale un
file, cioè attribuire a quel file una data area
di memoria (meglio un segmento perché
preserva l’offset) e poi gestirne gli accessi
come se fossero indirizzi di memoria
quando il file viene chiuso tutte le
modifiche apportate nell’area di memoria
vengono riportate sul file
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
415
6.6 File system e protezione
struttura della directory 1


Ogni volume logico contiene uno o più file
ed una o più directory di file
le directory possono essere classificate in
–
–
–
–
–
directory a livello singolo
directory a due livelli
directory ad albero
directory a grafo aperto
directory a grafo generalizzato
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
416
6.6 File system e protezione
struttura della directory 2

directory a livello singolo
– tutti i file sono organizzati in un’unica grande
lista, ognuno con un nome diverso
– semplice da capire ed implementare, ma
difficile da gestire per il gran numero di file
NomeFile attributi puntatore
FILE 1
Sistema Operativo
FILE 2
FILE 3
FILE 4
Architettura degli elaboratori 1 - A. Memo
dati
FILE 5
FILE 6
417
6.6 File system e protezione
struttura della directory 3

directory a due livelli
– una Master File Directory contenente tante User File
Directory quanti sono gli utenti
– quando un utente entra (log-in) vede solo la sua UFD
– utile nei SO multiuser perché isola gli utenti
– il SO per accedere ai file usa il path name
– i programmi di sistema possono o essere copiati su
tutte le UFD (pessimo), o si introduce il concetto di
search path e directory di sistema
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
418
6.6 File system e protezione
struttura della directory 4

directory ad albero
–
–
–
–
numero arbitrario di livelli
il livello superiore viene detto root level
ogni directory può contenere file o sottodirectory
ogni utente ha la sua directory corrente, che può
essere cambiata con comandi di sistema
– se non si specifica il path name, è quello corrente
– il path name può essere assoluto o relativo
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
419
6.6 File system e protezione
struttura della directory 5
/
radice
Esempi:
docenti
studenti
directory corrente: Rossi
directory padre: ‘.’
Rossi
Bianchi
directory figlio: ‘..’
prg
misc
doc
odb
il file A1 può essere chiamato
doc/A1 (relativo)
A1
A2
D1
D2
/studenti/Rossi/doc/A1
il file D1 di un altro ramo (purchè abilitato):
../studenti/Bianchi/odb/D1 (relativo)
/studenti/Bianchi/odb/D1
(assoluto)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
420
6.6 File system e protezione
struttura della directory 6

directory a grafo aperto
– rappresenta la generalizzazione dell’albero, in cui
un file può essere condiviso da più directory
– in UNIX si utilizzano dei collegamenti simbolici
tra nome locale e quello reale; il SO potrà avere
collegamenti ciclici (riferimenti circolari)
– in altri SO si duplicano gli
studenti
identificatori (handle) dei
Rossi
Bianchi
file: coerenza difficile da
assicurare
prg
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
prg
prg
421
6.6 File system e protezione
operazioni con le directory





create dir
delete dir
change dir
rename dir
link /unlink
Sistema Operativo
crea una nuova sottodirectory
elimina una sottodirectory
cambia la directory corrente
cambia nome alla sottodirectory
crea/annulla collegamenti simbolici
Architettura degli elaboratori 1 - A. Memo
422
6.6 File system e protezione
implementazione del file system 1



i dischi vengono letti e scritti a blocchi
(cluster)
ogni blocco è composto da uno o più settori
caricamento del File System (mounting)
– il SO inserisce il dispositivo specificato
nel punto indicato della directory corrente
– in UNIX può avvenire in run time
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
423
6.6 File system e protezione
implementazione del file system 2
dalle informazioni
simboliche
all’allocazione logica
dai blocchi logici di
un file a quelli fisici
lettura/scrittura
dei blocchi fisici
dai comandi di alto
livello (API del SO) a quelli
di basso livello (hardware)
hardware controllabile
e programmabile
Sistema Operativo
File System logico
tabella dei
file aperti
organizzazione dei file
mappa
allocazione
File System fisico
buffer
d’accesso
Device driver
parametri
config.
Disk driver e controller
Architettura degli elaboratori 1 - A. Memo
424
6.6 File system e protezione
implementazione dei file 1

allocazione contigua
– memorizzazione dei file in blocchi fisici consecutivi
– un file è identificato dall’indirizzo del primo blocco e
dal numero di blocchi utilizzati
– supporta l’accesso sequenziale e diretto, ha ottime
prestazioni (una sola operazione di I/O)
– induce frammentazione interna ed esterna (eliminabile
con la compattazione), richiede la conoscenza
anticipata della dimensione massima
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
425
6.6 File system e protezione
implementazione dei file 2

allocazione a lista concatenata
– un file è rappresentato da una lista concatenata di
blocchi fisici
– nella directory il file è caratterizzato dal puntatore al
primo blocco ed in alcuni SO anche all’ultimo
– i blocchi dei file contengono il puntatore al blocco
successivo (o NULL) e poi i dati
– la lettura sequenziale è semplice, quella diretta più
complessa
– si induce frammentazione interna e l’affidabilità della
lista rappresenta un problema
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
426
6.6 File system e protezione
implementazione dei file 3




File Allocation Table (MS DOS e successivi)
tabella ordinata di puntatori,
uno per ogni blocco del disco
0 blocco libero
N blocco successivo del file
EOF ultimo blocco del file
tutta o parte della FAT deve
essere copiata in RAM
permete l’accesso diretto
Sistema Operativo
FAT
0
1
2
3
4
5
6
7
Architettura degli elaboratori 1 - A. Memo
0
0
4
0
5
6
EOF
FILE_1
vuoti
2
4
5
6
0
427
6.6 File system e protezione
implementazione dei file 4

allocazione a lista indicizzata
– una lista di puntatori ai blocchi affianca la
directory
– quando si crea un file si aggiunge il descrittore
relativo nella directory e si crea un blocco
indice, con tutti i puntatori a NULL
– tutti gli accessi contemplano un’operazione di
ricerca su blocco indice e poi un accesso diretto
al blocco contenente i dati cercati
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
428
6.6 File system e protezione
implementazione dei file 5

allocazione a lista indicizzata (segue)
– non c’è frammentazione esterna, non è richiesta
la dimensione massima, implementa accessi
sequenziali e diretti
– per file molto piccoli un blocco indice è sprecato
– per file molto grandi si possono concatenare più
blocchi indice, o organizzarli a più livelli
gerarchici
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
429
6.6 File system e protezione
implementazione dei file 6

allocazione a nodi indice (i-node)
– ad ogni file viene associata una tabellina contenuta in un
blocco, detta i-node, che contiene gli attributi del file ed i
puntatori ai blocchi del file relativo
– file piccoli: gli indirizzi dei blocchi contenenti i dati sono
memorizzati direttamente in un numero contenuto di campi
dell’i-node
– file medi: oltre agli indirizzi precedenti, c’è un campo che
punta ad un single indirect node posto in un blocco
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
430
6.6 File system e protezione
implementazione dei file 7
–
–
–
–
% segue
file grandi: oltre a quanto visto, un campo punta a un
livello di blocchi intermedio che a loro volta puntano ai
blocchi diretti dei dati
file molto grandi; si può arrivare a tre livello di
reindirizzamento
la struttura di i-node deve essere salvata inizialmente in
memoria, per una più rapida consultazione
viene utilizzata in UNIX
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
431
6.6 File system e protezione
implementazione dei file 8

gestione dei blocchi vuoti
– vettore di bit, ogni bit indica lo stato del blocco
relativo, 0 = libero, 1 = occupato
– lista concatenata, sfruttando i campi puntatore
al successivo
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
432
6.6 File system e protezione
implementazione delle directory 1


la funzione delle directory è quella di suddividere
lo spazio fisico della memoria secondaria in più
aree logiche distinte, e l’obiettivo della loro
implementazione è quello di correlare la stringa
ASCII del nome del file alle informazioni
necessarie al recupero di quel file
le directory possono essere implementate con
– liste lineari ad uno o più livelli
– ricorrendo a tabelle di hash
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
433
6.6 File system e protezione
implementazione delle directory 2

lista lineare
– ogni elemento della directory rappresenta un
file (o una sottodirectory) caratterizzato dal suo
nome e dai relativi attributi
– non c’è un ordine specifico, ed i tempi di
ricerca sono elevati

tabella di hash
– c’è ancora una lista lineare, ma mediante una
tabella dei nomi e dei puntatori ai relativi
elementi della lista, l’accesso è velocizzato
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
434
6.6 File system e protezione
implementazione delle directory 3
•
•
MS-DOS
Directory gerarchica a più livelli.
campi della directory a 32 bit:
1 Nome file:
8 bytes
2 Estensione file
3 bytes
3 Attributi:
1 byte
4 riservati:
10 bytes
5 Orario:
6 Data:
7 Primo blocco:
8 Dimensione:
Orario (unsigned a 16 bit):
2048*Ore [2048*24=41.184]
32*minuti
[32*60=1920]
0,5*secondi
[60/2=30]
1
2
3
2 bytes
2 bytes
2 bytes
4 bytes
Data (unsigned a 16 bit):
512*(anno-1980) = 1980-2108
32*mese
[32*12=384]
1*giorno
[31]
4
5
6
7
8
Riservato per sviluppi futuri
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
435
6.6 File system e protezione
UNIX - file system 1
Il file system di UNIX è composto da 4 elementi:
 boot block (blocco 0)
– non sempre usato, contiene il programma di boot
 superblock (blocco 1)
– informazioni sulla struttura del file system
(numero di i-node, numero di blocchi sul disco,
inizio della free list, flag di modifica e di
bloccaggio ...)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
436
6.6 File system e protezione
UNIX - file system 2

lista degli i-node (a partire dal blocco 2)
– contiene un i-node per ogni file
– ogni i-node occupa 64 Byte e la lista ne può contenere
65.535
– un i-node contiene informazioni sul file relativo
(processo utilizzatore, protezioni, orario dell’ultimo
accesso e modifica, dimensione, indirizzi per
localizzare i blocchi contenenti i dati del file, ...)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
437
6.6 File system e protezione
UNIX - file system 3

blocchi di dati, contenenti
– la directory radice
– tutte le sottodirectory e la loro organizzazione
– la lista dei blocchi liberi su disco
– i blocchi di primo, secondo e terzo livello di
reindirizzamento dei vari file presenti
– un file può occupare anche blocchi non contigui
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
438
6.6 File system e protezione
UNIX - elemento di directory

un elemento di directory è composto da:
– numero dell’i-node relativo al file (2 byte)
– nome del file (stringa ASCII da 14 byte max)

una directory viene memorizzata in un blocco del
disco, e contiene i nomi dei suoi file ed i puntatori
ai relativi i-node
in un blocco da 1Kbyte si possono inserire 64
elementi di directory (da 16 byte ciascuno)

Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
439
6.6 File system e protezione
affidabilità del file system 1


gestione dei blocchi danneggiati
– hardware, creando in un settore del disco un
elenco di blocchi danneggiati ed i loro sostituti
– software, ricorrendo ad un falso file che
utilizza tutti i blocchi danneggiati
salvataggio del file system
– su nastro, tempi lunghi, possibilità incrementale
– su disco, con partizione di backup o RAID,
Redundant Array of Inexpensive Disks
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
440
6.6 File system e protezione
affidabilità del file system 2

consistenza del file system
– un file viene aperto, modificato e poi salvato; se il sistema
cade tra la modifica ed il salvataggio, il file risulta essere
inconsistente
– consistenza dei blocchi: si producono due liste, un
contatore per ogni blocco; la lista dei blocchi in uso dei
file e la lista dei blocchi liberi.
 consistenza: ciascun blocco appartiene ad una sola lista
 perdita: il blocco non appartiene ad alcuna lista
 duplicazione: il contatore del blocco è maggiore di 1
in una delle due liste
– consistenza dei file: analogo per i file
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
441
6.6 File system e protezione
prestazioni del file system 1



data la lentezza dell’accesso ai dischi, si interpone
tra memoria principale e secondaria un buffer
(organizzato come una cache) della dimensione di
alcuni blocchi
quando il buffer è pieno si possono adottare
politiche di rimpiazzo analoghe alla paginazione
(LRU)
c’è il problema della scrittura e della consistenza
dei dati: per i blocchi i-nodes o di indirizzamento
indiretto si aggiorna il disco molto frequentemente
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
442
6.6 File system e protezione
prestazioni del file system 2


UNIX adotta la chiamata automatica di SYNC
ogni 30 secondi circa
MS-DOS adotta la politica write-through (più
lenta, meno efficace, si può togliere un FD in
qualsiasi momento)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
443
6.6 File system e protezione
sicurezza: generalità


la multiutenza e la multiprogrammazione
condividono le risorse: occorre evitare
utilizzi non autorizzati
protezione
– meccanismi di salvaguardia delle risorse dai
malfunzionamenti

sicurezza
– impedire l’uso non autorizzato (volontario o
meno) di risorse
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
444
6.6 File system e protezione
sicurezza: intrusioni



intrusi passivi, leggono file a loro negati
intrusi attivi, apportano modifiche non
consentite a file
classificabili in
–
–
–
–
intrusi di passaggio, casuali
intrusi a scopo di curiosità (interni al sistema)
intrusi a scopo di lucro
intrusi a scopo di spionaggio
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
445
6.6 File system e protezione
sicurezza: esempio di difetto

lpr (UNIX)
– il comando lpr stampa un file e, se attivata
l’opzione -r, il file viene successivamente
rimosso: si poteva lanciare la stampa del file
delle password e poi farlo eliminare, rendendo
accessibile l’intero sistema
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
446
6.6 File system e protezione
sicurezza: esempi di attacchi



richiedere pagine di memoria, aree di dati o
blocchi di disco: molti SO non le cancellano prima
di riutilizzarle
effettuare chiamate di sistema con parametri errati
o incoerenti: molti SO non prevedono tutti i casi
possibili
digitare DEL, BREAK o simili all’interno della
password: il SO potrebbe chiudere il programma
di test e considerare valido il login
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
447
6.6 File system e protezione
sicurezza: virus





segmento di codice aggiunto ad un programma
con l’obiettivo di replicarsi su altri programmi
virus di boot, attivati durante la fase di avvio si
collegano alle chiamate di sistema ed infettano
tutto il sistema
virus di file, presenti in fle eseguibili
virus di macro
virus polimorfi
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
448