Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Domenico Cotroneo » 19.I/O e gestione dei dischi


I/O e gestione dei dischi

Sommario

  • Dispositivi, e obiettivi di progetto del sistema di I/O
  • Tecniche di comunicazione di I/O
  • Architettura del sistema di I/O
  • I/O su disco e politiche di scheduling delle richieste
  • Scheduling del disco nel sistema operativo Linux
  • RAID

Dispositivi di I/O

Classificazione in base all’uso:

  • Human readable:  utilizzati per interagire con l’utente (stampanti, video …);
  • Machine readable: utilizzati per interagire con i dispositivi hardware (dischi, nastri, sensori …);
  • Comunicazione: utilizzati per comunicare con dispositivi remoti (modem, schede di rete …).

Classificazione in base alla modalità di trasferimento:

  • a blocchi (dischi, nastri, …);
  • a caratteri (tastiera, mouse, modem, rete, stampante…);
  • speciali (timer).

Eterogeneità dei dispositivi di I/O


Supporto architetturale all’I/O

Bus e interfacce standard semplificano lo sviluppo del sistema di I/O, riducendo l’eterogeneità

Bus e interfacce standard semplificano lo sviluppo del sistema di I/O, riducendo l’eterogeneità


Tecniche di comincazione di I/O

I/O programmato

  • Il processo attende (busy-wait) per il completamento dell’operazione di I/O.

I/O Interrupt-driven

  • Viene invocato un comando di I/O;
  • il processore continua ad essere attivo in quanto il processo che ha invocato il comando viene sospeso;
  • il modulo I/O invia un interrupt quando ha terminato;

Direct Memory Access (DMA)

  • Il DMA è in grado di controllare lo scambio di blocchi di dati tra la memoria principale ed il dispositivo di I/O;
  • il processore viene interrotto solo dopo che l’intero blocco dei dati è stato trasferito.

Interrupt Handler

Gli interrupt sono nascosti nel cuore del sistema operativo.

Sono gestiti nel livello più basso del sistema operativo

Servono per segnalare via HW al SO il verificarsi di determinati eventi (es. un blocco di dati è pronto).

Il processo che richiede dei dati si sospende in attesa dell’evento “dati disponibili” segnalato da un interrupt.

DMA- Direct Memory Access

il S.O. invia al DMA:

  • richiesta di lettura o scrittura;
  • indirizzo del dispositivo di I/O;
  • locazione di partenza (IND) della memoria da cui leggere o scrivere;
  • numero di parole (CONT) da leggere o scrivere.

Completato il trasferimento, il DMA invia un interrupt alla CPU.


Configurazioni di DMA


Obbiettivi di progetto del sistema di I/O

Efficienza

La maggior parte dei dispositivi di I/O sono estrememante lenti se comparati alla memoria centrale.

Le operazioni di I/O non devono inficiare le prestazioni del sistema (CPU+RAM).

Rendere efficiente l’I/O significa anche rendere efficiente altri componenti del sistema operativo, ad esempio le attività di swapping.

Obbiettivi di progetto del sistema di I/O

Efficienza

  • minimizzare i tempi medi necessari per soddisfare una richiesta di servizio;
  • massimizzare il numero di richieste servite nell’unità di tempo (throughput);
  • massimizzare l’utilizzo delle periferiche e al contempo della CPU;
  • minimizzare la varianza fra i tempi entro cui le richieste sono soddisfatte, privilegiando imparzialità e predicibilità.

Tali parametri possono essere migliorati da un’oculata gestione del I/O da parte del SO, specialmente quando il grado di multiprogrammazione e il carico cui è sottoposto il sistema sono elevati.

Obbiettivi di progetto del sistema di I/O

Generalità

Offrire un’interfaccia unica ed uniforme per l’esecuzione delle operazioni di I/O.

Nascondendo la maggior parte dei dettagli implementativi ed architetturali. In tal modo i processi accedono a tutti i device in maniera uniforme (read, write, open, close, lock, unlock).

Architettura del sistema di I/O


Responsabilità del livello indipendente dai dispositivi

  • Naming
  • Buffering
  • Gestione dei guasti
  • Virtualizzazione delle periferiche
  • Allocazione dei dispositivi e spooling

