5/15/14

1

Gestione dell’ I/O e

Scheduling dei Dischi

Sommario – Dispositivi di I/O – Organizzazione delle funzioni di I/O – Problematiche di Progettazione –  I/O Buffering – Disk Scheduling

Categorie di Dispositivi di I/O

•  Area problematica nella progettazione di un OS – Difficile sviluppare una soluzione

omnicomprensiva a causa della diversità dei dispositivi e delle applicazioni

•  Tre Categorie: – Dispositivi “Human readable” – Dispositivi “Machine readable” – Dispositivi di Comunicazione

Human readable

•  Dispositivi usati per comunicare con l’utente

•  Stampanti e Terminali – Video display – Tastiere – Mouse etc

5/15/14

2

Machine readable

•  Usati per comunicare con memorie di massa o sorgenti di informazione esterne – Disk drive – USB – Sensori – Controllori – Attuatori

Comunicazione

•  Usati per comunicare con dispositivi remoti – Controllori di linee digitali – Modem

Differenze tra Dispositivi I/O

•  Differiscono per numerosi aspetti – Tasso di trasferimento dati – Applicazioni – Complessitaà di controllo – Modalità di trasferimento – Rappresentazione dei dati – Condizioni di Errore

Tasso di trasferimento dati

•  Enormi differenze tra dispositivo e dispositivo

5/15/14

3

Applicazioni

– Un disco per la memorizzazione di file necessita di software per la gestione dei file

– Un Disco per la memorizzazione di pagine di memoria virtuale necessita’ di hw e sw specifico di supporto

– Terminali usati da system administrator possono avere diverse priorita’ rispetto a terminali utente

Complessità di controllo

•  Una stampante necessita di un’interfaccia relativamente semplice

•  Un disco richiede maggiore complessità di controllo.

•  Diversità in parte bilanciate dalla diversa complessità dei moduli I/O che controllano i dispositivi.

Modalità di trasferimento

•  I Dati possono essere transferiti come – Flussi (stream) di byte o caratteri (es.,

terminali I/O) – a blocchi (es., dischi).

Rappresentazione Dati

•  Diversi schemi di codifica sono usati dai diversi dispositivi, – Anche differenti codifiche dei caratteri o

schemi di parità.

5/15/14

4

Condizioni di Errore

•  La natura degli errori possibili: –  Il modo in cui gli errori vengono riportati, – Le loro consequenze, –  Il range di possibili contromisure

Sommario – Dispositivi di I/O – Organizzazione delle funzioni di I/O – Problematiche di Progettazione –  I/O Buffering – Disk Scheduling

Tecniche di I/O

•  I/O Programmato •  I/O Interrupt-driven •  Direct memory access (DMA)

Evoluzione dei modelli di I/O

1.  Il Processore controlla direttamente un dispositivo periferico

2.  Aggiunta di un Controller o modulo di I/O – Processore usa “I/O programmato” senza

interrupt – Processore non gestisce i dispositivi esterni

nei dettagli

5/15/14

5

Evoluzione dei modelli di I/O

3.  Controller o modulo di I/O con interrupt – Efficienza aumenta: il processore non aspetta

il completamento di un’operazione di I/O 4.  Direct Memory Access

– Blocchi di dati sono spostati in memoria senza l’intervento del processore

– Processore interviene solo all’inizio ed alla fine dell’operazione

Evoluzione dei modelli di I/O

5.  Modulo I/O e’ un processore dedicato –  CPU delega al processore I/O l’esecuzione di

programmi I/O in memoria centrale. 6.  Processori I/O

– Modulo I/O dispone di memoria locale – Tipico uso: controllo della comunicazione con

terminali interattivi

Direct Memory Address

•  Il Processore delega operazioni di I/O al modulo DMA

•  Modulo DMA trasferisce I dati direttamente dalla/nella memoria

•  Al completamento, il modulo DMA invia un interrupt al processore

Configurazioni DMA: Bus Singolo

•  DMA puo’ essere configurato in diversi modi •  Qui, tutti i moduli condividono lo stesso bus di

sistema

5/15/14

6

Configurazioni DMA: DMA e I/O Integrati

•  Connessione diretta tra DMA e moduli I/O •  Risultato: riduzione di cicli di bus necessari a

completare un operazione

Configurazioni DMA: I/O Bus

•  Riduce il numero di interfacce per I/O nel modulo DMA

Sommario – Dispositivi di I/O – Organizzazione delle funzioni di I/O – Problematiche di Progettazione –  I/O Buffering – Disk Scheduling

Scopi: Efficienza

•  I dispositivi di I/O sono molto lenti rispetto alla memoria

