La gestione dell’I/O e del disco

Indice:

• Introduzione
• Come comunicare con le periferiche
• Cenni storici
• Il DMA
• Configurazioni del DMA
• Progettazione delle funzioni di I/O (Generalità ed Efficenza)
• Bufferizzazione dei dati
• Tipi di buffer. Singolo e Doppio.
• Schedulazione del disco
• Ritardi del disco
• Tipi di scheduling (FCFS, Priorità, LIFO, SSTF , SCAN, FSCAN)
• Cache del disco (a due e tre sezioni)

INTRODUZIONE
Esistono diverse tipologie di dispositivi con cui interagisce un sistema operativo. Ad esempo ci sono dispositivi leggibili dall'uomo (monitor, stampante, mouse), altri leggibili dalla macchina (dischi, controller, periferiche di archiviazione di massa esterne) e altri ancora che riguardano il supporto di rete (modem, schede di rete).

Il modo con cui una CPU interagisce con questi differenti dispositivi vari a seconda della loro velocità (ad esempio un nastro o un disco è molto più lento di una ram). Prendiamo ad esempo un dattilografo che scrive a una frequenza di 100msec; sebbene sia un tempo molto breve rispetto alla maggior parte dell'umanità è quanto mai ovvio che risulti un tempo infinito per una macchina che lavora in termini di nanosecondi: è quindi fondamentale che la CPU si rapporti in maniera diversa a seconda del dispositivo in modo tale che la velocità del dispositivo più lento non costringa il processore ad inutili attese.
Esistono inolte altre discriminanti con cui raggruppare questi dispositivi, ovvero:

• complessità di controllo
• unità di trasferimento (blocco)
• rappresentazione dei dati (codifiche)
• condizioni di errore e relativo rilevamento

COME COMUNICARE CON LE PERIFERICHE
Esistono 3 tecniche per comunicare con le periferiche:

