[Sistemi Operativi] Gestione dell’ I/O

InputOutputLOGO

[Sistemi Operativi] Gestione dell’ I/O

0

In questo articolo: DMA, buffering, scheduling del disco e Cache.

I dispositivi di input/output possono essere raggruppati in tre categorie:

  • Leggibili all’ uomo: stampante, video, tastiere, mouse ecc
  • Leggibili alla macchina: dischi, drives, sensori, controllers ecc
  • Per comunicazioni con altri dispositivi: digital drives, modem ecc

Le tecniche di gestione dell’ I/O sono:

  1. I/O Programmato: Il processore manda un comando ad un modulo di I/O a nome di un processo; il processo intanto aspetta  il completaento dell’ operazione richiesta prima di continuare
  2. Interrupt Driven I/O: Anche quì il processore invia un comando ad un modulo I/O a nome di un processo e mentre la richiesta viene soddisfatta il processore continua ad eseguire istruzioni (dello stesso processo se può) finchè non riceve un’ interrupt da parte del modulo.
  3. Direct Memory Access (DMA): un modulo DMA controlla sostanzialmente lo scambio di dati tra memoria centrale e il modulo di I/O. Il processore invia una richiesta al modulo DMA per il trasferimento di un blocco di dati dal DMA e viene ricevuto un interrupt solo quando l’intero blocco viene trasferito. Quando il procssore deve leggere un blocco di dati, invia un comando al DMA con:
    • Tipo di richiesta: può essere di lettura o di scrittura,
    • Indirizzo del dispositivo di I/O coinvolto,
    • Indirizzo di partenza da cui cominciare a leggere o scrivere,
    • Numero di words che devono essere scritto o lette.

Direct Memory Access

Il DMA può essere un modulo che arriva ad essere molto complesso con una sua CPU ed una sua memoria locale, che permette quindi di eseguire un largo set di istruzioni riguardanti la memoria senza interpellare la cpu.

Il processore infatti, viene interpellato due volte: uno all’ inizio per la comunicazione della richiesta, ed una volta quando la richiesta è completata.

Il DMA trasferisce i dati una word per vola utilizzando la tecnica dell’ I/O Programmato ed esistono tre configurazioni possibili:

  • Collegare il DMA al bus di sistema insieme agli altri dispositivi di I/O: Il DMA è uno solo e si trova sul bus come tutti i moduli di I/O, il processore e la memoria. Ogni trasferimento richiede due cicli di bus: uno per richiedere il trasferimento, e uno per il trasferimento stesso.
  • Possiamo ridurre il numero di cicli di bus integrando il DMA ai moduli I/O in questo modo abbiamo il DMA collegato ad uno o più moduli di I/O senza occupare il bus di sistema.
  • Implementiamo un I/O bus a cui colleghiamo tutti i moduli di I/O e il DMA: quest’ultimo viene collegato poi al bus di sistema.

Obiettivi della gestione dell’ I/O

I due obiettivi che ci poniamo con la gestione dell’ I/O sono:

  • L’ efficienza: sappiamo bene che le richieste I/O sono le computazioni più lente del nostro computer. L’efficienza dei dispositivi di I/O è fondamentale
  • Generalità: vogliamo poter gestire tutta una varietà di dispositivi in maniera uniforme: sia da come un processo può acccedere ad un dispositivo, sia come il SO lo gestisce.

Struttura logica dell’ I/O

La struttura e’ gerarchica e varia a seconda del SO. In generale comunque i livelli sono:

  • Logical I/O: A questo livello i dispositivi vengono trattati come risorse logiche. Astraendo la rispettiva implementazione di ogni dispositivo, questo livello permette ai processi di eseguire operazioni con riferimenti “semplici” (es Read, Write, ecc).
  • Device I/O: Tecniche di buffering e miglioramento delle prestazioni, e traduzione in sequenze di istruzioni I/O.
  • Scheduling e controllo: Al livello più basso vengono gestiti lo scheduling del disco e le operazioni di controllo. Gestisce gli interrupt ed interagisce col modulo I/O (e quindi con l’hardware).

Per i dispositivi di comunicazione, la struttura è simile apparte il fatto che la Logica I/O potrebbe essere suddivisa in ulteriori livelli, come nel caso di TCP/IP.

Nei dispositivi di archiviazione secondari che supportano il File System, il modulo di Logical I/O è costituito da:

  • Directory Managment: I riferimenti simbolici vengono tradotti in identificatori che referenziano il file attraverso una Index Table. Gestisce anche le operazioni di base tipo Read, Write ecc.
  • File System: Questo livello tratta la struttura logica dei file e le operazioni eseguibili da ogni utente, ovvero gestisce anche i permessi.
  • Organizzazione Fisica: I riferimenti logici devono essere trasformati in riferimenti reali. Questo livello gestisce anche l’allocazione dello spazio ed i Buffers.

Buffer

Dopo diversi studi, si sono accorti che è molto conveniente ritardare le richieste di scrittura nei dispositivi I/O, ed anticipare quelle di lettura.

Un oggettino molto interessante, è il Buffer: sostanzialmente è un’area di memoria nello spazio del SO che viene suddivisa in sotto buffer ed assegnati ai processi che effettuano richieste I/O. I dati caricati o da caricare vengono inseriti dal SO in questo buffer, ed il processo penserà a prenderselo.