•  Multiprogrammazione per avere concorrenza tra processi in I/O e processi in elaborazione

•  I/O non può avanzare al passo della CPU – Swapping per includere altri processi pronti – Ma swapping implica ulteriori operazioni di I/O

5/15/14

7

Scopi: Generalità

•  Gestione uniforme dei dispositivi I/O aumenta la semplicità e riduce gli errori

•  Delegare dettagli dei dispositivi alle routine di basso livello

•  Date le differenze tra i dispositivi e difficile ottenere una vera generalità; si può usare una progettazione modulare a livelli delle funzionalità di I/O

Progettazione Gerarchica

•  Organizzazione a livelli •  Ogni livello si serve del livello

immediatamente inferiore per funzionalità di livello più basso

•  Fornisce servizi al livello immediatamente superiore

•  Modifiche hanno effetti solo su un livello

Dispositivi di periferiche locali •  I/O logico:

– Gestisce il dispositivo come una risorsa logica

•  Dispositivo I/O: – Converte le operazioni logiche richieste in

una sequenza di istruzioni di I/O •  Scheduling e Controllo

– Opera l’ordinamento e controllo delle vere e proprie operazioni di I/O

Porte di Comunicazione •  Simile alla struttura precedente; il

modulo di I/O logico e’ sostituito da un’architettura per la comunicazione, – A sua volta strutturata per livelli di

funzionalitaà. – Esempio: TCP/IP,

5/15/14

8

File System •  Gestione delle Directory

– Riguarda le operazioni sui file, copie, cancellazioni, link

•  File System – Struttura logica dei file, operazioni

quali read, open, write •  Organizzazione Fisica

– Converte nomi logici in indirizzi fisici, allocazione, bufferizzazione

Sommario – Dispositivi di I/O – Organizzazione delle funzioni di I/O – Problematiche di Progettazione –  I/O Buffering – Disk Scheduling

Buffer per I/O

•  I Processi devono attendere il completamento dell’I/O prima di continuare – Per evitare deadlock alcune pagine devono

rimanere in memoria durante I/O •  In alternativa, è possibile anticipare

trasferimenti in memoria e/o posticipare trasferimenti in output rispetto alla richiesta effettiva.

Buffer orientato ai Blocchi

•  Informazioni organizzate in blocchi di dimensione fissata

•  Trasferimenti operati per blocchi – Riferimenti ai dati mediante numero di blocco

•  Usato per i dischi e USB key

5/15/14

9

Buffer orientato agli Stream

•  Informazioni trasferite come stream di byte •  Usato per terminali, stampanti, porte di

comunicazione, mouse, e altri dispositivi di puntamento, inclusi molti altri dispositivi non di memoria di massa

Nessuna Bufferizzazione

•  In assenza di bufferizzazione, il SO accede direttamente al dispositivo come e quando vuole

Buffer singolo

•  SO assegna un’area di buffer in memoria ad ogni richiesta di I/O

Buffer Singolo Orientato ai Blocchi

•  Trasferimenti Input inviati al buffer •  Terminato il trasferimento di un blocco lo si

passa alla memoria utente •  Il blocco successivo viene caricato nel

buffer – Read ahead o Input Anticipato

•  Spesso utile, perché molti accessi sono sequenziali (similarità: prepaging)

5/15/14

10

Buffer Singolo vs No Buffer

•  T tempo di trasferimento dal dispositivo •  C tempo di computazione dell’istruzione •  M tempo di trasferimento dal buffer a MEM

•  Senza buffer – T+C

•  Con buffer singolo – Max{C,T}+M

Buffer Singolo Stream-oriented

•  Trasferimento a linee o a carattere •  Per terminali bufferizzazione a linee

(attende CR) •  Bufferizzazione a carattere o byte-

oriented utile per dispositivi e applicazioni con risoluzione più alta dell’input – anche sensori e controllori

Buffer Doppio

•  Usa due buffer di sistema per richiesta •  Un processo può trasferire dati ad/da un

buffer, mentre il SO svuota o riempie l’altro buffer

Buffer Circolare

•  Più di due buffer in uso •  Ogni buffer rappresenta un’unità del buffer

circolare •  Usato per aumentare il parallelismo delle

operazioni di I/O.

5/15/14

11

Limiti della Bufferizzazione

•  Buffering riduce accumulo/picchi di I/O. – Ovviamente, # richieste molto elevato -> buffer

overflow -> nessun vantaggio •  Con distribuzione omogenea di

–  richieste di I/O – elaborazione

•  la bufferizzazione migliora –  l’efficienza del SO e – performance dei singoli processi.

Sommario – Dispositivi di I/O – Organizzazione delle funzioni di I/O – Problematiche di Progettazione –  I/O Buffering – Disk Scheduling

