Memoria di massa e scheduling del disco

La memoria di massa (mass storage) è il livello più lento e capace della gerarchia (Gerarchia di memoria e principio di localitàCaratteristiche delle memorie (posizione, capacità, unità di trasferimento, metodo di accesso, prestazioni, volatilità); compromesso costo-capacità-velocità e gerarchia a livelli; località temporale e spaziale con esempi; hit, miss e tempo medio di accesso con calcolo svolto.Gerarchia di memoria e principio di località →). Questa nota la guarda dal lato del sistema operativo: come si ordinano le richieste ai dischi, come si gestiscono i dispositivi e la ridondanza. Il lato hardware dei dischi e dei RAID è anche in Memoria esterna - dischi, RAID e memorie otticheDisco magnetico (piatti, facce, tracce, settori, cilindri); tempo di accesso come somma di posizionamento, latenza rotazionale e trasferimento, con formule ed esempio; algoritmi di scheduling FCFS, SSTF e ascensore; livelli RAID da 0 a 6; SSD; CD, DVD e nastri.Memoria esterna - dischi, RAID e memorie ottiche →; il file system che ci sta sopra è in 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 →.

Tipi di dispositivi

La maggior parte della memoria secondaria dei calcolatori è fatta di dischi rigidi (hard disk drive, HDD) e di memorie non volatili (NVM), oggi spesso dischi a stato solido (SSD) basati su flash NAND; ci sono anche le chiavette USB, i "dischi" in DRAM e le memorie saldate sulla scheda madre (smartphone). Il nastro magnetico si usa per le copie di sicurezza.

Dischi rigidi

• I piatti (platters) rivestiti di materiale magnetico ruotano sotto le testine di lettura e scrittura, montate su un braccio mobile; ruotano da 60 a 250 volte al secondo (3600-15000 RPM).
• Ogni piatto è diviso in tracce circolari; le stesse tracce dei vari piatti formano un cilindro; ogni traccia è divisa in settori da 512 o 4096 byte.
• Il tempo di posizionamento (random access time) ha due parti: il seek time (spostare il braccio sul cilindro: pochi millisecondi) e la latenza rotazionale (attendere che il settore passi sotto la testina).
• Dimensioni dei piatti: 3,5", 2,5", 1,8"; capacità da GB a TB; velocità di trasferimento tipica di qualche Gbit/s.

Definizione (tempo di accesso e di I/O). Il tempo medio di accesso è $T_{\text{acc}}=T_{\text{seek}}+T_{\text{lat}}$, dove la latenza media è il tempo di mezza rotazione:

$$T_{\text{lat}}=\frac{0{,}5}{\text{RPM}/60}=\frac{30}{\text{RPM}}\ \text{s}.$$

Il tempo medio di I/O è $T_{I/O}=T_{\text{acc}}+T_{\text{trasf}}+T_{\text{ctrl}}$, con $T_{\text{trasf}}=\dfrac{\text{quantità da trasferire}}{\text{velocità di trasferimento}}$ e $T_{\text{ctrl}}$ l'overhead del controller.

Esempio (slide). Blocco da 4 KB, disco a 7200 RPM, seek medio 5 ms, 1 Gbit/s, controller 0,1 ms.

• $T_{\text{lat}}=30/7200=4{,}1667$ ms, $T_{\text{acc}}=5+4{,}17=9{,}17$ ms.
• $T_{\text{trasf}}=\dfrac{4\text{ KB}}{0{,}125\text{ GB/s}}=\dfrac{4}{0{,}125\cdot1024^2}\text{ s}\approx3{,}05\cdot10^{-5}\text{ s}\approx0{,}031$ ms.
• $T_{I/O}=9{,}17+0{,}031+0{,}1=9{,}301$ ms (con i valori non arrotondati 9,298 ms).

