Sistemi di I-O e memory-mapped I-O

La gestione dell'I/O (input e output) è una parte importante del progetto e del funzionamento di un sistema operativo: i dispositivi sono tantissimi e diversissimi, e ne nascono sempre di nuovi. Il sistema operativo li nasconde dietro driver e un'interfaccia uniforme. Il lato hardware delle interfacce (strobing, handshaking, interrupt, DMA) è trattato anche in Moduli di input-output e input-output programmatoPerché servono i moduli di I/O; funzioni del modulo (controllo, comunicazione, buffer, errori) e registri di stato, controllo e dati; I/O mappato in memoria e isolato con esempi; I/O programmato con attesa attiva e suo costo; confronto delle tre tecniche.Moduli di input-output e input-output programmato →, InterruptClassi di interruzioni; I/O guidato da interrupt; sequenza hardware e software di gestione con salvataggio del contesto sullo stack; identificazione della sorgente (linee multiple, polling, daisy chain, vettore); priorità e interruzioni annidate; eccezioni e modi in ARM.Interrupt →, Accesso diretto alla memoria (DMA)Modulo DMA e informazioni che riceve dalla CPU; trasferimento a blocco con un solo interrupt finale; furto di cicli e modalità a burst, punti in cui la CPU può essere sospesa; configurazioni del bus; canali e processori di I/O; confronto quantitativo con l'I/O a interrupt.Accesso diretto alla memoria (DMA) →, Bus e interconnessioneBus di sistema diviso in linee dati, indirizzi e controllo; ampiezza del bus e spazio di indirizzamento; arbitraggio; bus singolo e gerarchie di bus multipli; temporizzazione sincrona e asincrona; interconnessioni punto a punto.Bus e interconnessione → e, per i microcontrollori, in Sottosistema di I-O - polling, interruzioni e DMALe periferiche si collegano al bus con una interfaccia che ha registri di dati (DREG), controllo (CREG) e stato (SREG); nei µC e DSP sono mappati in memoria (si leggono e scrivono come locazioni). Poiché le periferiche sono asincrone e lente, la sincronizzazione avviene per polling (inefficiente), per interruzioni (la più usata) o per DMA (costoso, per grandi quantità di dati). Una interruzione: completa l'istruzione, salva il contesto (PC e registro di stato, spesso altro), esegue la ISR, ripristina. Le sorgenti si distinguono con ISR di stato, interruzioni vettorizzate o daisy-chaincollegamento delle periferiche in catena, in cui il segnale di riconoscimento passa dall'una all'altra; le NMI non sono mascherabili.Sottosistema di I-O - polling, interruzioni e DMA →.

Caratteristiche dei dispositivi

I dispositivi differiscono in molti modi:

• a flusso di caratteri o a blocchi;
• ad accesso sequenziale o casuale;
• sincroni o asincroni;
• condivisibili o dedicati;
• di sola lettura, sola scrittura o lettura e scrittura;
• velocità di funzionamento.

Le classi principali:

I dispositivi di rete sono abbastanza diversi da avere una propria interfaccia software: Linux, UNIX e Windows hanno l'interfaccia delle socket, che separa il protocollo di rete dall'operazione di rete e serve anche per la comunicazione tra processi (vedi System call POSIX, file descriptor e API delle socketLe system call sono le funzioni con cui un programma in user space chiede servizi al kernel (open, read, write, close, fork, pipe, dup2, socket, bind, listen, accept, connect); restituiscono -1 e impostano errno in caso di errore; un file descriptor e' un intero che indicizza la tabella dei file aperti del processo (0 stdin, 1 stdout, 2 stderr) e vale per file, pipe e socket; read e write possono trasferire MENO byte del richiesto (e sui socket TCP non c'e' nessun confine fra i messaggi), quindi servono cicli write_all e read_exact; l'API delle socket crea un punto finale di comunicazione (socket), lo lega a indirizzo e porta (bind), lo rende passivo (listen), accetta connessioni (accept) o si connette (connect); getaddrinfo traduce nomi e porte in indirizzi (IPv4 e IPv6); UDP usa sendto e recvfrom e conserva i confini dei datagrammi, TCP e' uno stream affidabile.System call POSIX, file descriptor e API delle socket →). Gli orologi e timer forniscono ora, tempo trascorso e interruzioni periodiche; i PC moderni hanno un timer di eventi ad alta precisione; la deriva dell'orologio si corregge con il protocollo di rete NTP.

Le particolarità sono nascoste dai driver. Per agire direttamente su un dispositivo c'è una "porta di servizio": in UNIX la chiamata ioctl() può inviare bit arbitrari ai registri di controllo e di dato.

Hardware di I/O

I dispositivi si collegano al calcolatore tramite:

• porta (port): punto di connessione, per esempio una porta seriale;
• bus: gruppo di fili che collega più dispositivi (PCI e PCIe nei PC e nei server; un bus di espansione per quelli lenti);
• controller (host adapter): l'elettronica che pilota porta, bus e dispositivo. Può essere integrato nel dispositivo o su una scheda separata, con processore, microcodice, memoria privata, controller del bus.

Registri e indirizzi

I dispositivi si comandano con istruzioni di I/O. Hanno di solito dei registri nei quali il driver scrive comandi, indirizzi e dati da scrivere, e da cui legge dati:

• data-in, letto dalla CPU per ricevere dati;
• data-out, scritto dalla CPU per inviare dati;
• status, con bit di stato (occupato, errore, dato pronto);
• control, scritto dalla CPU per avviare un comando o cambiare modo.

I registri di dato possono avere buffer FIFO. I dispositivi hanno indirizzi usati in due modi:

• istruzioni di I/O dirette (spazio di indirizzi di I/O separato, istruzioni come in e out);
• memory-mapped I/O: i registri del dispositivo sono mappati nello spazio di indirizzi (anche virtuale) e si leggono e scrivono con le normali istruzioni di accesso alla memoria. È utile soprattutto con grandi spazi di indirizzi (la scheda grafica).

Polling

Per ogni byte di I/O:

1. l'host legge il bit busy del registro di stato finché vale 0;
2. l'host imposta il bit di lettura o scrittura nel registro di comando (se scrive, copia il dato in data-out);
3. l'host imposta il bit command-ready;
4. il controller imposta busy ed esegue il trasferimento;
5. a trasferimento finito il controller azzera busy, il bit di errore e command-ready.

Il polling (busy-wait) usa poche istruzioni, quindi è ragionevole con dispositivi veloci, inefficiente con dispositivi lenti perché la CPU gira a vuoto.

Interruzioni

Se il dispositivo è spesso occupato o i dati arrivano di rado, il polling spreca CPU. Con le interruzioni il dispositivo attiva la linea di richiesta di interruzione (IRQ); la CPU la controlla dopo ogni istruzione e, se è attiva, salta al gestore dell'interruzione (interrupt handler). Dettagli:

• all'inizio e alla fine servono un cambio di contesto (salvataggio e ripristino dello stato);
• il servizio avviene secondo la priorità;
• ci sono interruzioni mascherabili e non mascherabili (queste non si possono disabilitare);
• il vettore delle interruzioni (interrupt vector) è una tabella con gli indirizzi dei gestori; se più dispositivi hanno lo stesso numero si usa il concatenamento (chaining).

Lo stesso meccanismo serve per i page fault e le eccezioni (errori hardware) e per le system call, eseguite con un trap (interruzione software) che fa partire il kernel. Vedi InterruptClassi di interruzioni; I/O guidato da interrupt; sequenza hardware e software di gestione con salvataggio del contesto sullo stack; identificazione della sorgente (linee multiple, polling, daisy chain, vettore); priorità e interruzioni annidate; eccezioni e modi in ARM.Interrupt → per il funzionamento del ciclo di fetch e Memoria virtuale - paginazione su richiesta e sostituzione delle pagineLa memoria virtuale separa la memoria logica da quella fisica: basta che alcune pagine siano in RAM; con la paginazione su richiesta (demand paging) una pagina si carica solo al primo riferimento, e un riferimento a una pagina non residente (bit di validità = i) genera un page fault gestito dal sistema operativo in sei passi; EAT = (1 - p) * accesso + p * servizio del fault, con p minuscolo; copy-on-write rende economica la fork; se non ci sono frame liberi si sceglie una vittima con FIFO (anomalia di Belady), OPT (ottimo, irrealizzabile), LRU (algoritmo a stack), second chance (bit di riferimento, orologio) o la versione con bit di modifica; i frame si assegnano in modo uguale o proporzionale, con sostituzione globale o locale; se un processo non ha abbastanza frame va in thrashing; il modello del working set e la frequenza dei page fault lo evitano; considerazioni su prepaging, dimensione della pagina, TLB reach e struttura dei programmi; memoria del kernel con buddy system e slab.Memoria virtuale - paginazione su richiesta e sostituzione delle pagine → per i fault.

La gestione delle interruzioni è critica: anche un sistema con un solo utente ne gestisce centinaia al secondo, i server centinaia di migliaia. Un desktop Linux inattivo può generarne circa 10 000 in 10 secondi (si vede con il comando dstat).

DMA (direct memory access)

Trasferire grandi quantità di dati un byte alla volta (I/O programmato) sovraccarica la CPU. Il DMA usa un controller DMA che trasferisce i dati direttamente tra il dispositivo e la memoria senza passare per la CPU.

1. Il sistema operativo scrive in memoria un blocco di comando DMA con indirizzo di origine e destinazione, modo (lettura o scrittura) e numero di byte.
2. Scrive l'indirizzo del blocco nel controller DMA.
3. Il controller DMA "ruba" il bus alla CPU (cycle stealing) e fa il trasferimento.
4. Alla fine invia un'interruzione per segnalare il completamento.

Esempio di scelta. Tastiera: pochi byte, rari: interruzioni (basta un'interruzione a ogni tasto). Scheda di rete e disco: blocchi grandi: DMA. Un contatore veloce che si aggiorna ogni pochi cicli: polling.

Interfaccia per le applicazioni

Le system call di I/O incapsulano il comportamento dei dispositivi in poche classi generiche. Il livello dei driver nasconde le differenze tra i controller al resto del kernel: i dispositivi che parlano protocolli già noti (per esempio USB) non richiedono altro lavoro. Ogni sistema operativo ha le proprie strutture e il proprio framework di driver.

In UNIX e Linux i dispositivi sono file speciali sotto /dev (ls -l /dev); per esempio i byte inviati dal mouse si stampano con sudo hd /dev/input/mouse0. Così si usano open, read, write anche sui dispositivi (vedi System call POSIX, file descriptor e API delle socketLe system call sono le funzioni con cui un programma in user space chiede servizi al kernel (open, read, write, close, fork, pipe, dup2, socket, bind, listen, accept, connect); restituiscono -1 e impostano errno in caso di errore; un file descriptor e' un intero che indicizza la tabella dei file aperti del processo (0 stdin, 1 stdout, 2 stderr) e vale per file, pipe e socket; read e write possono trasferire MENO byte del richiesto (e sui socket TCP non c'e' nessun confine fra i messaggi), quindi servono cicli write_all e read_exact; l'API delle socket crea un punto finale di comunicazione (socket), lo lega a indirizzo e porta (bind), lo rende passivo (listen), accetta connessioni (accept) o si connette (connect); getaddrinfo traduce nomi e porte in indirizzi (IPv4 e IPv6); UDP usa sendto e recvfrom e conserva i confini dei datagrammi, TCP e' uno stream affidabile.System call POSIX, file descriptor e API delle socket →).

Dall'I/O all'hardware

Leggere un file dal disco richiede: determinare il dispositivo che contiene il file; tradurre il nome nella rappresentazione del dispositivo; leggere fisicamente i dati dal disco nel buffer; rendere i dati disponibili al processo; restituirgli il controllo. Il percorso passa per i livelli del File system - interfaccia, directory e implementazioneUn file è uno spazio di indirizzi logici contigui con attributi (nome, identificatore, tipo, posizione, dimensione, protezione, date) e operazioni (create, read, write, seek, delete, truncate, open, close); il sistema tiene una tabella dei file aperti di sistema e una per processo; l'accesso è sequenziale o diretto; le directory si organizzano a livello singolo, a due livelli, ad albero, a grafo aciclico (hard link e link simbolici) o a grafo generale; i permessi UNIX rwx per proprietario, gruppo e altri (chmod 754); il file system è a strati (file system logico, organizzazione dei file, file system di base, controllo dell'I/O), con strutture su disco (boot block, superblock, directory, FCB o inode) e in memoria; i blocchi si allocano in modo contiguo (extent), concatenato (FAT) o indicizzato (inode con puntatori diretti e indiretti, ext4 con extent); lo spazio libero con bitmap, lista, raggruppamento o conteggio; mount, VFS, file system distribuiti (NFS) e semantiche di consistenza.File system - interfaccia, directory e implementazione →.

Bloccante, non bloccante e asincrono

Il non bloccante restituisce subito qualcosa (o niente); l'asincrono restituisce tutti i dati, ma in futuro. Per il passaggio dei processi tra stati (pronto, in attesa) vedi Processi - stati, PCB, creazione con fork ed execUn processo è un programma in esecuzione (entità attiva) con codice (text), dati globali, heap, stack e lo stato dell'esecuzione; il kernel lo descrive con il PCB (Process Control Block: stato, program counter, registri, informazioni di scheduling, memoria, accounting, file aperti, in Linux la struct task_struct) e passa da un processo all'altro con il context switch (puro overhead); gli stati sono new, ready, running, waiting, terminated, con una ready queue e varie wait queue; in UNIX fork() crea un figlio copia del padre (restituisce 0 al figlio e il pid del figlio al padre), exec() sostituisce il programma del figlio, wait()/waitpid() raccoglie lo stato di uscita: senza di essa un figlio terminato è uno zombie, un figlio il cui padre è morto è un orfano adottato da init/systemd; i processi cooperanti comunicano con memoria condivisa (POSIX shm) o scambio di messaggi (diretto o indiretto, sincrono o asincrono, buffer a capacità zero, limitata, illimitata) e con pipe ordinarie (padre-figlio, unidirezionali) e named pipe (FIFO).Processi - stati, PCB, creazione con fork ed exec →.

Errori e protezione

Il sistema operativo può recuperare da errori di lettura del disco, dispositivo non disponibile, errori transitori di scrittura; restituisce un codice di errore se la richiesta fallisce e registra i problemi nei log. Un processo potrebbe, per sbaglio o apposta, disturbare il funzionamento con istruzioni di I/O illegali: perciò tutte le istruzioni di I/O sono privilegiate e l'I/O avviene solo tramite system call.

File mappati in memoria (memory-mapped files)

Attenzione ai due significati: il memory-mapped I/O dei dispositivi (registri nello spazio di indirizzi) e i file mappati in memoria, di cui parla il laboratorio 8. Qui si tratta dei secondi.

Definizione (file mappato in memoria). È un modo di fare I/O che non richiede system call (tranne per l'inizializzazione): il file è mappato nello spazio di indirizzi del processo, in modo che a ogni indirizzo corrisponda una parola del file. Il file è accessibile come qualunque altro dato in memoria, con istruzioni di load e store, e permette anche la comunicazione fra processi tramite file.

La chiamata mmap()

Linux realizza lo standard POSIX mmap(): un processo chiede al kernel di mappare un file nel proprio spazio di indirizzi. Sei argomenti:

In caso di successo restituisce un puntatore alla zona mappata, altrimenti MAP_FAILED. munmap(addr, length) toglie la mappatura. Prima di mappare un file nuovo bisogna dargli la lunghezza con ftruncate(fd, dimensione). Dopo la mappatura si può chiudere il file (close(fd)): la mappatura resta valida.

Punto chiave. Le pagine del file non sono portate in memoria fisica finché non vengono riferite: mmap() carica le pagine solo quando servono (caricamento pigro, lazy loading), con il demand paging (vedi Memoria virtuale - paginazione su richiesta e sostituzione delle pagineLa memoria virtuale separa la memoria logica da quella fisica: basta che alcune pagine siano in RAM; con la paginazione su richiesta (demand paging) una pagina si carica solo al primo riferimento, e un riferimento a una pagina non residente (bit di validità = i) genera un page fault gestito dal sistema operativo in sei passi; EAT = (1 - p) * accesso + p * servizio del fault, con p minuscolo; copy-on-write rende economica la fork; se non ci sono frame liberi si sceglie una vittima con FIFO (anomalia di Belady), OPT (ottimo, irrealizzabile), LRU (algoritmo a stack), second chance (bit di riferimento, orologio) o la versione con bit di modifica; i frame si assegnano in modo uguale o proporzionale, con sostituzione globale o locale; se un processo non ha abbastanza frame va in thrashing; il modello del working set e la frequenza dei page fault lo evitano; considerazioni su prepaging, dimensione della pagina, TLB reach e struttura dei programmi; memoria del kernel con buddy system e slab.Memoria virtuale - paginazione su richiesta e sostituzione delle pagine →). Il primo accesso a una pagina provoca un page fault e il kernel la legge dal disco nella page cache.

Vantaggi

• Evitare caricamenti inutili: una pagina mai riferita non viene mai caricata; con l'I/O standard si rischia di leggere dati mai usati.
• Comodità di programmazione: si manipola il file con i puntatori, e non servono buffer utente aggiuntivi, perché la page cache è gestita dal sistema.
• Prestazioni: di solito più veloce delle system call, soprattutto con file grandi, perché elimina il costo di ogni chiamata di sistema (cambio da modalità utente a kernel) e la copia dei dati tra buffer diversi.

Esempio del laboratorio: 1 000 000 di accessi a posizioni casuali di un file da 100 MB. Con mmap() ogni accesso è un load (a volte un page fault); con lseek più read ogni accesso costa due system call. Il programma confronta i due tempi e ci si aspetta che la versione con mmap() sia molto più veloce (il confronto non è stato misurato qui). Il codice è in Esercizio - File mappati in memoria con mmap e processi che li condividono (laboratorio 8).

Condivisione tra processi

Con MAP_SHARED, due processi che mappano lo stesso file vedono le stesse pagine fisiche: una scrittura dell'uno è visibile subito all'altro. Dopo una fork, la mappatura è ereditata, quindi padre e figlio possono comunicare tramite l'area condivisa (a differenza del normale copy-on-write della fork, vedi Processi - stati, PCB, creazione con fork ed execUn processo è un programma in esecuzione (entità attiva) con codice (text), dati globali, heap, stack e lo stato dell'esecuzione; il kernel lo descrive con il PCB (Process Control Block: stato, program counter, registri, informazioni di scheduling, memoria, accounting, file aperti, in Linux la struct task_struct) e passa da un processo all'altro con il context switch (puro overhead); gli stati sono new, ready, running, waiting, terminated, con una ready queue e varie wait queue; in UNIX fork() crea un figlio copia del padre (restituisce 0 al figlio e il pid del figlio al padre), exec() sostituisce il programma del figlio, wait()/waitpid() raccoglie lo stato di uscita: senza di essa un figlio terminato è uno zombie, un figlio il cui padre è morto è un orfano adottato da init/systemd; i processi cooperanti comunicano con memoria condivisa (POSIX shm) o scambio di messaggi (diretto o indiretto, sincrono o asincrono, buffer a capacità zero, limitata, illimitata) e con pipe ordinarie (padre-figlio, unidirezionali) e named pipe (FIFO).Processi - stati, PCB, creazione con fork ed exec →). Serve comunque la sincronizzazione (Sincronizzazione - sezione critica, race condition e mutexQuando più processi o thread accedono agli stessi dati e il risultato dipende dall'ordine degli accessi si ha una race condition (esempio: counter++ e counter-- sono tre istruzioni macchina ciascuna, e interleaving diversi danno 4, 5 o 6 partendo da 5); il problema della sezione critica chiede un protocollo (entry section, sezione critica, exit section, remainder section) che garantisca mutua esclusione, progresso e attesa limitata; disabilitare gli interrupt non scala sui multiprocessori, l'alternanza stretta con turn viola il progresso, la soluzione di Peterson (flag[2] e turn) soddisfa i tre requisiti ma può fallire su hardware moderno per il riordino delle istruzioni, per cui servono barriere di memoria; l'hardware offre test_and_set e compare_and_swap (atomiche) e variabili atomiche; il mutex lock (acquire/release, in POSIX pthread_mutex_t) è lo strumento di alto livello, con attesa attiva se è uno spinlock oppure con sospensione del thread se è un mutex di sistema; bloccare due volte lo stesso mutex senza sbloccarlo causa deadlock.Sincronizzazione - sezione critica, race condition e mutex →): nell'esempio del laboratorio il padre aspetta con wait() che il figlio abbia scritto.

Domande d'esame

1. Confrontare polling, interruzioni e DMA. Polling: la CPU legge il registro di stato finché il dispositivo è pronto; semplice, ottimo con dispositivi veloci, spreca CPU con quelli lenti. Interruzioni: il dispositivo avvisa con la linea IRQ, la CPU esegue il gestore (con cambio di contesto, priorità, vettore); adatto a eventi rari. DMA: il controller trasferisce blocchi tra dispositivo e memoria senza la CPU e interrompe solo alla fine; per grandi quantità di dati.
2. Differenza tra I/O bloccante, non bloccante e asincrono. Bloccante: il processo aspetta il completamento. Non bloccante: ritorna subito con ciò che c'è. Asincrona: il processo prosegue e viene avvisato a I/O finito, ricevendo tutti i dati più tardi.
3. Perché mmap() è spesso più veloce di read e write, e cosa succede al primo accesso a una pagina mappata? Niente system call per ogni accesso e niente copia dal kernel a un buffer utente; il primo accesso causa un page fault e il kernel carica la pagina (lazy loading, demand paging).