Sistemi Operativi B 2006/2007 - Appunti delle lezioni 1
Sistemi Operativi B2006/2007DSI@Unive
L’interfaccia del File System(Capitolo 10 Silberschatz)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 2
Sommario
Concetto di file
Metodo d’accesso
Struttura delle directory
Montaggio di un file system
Condivisione di file
Protezione dell’accesso
http://www.dsi.unive.it/~sob
http://www.dsi.unive.it/~auce
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 3
Obiettivi
Spiegare le funzionalità di un file system
Descrivere le interfacce verso un file system
Discutere i principi di progetto e protezione
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 4
Il concetto di fileUn file è un insieme di informazioni , correlate e registrate nella memoria secondaria, cui è statoa ssegnato un nomeI file sono organizzati in raggruppamenti logici (talvolta fisici) detti cataloghi (directory)Tipi fondamentali:
DatiNumericiAlfabetici, alfanumericiBinariEtc.
ProgrammiEseguibililibrerie
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 5
Struttura dei fileNessuna: sequenza di bit, byte, wordStrutture semplici a record
Linee di testoLunghezza fissaLunghezza variabile
Strutture complesseEs. documento formattatoEs. file eseguibileÈ possibile simulare una struttura su una semplice sequenza per mezzo di convenzioni e caratteri di controllo
Chi decide:Sistema operativoprogrammi
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 6
Attributi dei fileNome: è l’unica informazione in forma umanamente leggibileIdentificatore: etichetta univoca (numero) che identifica il file all’interno del file systemTipo: informazione necessaria ai sistemi che gestiscono tipi di file diversiLocazione: puntatore al dispositivo e alla locazione del file in tale dispositivoDimensione: dimensione del fileProtezione: controlla chi può leggere, scrivere o far eseguire il fileOra, data e identificazione dell’utente: dati utili ai fini della protezione e del controllo di utilizzoLe informazioni sui file sono conservate nella struttura di directory, che risiede anch’essa nella memoria secondaria.
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 7
Operazioni sui file
Il file può essere considerato un tipo di dato astratto (classe)
Creazione di un file (create)
Scrittura di un file (write)
Lettura di un file (read)
Riposizionamento in un file (seek)
Cancellazione di un file (delete, remove, unlink)
Troncamento di un file (truncate)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 8
Operazioni fondamentaliUn file deve essere predisposto all’uso e rilasciato quando non è più utilizzato
open(Fi) : ricerca nella struttura di directory del disco l’elemento Fi, e ne sposta il contenuto in memoria
close(Fi) : rimuove il contenuto dell’elemento Fi dalla memoria alla struttura di directory del disco
Da programma un file è identificato da un descrittore che contiene tutte le informazioni necessarie per gestirlo
fd = open(nome, modo)
fclose (fd)
fd = fopen(nome, modo)
fclose (fd)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 9
Gestione dei file aperti
Per gestire i file aperti sono necessarie alcune informazioni specifiche:
File pointer: puntatore all’ultima posizione letta/scrittaUno per ogni processo che usa il file
Posizione del file su discoCache degli accessi recenti
Diritti di accessoSpecifici per ogni processo
Contatore di aperture: conta quante volte un file èaperto
Serve per rimuovere le informazioni di gestione quando il file non è più utilizzato da nessuno
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 10
Gestione dei file in sistemi multiutente
In un sistema multiutente/multitask servono due livelli di informazioni (tabelle)
Di sistema: indipendenti dai processi (+ contatore di aperture)
Di processo: dipendenti dai processi
Puntatore alla tabella di sistema
Informazioni locali (posizione di lettura/scrittura, modalità di utilizzo)
Proc 1 Proc 2
Info locali
Info 2
Tabella diSistema
Info locali
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 11
Identificazione dei tipi di fileIl tipo di un file può essere riconosciuto e gestito in modo personalizzato
Unix, Windows: supporto minimo da parte del sistemaSequenze di byte, formato definito dalle applicazioni
Tipo identificato per convenzione sul nome (estensione) o sui primi caratteri del contenuto (magico number)
Eseguibili e librerie hanno un formato definito dal sistema
MacOS: il sistema gestisce un livello di riconoscimento piùavanzato
Tipo/creatore del file, richiama automaticamente l’applicazione
Divisione in resource fork e data fork
RSX-11M, VMS: gestisce diversi tipi di formatiAd accesso sequenziale/diretto
A record / a blocchi / stream
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 12
Tipi di file e estensioni
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 13
Metodi d’accessoAccesso sequenziale
read next
write next
reset, rewind
(rewrite)
Accesso direttoread n (n=numero relativo del record)
write n (rewrite n)
seek n
(read next)
(write next)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 14
File ad accesso sequenzialeSi ispira al modello dei nastri magnetici
read next
write next
reset, rewind
(rewrite)
Non è possibile leggere dopo l’ultima scrittura
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 15
Accesso direttoSi ispira al modello dell’array
Il file è formato da blocchi logici (di lunghezza fissa), detti record, numerati progressivamente, ad accesso casuale
E’ la modalità di accesso ai dischi (ma la rotazione è sequenziale
read n (n=numero relativo del record)
write n (rewrite n)
seek n
(read next)
(write next)
0 1 2 … n n+1
Inizio Fine
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 16
Accesso sequenziale su un file ad accesso diretto
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 17
Esempio di file a indice
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 18
Indice multilivello
ABC
ST
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 19
Struttura di directory
Un insieme di nodi contenenti informazioni su tutti i file
Sia la directory sia i file risiedono sul disco
F 1 F 2F 3
F 4
F n
Directory
Files
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 20
Organizzazione del file system
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 21
Informazioni sui file nella directoryNome
Tipo
Indirizzo
Dimensione corrente
Dimensione massima
Data dell’ultimo accesso
Data dell’ultimo aggiornamento
ID del proprietario
Informazioni di protezione
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 22
Operazioni eseguite su una directory
Ricerca di un file
Creazione di un file
Cancellazione di un file
Elencazione di una directory
Ridenominazione di un file
Attraversamento del file system
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 23
Criteri organizzativi di una directory
Efficienza – individuare rapidamente un file
Scelta del nome – conveniente per gli utentiDue utenti possono usare lo stesso nome per file differenti
Lo stesso file può avere più nomi diversi tra loro
Raggruppamento – raggruppamento logico del file in base a specifiche caratteristiche (es. tutti i programmi, tutti i giochi, tutti i documenti di un progetto, etc.)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 24
Directory ad albero (gerarchica)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 25
Directory a due livelli
Directory separate per ciascun utenteNome di percorso (path name)
Un file può avere lo stesso nome per utenti diversi
Ricerca efficiente
Non è possibile una gestione complessa per ogni utente
Necessità di meccanismi di protezione
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 26
Directory a livello singolo
Una singola directory per tutti gli utentiConfusione nei nomi dei file
Problemi di gestione (nessun raggruppamento)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 27
Directory ad alberoPath name relativo o assoluto
La creazione di un nuovo file può far riferimento alla directorycorrente o al path name assoluto
Cancellazione di file e directory
Creazione di un nuova directory (con path name relativo o assoluto)
mkdir esami
mkdir /utenti/auce/didattica/sob/esami
Cancellando mail si cancella (si cancellerebbe…) l’intero sottoalbero che ne discende
prog copy prt exp count
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 28
Directory a grafo aciclico 1/2Possono avere sottodirectory e file condivisi in più directory
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 29
Directory a grafo aciclico 2/2Più pathname per lo stesso file (aliasing)Se si cancella un file condiviso restano riferimenti non risolti (dangling referings)
Riferimenti da un file a tutte le directory in cui ècontenuto
Struttura a dimensione variabileStruttura a daisy chain
Contatori di condivisione, il file si cancella solo se non è più accessibile
Creazione di nuovi elementi in directoryLink, crea un altro nome per un file esistentePer accedere al file si segue il link
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 30
Directory a grafo generale 1/2
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 31
Directory a grafo generale 2/2
L’esistenza dei cicli è problematicaAttraversamento infinito del file system
Cicli isolati
Come possiamo garantire di non avere cicli?Permettere solo link condivisi a file e non a directory
Garbage collection per scoprire cicli isolati
Per ogni nuovo link si controlla se crea un ciclo (oneroso)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 32
Link multipli ai file 1/5
Diversi path possono riferire allo stesso file o directory
Utile ad esempio per condividere file tra utentiEs: se gli utenti Bianchi e Bruni lavorano allo stesso progetto possono avere la directory coi file di progetto ambedue nella propria home
Oppure … diverse versioni di gcc (gcc –verxy), ma vogliamo che /usr/bin/gcc sia una specifica di queste
Nota: non ci sono due copie del file o della directoryIl file è unico, ma esistono due riferimenti distinti
Ogni modifica al file è visibile in entrambe le directory
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 33
Link multipli ai file 2/5
La struttura a grafo è implementata come:1. Link “simbolico”
Elemento di directory speciale che punta al file
pluto contiene il path di pippo
2. Link “hard”Le informazioni relative al file sono duplicate nelle due directory
Non vi è un link e un originale
pippo… … pluto… …
pippo… … pluto… …
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 34
Link multipli ai file 3/5Unix
Hard linkSymbolic link
WindowsNessun hard linkCollegamenti (link simbolici)
Mac OSXLink hard (a livello interno Unix-like)Link simbolici (a livello interno Unix-like)Alias (link simbolici con riferimento più complesso al file originale)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 35
Link multipli ai file 4/5Attraversamento del File System
Ad esempio per effettuare il backup (non si vogliono salvare duecopie dei file condivisi)Per funzioni statiche o di accounting, non si deve accedere due volte allo stesso file o directorySoluzione Unix: non seguire i link simbolici (oppure marcare gli i-node visitati)
CancellazioneDopo la cancellazione di un file condiviso potrebbero rimanere dei puntatori ad un file che non esiste più (particolarmente grave se questi puntano direttamente al disco)Soluzione Unix:
Link sibolici: quando si rimuove il file i puntatori restano dangling. E se creo un nuovo file con lo stesso nome?Link hard: per ogni file si mantiene un contatore di condivisione (numero di riferimenti) e lo si elimina solo quando il contatore vale 0
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 36
Link multipli ai file 5/5
CancellazioneIl contatore di condivisione usato nel caso aciclico può non funzionare correttamente
Dopo la cancellazione di root viene, il contatore rimane a 1
Soluzione: garbage collection che è un meccanismo troppo dispendioso
(slide incompleta)
pippo pluto
root
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 37
Parent directory e link 1/2Riferimento alla Directory Genitore
Molti sistemi permettono di “navigare” il file system riferendo la directory padre dalla directory corrente
Es. Unixcd..
La working directory diviene la directory genitore di quella corrente
cd /home/auce/progetto
cd.. nuova wd = /home/auce
E in presenza di link?cd /home/bruni/dir
cd.. nuova wd= ??
home
bruni rossi
dir
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 38
Parent directory e link 2/2DipendeUnix
Solo link simbolici a directory (hard link sarebbero problematici)cd /home/rossi/symlinkcd..Dipende dalla shell
Korn- cd.. Torna a /home/bruni
Bash- Distingue wd logica (/home/rossi/symlink) e wd fisica
(/home/bruni/dir)- cd.. Usa la wd logica e torna a /home/rossi
home
bruni rossi
dir
symlink
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 39
Condivisione di file
La condivisione di file nei sistemi multiutente èuna caratteristica certamente desiderabile
La condivisione richiede la presenza di uno schema di protezione
User id identifica gli utenti permettendo di assegnare diritti e protezioni utente per utente
Group id permette di raggruppare gli utenti assegnando diritti comuni
Nei sistemi distibuiti i file sono condivisi attraverso una rete
Es. NFS (network file system) è un metodo comune di condivisione di file
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 40
Semantica della coerenzaLa semantica della coerenza specifica come più utenti possano accedere ad un file condivisoPresenta problematiche simili alla sincronizzazione dei processi
Meno complessa a causa di tempi meno critici
Unix implementa una semantica basata sui seguenti principi:
Le scritture su un file sono immediatamente visibili da tutti gli altri utenti dello stesso filePuntatori condivisi al file permettono a più utenti di leggere e scrivere in modo contemporaneo
Altre ipotesi:Le modifiche a un file sono visibili solo dopo la chiusura del fileI file sono aperti in modo esclusivo: gli altri processi sono sospesi fino al rilascio esplicito del file (lock/unlock)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 41
ProtezioneIl proprietario/creatore di un file deve essere in grado di controllare:
Che cosa può essere fattoDa chi
Tipi di accessoLetturaScritturaEsecuzioneEstenzioneCancellazioneElencazione
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 42
Controllo degli accessiLa tecnica più diretta e completa si basa sul concetto di Access Control List (ACL)
Ad ogni file si associa un elenco di controllo degli accessi (ACL) che specifica:
Nomi o classi di utenti
Tipi di accesso consentito
Esempio:FILE ACLpippo (rw (bianchi, rossi)) (rx (verdi, bianchi))
pluto (r (verdi, rossi)) (x (bianchi, verdi))
Consente un controllo preciso sugli accessi ma:La ACL può essere lunga e problematica da manutenere
L’elemento di directory che descrive un file non ha piùdimensione fissa
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 43
Windows XP Access Control List
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 44
GruppiPer esprimere l’ACL in modo ordinato molti sistemi subdividono gli utenti in tre classi:
ProprietarioCreatore del file (default, non può essere modificabile)
GruppoGruppo di utenti che condividono il file
UniversoTutti gli altri utenti
Ad ogni file sono attribuiti dei diritti di accesso specifici per ogni classeAlcuni sistemi combinano i due meccanismi, ACL più gruppi
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 45
Controllo degli accessi UNIX
Modalità di accesso: lettura (r), scrittura (w), esecuzione (x)
Tre classi di utentir w x
a) proprietario 7 ⇒ 1 1 1r w x
b) gruppo 6 ⇒ 1 1 0r w x
c) universo 1 ⇒ 0 0 1
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 46
Esempio di directory in Unix
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 47
Altri metodi di protezione
Alternativamente la protezione di file e directory può essere assicurata tramite password
Questo metodo non può essere applicato in generale (troppe password!)
Può essere associato a directory e a volumiMac OSX permette di associare password a immagini di volumi virtuali e a volumi removibili
Volume removibile Iomega ZIP può essere protetto da password (gestita in modo ottico direttamente dal driver hardware)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 48
Montaggio di un file system 1/2
Un file system deve essere montato (mount) prima di essere utilizzato
Il montaggio consiste nell’associare la radice del file system con un punto di montaggio, solitamente foglia del file system principale
Si crea una struttura gerarchica estensibile
Si possono aggiungere volumi rimovibili
Un file system montato può essere “smontato”(unmount)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 49
Montaggio di un file system 2/2
a) Esistente b) Partizione da montare
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 50
Mount point
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 51
Montaggio di un volume rimovibileroot
root
mnt
cdetc
home
bianchi
File system su CD-ROM(/dev/cdrom)
… dopo mount (/dev/cd, /mnt/cdrom)mnt
cdetc
home
bianchi
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 52
Montaggio iniziale del file system>more /etc/fstab
# /etc/fstab: static file system information
#
# <file system> <mount point> <type> <options>
proc /proc proc defaults
/dev/cciss/c0d0p1 / ext3 defaults,errors=remove
/dev/cciss/c0d0p11 /extra ext3 defaults,quota
/dev/cciss/c0d0p9 /home ext3 defaults,quota
/dev/cciss/c0d0p12 /cvsrep ext3 defaults
/dev/cciss/c0d0p13 /scratch ext3 noatime
/dev/cciss/c0d0p5 /usr ext3 noatime
/dev/cciss/c0d0p6 /var ext3 defaults
/dev/cciss/c0d0p10 /var/mail ext3 defaults,quota
/dev/cciss/c0d0p7 none swap sw
/dev/cciss/c0d0p8 none swap sw
/dev/hda /media/cdrom0 udf,iso9660 ro,user,noauto
/dev/fd0 /media/floppy0 auto rw,user,noauto
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 53
Sistemi Operativi B2006/2007DSI@Unive
Realizzazione del file system(Capitolo 11 Silberschatz)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 54
Realizzazione del file system
Struttura del file system
Realizzazione del file system
Realizzazione delle directory
Metodi di assegnazione
Gestione dello spazio libero
Efficienza e prestazioni
Ripristino
File system con annotazione delle modifiche
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 55
Obiettivi
Descrivere la realizzazione del file system in ambito locale e di strutture di directory
Descrivere le tecniche di allocazione dei blocchi sul disco
Descrivere le tecniche di gestione delle aree libere
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 56
Struttura del file system
Struttura del fileUnità di memorizzazione logica
Raccolta di informazioni correlate
Il file system risiede permanentemente nella memoria secondaria
Blocco di controllo del file (FCB, file control block), struttura di memorizzazione che contiene informazioni riguarda al file, come le proprietà, i permessi e la posizione.
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 57
File system stratificato
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 58
User Program
Basic I/O Supervisor
Tape Device DriverDisk Device Driver
Basic File System
Logical I/O
HashedIndexedIndexedSequentialSequentialFile
File system Software Architecture
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 59
Livelli del file system 1/2
Controllo dell’I/ODriver di dispositivo: traducono richieste ad alto livello (es. “leggi il blocco 27”) in sequenze di comando per il (controllore del) dispositivo
Gestori delle interruzioni di I/O (inizio/fine delle operazioni di I/O)
File system di baseSi occupa di inviare comandi all’ap[…] per leggere e scrivere blocchi fisici […] scheduling degli accessi, buffering […] slide incompleta
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 60
Livelli del file system 2/2Richiesta di lettura sul file C:\pippoFS logico: gestione dei metadati
Recupera il FD dalla tabella dei file aperti (pippo deve essere stato aperto)Verifica i diritti di accessoIl puntatore di lettura/scrittura indica il numero del blocco logico da leggere
FS logico: modulo di organizzazione dei fileData la locazione e la struttura del file traduce la richiesta in una lettura del blocco fisico
FS di baseGestisce la richiesta di lettura secondo le sue politiche, tramite buffer, passandola al driver del disco C
Gestione dell’I/OIl dirver “inoltra” la richiesta di lettura traducendola ed inviandola al dispositivo
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 61
Livelli del file system: Perchè?
I comuni SO gestiscono vari file system:Unix: UFS, ext, ext3, msdos, ntsf, xenix, minix…
Windows: FAT, FAT32, ntsf
MacOSX: HFS, HFS+, FAT; ntsf (…)
I vari file system differiscono per il livello “FS logico”, mentre possono condividere:
Controllo dell’I/O
File system di base
E’ necessario un ulteriore livello VFS (Virtual File System) che fornisce un’interfaccia comune ai vari file system
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 62
Un tipico descrittore di file
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 63
Struttura del file system in memoria
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 64
Metodi di allocazione
Un metodo di allocazione indica il modo in cui i blocchi di disco vengono assegnati ai file
Allocazione contigua
Allocazione concatenata
Allocazione indicizzata
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 65
Allocazione contigua 1/3
Ciascun file deve occupare un insieme di blocchi contigui nel disco
Semplice: è richiesto solo l’indirizzo del primo blocco (inteso come numero di blocco) e la lunghezza (espressa in blocchi)
Impiego di spazio (problema dell’assegnazione dinamica della memoria)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 66
Allocazione contigua 2/3
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 67
Allocazione contigua 3/3
Corrispondenza tra indirizzo logico e posizione fisica
Indirizzo Logico
Dimensione cluster
Q
R
Cluster di accesso= Q + indirizzo del primo clusterOffset nel cluster = R
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 68
Un esempio “storico” (anni 70-80) 1/2Hardware Digital PDP-11
Famiglia di processori 16 bit, a Mb RAM maxMemoria virtuale segmentata, 8 x 8Kb, 64(+64)Kbmax
Sistema operativo Digital RSX-11MMultitask, multiutente, real-time a prioritàDirectory a un livelloDue file system: FCS (sequenziale, diretto) e RMS (indicizzato)Ambienti di sviluppo: Fortran, C, Basic, Datatrieve
Rilevato da Mentec Inc., ancora assistito (Sw)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 69
Un esempio “storico” (anni 70-80) 2/2Ottimizzato per applicazioni real-time
Compromesso tra velocità e occupazione di memoriaCodice condiviso (rientrante)
Processi residenti in memoria per l’esecuzioneBasso tempo di caricamentoFissaggio in memoria dei processi criticiNecessità di riorganizzazione periodica della memoria
Accesso alla memoria in DMACodice dei programmi contiguo e compatto…
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 70
Sistemi con estensione
Si può usare uno schema di assegnazione contigua modificato
I file system con estensione aggiungono alla porzione di spazio contiguo assegnata, un’altra porzione di spazio
Un’estensione è un blocco contiguo di dischi. La locazione dei blocchi dei file si registra come una locazione e un numero dei blocchi, insieme con l’indirizzo del primo blocco dell’estensione seguente
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 71
Allocazione concatenata 1/3
Ciascun file è composto da una lista concatenata di blocchi del disco i quali possono essere sparsi in qualsiasi punto del disco stesso.
puntatoreblocco =
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 72
Allocazione concatenata 2/3
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 73
Allocazione concatenata 3/3Semplice: necessita solo dell’indirizo di partenza
Sistema di gestione dello spazio libero: non c’è spreco di spazio
Ma ogni blocco contiene dati + puntatore al prossimo blocco
Problemi nel caricamento DMA
Dimensione dei dati non gestibile come multiplo della dimensione del blocco
Non vi è accesso casuale
Una variante importante del metodo di allocazione concatenata consiste nell’uso della tabella di assegnazione dei file (FAT, file allocation table). Tale metodi di allocazione dello spazio di dischi è usato nei sistemi operativi MS-DOS e Windows.
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 74
Un altro esempio storico (anni 80-90)Commodore Amiga
CPU Motorola 68000, 68030>= 512 Kb memoria centraleInizialmente solo su floppy diskProblema affidabilità
File system ad allocazione concatenata488 byte di dati per blocco24 byte header di blocco
Doppia lista concatenata di blocchi di fileRiferimenti al file header
Possibilità di recuperare i file anche in caso di corruzione del discoPerdita di un bloccoPerdita della directory
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 75
Allocazione indicizzata 1/4
Raggruppa tutti i puntatori in una sola locazione: il blocco indice
tabella indice
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 76
Allocazione indicizzata 2/4
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 77
Allocazione indicizzata 3/4Necessita di una tabella indiceAccesso casualeAccesso dinamico senza frammentazione esternaOgni file deve avere un blocco indice
Auspicabile una piccola dimensioneSe troppo piccolo non può contenere un numero di […] sufficiente per un file di grandi dimensioni
E’ necessario un meccaniscmo per la gestione di […] ragionevolmente grandi:
Schema concatenato (dimensioni potenzialmente illimitate)Indice a più livelli (dimensioni limitate)Schema combinato (in Unix, soluzione favorevole che consente file grandi)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 78
Allocazione indicizzata 4/4Corrispondenza tra indirizzo logico e indirizzo fisico
Dipende dalle dimensioni del blocco di indice e dalle dimensionimassime del file
EsempioMapping da indirizzo logico a indirizzo fisico per un file di dimensione massima di 512K byte, 1024 byte per cluster fisico, 2 byte per puntatore
Un blocco di indice (=cluster fisico) contiene 512 puntatori per indirizzare 512 blocchi
Indirizzo LogicoDimensione cluster
Q
RCluster di accesso= QOffset nel cluster = R
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 79
Allocazione indicizzata multilivello
M
outer-index
index table file
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 80
Schema combinato UNIX
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 81
Gestione dello spazio libero 1/2
Vettore di bit (n blocchi)
…0 1 2 n-1
bit[i] =
678 0 ⇒ blocco[i] libero
1 ⇒ blocco[i] occupato
Il numero di blocchi è dato dalla seguente espressione
(numero bit per parola) x (numero parole di valore 0) + scostamento del primo bit 1
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 82
Gestione dello spazio libero 2/2
La bitmap richiede spazio per la sua memorizzazione
Esempio:Block size = 212 bytes (4Kbyte)
Disk size = 236 bytes (64 Gbyte)
n=236/212 = 224 bits (16Mbyte)
È facile trovare spazio contiguo
La lista concatenata (FAT) non richiede spazio supplementare
Ma non è facile trovare spazio contiguo
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 83
Gestione dei settori difettosi di un discoProblema molto importante con supporti a bassa affidabilità (floppy, dischi rimovibili)Le soluzioni correggono,non prevengonoDipende da difetti di fabbricazione e da usura
Difetti di fabbricazione: gestiti dal controller del disco attraverso una riserva di blocchi disponibiliUsura: può essere risolta dal controller attraverso la stessa riserva, oppure attraverso utility di verifica
I settori difettosi (bad blocks) vengono considerati
Inesistenti (filtrati dal controller)Appartenenti ad un file non modificabile
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 84
Tecniche per garantire la coerenza
I meccanismi di caching possono causare inconsistenze sul file system
Ad esempio, a causa di interruzioni di corrente
Il problema è particolarmente critico per zone del disco contenenti strutture dati per la gestione: FAT, bitmap, i-node, directory
Due possibili soluzioni:Curare (file system checker)
fsck, scandisk
Prevenire (journaling file system)ext3, ntsf, hfs+
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 85
Controlli di coerenza 1/3Controlli sui blocchi
Effetuati periodicamente o su richiesta dall’utente
Si costruiscono due tabelle used[i] e free[i], indicizzate dai blocchi presenti nel file system
Tabella used[i]:Conta quante volte il blocco i è presente nell’elenco dei blocchi di un file
Ottenuta esaminando tutti i file nel file systemSi inizializza a 0
Se il blocco i è indicizzato da un file, si incrementa il contatore
Tabella free[i]:Conta quante volte il blocco i compare nell’elenco di blocchi liberi
Ottenuta esaminando la lista dei blocchi liberi, oppure dal vettore dei bit (~copia dei bitmap)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 86
Controlli di coerenza 2/3free[i] + used[i] = 1
Il blocco è correttamente elencato nel file system
free[i] + used[i] = 0Blocco mancante: non è né libero né occupato
Problema: nessun problema di coerenza, ma spazio sprecato
Azione: riportare il blocco nell’elenco de blocchi liberi
free[i] > 1Il blocco compare più volte nella lista dei blocchi liberi
Problema: nessun problema di coerenza (per ora), ma in futuro ilblocco potrebbe essere assegnato due volte
Azione: mostrare una sola occorrenza nell’elenco
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 87
Controlli di coerenza 3/3free[i] = 1 , used[i] > 0
Blocco i è sia libero che occupatoProblema: nessun problema di coerenza (per ora), ma in futuro il blocco potrebbe essere assegnato due volteAzione: togliere il blocco dall’elenco dei blocchi liberi
used[i] > 1Blocco i è utilizzato da due o più file contemporaneamenteProblema: forti problemi di coerenza nel file!Azione: cercare un nuovo blocco, copiare interamente il blocco presente, utilizzare la nuova copia per risolvere il problema
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 88
Organizzazione dei dati su disco
Le strutture dati memorizzate sul disco devono contenere informazioni su
Organizzazione logica del disco (partizioni)
Eventuale avviamento del sistema operativo memorizzato nel disco
Numero complessivo dei blocchi, numero e locazione dei blocchi liberi
Struttura delle directory e dei file
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 89
Gestione dell’unità discoPrima che un disco magnetico possa memorizzare dati deve essere diviso in settori che possano essere letto o scritti dal controllorePer usare un disco come contenitore di informazioni, il sistema operativo deve registrare le proprie strutture dati all’interno del disco. Ciò avviene in due passi:
Suddividere il disco in uno o più gruppi (partizioni)Creare un file system (formattazione logica)
Il blocco d’avviamento (boot block) inizializza il sistemaUn piccolo caricatore d’avviamento (bootstrap loader) è memorizzato nella ROM
La formattazione fisica mette anche da parte dei settori di riserva non visibili al sistema operativo, si può istruire il controllore affinchésostituisca da un punto di vista logico un settore difettoso con uno dei settori di riserva non utilizzati. Questa strategia è nota come accantonamento dei settori (sector sparing)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 90
Organizzazione dei dati su discoUn disco può essere diviso in partizioni, che possono essere indipendenti e ospitare file system differenti
Il primo settore dei dischi è il cosiddetto master boot record (MBR)Contiene il boot loader utilizzato per il boot del sistema
Contiene la partition table (tabella delle partizioni)
Contiene l’indicazione della partizione attiva (bootable)
All’avvio (boot), il MBR viene letto ed eseguito
Partizione 3Partizione 2Partizione 1MBR
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 91
Struttura generale di una partizioneGestione spazio libero
Struttura dati per la gestione dello spazio libero (es. contatore blocchi liberi e relativi puntatori)
Gestione spazio occupatoStruttura dati per la gestione dello spazio allocato ai file
UFS: tabella i-node; NTFS: database relazionale nella MFT
Root directoryDirectory radice del file system (ad albero o grafo radicato)
File/directorySpazio dati per la struttura di directory e i file
File/
directoryRoot dirFile Descr.
Gestione spazio
occupato
Gestione spazio libero
SuperblockBoot-block
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 92
Boot del sistemaAll’avvio (boot) del sistema
Si carica il MBR e lo si esegueMBR carica il boot block della partizione attiva
MBR deve “conoscere” i diversi file system nel sistema
Il boot block monta sia la root partition che il nucleo del sistema operativo (ed altri file di sistema)
Automaticamente come nel caso di Windows e MacOSXCome indicato nel file /etc/fstab, o per esplicita richiesta di utenti/applicazioni come nel caso di Unix
MBR e boot block sono in posizione e formato prestabiliti, non vi si accede, ovviamente, tramite il file system
Raw partition (partizione senza file system)Raw partition usata anche per l’area di swap dei processi
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 93
Realizzazione delle directoryLista lineare contenente i nomi dei file con puntatori ai blocchi di dati
Metodo di facile programmazioneEsecuzione onerosa in termini di tempo
Tabella ordinataNecessità di riorganizzazione per ogni modificaPossibile solo per piccole quantità di dati
Tabella hashVeloce ma a dimensione fissaCollisioni: da due nomi di file si può avere un riferimento allastessa chiave
Albero bilanciatoVeloce nella riorganizzazione
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 94
Efficienza e prestazioniL’efficienza dipende in generale da:
Algoritmi usati per l’allocazione dello spazio su disco
Gestione delle directory
Gestione delle operazioni di I/O
Le prestazioni possono essere migliorate con interventi specifici
Cache del disco: sezione separata della memoria centrale dove tenere i blocchi in previsione di un loro utilizzo entro breve tempo
Rilascio immediato (free-behind) e lettura anticipata (read-ahead): tecniche di ottimizzazione degli accessi sequenziali
(storico) si riserva e si gestisce una sezione della memoria come disco virtuale (RAM disk)
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 95
I/O senza buffer cache unica
Sistemi Operativi B 2006/2007 - Appunti delle lezioni 96
I/O senza buffer cache unica
11.1 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
RecoveryRecovery
Consistency checking – compares data in directory structure with data blocks on disk, and tries to fix inconsistencies
Use system programs to back up data from disk to another storage device (floppy disk, magnetic tape, other magnetic disk, optical)
Recover lost file or disk by restoring data from backup
11.2 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Log Structured File SystemsLog Structured File Systems
Log structured (or journaling) file systems record each update to the file system as a transaction
All transactions are written to a logA transaction is considered committed once it is written to the logHowever, the file system may not yet be updated
The transactions in the log are asynchronously written to the file system
When the file system is modified, the transaction is removed from the log
If the file system crashes, all remaining transactions in the log must still be performed
11.3 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
The Sun Network File System (NFS)The Sun Network File System (NFS)
An implementation and a specification of a software system for accessing remote files across LANs (or WANs)
The implementation is part of the Solaris and SunOS operating systems running on Sun workstations using an unreliable datagramprotocol (UDP/IP protocol and Ethernet
11.4 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
NFS (Cont.)NFS (Cont.)
Interconnected workstations viewed as a set of independent machines with independent file systems, which allows sharing among these file systems in a transparent manner
A remote directory is mounted over a local file system directoryThe mounted directory looks like an integral subtree of the local file system, replacing the subtree descending from the local directory
Specification of the remote directory for the mount operation isnontransparent; the host name of the remote directory has to be provided
Files in the remote directory can then be accessed in a transparent manner
Subject to access-rights accreditation, potentially any file system (or directory within a file system), can be mounted remotely on top of any local directory
11.5 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
NFS (Cont.)NFS (Cont.)
NFS is designed to operate in a heterogeneous environment of different machines, operating systems, and network architectures; the NFS specifications independent of these media
This independence is achieved through the use of RPC primitives built on top of an External Data Representation (XDR) protocol used between two implementation-independent interfaces
The NFS specification distinguishes between the services provided by a mount mechanism and the actual remote-file-access services
11.6 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Three Independent File SystemsThree Independent File Systems
11.7 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Mounting in NFS Mounting in NFS
Mounts Cascading mounts
11.8 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
NFS Mount ProtocolNFS Mount Protocol
Establishes initial logical connection between server and clientMount operation includes name of remote directory to be mounted and name of server machine storing it
Mount request is mapped to corresponding RPC and forwarded to mount server running on server machine Export list – specifies local file systems that server exports for mounting, along with names of machines that are permitted to mount them
Following a mount request that conforms to its export list, the server returns a file handle—a key for further accessesFile handle – a file-system identifier, and an inode number to identify the mounted directory within the exported file systemThe mount operation changes only the user’s view and does not affect the server side
11.9 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
NFS ProtocolNFS Protocol
Provides a set of remote procedure calls for remote file operations.The procedures support the following operations:
searching for a file within a directory reading a set of directory entries manipulating links and directories accessing file attributesreading and writing files
NFS servers are stateless; each request has to provide a full set of arguments
(NFS V4 is just coming available – very different, stateful)Modified data must be committed to the server’s disk before results are returned to the client (lose advantages of caching)The NFS protocol does not provide concurrency-control mechanisms
11.10 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Three Major Layers of NFS Architecture Three Major Layers of NFS Architecture
UNIX file-system interface (based on the open, read, write, and close calls, and file descriptors)
Virtual File System (VFS) layer – distinguishes local files from remote ones, and local files are further distinguished according to their file-system types
The VFS activates file-system-specific operations to handle local requests according to their file-system types Calls the NFS protocol procedures for remote requests
NFS service layer – bottom layer of the architectureImplements the NFS protocol
11.11 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Schematic View of NFS Architecture Schematic View of NFS Architecture
11.12 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
NFS PathNFS Path--Name TranslationName Translation
Performed by breaking the path into component names and performing a separate NFS lookup call for every pair of component name and directory vnode
To make lookup faster, a directory name lookup cache on the client’s side holds the vnodes for remote directory names
11.13 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
NFS Remote OperationsNFS Remote Operations
Nearly one-to-one correspondence between regular UNIX system calls and the NFS protocol RPCs (except opening and closing files)NFS adheres to the remote-service paradigm, but employs buffering and caching techniques for the sake of performance File-blocks cache – when a file is opened, the kernel checks with the remote server whether to fetch or revalidate the cached attributes
Cached file blocks are used only if the corresponding cached attributes are up to date
File-attribute cache – the attribute cache is updated whenever new attributes arrive from the serverClients do not free delayed-write blocks until the server confirms that the data have been written to disk
11.14 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Example: WAFL File SystemExample: WAFL File System
Used on Network Appliance “Filers” – distributed file system appliances“Write-anywhere file layout”Serves up NFS, CIFS, http, ftpRandom I/O optimized, write optimized
NVRAM for write cachingSimilar to Berkeley Fast File System, with extensive modifications
11.15 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
The WAFL File LayoutThe WAFL File Layout
11.16 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Snapshots in WAFLSnapshots in WAFL
11.17 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
11.0211.02
Chapter 12: MassChapter 12: Mass--Storage SystemsStorage Systems
12.2 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Chapter 12: MassChapter 12: Mass--Storage SystemsStorage Systems
Overview of Mass Storage StructureDisk StructureDisk AttachmentDisk SchedulingDisk ManagementSwap-Space ManagementRAID StructureDisk AttachmentStable-Storage ImplementationTertiary Storage DevicesOperating System IssuesPerformance Issues
12.3 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
ObjectivesObjectives
Describe the physical structure of secondary and tertiary storage devices and the resulting effects on the uses of the devicesExplain the performance characteristics of mass-storage devicesDiscuss operating-system services provided for mass storage, including RAID and HSM
12.4 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Overview of Mass Storage StructureOverview of Mass Storage Structure
Magnetic disks provide bulk of secondary storage of modern computersDrives rotate at 60 to 200 times per secondTransfer rate is rate at which data flow between drive and computerPositioning time (random-access time) is time to move disk arm to desired cylinder (seek time) and time for desired sector to rotate under the disk head (rotational latency)Head crash results from disk head making contact with the disk surface
That’s badDisks can be removableDrive attached to computer via I/O bus
Busses vary, including EIDE, ATA, SATA, USB, Fibre Channel, SCSIHost controller in computer uses bus to talk to disk controller builtinto drive or storage array
12.5 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
MovingMoving--head Disk head Disk MachanismMachanism
12.6 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Overview of Mass Storage Structure (Cont.)Overview of Mass Storage Structure (Cont.)
Magnetic tapeWas early secondary-storage mediumRelatively permanent and holds large quantities of dataAccess time slowRandom access ~1000 times slower than diskMainly used for backup, storage of infrequently-used data, transfer medium between systemsKept in spool and wound or rewound past read-write headOnce data under head, transfer rates comparable to disk20-200GB typical storageCommon technologies are 4mm, 8mm, 19mm, LTO-2 and SDLT
12.7 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Disk StructureDisk Structure
Disk drives are addressed as large 1-dimensional arrays of logicalblocks, where the logical block is the smallest unit of transfer.
The 1-dimensional array of logical blocks is mapped into the sectors of the disk sequentially.
Sector 0 is the first sector of the first track on the outermostcylinder.Mapping proceeds in order through that track, then the rest of the tracks in that cylinder, and then through the rest of the cylinders from outermost to innermost.
12.8 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Disk AttachmentDisk Attachment
Host-attached storage accessed through I/O ports talking to I/O bussesSCSI itself is a bus, up to 16 devices on one cable, SCSI initiatorrequests operation and SCSI targets perform tasks
Each target can have up to 8 logical units (disks attached to device controller
FC is high-speed serial architectureCan be switched fabric with 24-bit address space – the basis of storage area networks (SANs) in which many hosts attach to many storage unitsCan be arbitrated loop (FC-AL) of 126 devices
12.9 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
NetworkNetwork--Attached StorageAttached Storage
Network-attached storage (NAS) is storage made available over a network rather than over a local connection (such as a bus)NFS and CIFS are common protocolsImplemented via remote procedure calls (RPCs) between host and storageNew iSCSI protocol uses IP network to carry the SCSI protocol
12.10 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Storage Area NetworkStorage Area Network
Common in large storage environments (and becoming more common)Multiple hosts attached to multiple storage arrays - flexible
12.11 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Disk SchedulingDisk Scheduling
The operating system is responsible for using hardware efficiently — for the disk drives, this means having a fast access time and disk bandwidth.Access time has two major components
Seek time is the time for the disk are to move the heads to the cylinder containing the desired sector.Rotational latency is the additional time waiting for the disk to rotate the desired sector to the disk head.
Minimize seek timeSeek time seek distanceDisk bandwidth is the total number of bytes transferred, divided by the total time between the first request for service and the completion of the last transfer.
12.12 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Disk Scheduling (Cont.)Disk Scheduling (Cont.)
Several algorithms exist to schedule the servicing of disk I/O requests.We illustrate them with a request queue (0-199).
98, 183, 37, 122, 14, 124, 65, 67
Head pointer 53
12.13 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
FCFSFCFS
Illustration shows total head movement of 640 cylinders.
12.14 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
SSTFSSTF
Selects the request with the minimum seek time from the current head position.SSTF scheduling is a form of SJF scheduling; may cause starvation of some requests.Illustration shows total head movement of 236 cylinders.
12.15 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
SSTF (Cont.)SSTF (Cont.)
12.16 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
SCANSCAN
The disk arm starts at one end of the disk, and moves toward theother end, servicing requests until it gets to the other end of the disk, where the head movement is reversed and servicing continues.Sometimes called the elevator algorithm.Illustration shows total head movement of 208 cylinders.
12.17 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
SCAN (Cont.)SCAN (Cont.)
12.18 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
CC--SCANSCAN
Provides a more uniform wait time than SCAN.The head moves from one end of the disk to the other. servicing requests as it goes. When it reaches the other end, however, itimmediately returns to the beginning of the disk, without servicing any requests on the return trip.Treats the cylinders as a circular list that wraps around from the last cylinder to the first one.
12.19 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
CC--SCAN (Cont.)SCAN (Cont.)
12.20 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
CC--LOOKLOOK
Version of C-SCANArm only goes as far as the last request in each direction, thenreverses direction immediately, without first going all the way to the end of the disk.
12.21 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
CC--LOOK (Cont.)LOOK (Cont.)
12.22 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Selecting a DiskSelecting a Disk--Scheduling AlgorithmScheduling Algorithm
SSTF is common and has a natural appealSCAN and C-SCAN perform better for systems that place a heavy load on the disk.Performance depends on the number and types of requests.Requests for disk service can be influenced by the file-allocation method.The disk-scheduling algorithm should be written as a separate module of the operating system, allowing it to be replaced with a different algorithm if necessary.Either SSTF or LOOK is a reasonable choice for the default algorithm.
12.23 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Disk ManagementDisk Management
Low-level formatting, or physical formatting — Dividing a disk into sectors that the disk controller can read and write.To use a disk to hold files, the operating system still needs torecord its own data structures on the disk.
Partition the disk into one or more groups of cylinders.Logical formatting or “making a file system”.
Boot block initializes system.The bootstrap is stored in ROM.Bootstrap loader program.
Methods such as sector sparing used to handle bad blocks.
12.24 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Booting from a Disk in Windows 2000Booting from a Disk in Windows 2000
12.25 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
SwapSwap--Space ManagementSpace Management
Swap-space — Virtual memory uses disk space as an extension of main memory.Swap-space can be carved out of the normal file system,or, more commonly, it can be in a separate disk partition.Swap-space management
4.3BSD allocates swap space when process starts; holds textsegment (the program) and data segment.Kernel uses swap maps to track swap-space use.Solaris 2 allocates swap space only when a page is forced out of physical memory, not when the virtual memory page is first created.
12.26 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Data Structures for Swapping on Linux Data Structures for Swapping on Linux SystemsSystems
12.27 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
RAID StructureRAID Structure
RAID – multiple disk drives provides reliability via redundancy.
RAID is arranged into six different levels.
12.28 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
RAID (cont)RAID (cont)
Several improvements in disk-use techniques involve the use of multiple disks working cooperatively.
Disk striping uses a group of disks as one storage unit.
RAID schemes improve performance and improve the reliability of the storage system by storing redundant data.
Mirroring or shadowing keeps duplicate of each disk.Block interleaved parity uses much less redundancy.
12.29 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
RAID LevelsRAID Levels
12.30 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
RAID (0 + 1) and (1 + 0)RAID (0 + 1) and (1 + 0)
12.31 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
StableStable--Storage ImplementationStorage Implementation
Write-ahead log scheme requires stable storage.
To implement stable storage:Replicate information on more than one nonvolatile storage media with independent failure modes.Update information in a controlled manner to ensure that we can recover the stable data after any failure during data transfer or recovery.
12.32 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Tertiary Storage DevicesTertiary Storage Devices
Low cost is the defining characteristic of tertiary storage.
Generally, tertiary storage is built using removable media
Common examples of removable media are floppy disks and CD-ROMs; other types are available.
12.33 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Removable DisksRemovable Disks
Floppy disk — thin flexible disk coated with magnetic material, enclosed in a protective plastic case.
Most floppies hold about 1 MB; similar technology is used for removable disks that hold more than 1 GB.Removable magnetic disks can be nearly as fast as hard disks, but they are at a greater risk of damage from exposure.
12.34 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Removable Disks (Cont.)Removable Disks (Cont.)
A magneto-optic disk records data on a rigid platter coated with magnetic material.
Laser heat is used to amplify a large, weak magnetic field to record a bit.Laser light is also used to read data (Kerr effect).The magneto-optic head flies much farther from the disk surface than a magnetic disk head, and the magnetic material is covered with a protective layer of plastic or glass; resistant to head crashes.
Optical disks do not use magnetism; they employ special materials that are altered by laser light.
12.35 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
WORM DisksWORM Disks
The data on read-write disks can be modified over and over.WORM (“Write Once, Read Many Times”) disks can be written only once.Thin aluminum film sandwiched between two glass or plastic platters.To write a bit, the drive uses a laser light to burn a small hole through the aluminum; information can be destroyed by not altered.Very durable and reliable.Read Only disks, such ad CD-ROM and DVD, com from the factory with the data pre-recorded.
12.36 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
TapesTapes
Compared to a disk, a tape is less expensive and holds more data, but random access is much slower.Tape is an economical medium for purposes that do not require fast random access, e.g., backup copies of disk data, holding huge volumes of data.Large tape installations typically use robotic tape changers that move tapes between tape drives and storage slots in a tape library.
stacker – library that holds a few tapessilo – library that holds thousands of tapes
A disk-resident file can be archived to tape for low cost storage; the computer can stage it back into disk storage for active use.
12.37 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Operating System IssuesOperating System Issues
Major OS jobs are to manage physical devices and to present a virtual machine abstraction to applications
For hard disks, the OS provides two abstraction:Raw device – an array of data blocks.File system – the OS queues and schedules the interleaved requests from several applications.
12.38 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Application InterfaceApplication Interface
Most OSs handle removable disks almost exactly like fixed disks— a new cartridge is formatted and an empty file system is generated on the disk.Tapes are presented as a raw storage medium, i.e., and application does not not open a file on the tape, it opens the whole tape drive as a raw device.Usually the tape drive is reserved for the exclusive use of thatapplication.Since the OS does not provide file system services, the application must decide how to use the array of blocks.Since every application makes up its own rules for how to organize a tape, a tape full of data can generally only be used by the program that created it.
12.39 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Tape DrivesTape Drives
The basic operations for a tape drive differ from those of a disk drive.locate positions the tape to a specific logical block, not an entire track (corresponds to seek).The read position operation returns the logical block number where the tape head is.The space operation enables relative motion.Tape drives are “append-only” devices; updating a block in the middle of the tape also effectively erases everything beyond that block.An EOT mark is placed after a block that is written.
12.40 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
File NamingFile Naming
The issue of naming files on removable media is especially difficult when we want to write data on a removable cartridge on one computer, and then use the cartridge in another computer. Contemporary OSs generally leave the name space problem unsolved for removable media, and depend on applications and users to figure out how to access and interpret the data.Some kinds of removable media (e.g., CDs) are so well standardized that all computers use them the same way.
12.41 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Hierarchical Storage Management (HSM)Hierarchical Storage Management (HSM)
A hierarchical storage system extends the storage hierarchy beyond primary memory and secondary storage to incorporate tertiary storage — usually implemented as a jukebox of tapes or removable disks.Usually incorporate tertiary storage by extending the file system.
Small and frequently used files remain on disk.Large, old, inactive files are archived to the jukebox.
HSM is usually found in supercomputing centers and other large installations that have enormous volumes of data.
12.42 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
SpeedSpeed
Two aspects of speed in tertiary storage are bandwidth and latency.
Bandwidth is measured in bytes per second.Sustained bandwidth – average data rate during a large transfer; # of bytes/transfer time.Data rate when the data stream is actually flowing.Effective bandwidth – average over the entire I/O time, including seek or locate, and cartridge switching.Drive’s overall data rate.
12.43 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Speed (Cont.)Speed (Cont.)
Access latency – amount of time needed to locate data.Access time for a disk – move the arm to the selected cylinder and wait for the rotational latency; < 35 milliseconds.Access on tape requires winding the tape reels until the selected block reaches the tape head; tens or hundreds of seconds.Generally say that random access within a tape cartridge is about a thousand times slower than random access on disk.
The low cost of tertiary storage is a result of having many cheap cartridges share a few expensive drives.A removable library is best devoted to the storage of infrequently used data, because the library can only satisfy a relatively small number of I/O requests per hour.
12.44 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
ReliabilityReliability
A fixed disk drive is likely to be more reliable than a removable disk or tape drive.
An optical cartridge is likely to be more reliable than a magnetic disk or tape.
A head crash in a fixed hard disk generally destroys the data, whereas the failure of a tape drive or optical disk drive often leaves the data cartridge unharmed.
12.45 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
CostCost
Main memory is much more expensive than disk storage
The cost per megabyte of hard disk storage is competitive with magnetic tape if only one tape is used per drive.
The cheapest tape drives and the cheapest disk drives have had about the same storage capacity over the years.
Tertiary storage gives a cost savings only when the number of cartridges is considerably larger than the number of drives.
12.46 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Price per Megabyte of DRAM, From 1981 to 2004Price per Megabyte of DRAM, From 1981 to 2004
12.47 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Price per Megabyte of Magnetic Hard Disk, From 1981 to 2004Price per Megabyte of Magnetic Hard Disk, From 1981 to 2004
12.48 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 1, 2005
Price per Megabyte of a Tape Drive, From 1984Price per Megabyte of a Tape Drive, From 1984--20002000
End of Chapter 12End of Chapter 12
Chapter 13: I/O SystemsChapter 13: I/O Systems
13.2 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Chapter 13: I/O SystemsChapter 13: I/O Systems
I/O HardwareApplication I/O InterfaceKernel I/O SubsystemTransforming I/O Requests to Hardware OperationsStreamsPerformance
13.3 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
ObjectivesObjectives
Explore the structure of an operating system’s I/O subsystemDiscuss the principles of I/O hardware and its complexityProvide details of the performance aspects of I/O hardware and software
13.4 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
I/O HardwareI/O Hardware
Incredible variety of I/O devicesCommon concepts
PortBus (daisy chain or shared direct access)Controller (host adapter)
I/O instructions control devicesDevices have addresses, used by
Direct I/O instructionsMemory-mapped I/O
13.5 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
A Typical PC Bus StructureA Typical PC Bus Structure
13.6 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Device I/O Port Locations on PCs (partial)Device I/O Port Locations on PCs (partial)
13.7 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
PollingPolling
Determines state of device command-readybusyError
Busy-wait cycle to wait for I/O from device
13.8 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
InterruptsInterrupts
CPU Interrupt-request line triggered by I/O device
Interrupt handler receives interrupts
Maskable to ignore or delay some interrupts
Interrupt vector to dispatch interrupt to correct handlerBased on prioritySome nonmaskable
Interrupt mechanism also used for exceptions
13.9 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
InterruptInterrupt--Driven I/O CycleDriven I/O Cycle
13.10 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Intel Pentium Processor EventIntel Pentium Processor Event--Vector TableVector Table
13.11 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Direct Memory AccessDirect Memory Access
Used to avoid programmed I/O for large data movement
Requires DMA controller
Bypasses CPU to transfer data directly between I/O device and memory
13.12 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Six Step Process to Perform DMA TransferSix Step Process to Perform DMA Transfer
13.13 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Application I/O InterfaceApplication I/O Interface
I/O system calls encapsulate device behaviors in generic classesDevice-driver layer hides differences among I/O controllers from kernelDevices vary in many dimensions
Character-stream or blockSequential or random-accessSharable or dedicatedSpeed of operationread-write, read only, or write only
13.14 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
A Kernel I/O StructureA Kernel I/O Structure
13.15 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Characteristics of I/O DevicesCharacteristics of I/O Devices
13.16 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Block and Character DevicesBlock and Character Devices
Block devices include disk drivesCommands include read, write, seek Raw I/O or file-system accessMemory-mapped file access possible
Character devices include keyboards, mice, serial portsCommands include get, putLibraries layered on top allow line editing
13.17 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Network DevicesNetwork Devices
Varying enough from block and character to have own interface
Unix and Windows NT/9x/2000 include socket interfaceSeparates network protocol from network operationIncludes select functionality
Approaches vary widely (pipes, FIFOs, streams, queues, mailboxes)
13.18 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Clocks and TimersClocks and Timers
Provide current time, elapsed time, timer
Programmable interval timer used for timings, periodic interrupts
ioctl (on UNIX) covers odd aspects of I/O such as clocks and timers
13.19 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Blocking and Nonblocking I/OBlocking and Nonblocking I/O
Blocking - process suspended until I/O completedEasy to use and understandInsufficient for some needs
Nonblocking - I/O call returns as much as availableUser interface, data copy (buffered I/O)Implemented via multi-threadingReturns quickly with count of bytes read or written
Asynchronous - process runs while I/O executesDifficult to useI/O subsystem signals process when I/O completed
13.20 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Two I/O MethodsTwo I/O Methods
Synchronous Asynchronous
13.21 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Kernel I/O SubsystemKernel I/O Subsystem
SchedulingSome I/O request ordering via per-device queueSome OSs try fairness
Buffering - store data in memory while transferring between devices
To cope with device speed mismatchTo cope with device transfer size mismatchTo maintain “copy semantics”
13.22 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
DeviceDevice--status Tablestatus Table
13.23 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Sun Enterprise 6000 DeviceSun Enterprise 6000 Device--Transfer RatesTransfer Rates
13.24 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Kernel I/O SubsystemKernel I/O Subsystem
Caching - fast memory holding copy of dataAlways just a copyKey to performance
Spooling - hold output for a deviceIf device can serve only one request at a time i.e., Printing
Device reservation - provides exclusive access to a deviceSystem calls for allocation and deallocationWatch out for deadlock
13.25 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Error HandlingError Handling
OS can recover from disk read, device unavailable, transient write failures
Most return an error number or code when I/O request fails
System error logs hold problem reports
13.26 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
I/O ProtectionI/O Protection
User process may accidentally or purposefully attempt to disruptnormal operation via illegal I/O instructions
All I/O instructions defined to be privilegedI/O must be performed via system calls
Memory-mapped and I/O port memory locations must be protected too
13.27 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Use of a System Call to Perform I/OUse of a System Call to Perform I/O
13.28 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Kernel Data StructuresKernel Data Structures
Kernel keeps state info for I/O components, including open file tables, network connections, character device state
Many, many complex data structures to track buffers, memory allocation, “dirty” blocks
Some use object-oriented methods and message passing to implement I/O
13.29 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
UNIX I/O Kernel StructureUNIX I/O Kernel Structure
13.30 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
I/O Requests to Hardware OperationsI/O Requests to Hardware Operations
Consider reading a file from disk for a process:
Determine device holding file Translate name to device representationPhysically read data from disk into bufferMake data available to requesting processReturn control to process
13.31 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Life Cycle of An I/O RequestLife Cycle of An I/O Request
13.32 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
STREAMSSTREAMS
STREAM – a full-duplex communication channel between a user-level process and a device in Unix System V and beyond
A STREAM consists of:- STREAM head interfaces with the user process- driver end interfaces with the device- zero or more STREAM modules between them.
Each module contains a read queue and a write queue
Message passing is used to communicate between queues
13.33 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
The STREAMS StructureThe STREAMS Structure
13.34 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
PerformancePerformance
I/O a major factor in system performance:
Demands CPU to execute device driver, kernel I/O codeContext switches due to interruptsData copyingNetwork traffic especially stressful
13.35 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Intercomputer CommunicationsIntercomputer Communications
13.36 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
Improving PerformanceImproving Performance
Reduce number of context switchesReduce data copying Reduce interrupts by using large transfers, smart controllers, pollingUse DMABalance CPU, memory, bus, and I/O performance for highest throughput
13.37 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Jan 2, 2005
DeviceDevice--Functionality ProgressionFunctionality Progression
End of Chapter 13End of Chapter 13
Top Related