• I/O Programmato la CPU si mette in attesa che i dati vengano prodotti dal dispositivo
• I/O Interrupt-Driven Il processore impartisce un comando alla periferica e continua poi con altre istruzioni. Verrà bloccato tramite interrupt dalla periferica quando questa avrà prodotto il lavoro richiesto.
• DMA Ci si affida al dispositivo DMA che controlla lo scambio di dati tra memoria e dispositivi di I/O (la CPU è completamente esterna dal trasferimento dati - può fare altro -, e il device va a scrivere o leggere direttamente all'interno della memoria di lavoro a lui riservata); quando l'I/O è completo il DMA manderà un interrupt al processore.

CENNI STORICI
Nei primi computer il processore si occupava direttamente di comunicare con la periferica, attendendo di volta in volta il termine delle operazioni chieste (una alla volta); il problema principale è che sebbene la CPU sia molto veloce (perfino le prime) questa viene pesantemente limitata dal dover aspettare i lunghissimi tempi della CPU.

Il passo successivo fu quindi quello di disaccoppiare il processore dalla periferica, tramite quello che fu chiamato Programmed I/O e Interrupt. In questi casi il processore manda la richiesta alla CPU e continua in altri compiti. Quando la periferica termina il proprio compito manderà un interrupt alla CPU segnalando il lavoro pronto.

Nei computer moderni viene invece utilizzato il cosidetto DMA Controller, ovvero un sistema ancora più sofsticato che attraverso un controller di tipo hardware dedicato, permette di liberare il processore dalla necessità di comunicare con i device esterni.

IL DMA
Il DMA (Direct Memory Access, «accesso diretto alla memoria») come abbiamo già detto, permette ad alcuni sottosistemi hardware di un computer di accedere alla memoria di sistema in lettura e/o scrittura indipendentemente dalla CPU.

Il DMA è un componente essenziale di tutti i computer moderni, in quanto permette a periferiche che lavorano a velocità diverse di comunicare senza assoggettare la CPU a un enorme carico di interrupt.

Essenzialmente, in un trasferimento DMA un blocco di memoria viene copiato da una periferica a un'altra. La CPU si limita a dare avvio al trasferimento, mentre il trasferimento vero e proprio è svolto dal controller DMA. Un caso tipico è lo spostamento di un blocco di memoria da unità di memoria esterna alla memoria principale. Se questa operazione, come avviene grazie al DMA, non blocca il processore, esso può continuare a svolgere altre operazioni.

Le interruzioni relative alla richiesta di bus vengono gestite ad ogni ciclo processore, mentre le interruzioni dei dispositive, compresa quella del DMA, vengono gestite tra una interruzione macchina e l'altra.

Esistono tre tipi di configurazioni per il DMA:

• Bus singolo - DMA separato: Il DMA può essere direttamente integrato nel bus di sistema, nel quale si inseriscono anche le periferiche
  
• Bus singolo - DMA e I/O integrati: Oppure può essere direttamente collegato a più periferiche  di I/O
  
• Bus di I/O: Altrimenti, il DMA può essere collegato a un bus dedicato per l'I/O, a cui vengono  collegati i dispositivi.
  

PROGETTAZIONE DELLE FUNZIONI DI I/O
Per progettare le funzionalità di un sistema di Input/Output non bisogna tenere solo conto della tecnica giusta tra il DMA,I/O Programmato o l'Interrupt. Ci sono infatti altre due problematiche:

• Generalità: Ossia cercare di gestire l'I/O in modo totalmente generico rispetto all'hardware, in particolare è necessario astrarre i metodi di scrittura e lettura dal dispositivo reale su cui si eseguono le operazioni. Non importa infatti se esso sia mouse, tastiera o stampante. Devono essere nascosti i dettagli delle periferiche da interfacce standard.
• Efficenza: E' necessario tenere conto anche dell'efficenza; in particolare è necessario prevedere dei buffer nei dispositivi in modo da bilanciare le differenti velocità tra i due dispositivi di comunicazione; è necessario anche prevedere algoritmi efficenti di I/O e swapping (lo swapping tende ad aumentare il throughput tramite aumento di multiprogrammazione, ma necessita di algoritmi molto efficenti).

Possiamo quindi rappresentare un modello di comunicazione tra la CPU e i dispositivi così:

BUFFERIZZAZIONE DEI DATI
Esistono due possibilità con cui far viaggiare i dati tra i dispositivi e il processo che li richiede. Il primo, più semplice e diretto è quello che dal dispositivo di I/O si va direttamente al buffer dell'utente; ciò significa che il processo, che sta aspettando l'informazione, non può essere swappabile (ossia messo nella memoria virtuale), perchè si trova in stato di attesa attiva (busy waiting) e non riceverà mai alcun dato dall'I/O.

D'altro canto tenere attivo il processo in memoria porta ad un sottoutilizzo della CPU, dove il processo rimane in memoria senza fare altro che aspettare dati e di fatto far si che tutti gli algoritmi di gestione della memoria già visti siano inutili.
Tutto questo senza contare possibili problemi di deadlock, nel caso in cui l'area di memoria destinata all'I/O sia swappabile: il processo rimane bloccato in attesa di I/O, ma l'I/O è bloccato in attesa che il processo sia di nuovo messo in memoria.

Si utilizza quindi un buffer intermedio dei messaggi gestito all'interno del sistema operativo. L'I/O quindi viene bufferizzato all'interno di un buffer e il trasferimento dei dati può essere di due tipi:

• trasferimento a blocchi: in cui vie è la bufferizzazione e conseguente trasferimento di blocchi di bytes verso l'OS.
• trasferimento stream (flusso): in cui c'è la bufferizzazione dei singoli bytes.

TIPI DI BUFFER: SINGOLO, DOPPIO E CIRCOLARE
Ci possono essere due tip di buffer, uno singolo e uno doppio.

• Buffer singolo: E' la situazione più semplice, si ha quando si inserisce un buffer intermedio nel sistema operativo. Il dispositivo esegue l'input, e una volta riempito il buffer, esso può essere copiato nella memoria.Questo buffer disaccoppia il dispositivo dal processo; questo disaccoppiamento porta a una parallelzzazione dell'I/O e se il trasferimento è stream potrebbero esserci sottoutilizzi della CPU e grande overhead generato dal sistema operativo nella gestione del buffer (a questo punto sarebbe conveniente portare tutto in memoria).La latenza sarà di max[C,T]+M (C= tempo di computazione tra due richieste, T tempo per l'input di un blocco e M tempo di copia nel buffer).

  