I/O Buffering

Perché l’utilizzo del Buffering

I processi tipicamente devono attendere il completamento di un’operazione di I/O prima di procedere.

Durante un’operazione di I/O le pagine interessate devono essere “marchiate” come “non-swappable”.

I/O Buffering

Block-oriented

Le informazioni sono memorizzate in blocchi di dimensione fissa.

L’unità minima del trasferimento è il blocco.

Utilizzato per dischi e nastri.

Stream-oriented

Le informazioni sono trattate come un flusso di byte.

Utilizzati per terminals, printers, communication ports, mouse.

Buffer singolo

Il sistema operativo alloca un buffer in memoria principale per memorizzare le richieste di I/O.
Il sistema operativo utiliza questo buffer per effettuare l’operazione di I/O:

  • nelle read: i dati vengono trasferiti nel buffer di SO e successivamente copiati nel buffer del processo (eccezion fatta per le funzioni mmap);
  • nelle write: i dati vengono copiati dal buffer del processo a quello del sistema operativo. Il controllo viene subito rilasciato al processo ed il SO si occuperà di effettuare l’operazione.

Buffer singolo e doppio buffer


Considerazioni sul Buffering

Si consideri

  • T= tempo di trasfermiento di un blocco;
  • C= tempo di calcolo tra due richieste di input;
  • M = tempo di trasferimento di un blocco verso il buffer.

Il tempo di esecuzione del blocco è:

  • senza Buffer: T+C
  • con Buffer: max[T,C]+M, M<< T,C
    • se C<T: si mantiene la velocità del dispositivo a blocchi al massimo;
    • se C>T: il processo non deve attendere l’I/O.

Considerazioni sul Buffering

Il Buffering migliora l’efficienza delle operazioni di I/O

… ma

Nessuna quantità di buffer sarà sufficiente per tenere al passo un dispositivo di I/O con un processo.

Un processo potrebbe essere in attesa per l’operazione di I/O e potrebbe essere swappato (altra Operazione di I/O).

Se lo swapping del processo in attesa dell’operazione di I/O avviene sullo stesso disco impegnato nell’I/O, non ha senso accodare le scritture: il processo potrebbe diventare Ready non appena terminato l’l/O!

Device Drivers

Ogni periferica necessita di essere configurata prima e dopo l’utilizzo.

Il numero dei registri e la natura dei comandi varia radicalmente da dispositivo a dispositivo.

Tutto il codice che dipende dal dispositivo viene gestito dal driver del dispositivo.

Il compito di un driver è di accettare richieste astratte provenienti dal device-independent software e di controllare che queste siano eseguire!

Device Drivers

Una richiesta tipica è ad es: “leggi il blocco n”.

Il driver si attiva per leggere da disco.

Se il dispositivo è occupato a fare un’altra richiesta, quest’ultima viene messa in coda, senza che il processo che ha richiesto l’operazione rimanga in attesa.

Quando il dispositivo è pronto, il driver prende la richiesta e da astratta viene tradotta in richiesta concreta (testa del driver).

Dopo aver terminato l’operazione (interrupt) controlla che non ci siano stati errori e rende il risultato al device independet layer (coda del driver).

Esecuzione di un driver

Ma in quale contesto viene eseguito un driver?

Si presentano principalmente due alternative.

Driver appartenente al kernel del SO:

  • il driver può essere eseguito solamente effettuando una supervisor call;
  • il processo che necessita dell’operazione di I/O può restare bloccato o meno;
  • quando possibile, verrà eseguito il driver e infine si uscirà dal kernel tornando al processo.

Esecuzione di un driver

Il driver eseguito nel contesto di uno specifico processo (PROCESSO DRIVER).

un processo che vuole eseguire un’operazione di I/O deve inviare un messaggio, servendosi delle procedure messe a disposizione dal kernel.

Successivamente tale processo si metterà in attesa.

Il processo driver eseguirà allora nel proprio contesto la routine driver e infine spedirà un messaggio di risposta al processo sospeso.

Considerazioni sui driver

