Sistemi Operativi B 2006/2007 DSI@Unive - canoaclubsandona.it SOB 2007 italiano.pdf · zIl file è...

Sistemi Operativi B 2006/2007 - Appunti delle lezioni 1

Sistemi Operativi B2006/2007DSI@Unive

L’interfaccia del File System(Capitolo 10 Silberschatz)


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


Obiettivi

Spiegare le funzionalità di un file system

Descrivere le interfacce verso un file system

Discutere i principi di progetto e protezione


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


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


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.


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)


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)


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


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


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


Tipi di file e estensioni


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)


File ad accesso sequenzialeSi ispira al modello dei nastri magnetici

read next

write next

reset, rewind

(rewrite)

Non è possibile leggere dopo l’ultima scrittura


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


Accesso sequenziale su un file ad accesso diretto


Esempio di file a indice


Indice multilivello

ABC

ST


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


Organizzazione del file system


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


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


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.)


Directory ad albero (gerarchica)


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


Directory a livello singolo

Una singola directory per tutti gli utentiConfusione nei nomi dei file

Problemi di gestione (nessun raggruppamento)


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

mail

prog copy prt exp count


Directory a grafo aciclico 1/2Possono avere sottodirectory e file condivisi in più directory


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


Directory a grafo generale 1/2


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)


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



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… …


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)


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



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


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


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


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


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)


ProtezioneIl proprietario/creatore di un file deve essere in grado di controllare:

Che cosa può essere fattoDa chi

Tipi di accessoLetturaScritturaEsecuzioneEstenzioneCancellazioneElencazione


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


Windows XP Access Control List


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


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


Esempio di directory in Unix


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)


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)


Montaggio di un file system 2/2

a) Esistente b) Partizione da montare


Mount point


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


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 B2006/2007DSI@Unive

Realizzazione del file system(Capitolo 11 Silberschatz)


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


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


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.


File system stratificato


User Program

Basic I/O Supervisor

Tape Device DriverDisk Device Driver

Basic File System

Logical I/O

HashedIndexedIndexedSequentialSequentialFile

File system Software Architecture


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


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


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


Un tipico descrittore di file


Struttura del file system in memoria


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


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)





Corrispondenza tra indirizzo logico e posizione fisica

Indirizzo Logico

Dimensione cluster

Q

R

Cluster di accesso= Q + indirizzo del primo clusterOffset nel cluster = R


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)


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 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


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 =


Allocazione concatenata 2/3


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.


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


Allocazione indicizzata 1/4

Raggruppa tutti i puntatori in una sola locazione: il blocco indice

tabella indice


Allocazione indicizzata 2/4


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)


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


Allocazione indicizzata multilivello

M

outer-index

index table file


Schema combinato UNIX


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


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


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


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+


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)


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


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


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


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)


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


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


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


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


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)


I/O senza buffer cache unica


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


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


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


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


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


Three Independent File SystemsThree Independent File Systems


Mounting in NFS Mounting in NFS

Mounts Cascading mounts


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


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


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


Schematic View of NFS Architecture Schematic View of NFS Architecture


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


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


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


The WAFL File LayoutThe WAFL File Layout


Snapshots in WAFLSnapshots in WAFL


11.0211.02

Chapter 12: MassChapter 12: Mass--Storage SystemsStorage Systems


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


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


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


MovingMoving--head Disk head Disk MachanismMachanism


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


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.


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


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


Storage Area NetworkStorage Area Network

Common in large storage environments (and becoming more common)Multiple hosts attached to multiple storage arrays - flexible


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.


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


FCFSFCFS

Illustration shows total head movement of 640 cylinders.


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.


SSTF (Cont.)SSTF (Cont.)


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.


SCAN (Cont.)SCAN (Cont.)


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.


CC--SCAN (Cont.)SCAN (Cont.)


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.


CC--LOOK (Cont.)LOOK (Cont.)


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.


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.


Booting from a Disk in Windows 2000Booting from a Disk in Windows 2000


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.


Data Structures for Swapping on Linux Data Structures for Swapping on Linux SystemsSystems


RAID StructureRAID Structure

RAID – multiple disk drives provides reliability via redundancy.

RAID is arranged into six different levels.


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.


RAID LevelsRAID Levels


RAID (0 + 1) and (1 + 0)RAID (0 + 1) and (1 + 0)


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


Price per Megabyte of DRAM, From 1981 to 2004Price per Megabyte of DRAM, From 1981 to 2004


Price per Megabyte of Magnetic Hard Disk, From 1981 to 2004Price per Megabyte of Magnetic Hard Disk, From 1981 to 2004


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


Chapter 13: I/O SystemsChapter 13: I/O Systems

I/O HardwareApplication I/O InterfaceKernel I/O SubsystemTransforming I/O Requests to Hardware OperationsStreamsPerformance


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


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


A Typical PC Bus StructureA Typical PC Bus Structure


Device I/O Port Locations on PCs (partial)Device I/O Port Locations on PCs (partial)


PollingPolling

Determines state of device command-readybusyError

Busy-wait cycle to wait for I/O from device


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


InterruptInterrupt--Driven I/O CycleDriven I/O Cycle


Intel Pentium Processor EventIntel Pentium Processor Event--Vector TableVector Table


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


Six Step Process to Perform DMA TransferSix Step Process to Perform DMA Transfer


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


A Kernel I/O StructureA Kernel I/O Structure


Characteristics of I/O DevicesCharacteristics of I/O Devices


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


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)


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


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


Two I/O MethodsTwo I/O Methods

Synchronous Asynchronous


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”


DeviceDevice--status Tablestatus Table


Sun Enterprise 6000 DeviceSun Enterprise 6000 Device--Transfer RatesTransfer Rates


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


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


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


Use of a System Call to Perform I/OUse of a System Call to Perform I/O


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


UNIX I/O Kernel StructureUNIX I/O Kernel Structure


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


Life Cycle of An I/O RequestLife Cycle of An I/O Request


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


The STREAMS StructureThe STREAMS Structure


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


Intercomputer CommunicationsIntercomputer Communications


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


DeviceDevice--Functionality ProgressionFunctionality Progression

End of Chapter 13End of Chapter 13

Sistemi Operativi B 2006/2007 DSI@Unive - canoaclubsandona.it SOB 2007 italiano.pdf · zIl file è...

Documents

Transcript of Sistemi Operativi B 2006/2007 DSI@Unive - canoaclubsandona.it SOB 2007 italiano.pdf · zIl file è...