Il tempo è dominato da seek e rotazione, non dal trasferimento: per questo conviene leggere in blocco e ordinare le richieste. Altri esercizi sui tempi: Esercizio - Tempi di accesso al disco e capacità (slide di esercizi, eserciziario, esercizi 88, 89 e 94).

Memorie non volatili (SSD)

• Memorie NAND flash senza parti in movimento: niente seek e niente latenza rotazionale; più affidabili degli HDD, più costose, più veloci, meno capaci, con vita limitata.
• Si leggono e scrivono a pagine (come i settori), ma non si può sovrascrivere una pagina in posizione: va prima cancellata, e la cancellazione avviene a blocchi più grandi. Ogni cella si può cancellare solo un numero limitato di volte (circa 100 000). La durata si misura in DWPD (drive writes per day): un disco da 1 TB con 5 DWPD può scrivere 5 TB al giorno per tutto il periodo di garanzia. Le celle flash e la loro scrittura sono spiegate in Memorie non volatili - gate flottante, EPROM, EEPROM e FlashLe memorie non volatili conservano il dato senza alimentazione. La PROM a fusibili (o antifusibili) si programma una volta interrompendo (o creando) un collegamento. Le memorie riprogrammabili usano il transistor a gate flottante: un gate di polisilicio isolato tra il canale e il gate di controllo; la carica (elettroni) intrappolata sul gate flottante aumenta la soglia vista dal gate di controllo, così il transistor programmato resta spento a tutte le tensioni di lettura (V_T,prog > V_DD). EPROM: programmazione per iniezione di portatori caldi, cancellazione collettiva con raggi UV. EEPROM (transistor FLOTOX, effetto tunnel Fowler-Nordheim attraverso un ossido sottile): cancellazione elettrica della singola cella, ma due transistor per cella (area quasi doppia). Flash: variante dell'EEPROM con una sola cella-transistor e cancellazione a blocchi o settori, struttura NOR o NAND.Memorie non volatili - gate flottante, EPROM, EEPROM e Flash → e Memorie - gerarchia, SRAM, DRAM, ROM e FLASHNei µC e DSP si usa solo memoria a stato solido ad accesso immediato, interna (on chip) o esterna. Parametri: dimensione, velocità (tempo di accesso, latenza, banda), consumo, integrazione. La memoria è gerarchica (registri → cache → SRAM interna → esterna) grazie alla localitàtendenza dei programmi a riusare gli stessi dati e a usare dati vicini in memoria spaziale e temporale. Tipi: SRAM (veloce, 4-6 transistori per cella, volatile, nessun refresh), DRAM (carica in un MOS, serve il refresh, più densa e a minor consumo), ROM/OTP/EPROM/EEPROM e FLASH (gate flottante: scrittura per elettroni caldi, cancellazione per effetto tunnel, solo per blocchi, $>10^5$ cicli). Una "RAM" è qualunque memoria con tempo di accesso indipendente dalla posizione.Memorie - gerarchia, SRAM, DRAM, ROM e FLASH →.
• Poiché non si sovrascrive, le pagine contengono un misto di dati validi e non validi (superati). Il controller usa:
  • la FTL (flash translation layer): tabella che tiene traccia dei blocchi logici validi;
  • la garbage collection: libera lo spazio delle pagine non valide copiando altrove quelle valide, poi cancella il blocco;
  • l'overprovisioning: spazio riservato (per esempio il 20% della capacità) come area di lavoro per la garbage collection;
  • il wear leveling: distribuisce le scritture in modo uniforme per consumare tutte le celle allo stesso modo.
• La write amplification (una scrittura che provoca garbage collection con molte letture e scritture) può ridurre il vantaggio di prestazioni.

Nastro magnetico

Primo mezzo di memoria secondaria. Capacità molto grandi (diversi TB, anche con compressione integrata), ma l'accesso casuale è da cento a mille volte più lento (portarsi nel punto giusto richiede minuti); una volta in posizione, la velocità è confrontabile con gli HDD. Si usa per backup, dati usati di rado e trasferimento fra sistemi.