Ogni driver, a prescindere dell’ambiente in cui si trova (utente o kernel), ha sempre bisogno di una procedura del kernel mediante la quale esso possa ‘sospendersi’ una volta che sia iniziata l’operazione di I/O.

Nel modello in cui il processo driver è direttamente accessibile agli altri processi, essa viene implementata a mezzo di una WAIT su di un semaforo privato (ogni driver possiede il proprio semaforo privato, inizializzato a zero).

Considerazioni sui driver

Per uscire poi dalla WAIT, occorre trasformare l’interrupt hardware generato dalla periferica in un interrupt software che sia in grado di sbloccare il driver.

Come procedere?

Basta inserire una SIGNAL nel relativo ramo della ISR.

La ISR sarà fatta in modo che in ognuno dei suo rami sia contenuta la SIGNAL per risvegliare il corrispondente processo driver.

I/O API di Unix

Unix integra tutti i dispositivi all’interno del file system, sotto forma di file speciali.

Ad ogni dispositivo è associato un nome di file in una specifica cartella (solitamente la cartella/dev).

Es:

  • Stampante: /dev/lp
  • Terminale: /dev/tty
  • Scheda ethernet: /dev/eth0

I/O in Unix

Grazie alla file & device independence i dispositivi possono essere acceduti con la stessa interfaccia usata per i file.

  • open, read, write, close …

Le operazioni di I/O possono essere buffered e unbuffered.

  • In Linux viene implementata una page cache impiegata per il buffering di tutto il traffico tra disco e memoria.

I drivers in Unix

In UNIX non esiste il concetto di processo driver.

Le operazioni di ingresso uscita possono essere realizzate solo da parte del processo utente mediante chiamate al kernel.

La ISR possiede tanti rami quanti sono i driver, e in ognuno di essi è presente la coda del rispettivo driver, la quale viene eseguita.

Al termine dell’operazione richiesta si torna al processo utente.

Criticità dell’I/O sul disco

Tra tutte le attività di I/O, quella relativa ai dischi risulta essere la più critica per le prestazioni di un sistema operativo.

I dischi sono utilizzati per la memorizzazione dei file tramite il file system.

I dischi sono utilizzati per la memorizzazione della pagine swapped.

I dischi sono utilizzati per lo spooling delle periferiche.

I/O su disco

Perchè i dischi?

La Memoria ha una capacità ridotta e prestazioni elevate. I dischi hanno una capacità estesa e prestazioni ridotte.

La memoria è volatile. I dischi sono non volatili.

I dischi costano meno.


Anatomia di un disco


Parametri prestazionali

Tempo di seek: tempo di ricerca medio per posizionare la testina sulla traccia desiderata.

Ritardo di rotazione: tempo necessario affinché il disco effettui mezza rotazione.

Tempo di trasferimento: tempo necessario alla rotazione completa di una traccia moltiplicato per la frazione della traccia da dover percorrere.


Tempo di trasferimento totale

T=T_S+T_{rl}+T_{tr}

T_{rl}=\frac 1 {2r} \text{ Ritardo di rotazione}

T_{tr}=\frac b {rN}\text { Tempo di trasferimento}

r = #rotazioni al secondo
b = byte da trasferire
N = # byte di un traccia

Un esempio

Ipotesi:

Disco 15000rpm, settori da 512byte, 500 settori per traccia, Ts=4ms

Si vuole leggere un file che consiste di 2500 settori per un totale di circa 1,22 Mbytes. Si vuole calcolare il tempo di trasferimento totale nei due seguenti casi:

  • caso 1) Il file è memorizzato in maniera compatta, occupando 5 tracce adiacenti (organizzazione sequenziale);
  • caso 2) Il file è memorizzato in settori che sono distribuiti in maniera random su disco (organizzazione random).

Un esempio

Caso 1) Tempo di Lettura della prima traccia

T=T_s+T_{rl}+T_{tr}=4ms+\frac 1 {2\cdot 0.250}ms+4ms=10ms

dove 4ms è relativo a 500 settori (una traccia)

Le tracce rimanenti possono essere lette consecutivamente (senza seek time). Quindi:

T = 10 + 4 * 6 = 34 ms= 0.034 s

Caso 2) Tempo di lettura di una traccia

