Input Output - vision.unipv.itvision.unipv.it/corsi/SistemiOperativi-mn/lucidi/SO-14.pdf · Sistemi...

Input Output

Principi di gestione dell’hardware di I/O Dispos itivi di I/O Gestione dei dischi magnetici Altri dispos itivi

Sistemi Operativi 12/13 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


Principi dell‘hardware di I/O


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) – SCSI (Small Computer System Interface)

• Spesso i controllori sono integrati sulle schede madri • Uso di buffer per blocco o sequenza di caratteri

CPU MemoriaControllore

del disco

Bus di sistema

Controllorestampante

Altricontrollori

Stampante

DischiInterfacciaControllore-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 • Il S.O effettua l'I/O scrivendo nei registri del controllore


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

copia_da_utente(buffer, p, contatore); abilita_interruzioni(); while(*stato_stampante != PRONTO); *registro_dati_stampante = p[0]; scheduler();

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

copia_da_utente(buffer, p, contatore); imposta_controllore_DMA(); scheduler();

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


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

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

S trutturaAlgoritmi di schedulingDischi RAIDCD-Rom


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)


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


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

++

+

+

+

++

+

628

64

5035

3314

Movimenti della testina 230

Distanza Tempo6 0.6

34 3.498 9.8

148 14.8183 18.3216 21.6230 23.0

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

279

10

74

Distanza57

20475666

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


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

50 85756652 990 11 39 45

++

+

+

+

+

++

Movimento totale della testina 192

52

149

10

99

28

Distanza

57

2130

40

54

153+14

164


+11

192Sequenza di servizio: 50 52 66 75 85 11 39


Scelta di un algoritmo

• Le prestazioni dipendono dal numero e dal tipo di richieste • La posizione dei blocchi indice sono importanti • Le informazioni più utilizzate sono messe nelle tracce centrali • l'allocazione di file influenza le prestazioni• è una grande semplificazione (non viene considerato il tempo

di seek) alcuni algoritmi di basso livello sono implementati dal controller quindi sfuggono dal controllo del SO


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)

• 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 dei settori danneggiati


RAID

• Redundant Array of Independent/Inexpensive Disk– più dischi sono combinati in un unico disco logico gestito dal

sistema operativo– ogni disco contiene una fetta (strip) dei dati


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

Disco 0 Disco 1

DatiDati

Backup Backup


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


Struttura di un CD o CD-ROM


Struttura logica dei dati

2048 byte su 7203 (588*98/8)153600 byte/s (X1)

Esercizi

S cheduling del disco


Scheduling del disco

Descrivere gli algoritmi di scheduling del disco.Analizzare la successione di accessi alle tracce con gli algoritmi

SSTF, SCAN, LOOK

20, 51, 8, 75, 37, 91

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

Valutare il tempo necessario per l'evasione delle richieste, se è necessario 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, 91, [35, 83]SSTF: (65,) 75, 91, [83], 51, 37, [35], 20, 8SCAN: (65,) 75, 91, 99, [83], 51, 37, [35], 20, 8C-SCAN: (65,) 75, 91, 99, 0, 8, 20, [35], 37, 51, [83]LOOK: (65,) 75, 91, [83], 51, 37, [35], 20, 8C-LOOK: (65,) 75, 91, 8, 20, [35], 37, 51, [83]



Descrivere gli algoritmi di scheduling del disco:analizzare la successione di accessi alle tracce

12, 91, 5, 38, 26, 52

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

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

Cosa cambia se dopo 50 ms arrivano le seguenti richieste?43, 27



FCFS: (9,) 12, 91, 5, 38, 26, 52, [43, 27]SSTF: (9,) 12, 5, 26, 38, 52, [43, 27], 91SCAN: (9,) 12, 26, 38, 52, 91, 99, [43, 27], 5C-SCAN: (9,) 12, 26, 38, 52, 91, 99, 0, 5, [27, 43]LOOK: (9,) 12, 26, 38, 52, 91, [43, 27], 5C-LOOK: (9,) 12, 26, 38, 52, 91, 5, [27, 43]

Input Output - vision.unipv.itvision.unipv.it/corsi/SistemiOperativi-mn/lucidi/SO-14.pdf · Sistemi...

Documents

Transcript of Input Output - vision.unipv.itvision.unipv.it/corsi/SistemiOperativi-mn/lucidi/SO-14.pdf · Sistemi...