Mappatura degli indirizzi

Un disco è visto come un grande vettore monodimensionale di blocchi logici, che sono la più piccola unità di trasferimento. Nell'HDD il vettore è mappato sui settori in sequenza: il settore 0 è il primo settore della prima traccia del cilindro più esterno; poi si percorre quella traccia, poi le altre tracce dello stesso cilindro (altre testine), poi gli altri cilindri dall'esterno verso l'interno. Nelle NVM la mappa è dalla tupla (chip, blocco, pagina) al vettore. Il LBA (logical block address) è più semplice per gli algoritmi di (cilindro, testina, settore) o di (chip, blocco, pagina).

Scheduling dell'HDD

Il sistema operativo deve usare bene l'hardware: tempo di accesso breve e grande banda (byte totali trasferiti diviso il tempo fra la prima richiesta e il completamento). Per l'HDD si minimizza l'accesso, quindi il seek time, quindi la distanza di seek. Il sistema mantiene una coda di richieste di I/O (modo, indirizzo su disco e in memoria, numero di settori). Un disco libero serve subito, uno occupato accoda le richieste: servono algoritmi di scheduling del disco.

Esempio comune (slide): cilindri da 0 a 199, coda 98, 183, 37, 122, 14, 124, 65, 67, testina inizialmente al cilindro 53.

FCFS

Le richieste sono servite nell'ordine di arrivo (coda FIFO): $53\to98\to183\to37\to122\to14\to124\to65\to67$.

$$|98-53|+|183-98|+|37-183|+|122-37|+|14-122|+|124-14|+|65-124|+|67-65|=45+85+146+85+108+110+59+2=640.$$

Equo, ma non ottimo.

SSTF (shortest-seek-time-first)

Si serve la richiesta più vicina alla testina: $53\to65\to67\to37\to14\to98\to122\to124\to183$.

$$12+2+30+23+84+24+2+59=236.$$

Quasi il 60% in meno di FCFS. È simile a SJF nella Scheduling della CPU - FCFS, SJF, priorità e round robinLo scheduler della CPU sceglie tra i processi pronti quello a cui dare il core (il dispatcher esegue il cambio, con latenza di dispatch); lo scheduling è non preemptive (il processo tiene la CPU finché termina o si blocca) o preemptive (la CPU gli può essere tolta, con rischio di race condition); i criteri sono utilizzo della CPU e throughput (da massimizzare), tempo di attesa, di turnaround (completamento meno arrivo) e di risposta (da minimizzare); FCFS è semplice ma soffre dell'effetto convoglio (esempio 24, 3, 3: attesa media 17 contro 3); SJF è ottimo per l'attesa media ma richiede la lunghezza del prossimo burst, stimata con la media esponenziale tau(n+1) = alfa t(n) + (1-alfa) tau(n); SRTF è la versione preemptive (esempio con attesa media 6,5 contro 7,75); round robin dà a ciascuno un quanto q e nessuno attende più di (n-1)q; la priorità causa starvation, risolta con l'aging; code multilivello e a feedback (MLFQ) combinano le politiche.Scheduling della CPU - FCFS, SJF, priorità e round robin →: può causare starvation (richieste lontane rimandate se ne arrivano continuamente di vicine).

SCAN (ascensore)

Il braccio parte da un'estremità e va verso l'altra servendo le richieste incontrate; arrivato in fondo, inverte la direzione. Nell'esempio, andando prima verso 0: $53\to37\to14\to0$ poi $\to65\to67\to98\to122\to124\to183$:

$$53+183=236.$$