T=T_s+T_{rl}+T_{tr}=4ms+\frac 1 {2\cdot 0.250}ms +0.008ms=6.008ms

dove 0.008ms è relativo ad un settore

Tempo TOTALE

T = 2500* 6.008 ≈ 15s

Politiche di Scheduling del disco

Il tempo di seek può incidere notevolmente sulle prestazioni delle operazioni di I/O.

Il sistema operativo ha il compito di schedulare le richieste di accesso ad un disco.

Se le richieste fossero schedulate in maniera random si avrebbero prestaziani basse.

E’ importante dunque il criterio di schedulazione delle richieste di I/O. Vari obiettivi:

  • massimizzare l’utilizzo del disco;
  • massimizzare il numero di richieste servite per unità di tempo;
  • …interattività..etc..

Politiche di Scheduling del disco

2 categorie

Selezione secondo il richiedente:

  • FIFO, priorità, LIFO;

Selezione secondo l’elemento richiesto:

  • SSTF, SCAN, C-SCAN, N-step-SCAN, FSCAN.

Politiche di Scheduling del disco

First-in, first-out (FIFO)

Le richieste vengono servite in maniera sequenziale.

Politica “Fair” su tutti i processi.

Si comporta male (prestazioni basse) nelle situazione in cui si devono gestire un alto numero di richieste.


Politiche di Scheduling del disco

Priorità

Come FIFO, ma i processi richiedenti sono organizzati in code diverse a seconda della loro priorità.

Ad esempio si possono privilegiare i processi interattivi o quelli brevi.

Possibilità di starvation per i richiedenti a bassa priorità.

Politiche di Scheduling del disco

Last-in, first-out (LIFO)

Utilizzato soprattutto per i sistemi transazionali.

Viene servita la richiesta più recente al fine di minimizzare il movimento dei braccetti del disco.

Possibilità di starvation (soprattutto per quelli che richiedono di effettuare un’operazione su una posizione “lontana” da quella corrente).

Politiche di Scheduling del disco

Shortest Service Time First

Seleziona la richiesta di I/O che richiede il minimo movimento dei braccetti del disco dalla posizione corrente.

Seleziona sempre il minimo Seek time.


Politiche di Scheduling del disco

SCAN (denominato anche Algoritmo dell’ascensore)

I bracci del disco si muovono solo in una direzione, soddisfacendo tutte le richieste pendenti fintanto che non si raggiunge l’ultima traccia in quelle direzione.

La direzione viene poi invertita.


Politiche di Scheduling del disco

C-SCAN (Circular SCAN)

Applica lo scanning secondo un’unica direzione.

Quando viene raggiunta l’ultima traccia, i braccetti del disco portano la testina alla parte opposta del disco, ricominciando così lo scanning.


Politiche di Scheduling del disco

N-step-SCAN

  • Segmenta la coda di richieste al disco in più code di lunghezza N.
  • Le N code sono processate una alla volta usando SCAN.
  • Le nuove richieste vengono aggiunte ad un altra code mentre la coda corrente è processata.

FSCAN

  • Due code.
  • Una di queste è dedicata alle nuove richieste entranti.

Scheduling del disco in Linux: Linus Elevator

Kernel 2.4.
Variante di C-SCAN:

  • mantiene una coda delle richieste;
  • la coda è mantenuta ordinata secondo il blocco richiesto (operazioni di sort e merge).

Il throughput è molto alto (migliori prestazioni globali).

Ma si può verificare starvation.

Le operazioni di lettura sono penalizzate rispetto a quelle di scrittura (writes-starving-reads): le scritture sono bufferizzate, le letture sono sincrone.


Il deadline scheduler (Linux 2.6)

Versione modificata del Linus Elevator.

Le richieste vengono inserite anche in una delle 2 code FIFO (code di lettura e di scrittura).

Le richieste vengono prelevate dalla coda ordinata, fino a quando qualche richiesta non esaurisce il suo tempo di attesa (deadline expired).

Per favorire le operazioni di lettura, si imposta un timeout minore rispetto alle operazioni di scrittura.


Anticipatory scheduler

Anche se il problema del writes-starving-reads è attenuato, il Deadline Scheduler può soffrire di un basso throughput.