Efficienza dei Dischi: Parametri

•  La durata di una richiesta di I/O su disco può dipendere da molti fattori – Un diagramma generale dei tempi di

trasferimento per un I/O su disco:

Posizionamento delle testine di Lettura/Scrittura

•  A regime, il disco ruota ad una velocità costante

•  La selezione della traccia implica lo spostamento del braccio delle testine radialmente al disco

5/15/14

12

Efficienza dei Dischi: Parametri

•  Tempo di Accesso. Somma di: – Tempo di Seek: Il tempo necessario a

posizionare la testina sulla traccia desiderata – Ritardo di Rotazione o latenza: Il tempo

necessario a raggiungere il settore desiderato •  Tempo di Trasferimento. Il tempo

necessario a trasferire i dati dal disco al buffer/memoria locale

Scheduling del Disco Politiche

•  Consideriamo un disco la cui testina si trovi sulla traccia 100. – Assumiamo che il disco abbia 200 tracce e

che le richieste ricevute indichino le seguenti tracce (nell’ordine ricevuto)

– 55, 58, 39, 18, 90, 160, 150, 38, 184.

First-in, first-out (FIFO o FCFS)

•  Richieste servite in sequenza •  Politica Imparziale •  Nessun vantaggio rispetto a scheduling

random, se il numero dei processi e’ alto

Last-in, first-out

•  Utile per sistemi di gestione delle transazioni –  Il dispositivo viene assegnato all’utente che lo

ha utilizzato più di recente, questo dovrebbe garantire movimenti della testina di piccola entità tra una richiesta e l’altra

•  Possibilità di starvation

5/15/14

13

Shortest Service Time First

•  Serve la richiesta che richiede il minimo movimento delle testine a partire dalla posizione corrente

•  Minimizza localmente il tempo di seek

SCAN

•  Il braccio delle testine si muove solo in una direzione, servendo tutte le richieste pendenti fino a raggiungere l’ultima traccia, nella direzione corrente, quindi inverte la direzione e ripete

C-SCAN

•  Come SCAN, tranne che al ritorno non vengono servite richieste

•  Al raggingimento dell’ultima traccia, il braccio ritorna alla prima traccia e ricomincia a scandire le richieste pendenti

N-step-SCAN

•  Le richieste sono partizionate in sottosequenze di lunghezza N

•  Le sottosequenze sono servite una alla volta, usado la politica SCAN

•  Mentre si serve una sottosequenza le nuove richieste vengono aggiunte ad altre sottosequenze

5/15/14

14

FSCAN

•  Due sottosequenze •  Quando la scansione comincia, tutte le

richieste sono in un’unica coda, con l’altra coda vuota.

•  Mentre avviene la scansione ed il servizio di una coda, le nuove richieste vengono aggiunte all’altra coda •  Servizio di una nuova richiesta differito al

momento in cui la coda attiva è vuota.

Confronti Lista delle richieste: 55, 58, 39, 18, 90, 160, 150, 38, 184 Posizione iniziale della testina: traccia 100. Numero tracce: 200

Roadmap –  I/O Devices – Organization of the I/O Function – Operating System Design Issues –  I/O Buffering – Disk Scheduling – Raid

Multiple Disks

•  Disk I/O può migliorare se le operazioni sono distribuite su più testine di lettura/scrittura – O dischi multipli

•  Disk failures e recovery mediante memorizzazione con ridondanza

5/15/14

15

RAID

•  Redundant Array of Independent Disks •  Set di disk drive visti dal SO come un

unico drive logico •  Dati distribuiti sui dischi fisici •  La capacità non utilizzata per I dati è usata

per informazione ridondante per il recovery da situazioni di errore/failure.

RAID 0 - Stripped

•  Non un vero RAID – nessuna ridondanza •  Nessuna possibilitaà di recovery •  Molto veloce (parallel read/write)

RAID 1 - Mirrored

•  Ridondanza = duplicazione •  Letture in parallelo. •  Semplice recovery (esistono due copie)

RAID 2 (Usa codici di Hamming)

•  Rotazione sincronizzata •  Uso di data stripping (extremely small) •  Hamming code correggono errori su un

singolo bit e riconscono errori su 2 bit

5/15/14

16

RAID 3 bit-interleaved parity

•  Similar to RAID-2 but uses all parity bits stored on a single drive

RAID 4 Block-level parity

•  A bit-by-bit parity strip is calculated across corresponding strips on each data disk

•  The parity bits are stored in the corresponding strip on the parity disk.

RAID 5 Block-level Distributed parity

•  Similar to RAID-4 but distributing the parity bits across all drives