• Buffer doppio: Si mettono più buffer, dipendentemente dalla periferica e dalla sua velocità. In questo modo si aumenta l'effetto di pipeline. Nel mentre un buffer viene riempito dalla periferica, il sistema operativo sta spostando il contenuto del buffer già riempito nella memoria in modo da diminuire considerevolmente la latenza (che sarà max[C,T]).Alcune note riguardo le prestazioni tra C e T. Se C < T significa che il tempo in cui il processo richiede un nuovo blocco è minore rispetto al tempo che la periferica impiega per trasferirlo. Ciò permette di mandare un device a piena velocità tenendola sotto pressione.

  Se C > T significa che il tempo di computazione per richiede un altro blocco è maggiore di quanto il dispositivo riesce a produrre: questo ha effetto di non far mai attende un processo n I/O.

  

  
  

• Buffer circolare: Il buffer doppio può essere esteso a uno di tipo circolare. In questo caso aumenta la memoria ma se si ha a che fare con una periferica molto veloce e il processo è lento, il buffer deve avere comunque un limite. Questo di solito avviene nei buffer dei socket, dove la velocità con cui arrivano i pacchetti è talmente superiore rispetto alla veloctà con cui il sistema operativo può trattargli che il buffer si riempie. In questo caso si iniziano a perdere pacchetti (succede nelle connessioni UDP in cui il protocollo non può perdere tempo a richiedere le parti mancanti perchè rallenterebbero la connessione, ad esempio durante streaming audio o video).

SCHEDULAZIONE DEL DISCO
Una volta compresa quale tipo di bufferizzazione si rende necessaria, sarà il costruttore della periferica a determinare il buffer necessario al dispositivo.
E' necessario quindi inserire un controller che riceve le richieste in modo concorrente dal sistema operativo, dai processi, e cerchi quindi di velocizzare il più possibile le operazioni sulla periferica tramite diverse algoritmi.

Nel caso di un disco ci dovrà essere un algoritmo che scheduli le letture dal disco in modo tale da migliorarne le performance, ovvero di rendere minimi gli spostamenti della testina sul disco. C'è anche la necessità di costruire una sorta di cache che può rispondere direttamente (e quindi senza che la meccanica sia attivata) a richieste frequenti.

RITARDI DEL DISCO
Quindi nel caso di un disco abbiamo un algoritmo di scheduling e uno di cache.
La schedulazione deriva dal fatto che più processi possono richiedere dati da un singolo disco.
La cache è importante perchè vi sono una serie di ritardi di accesso al disco. I più importanti sono il seek time e il ritardo di rotazione, oltre ai ritardi precedenti che dipendono dalle richieste dei processi (attesa di turno/di canale).

Il ritardo di rotazione è un ritardo costante e dipende dalla velocità di rotazione dei cerchi concentrici su cui opera la testina (è mediamente la metà del tempo di rotazione).
Il ritardo maggiore è quello dovuto al movimento della testina, che è un movimento meccanico ed è fatto nell'ordine dei microsecondi (quando generalmente in ambito elettronico i tempi sono in millisecondi).
E' quindi ovvia la necessità di schedulizzazione in modo da minimizzare gli spostamenti e le richieste.

TIPI DI SCHEDULING
Esistono sei tipi di scheduling del disco:

• Scheduling FCFS (First Come-First Served):  E' lo scheduling più semplice in cui le richieste vengono servite nel loro ordine di arrivo. In questa schedulazione non c'è alcun vantaggio per minimizzare lo spostamento delle testine, le richieste vengono servite principalmente in ordine di richiesta e niente di più. (Nessuna minimizzazione seek time, No starvation tutte servite).
• Schedulazione su priorità: Per ridurre il seektime, si può pensare di dare una priorità alle richieste del disco. In questo modo però ci potrebbero essere delle richieste mai servite perchè hanno priorità bassa che viene superata sempre da altri.
  
  
• Schedulazione LIFO (last in, first out): (venne implementato principalmente negli anni 70). Quando si richiede qualcosa al nastro, al richiesta successiva era con molta probabilità il blocco successivo, quindi l'idea è quella di minimizzare il seektime in caso di accessi sequenziali (perchè l'allocazione dei dati non era casuale ma contigua) servendo le richieste in ordine inverso da quello di arrivo. Ogni tanto però era necessario spostare la testina (o il nastro in maniera inversa).
• Schedulazione SSTF (Shortest Service Time First): In questo caso si da la priorità alle richieste che permettono di volta in volta di fare il minor spostamento. Anche questa come quella FCFS può produrre starvation perchè potrebbero arrivare in continuazione richieste con spostamenti minimi senza che quella a spostamento più lungo venga servita.
• Scheduling SCAN: L'algoritmo SCAN non sfrutta la vicinanza delle tracce; per come è strutturato il disco è conveniente leggere la testina verso le tracce più alte e quando sono finite le richieste tornare indietro piuttosto che invertire sempre la testina. Questo cambiamento di direzione infatti porta sotto stress il disco e oltre a rischiare rotture viene impiegato più tempo.Quindi lo scheduling di questo tipo avviene in una data direzione fino al termine delle tracce anche se fosse più vicina una traccia che prevede inversione. (Una variante C-SCAN utilizza la scansione in una sola direzione). (Può produrre starvation)
• Scheduling FSCAN: SCAN e C-SCAN sono basati su priorità che inevitabilmente porta a starvation. LFSCAN risolve presentando due code distinte.
  In una coda ci sono gli elementi che occorre servire, ed essi vengono schedulati secondo l'algoritmo SCAN (o quello più opportuno).
  Le altre richieste in arrivo vengono inserite in una seconda coda, che non viene letta finché non sono state servite tutte le richeste nella prima coda.

CACHE DEL DISCO
Gestire la cache vuol dire risparmiare tempo mantenendo una lista dei dati che il disco crede vengano letti più frequentemente. Utilizzando la cache di risparmia quindi il tempo di spostamento meccanico e la lettura.

Si può quindi diminuire la latenza e il carico sul disco gestendo la sostituzione dei blocchi:

• Least-Recently-Used viene mantenuta una lista di gestione a stack, e viene  eliminato il blocco che è stato richiesto più lontano nel tempo.
• Least-Frequently-Used si mantiene un contatore di riferimenti al blocco indicante  il numero di accessi da quando è stato caricato.

Entrambi questi tipi di strategia hanno problemi sulla variazione di località. E' un problema diverso dal memory management. Qui non c'è un solo processo che fa richieste, ma sono una serie  di processi. La località esiste sempre, ma è molto più debole. Occorre creare una struttura a buffer  che riesca a far fronte a questa "località indebolita".

• Buffer cache a due sezioni: La soluzione è quella di dividere in due il buffer. C'è una sezione nuova dove ci saranno i blocchi che più recentemente sono stat visitati e un'altra vecchia dove questi blocchi passano man mano che vengono sostituiti.Prima di andare via il blocco deve essere tra quelli meno richiesti anche nella sezione vecchia. C'è un buffer a due livelli , questo perchè un processo può fare una richiesta e poi sfruttare il principio di località, ma una sua successiva richiesta potrebbe arrivare tempo dopo; il blocco non deve essere quindi tolto via subito.Ogni blocco ha quindi un contatore che gli permette di stare, in base alle richiesta, in una o nell'altra e di entrare dall'esterno.

  
  
  

• Buffer cache a tre sezioni: In questo modo, molto usato, ci sono tre sezioni, con una sezione intermedia dove possono passare i blocchi verso quella vecchia o quella nuova.

3-03-2007

[tags]DMA, Configurazioni del DMA, Progettazione Funzioni I/O,Bufferizzazione dei dati, Buffer Singolo, Buffer Doppio,Schedulazione del disco,Ritardi del disco,Scheduling FCFS,Scheduling a Priorità,Scheduling LIFO,Scheduling SSTF ,Scheduling SCAN,Scheduling FSCAN), Cache del disco due sezioni,Cache del disco tre sezioni[/tags]