Input Output
Principi di gestione dell’hardware di I/O Dispositivi di I/O
Gestione dei dischi magnetici Altri dispositivi
Principi dell‘hardware di I/O
• L'hardware di I/O può essere descritto a vari
livelli
– Ingegneri elettronici – Programmatori
– Sistema operativo
• Quali sono i moduli che gestiscono l'hardware?
– Interfaccia applicativa di I/O – Sottosistema del kernel per I/O
– Trasformazione di richiesta di I/O in operazioni hardware
• Aspetto importante: le prestazioni
Dispositivi Velocità di trasferimento Keyboard 10 bytes/sec
Mouse 100 bytes/sec
56K modem 7 KB/sec
Scanner at 300 dpi 1 MB/sec Digital camcorder 3.5 MB/sec
4x Blu-ray disc 18 MB/sec 802.11n Wireless 37.5 MB/sec
USB 2.0 60 MB/sec
FireWire 800 100 MB/sec Gigabit Ethernet 125 MB/sec SATA 3 disk drive 600 MB/sec
USB 3.0 625 MB/sec
SCSI Ultra 5 bus 640 MB/sec Single-lane PCIe 3.0
bus
985 MB/sec Thunderbolt 2 bus 2.5 GB/sec
SONET OC-768
Dispositivi di I/O
• Si distinguono due categorie di dispositivi:
1. dispositivi a blocchi
• Blocco da 512 byte a 64K
• Ogni blocco può essere letto e scritto indipendentemente dagli altri. • Ogni blocco è identificato da un indirizzo
• I comandi comprendono read, write, seek
• L'accesso ai file viene fatto tramite mappatura in memoria
• Ove possibile l’accesso viene fatto a basso livello oppure con un sistema di file system
2. dispositivi a caratteri
• Un dispositivo a carattere non è indirizzabile e non ha alcuna primitiva di posizionamento (seek)
• I comandi comprendono get e put
• L'editing di linea è possibile mediante librerie ad hoc
• Non tutti i dispositivi di I/O ricadono in questa tassonomia
(timer, display mappati in memoria)
I controllori di dispositivo
• Le unità di I/O: componente elettronica e meccanica
• La parte elettronica è gestita dal controllore di
dispositivo o adattatore
• Esempi: controllori
– IDE (Integrated Drive Electronics)
• (P)ATA ((Parallel) AT Attachment)
– SCSI (Small Computer System Interface)
– SATA (Serial Advanced Technology Attachment)
• Spesso i controllori sono integrati sulle schede madri
• Uso di buffer per blocco o sequenze di caratteri
CPU Memoria Controlloredel disco Controllorestampante controlloriAltri Stampante
Dischi Interfaccia
I/O
• Ogni controllore usa un insieme di registri per comunicare
con la CPU
• Su alcuni computer (es. 680x0) i registri sono nel normale
spazio di indirizzamento della memoria (I/O mappato in memoria)
• In altri casi si utilizza uno spazio di indirizzamento separato
– Esiste anche un approccio misto
• Il S.O effettua l'I/O scrivendo nei registri del controllore
Memoria Porte di I/O
Memoria Memoria
Accesso diretto in memoria (DMA)
• Viene usato per evitare l'I/O programmato e per grandi
trasferimenti di dati
• Richiede un controller di DMA: si trova concettualmente tra la
CPU e la memoria
• Fisicamente è collegato a memoria e CPU tramite bus
• Consente di scaricare la CPU dal compito di trasferire dati tra
il dispositivo di I/O e la memoria
CPU Memoria Valore del contatore Controllore del disco Buffer Registri DMA Indirizzo di memoria Contatore Disco
I/O gestito da interrupt
• Al termine di ogni operazione di I/O corrisponde un segnale
rilevato dal controllore di interrupt
• Se non vi sono altre interruzioni in corso la richiesta viene
gestita immediatamente, altrimenti viene momentaneamente ignorata
I/O programmato
copia_da_utente(buffer, p, contatore); for(c=0; c<contatore; c++) { while(*stato_stampante != PRONTO); *registro_dati_stampante = p[c]; } ritorna_a_utente();I/O guidato dalle interruzioni
// codice chiamata di sistema
copia_da_utente(buffer, p, contatore); abilita_interruzioni();
while(*stato_stampante != PRONTO); *registro_dati_stampante = p[0]; Scheduler();
// codice di servizio di ogni interupt
if(contatore == 0) { sblocca_utente(); } else { *registro_dati_stampante = p[c]; contatore = contatore – 1; c = c + 1; } acknowledge_interruzione();
I/O tramite DMA
// codice chiamata di sistema
copia_da_utente(buffer, p, contatore); imposta_controllore_DMA();
scheduler();
// codice di servizio interupt
acknowledge_interruzione(); sblocca_utente();
Device Driver
• Contiene tutto il software dipendente dal dispositivo
• Impartisce i comandi al controllore e ne verifica il corretto
funzionamento
• Accetta richieste astratte indipendenti dal dispositivo e le
traduce in istruzioni dipendenti
• Scrive nei registri del controllore
• Il gestore può essere bloccato oppure no. Nel primo caso
viene risvegliato da un interrupt
• Dopo il completamento della operazione di I/O il gestore deve
SW di I/O indipendente dal dispositivo
• Interfacciamento uniforme dei device driver • Assegnamento dei nomi ai dispositivi
• Protezione dei dispositivi
• Dimensione del blocco indipendente dal dispositivo • Buffering
• Allocazione della memoria per i dispositivi a blocchi • Allocazione e rilascio di dispositivi dedicati
Buffering
(a) Input senza uso di buffer
(b) Uso di buffer nello spazio utente
(c) Uso di buffer nello spazio del kernel seguito dalla copia nello spazio utente
Livelli del software di I/O
Funzioni di I/O Livello Hardware Gestore delle interruzioni Driver di dispositivo Software indipendente dal dispositivoProcessi utente Eseguire chiamate di I/O, formattazione I/O, spooling
Eseguire le operazioni di I/O
Attivazione del driver quando l’I/O è completato
Impostazione registri, controllo dello stato
Gestione dei nomi, protezione, bufferizzazione, allocazione
Clock
• I clock o timer servono per gestire il timesharing, per la CPU e
per tutta la gestione dei segnali
il software per gestire il clock è considerato un device driver
• I clock più semplici sono collegati all'alimentazione (una
interruzione a ogni ciclo di tensione, 50 o 60 Hz)
• I clock più complessi sono composti da un oscillatore, un
contatore e un registro di caricamento (per quelli programmabili)
Software del clock
• L'hardware genera solo una interruzione ad intervalli definiti • Qualunque altra attività deve essere gestita via software
generalmente il driver del clock gestisce – L'ora di sistema
– La temporizzazione dei processi – L'addebito della CPU
– Meccanismi di allarme ed attesa
• La gestione degli allarmi può essere fatta tramite una lista ordinata delle richieste di clock pendenti
Ora di sistema
• L'ora di sistema (tempo reale) viene normalmente gestita
tramite un contatore che misura i tick a partire da un istante di riferimento (per UNIX 1 gennaio 1970)
– con un contatore a 32 bit ed una frequenza di clock di 60Hz in due anni si ha un overflow per cui in genere si utilizzano due contatori
• contando solo i secondi un contatore è sufficiente per 136 anni, per avere l'equivalente del millenium bug bisogna aspettare fino al ventiduesimo secolo (ma se considero il segno diventa critico il 19 gennaio 2038), in questo caso il numero di tick del secondo corrente viene misurato a parte
• Un diverso approccio consiste nel contare i tick, dall'istante di
avvio del sistema
Dischi magnetici
StrutturaAlgoritmi di scheduling Dischi RAID
Dischi magnetici
• È il dispositivo principale di memorizzazione di massa
– memoria non volatile
– ottima capacità a prezzi ragionevoli – accesso casuale
– tempi di accesso abbastanza lunghi (ordine ms)
• Dischi a stato solido
– durata di vita più breve (in crescita) – costo più alto (in diminuzione)
– accesso casuale uniforme
• non hanno bisogno di deframmentazione – tempi di accesso più brevi (decimi di ms) – bassa (o nulla) rumorosità
Schema funzionale di un disco
Struttura logica di un disco
• tracce • cilindri • settori
– all'interno di una traccia
– qualche centinaio sui dischi rigidi – a dimensione fissa o variabile
• blocchi
– unità di trasferimento tra disco e memoria
Esempio floppy
• 40 cilindri per disco • 2 tracce per cilindro • 9 settori per tracce • 720 settori per disco • 512 byte per settore • 360 KB per disco
Tempi di accesso a un disco rigido
1) Tempo di seek
tempo necessario per muovere la testina sul cilindro alcuni millisecondi (2-10 ms)
2) Tempo di latenza
tempo necessario affinché il settore sia sotto la testina dipende dalla velocità di rotazione
7200 rpm (giri al minuto) = 120 rps 1/120 sec/giro = 8.3 ms/giro
3) Tempo di trasferimento
è proporzionale all'ammontare dell'informazione trasferita se una traccia ha 100 blocchi, è pari a 1/100 del tempo di
rivoluzione per blocco
4) Tempo medio di accesso
tempo medio di seek + tempo medio di latenza + tempo medio di trasferimento
DMA e accesso ai dischi
• Un controllore che supporta l'accesso DMA deve avere al suo
interno:
– I registri DMA – Un buffer
– I controllori più semplici non riescono a gestire l'input e l'output simultanei: riescono a leggere un blocco ogni due
– Per leggere due settori consecutivi sono necessari due rotazioni – Si ovvia a questo inconveniente con la tecnica di Interleaving
Interleaving
• La numerazione logica dei settori è diversa dall'ordinamento
fisico, saltando un (o più) settore si lascia il tempo per il trasferimento dati del precedente
7 0 6 5 4 3 2 1 3 7 0 6 2 5 1 4 2 5 0 7 4 1 6 3
Pendenza di cilindro
Algoritmi di scheduling del disco
• Al disco arrivano delle richieste di lettura - scrittura generate
dai processi
• Tali operazioni possono essere concorrenti o no
• A prescindere dalla concorrenza, occorre stabilire l'ordine con
cui si evadono le richieste al disco È compito del sistema operativo
Algoritmi possibili:
– First-Come-First-Served (FCFS) – Shortest Seek Time First (SSTF) – SCAN
Algoritmo FCFS
• Le richieste sono evase a seconda del loro tempo di arrivo • facilità d'implementazione
– Modellizzazione: coda FIFO o tabelle indicizzate
• non introduce problemi di starvation • performance
– basse prestazioni per accessi frequenti – è sufficiente per sistemi mono-utente
Confronto di algoritmi
La valutazione si basa su un modello di richieste
• distanza totale che deve compiere la testina • tempo richiesto (proporzionale alla distanza)
• tempi di latenza e di trasferimento vengono ignorati
– perché non possono essere sotto il controllo del S.O
– dipendono dall'hardware e dall'ammontare dei dati trasferiti Occorre conoscere le condizioni iniziali
• posizione iniziale
Algoritmo FCFS
sequenza di riferimento: 39 11 75 50 85 52 66
• condizioni iniziali: cilindro 45, velocità 10 cilindri/ms in
direzione di cilindri crescenti
50 52 66 75 85 99 0 11 39 45 + + + + + + + 6 28 64 25 35 33 14
Movimenti della testina 205
Distanza Tempo 6 0.6 34 3.4 98 9.8 123 12.3 158 15.8 191 19.1 205 20.5 Sequenza di riferimento: 39 11 75 50 85 52 66
Algoritmo SSTF
• si evade la richiesta che richiede il tempo di seek inferiore a
partire dalla posizione corrente
– di solito si comporta meglio del FCFS
– si può verificare la starvation: le richieste lontane dal centro ottengono un pessimo servizio
50 52 66 75 85 99 0 11 39 45 + + + + + + + 5 2 13 27 9 10 Distanza 5 7 20 47 56 66 Sequenza di riferimento: 39 11 75 50 85 52 66 Sequenza di servizio: 50 52 39 66 75 85 11
Algoritmo dell’ascensore (SCAN)
• la testina si muove da un'estremità all'altra del disco,
una variante (LOOK) non sposta la testina fino alla fine ma solo se necessario per soddisfare le richieste pendenti, altrimenti inverte subito il movimento della testina
• esiste un limite superiore al movimento della testina:
– uno spostamento di due volte il numero di cilindri
necessariamente permette di soddisfare qualunque coda di richieste
Algoritmo SCAN
50 52 66 75 85 99 0 11 39 45 + + + + + + + +Movimento totale della testina 142 5 2 14 9 10 60 28 Distanza 5 7 21 30 40 54 114 + 14 142 Sequenza di riferimento: 39 11 75 50 85 52 66 Sequenza di servizio: 50 52 66 75 85 39 11 46 86 114
Algoritmo C-SCAN
• La scansione è sempre nella stessa direzione • Tempi di attesa più uniformi rispetto allo SCAN
– Esiste la variante C-LOOK
50 52 66 75 85 99 0 11 39 45 + + + + + + + +
Movimento totale della testina 192
5 2 14 9 10 99 28 Distanza 5 7 21 30 40 54 153 + 14 164 Sequenza di riferimento: 39 11 75 50 85 52 66 + 11 192 Sequenza di servizio: 50 52 66 75 85 11 39
Scelta di un algoritmo
• Le prestazioni dipendono dal numero e dal tipo di richieste • È una grande semplificazione alcuni algoritmi di basso livello
sono implementati dal controller quindi sfuggono dal controllo del SO
• La posizione dei blocchi indice sono importanti
• Le informazioni più utilizzate sono messe nelle tracce centrali • L'allocazione di file influenza le prestazioni
• Può essere utile mettere in cache una traccia intera
– vantaggio: si ottimizzano le prestazioni (meno trasferimenti) – la cache può essere gestita dal dispositivo o dal sistema
operativo
• I dischi allo stato solido non hanno bisogno di algoritmi di
schedulazione (o comunque dovrebbero soddisfare vincoli diversi)
Gestione degli errori su disco
• Generalmente è il driver del disco che gestisce gli errori che
possono essere:
– errori di programmazione (richiesta di settori inesistenti) – errori di checksum (transitori)
– errori di checksum (permanenti)
– errori di posizionamento (recalibrate)
RAID
• Redundant Array of Independent/Inexpensive Disk
– più dischi sono combinati in unico disco logico gestito dal sistema operativo
– ogni disco contiene una fetta (strip) dei dati
RAID 0 (non-ridondante)
• Alta capacità di trasferimento dati, se i trasferimenti
riguardano grandi quantità di dati logici contigui
• Basso tempo di risposta, se il numero di richieste è alto per
RAID 1 (mirrored)
• presenta il vantaggio collaterale di permettere una velocità
di lettura doppia
• le operazioni di scrittura sono doppie, ma parallele • è facile sostituire componenti difettose
RAID 2
• Memorizzazione ridondante tramite un codice Hamming • Buon trasferimento di dati, scarsa frequenza di accesso • I dischi spesso sono sincronizzati
RAID 3
• Un solo bit di parità
RAID 4
• Parità di blocco (come RAID 0 + parità) • Trasferimento di dati non ottimo
RAID 5
• La parità è distribuita
RAID 6 – aggiunge maggiore ridondanza, può gestire guasti su più dischi
RAID 0 + 1
• Il livello 0 fornisce le prestazioni • Il livello 1 l'affidabilità
Esercizi
Scheduling del disco
Analizzare la successione di accessi ai cilindri con gli algoritmi SSTF, SCAN, C-LOOK
20, 51, 8, 75, 37, 96
posizione iniziale 65, verso i cilindri alti, il numero totale di cilindri è 100.
Valutare il tempo necessario per l'evasione delle richieste, se sono necessari 0.1 ms per lo spostamento da un cilindro a quello contiguo.
Cosa cambia se dopo 3 ms arrivano le seguenti richieste? 35, 83
Scheduling del disco
FCFS: (65,) 20, 51, 8, 75, 37, 96, [35, 83] SSTF: (65,) 75, 96, [83], 51, 37, [35], 20, 8 SCAN: (65,) 75, 96, 99, [83], 51, 37, [35], 20, 8 C-SCAN: (65,) 75, 96, 99, 0, 8, 20, [35], 37, 51, [83] LOOK: (65,) 75, 96, [83], 51, 37, [35], 20, 8 C-LOOK: (65,) 75, 96, 8, 20, [35], 37, 51, [83]Scheduling del disco
FCFS: (65,) 20, 51, 8, 75, 37, 96, [35, 83] SSTF: (65,) 75, 96, [83], 51, 37, [35], 20, 8
Scheduling del disco
SCAN: (65,) 75, 96, 99, [83], 51, 37, [35], 20, 8 LOOK: (65,) 75, 96, [83], 51, 37, [35], 20, 8
Scheduling del disco
C-SCAN: (65,) 75, 96, 99, 0, 8, 20, [35], 37, 51, [83] C-LOOK: (65,) 75, 96, 8, 20, [35], 37, 51, [83]
Scheduling del disco
Analizzare la successione di accessi con l'algoritmo SSTF 45 61 31 55 91 98 34
posizione iniziale 40, il numero totale di cilindri è 100.
Valutare il tempo necessario per l'evasione delle richieste, se sono necessari 0.1 ms per lo spostamento da un cilindro a quello contiguo.
Scheduling del disco
SSTF: (40,) 45 55 61 34 31 91 98
Scheduling del disco
Schedulazione del disco: analizzare la successione di accessi ai cilindri con gli algoritmi SSTF, LOOK
159, 97, 183, 49, 128, 7, 130, 32, 120
posizione iniziale 69, il movimento è verso l’alto, i cilindri sono numerate da 0 a 199.
Valutare il tempo necessario per l'evasione delle richieste, se è necessario un tempo di 0.1 ms per lo spostamento da una
cilindro a quello contiguo, le ultime 3 richieste arrivano dopo 6ms.