Esistono tre tipi di buffer:

  • Il buffer singolo: Viene chiamato anche Reading Ahead, e consiste in quello che abbiamo detto poco fà. Un buffer dove il SO carica i dati, ed il processo che se li trasferisce da lì.
  • Doppio buffer: E’ simile ad avere due braccia: mentre si “passa” ad un processo i dati richiesti da un buffer, nell’altro si carica il blocco successivo. Se il tempo di caricamento nei buffer è minore del tempo di consumo dei dati da parte del processo c’è comunque un rallentamento.
  • Buffer circolare: Vengono impiegati una serie di buffer per processo.

Scheduling del disco

E’ noto ormai da tempo che la velocità di elaborazione dei processori, è di gran lunga superiore alla velocità di trasferimento dei dati dal disco fisso. Questo perchè gli hard disk hanno una testina che deve fisicamente spostarsi da un punto all’altro e sprecando quindi un sacco di tempo in questo spostamento.

Il tempo impiegato dalla testina per spostarsi sulla traccia desiderata, è chiamato Seek Time. Per ridurre questo tempo di accesso ai dati, sia di scrittura che di lettura, si utilizzano tecniche di Scheduling del disco per cercare di migliorare le performance dell’ hard disk.

Come Upper bound c’è il Random Scheduling: ovvero presa una coda di processi che devono leggere/scrivere sul disco, si selezionano le richieste a caso. Ovviamente il Random Scheduling è terribilmente inefficiente: ed è per questo che lo usiamo come Upper Bound, ovvero come punto di riferimento e per cercare di “fare meglio”.

Vediamo quindi alcuni tipi di scheduling del disco:

  • Scheduling con la Coda FIFO (First In First Out): Mano a mano che arrivano le richieste, vengono soddisfatte. Anche se è una strategia paritaria (i processi che richiedono prima dati vengono serviti prima) la sua efficienza è simile a quella del Random Scheduling.
  • Scheduling con una Pila LIFO (Last In First Out): Sembra strano ma grazie al principio di località, concedere la lettura del disco agli ultimi arrivati potrebbe essere una buona soluzione, in quanto grazie al principio di località la testina dovrebbe compiere pochi spostamenti. Se però deve gestire processi molto lunghi, i primi potrebbero subire starvation (morire di fame :().
  • Scheduling con Priorità (PRI): Vengono eseguiti prima i jobs più piccoli in modo da avere un buon Response Time. Jobs più lunghi potrebbero subire Starvation, una buona pratica sarebbe spezzare le richieste in Jobs più piccoli.
  • Shortest Service Time First( SSTF): Ok, finora abbiamo visto tre sistemi non molto efficienti. Se però la posizione della testina è nota allo scheduler, quest’ultimo può sfruttare quest’informazione aggiuntiva per migliorare la sua efficienza. Proprio su questo si basa lo SSTF: cerca i jobs che richiedono il minore spostamento e li esegue prima. Questo però non vuol dire sempre maggiore efficienza.
  • Scan: In questo caso la testina si muove in una direzione, una volta arrivata al bordo del disco ricomincia da li e torna indietro servendo tutte le richieste che incontra. Questo metodo favorisce i processi che eseguono richieste ai bordi del disco.
  • C-Scan (Circular-Scan): Per rimediare al fatto che vengono favoriti i processi ai bordi, il C-Scan una volta arrivato ad un bordo ricomincia dall’altro e si muove sempre in una direzione.
  • N-Step-Scan: Divide la coda in N code che processa usando la politica Scan
  • F-Scan: Usa due sottocode, e mentre processa le richieste di una coda quelle nuove vengono inserite nell’ altra in modo da dare parità.

Cache del disco

Di questo argomento volevo scrivere un articolo a parte, diviso in due (e solo la prima parte per ora è pronta :C) per questo ne parlerò brevemente anche quì.

La cache è un Buffer in memoria centrale che mantiene la copia di alcuni settori contenuti nel disco. In questo modo, se viene richiesto un dato dalla memoria secondaria ma che è cashato in memoria centrale, si può o trasferire il blocco o mandare al processo un puntatore alla disk cache.

Quando la cache è piena, alcuni dati devono essere eliminati e sostituiti con i nuovi. Per farlo le due politiche più famose sono: 

  • Least Recently Used (LRU): Sfrutta il principio di località, dicendo che i dati richiesti da poco tempo verranno ri-richiesti a breve. Quindi viene sovrascritto il blocco che si trova da più tempo nella cache. Quindi diciamo che realizza una coda.
  • Least Frequently Used (LFU): Viene sostituito il blocco che viene acceduto meno di frequente. Le prestazioni non sono esaltanti, un incremento significativo che lo rende migliore anche di LRU è quello di avere lo Stack diviso in 3 parti (NEW SECTION, MIDDLE SECTION, OLD SECTION).Quando c’è una disk Hit il blocco interessato viene spostato in testa alla pila. Se si trovava già in NEW SECTION non sucede nulla altrimenti incrementa il conteggio di accesso. Quando c’è un MISS (e bisogna sostituire un blocco) viene scelto quello con contatore minore nella OLD SECTION. La Middle section è un’area fra la NEW e la OLD che permette ai dati di avere più “chance” di essere riacceduti. Finchè si trovano nella MIDDLE sono “al sicuro” :).

About the Author

Federico PonziStudente, Webmaster ed appassionato di tutto ciò che è informatico con una spruzzata di scienza.View all posts by Federico Ponzi

Leave a Reply