(Se la testina andasse prima verso l'alto: $53\to199$ servendo le richieste incontrate, poi $199\to14$ servendo 37 e 14, cioè $146+185=331$: il risultato dipende dalla direzione iniziale.) Problema: con richieste uniformi, la densità maggiore è all'estremo appena toccato, e le richieste dell'altro estremo aspettano più a lungo.

C-SCAN (circular SCAN)

Più uniforme: la testina va in una sola direzione servendo le richieste; arrivata all'estremo, torna subito all'inizio senza servire nulla nel ritorno. I cilindri sono trattati come una lista circolare. Nell'esempio: $53\to199$ (146), ritorno $199\to0$ (199), poi $0\to37$ (37): $146+199+37=382$ (contando il ritorno; se non si conta, $183$). Pro: attesa più uniforme. Contro: il tempo totale può essere molto maggiore (qui 382 contro 236).

LOOK e C-LOOK sono le varianti usate davvero: la testina non va fino alla fine del disco ma solo all'ultima richiesta in quella direzione. Un simulatore in C dei quattro algoritmi principali e un esercizio con le richieste che arrivano a tempi diversi sono in Esercizio - Scheduling del disco con FCFS, SSTF, SCAN e C-SCAN (slide di memoria di massa, eserciziario, esercizio 95).

Scegliere un algoritmo

SSTF è comune e più sensato di FCFS; SCAN e C-SCAN funzionano meglio con carico pesante (meno starvation, anche se possibile). Linux usa lo scheduler deadline: tiene code separate di lettura e scrittura con priorità alle letture (un processo si blocca di più su una lettura, perché ha bisogno del dato per proseguire) e una scadenza (di solito 500 ms) per servire le richieste che aspettano da troppo.

Scheduling per le NVM

Senza testine e rotazione, ma c'è spazio per ottimizzare: Linux usa NOOP (FIFO), unendo le richieste di LBA adiacenti. Le NVM sono migliori sull'I/O casuale, gli HDD su quello sequenziale; la velocità di trasferimento può essere simile (senza seek), ma le operazioni di I/O al secondo sono molto superiori nelle NVM.

Gestione dei dispositivi

• Formattazione di basso livello (fisica): divide il disco in settori (blocchi logici) che il controller sa leggere e scrivere. Ogni settore ha intestazione, dati (tradizionalmente 512 byte, oggi 4 KB) e codice di correzione degli errori (ECC).
• Per usare il disco con i file, il sistema operativo scrive le proprie strutture dati in tre passi: partizionare il disco in gruppi di cilindri; creare un volume (disco logico, a volte implicito); formattazione logica (creare il file system). Vedi 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 →.
• La partizione radice contiene i file del sistema operativo e viene montata all'avvio; le altre partizioni possono avere altri sistemi operativi o file system, oppure essere grezze (raw). Il boot block punta al volume o al boot loader, l'insieme di blocchi con abbastanza codice per caricare il kernel dal file system; per l'avvio di più sistemi esiste un programma di boot (per esempio GRUB).

Gestione dello spazio di swap

Lo swap space serve a spostare processi interi o pagine dalla memoria a quella secondaria quando la memoria non basta (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 →). Poiché la memoria secondaria è più lenta, conta l'ottimizzazione: meglio dispositivi dedicati, anche più aree di swap per ripartire l'I/O; può essere una partizione grezza o un file in un file system. In Linux l'area è divisa in slot di pagina e una mappa di swap associa a ogni slot un contatore: 0 = libero, $n>0$ = condiviso da $n$ processi.

Rilevamento e correzione degli errori

Il rilevamento stabilisce se c'è stato un errore (per esempio un bit invertito); si può fermare l'operazione. Si fa spesso con un bit di parità, che è una forma di checksum (aritmetica modulare su parole di lunghezza fissa). Un codice di correzione (ECC) non solo rileva ma corregge alcuni errori: gli errori soft si correggono, quelli hard si rilevano ma non si correggono.

RAID

Definizione (RAID). RAID (redundant array of inexpensive/independent disks) usa più dischi insieme per ottenere affidabilità tramite ridondanza e maggiore velocità con l'accesso in parallelo.

Tecniche:

• striping: i dati sono divisi a pezzi (strisce) distribuiti sui dischi, che si usano come un'unica unità: più banda;
• mirroring (specchio): ogni disco ha una copia: più affidabilità;
• parità: informazione per ricostruire un disco perso, con meno ridondanza.

Prestazioni teoriche e guasti

Con $n$ dischi ciascuno con velocità di trasferimento $v$:

• RAID 0: lettura e scrittura $nv$.
• RAID 1+0 con $n=4$: lettura $4v$ (si legge da tutti i dischi), scrittura $2v$ (due coppie in mirror: ogni dato va scritto su due dischi).
• Un guasto in un RAID 1+0: nessuna perdita, rallentamento in lettura ma non in scrittura; due guasti: perdita solo se i due dischi sono dello stesso mirror.

Esempio (esercizio 43). Due dischi da 200 GB. RAID 1: capacità 200 GB, e se $p$ è la probabilità che un disco si guasti in 24 ore, quella che si guastino entrambi è $p^2$ (molto più bassa). RAID 0: capacità 400 GB, e la probabilità che il sistema si guasti sale a $1-(1-p)^2$ (con $p=0{,}0001$: $0{,}00019999$, quasi il doppio). Quattro dischi da 500 GB e 120 MB/s: RAID 0 dà 2000 GB, lettura e scrittura $4\cdot120=480$ MB/s; RAID 10 dà 1000 GB, lettura $480$ MB/s, scrittura $240$ MB/s. (La soluzione del corso scrive GB/s al posto di MB/s: è un refuso.)

Affidabilità

Il RAID aumenta il MTBF (tempo medio tra guasti). Il MTTR (tempo medio di riparazione) è la finestra di esposizione in cui un secondo guasto fa perdere dati. Il MTTDL (tempo medio fino alla perdita di dati) dipende da entrambi.

Esempio (slide). RAID 1 con due dischi A e B, MTBF $=100\,000$ h, MTTR $=10$ h. Probabilità di guasto in un'ora: $P_F=1/100\,000=10^{-5}$; di riparazione: $P_R=10/100\,000=10^{-4}$. Se i guasti sono indipendenti: $P_{DL}\approx P_F(A)P_R(B)+P_F(B)P_R(A)=2\cdot10^{-5}\cdot10^{-4}=2\cdot10^{-9}$. Quindi $\text{MTTDL}=1/P_{DL}=500\cdot10^{6}$ ore, circa 57 000 anni.

Esercizi sulla capacità (esercizio 74): con 8 GB utili, RAID 0 usa 4 dischi da 2 GB (8 GB), RAID 1 usa 4 dischi da 4 GB (16 GB totali, 8 utili), RAID 4 usa 5 dischi da 2 GB (10 GB totali, 8 utili), RAID 5 usa 3 dischi da 4 GB (12 GB totali, $2/3$ utili cioè 8). Vedi Esercizio - RAID, capacità, prestazioni e guasti (eserciziario, esercizi 43 e 74).

Domande d'esame

1. Calcolare il tempo medio di I/O di un blocco da 4 KB, a 10 000 RPM, seek 4 ms, 100 MB/s, controller 0,2 ms. $T_{\text{lat}}=30/10000=3$ ms; $T_{\text{trasf}}=4\text{ KB}/100\text{ MB/s}\approx0{,}04$ ms; $T_{I/O}\approx4+3+0{,}04+0{,}2=7{,}24$ ms.
2. Differenza tra SCAN e C-SCAN e quando serve LOOK. SCAN inverte la direzione agli estremi; C-SCAN ritorna all'inizio senza servire, quindi l'attesa è più uniforme ma il percorso più lungo. LOOK e C-LOOK si fermano all'ultima richiesta in quella direzione senza arrivare all'estremo.
3. Quattro dischi da 1 TB: capacità e tolleranza ai guasti di RAID 0, 5 e 10. RAID 0: 4 TB, nessuna tolleranza. RAID 5: 3 TB, un guasto. RAID 10: 2 TB, un guasto, due solo se in mirror diversi.