Quando scade la deadline di un gruppo di letture dipendenti che sono situate in un’altra zona del disco, l’algoritmo genera molte operazioni di seek.

L’algoritmo Anticipatorio, dopo aver servito una richiesta di lettura, attende senza effettuare altre operazioni.

Se durante l’attesa una nuova richiesta di lettura viene generata in prossimità della testina del disco, si avrà avuto un guadagno rispetto all’algoritmo Deadline.

Per evitare attese inutili, l’algoritmo attua delle euristiche per prevedere se sarà conveniente attendere oppure no.

1) Deadline

1) Deadline

2) Anticipatorio

2) Anticipatorio


Writes-starving-reads

Risultati sperimentali:

\begin{tabular}{c|c|c|}\toprule &Kernel 2.6.10&Kernel 2.4.26 \\tempo medio tra due letture&7.149 s&55.057 s \\ \bottomrule \end{tabular}

Il nuovo algoritmo di scheduling previene il fenomeno del writes-starving-reads, conseguendo dei tempi di servizio inferiori di quasi un ordine di grandezza.

RAID

Redundant Array of Independent Disks

Un insieme di dischi che viene visto dal sistema come un’unica unità logica.

Perché dischi ridondanti?

  • Aumentare il throughput (accesso in parallelo).
  • Aumentare l’affidabilità (ridondanza dei dati).

I dati sono distribuiti sui i dischi con varie modalità.

Viene in genere utilizzata una porzione dello spazio per applicare varie forme di ridondanza al fine di migliorare l’affidabilità.


RAID 0 (non-ridondante)

Alta frequenza di I/O requests.

Load Balancing.

Le prestazione dipendono anche dalla dimensione delle strip.

Dischi richiesti = N.


RAID 1 (mirroring)

Ridondanza dei dati con tecnica di mirroring.

Buon Livello di affidabilità (in genere migliore di RAID 2,3,4 o 5. Minore livello di affidabilità del RAID 6).

Buon Throughput:

  • possibilità di accesso parallelo;
  • possibilità di lettura contemporanea dello stesso insieme di dati da due dischi diversi.

Dischi richiesti = 2N, 3N , …


RAID 2 (codici di Hamming)

Ridondanza dei dati con codifica di Hamming.

Buon Livello di affidabilità (in genere migliore di RAID 3,4).

Alta capacità di trasferimento (dovuto anche alla possibilità di accesso parallelo).

Dischi richiesti = N+m.


RAID 3 (parità bit-interleaved)

Ridondanza dei dati con bit di parità.

Buon Livello di affidabilità (comparabile con RAID 4 o 5).

Alta capacità di trasferimento (dovuto anche alla possibilità di accesso parallelo).

Dischi richiesti = N+1.


RAID 4 (parità a livello di blocco)

Ridondanza dei dati con bit di parità per blocco.

Buon Livello di affidabilità (comparabile con RAID 2,3 o 5).

In lettura la capacità di trasferimento è simile al RAID 0, la scrittura è penalizzata (read-modify-write).

Dischi richiesti = N+1.


RAID 5 (parità a livello di blocco, distribuita tra i dischi)

Ridondanza dei dati con bit di parità per blocco distribuiti su più dischi.

Buon Livello di affidabilità (comparabile con RAID 2,3 o 4).

In lettura la capacità di trasferimento è simile al RAID 0, la scrittura è penalizzata.

Dischi richiesti = N+1.


RAID 6 (ridondanza duale)

Ridondanza dei dati con doppio bit di parità per blocco distribuiti su più dischi.

Tra le soluzione presentate RAID-6 è quella che ha il miglior livello di affidabilità.

In lettura la capacità di trasferimento è simile al RAID 0, la scrittura è penalizzata (è il peggiore di tutti per le prestazioni in scrittura).

Dischi richiesti = N+2.


I materiali di supporto della lezione

Dispensa didattica su I/0 e gestione dei dischi

P. Ancilotti, M. Boari, A. Ciampolini, G. Lipari, “Sistemi Operativi”, Mc-Graw-Hill (Cap.5)

W. Stallings “Operating Systems, Cap. 11

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion