Input Output - Pavia · 2020-05-20 · Sistemi Operativi 19/20 Input Output 6 I/O • Ogni...

Input Output

Principi di gestione dell’hardware di I/O Dispositivi di I/O Gestione dei dischi magnetici Altri dispositivi

Sistemi Operativi 19/20 Input Output 2

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 network

5 GB/sec


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)

• È fondamentale che il S.O. possa gestire l'I/O indipendentemente dal dispositivo


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 MemoriaControllore

del disco

Bus di sistema

Controllorestampante

Altricontrollori

Stampante

DischiInterfaccia

Controllore-dispositivo


Tipica struttura del bus di un PC


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

Porte di I/O

Memoria

Buffer di I/O

Porte di I/O


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

Valoredelcontatore

Controlloredel

disco

Buffer

Registri DMAIndirizzo di memoriaContatore

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(); ritorna_da_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(); ritorna_da_interruzione();


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 controllare la correttezza dell'operazione


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

• Informazioni sugli errori


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(d) Doppio buffer nel kernel


Livelli del software di I/O

Funzioni di I/OLivello

Hardware

Gestore delle interruzioni

Driver di dispositivo

Software indipendente dal dispositivo

Processi 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

Richiesta di I/O Risposta di I/O


Clock

• I clock o timer servono per gestire il timesharing, per la CPU e per tutta la gestione dei segnaliil 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)

• In genere poi vi è un clock di riserva alimentato a batteria


Software del clock

• L'hardware genera solo una interruzione ad intervalli definiti

• Qualunque altra attività deve essere gestita via softwaregeneralmente 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

– Funzioni statistiche


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– se il sistema rimane attivo più di due anni si ha overflow

Dischi magnetici

StrutturaAlgoritmi di schedulingDischi 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

● Componenti elettronici (il controller)● Conversione analogico-digitale dei segnali● Strutturazione dei dati (byte, word, blocchi)


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

– deve essere compatibile con le dimensioni dei settori


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

• 128 byte per settore

• 175 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 065

4 321

7 036

2 514

5 02

74 1

63

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

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

• direzione di spostamento


Algoritmo FCFS

sequenza di riferimento: 39 11 75 50 85 52 66

• condizioni iniziali: traccia 45, velocità 10 tracce/ms in direzione di tracce crescenti

50 85756652 990 11 39 45

++

+

+

+

++

+

6

28

64

25

35

3314

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 85756652 990 11 39 45

++

+

+

+

++

+Movimenti totali della testina: 140

5 2

13

27

910

74

Distanza

5

7

20

47

56

66

140


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

permette di soddisfare qualunque coda di richieste

• performance molto buone per carichi elevati


Algoritmo SCAN

50 85756652 990 11 39 45

++

+

+

+

+

+

+

Movimento totale della testina 142

52

14

9

10

60

28

Distanza

5

7

21

30

40

54

114

+14

142



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 85756652 990 11 39 45

++

+

+

+

+

++

Movimento totale della testina 192

52

14

9

10

99

28

Distanza

5

7

21

30

40

54

153

+14

164


+11

192



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


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)

• Gestione dei settori danneggiati


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 può essere realizzato a livello di SO o di dispositivo


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 piccole quantità di dati


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à

• Buon trasferimento di dati, scarsa frequenza di accesso


RAID 4

• Parità di blocco (come RAID 0 + parità)

• Trasferimento di dati non ottimo

• Possibile collo di bottiglia sul disco di parità


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à


RAID 1 + 0

Esercizi

Scheduling del disco



Analizzare la successione di accessi alle tracce con gli algoritmi SSTF, SCAN, C-LOOK

20, 51, 8, 75, 37, 96

posizione iniziale 65, verso le tracce alte, il numero totale di tracce è 100.

Valutare il tempo necessario per l'evasione delle richieste, se sono necessari 0.1 ms per lo spostamento da una traccia a quella contigua.

Cosa cambia se dopo 3 ms arrivano le seguenti richieste?

35, 83



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]



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

LOOK: (65,) 75, 96, [83], 51, 37, [35], 20, 8



C-SCAN: (65,) 75, 96, 99, 0, 8, 20, [35], 37, 51, [83]

C-LOOK: (65,) 75, 96, 8, 20, [35], 37, 51, [83]



Analizzare la successione di accessi con l'algoritmo SSTF

45 61 31 55 91 98 34

posizione iniziale 40, il numero totale di tracce è 100.

Valutare il tempo necessario per l'evasione delle richieste, se sono necessari 0.1 ms per lo spostamento da una traccia a quella contigua.

Cosa cambia se dopo 2 ms arriva la richiesta 70?



SSTF: (40,) 45 55 61 34 31 91 98

SSTF: (40,) 45 55 61 70 91 98 34 31 (considerando 70)



Schedulazione del disco: analizzare la successione di accessi alle tracce con gli algoritmi SSTF, LOOK

159, 97, 183, 49, 128, 7, 130, 32, 120

posizione iniziale 69, il movimento è verso le tracce alte, le tracce 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 traccia a quella contigua, le ultime 3 richieste arrivano dopo 6ms.



159, 97, 183, 49, 128, 7 - 130, 32, 120

Input Output - Pavia · 2020-05-20 · Sistemi Operativi 19/20 Input Output 6 I/O • Ogni...

Documents

Transcript of Input Output - Pavia · 2020-05-20 · Sistemi Operativi 19/20 Input Output 6 I/O • Ogni...