11. Gestione della memoria secondaria

Tipologie di supporto

Vediamo le principali tipologie di supporto e le loro caratteristiche.

Nastri magnetici

Uno dei primi tipi di memoria secondaria è il nastro magnetico, una sottile striscia in materiale plastico, rivestita da un materiale magnetizzabile. Questo tipo di memoria ha avuto una massima capacità di circa 5TB nel 2011, arrivata poi a 45TB nel 2021.
Tuttavia, l'accesso a questa memoria è sequenziale, il che significa che è molto più lento rispetto alla memoria principale e ai dischi magnetici in termini di tempo di accesso. Il riposizionamento della testina di lettura richiede decine di secondi, il che lo rende un processo abbastanza lento.
A causa di queste limitazioni, le memorie magnetiche di questo tipo sono state rimpiazzate dai dischi magnetici e dalle memorie a stato solido, che offrono prestazioni migliori. I dischi magnetici e le memorie a stato solido hanno una capacità di archiviazione tre ordini di grandezza superiore rispetto a questo tipo di memoria.
Oggi, le sottili strisce magnetiche sono ormai usate solo per scopi di backup.

Dischi magnetici

Sono piatti di alluminio o di altro materiale ricoperti di materiale ferromagnetico con una massima capienza di $4TB$ (nel 2011). Il fattore di forma o diametro è sempre più piccolo in modo da raggiungere maggiori velocità di rotazione. Parte da 3:5 pollici per i sistemi desktop e fino a 1 pollice per i mobili. La lettura e la scrittura avvengono tramite una testina sospesa sulla superficie magnetica. Nella scrittura il passaggio di corrente positiva o negativa attraverso la testina magnetizza la superficie, mentre nella lettura il passaggio sopra un’area magnetizzata induce una corrente positiva o negativa nella testina.

Struttura di un disco

Da un punto di vista fisico il disco è costituito da superfici (platter, i dischi), cilindri (cylinder, le tracce di tutti i dischi con la stessa posizione), tracce (cerchi di settori all’interno di un disco) e settori (sottoaree del disco disposte in cerchi concentrici).

Settore

Il settore è l’unita più piccola di informazione che può essere letta o scritta su disco.
Ha una dimensione variabile tra i 32 byte e i 4KB (tipicamente di 512 byte). Sono generalmente raggruppati logicamente in cluster per aumentare l’efficienza. La dimensione dei cluster dipende dalla grandezza del disco e dal sistema operativo (da 2KB a 32KB). Un file occupa sempre almeno un cluster. Per accedere a un settore si necessita di sapere la superficie, la traccia e il settore stesso.

Tempo di accesso al disco

Il tempo di accesso è la somma del seek time (tempo necessario a spostare la testina sulla traccia),
del latency time (latenza, il tempo necessario a posizionare il settore desiderato sotto la testina che dipende dalla velocità di rotazione) e del transfer time (il tempo necessario al settore per passare sotto la testina).
Il seek time va da 3ms fino a 15ms, mediamente 9ms per dischi desktop.
La latenza, considerando in media mezza rotazione del disco per ogni accesso è $0.5\cdot (\frac{60}{\text{velocità di rotazione}})$. Per un disco da $7200rpm$ è di $4.16ms$.
Il transfer time è il rapporto tra la dimensione del blocco e la velocità di trasferimento. Per un disco da $7200rpm$ si ha: disk-to-buffer $1030\frac{Mbits}{sec}$ e buffer-to-computer $300\frac{MB}{sec}$.

Dunque, mettendo tutti questi dati, mediamente abbiamo una velocità di trasferimento pari a $40MB/s$, velocità di rotazione pari a $10000rpm=166rps$, rotazione media pari a $\frac{1}{2}$ traccia, una dimensione del blocco pari a $512Byte$ ed un seek time pari a $5ms$.
Possiamo quindi calcolare il tempo di accesso, pari a:

Si noti come il seek time è dominante e pertanto dato il grande numero di processi che accedono al disco è necessario minimizzare il seek time tramite algoritmi di scheduling per ordinare gli accessi al disco in modo da minimizzare il tempo di accesso totale (riducendo lo spostamento della testina) o massimizzare la banda, che è il numero di byte trasferiti nell’unità di tempo (misura la velocità effettiva).

Dispositivi a stato solido

Utilizzano chip NVRAM o memorie flash NAND per memorizzare dati in modo non volatile. Usano la stessa interfaccia dei dischi fissi e pertanto possono rimpiazzarli facilmente. Hanno una capacità fino a 2TB.

Performance delle flash memory

Hanno letture simili a DRAM negli ordini dei nanosecondi e scritture simili ai dischi magnetici nell’ordine dei millisecondi. Rispetto ai dischi fissi sono meno soggette a danni, ma con un limite sul numero di write (1-5 milioni), più silenziosi, più efficienti nel tempo di accesso, non necessitano di essere deframmentate e sono più costose.

Scheduling degli accessi a disco

Logicamente il disco può essere considerato come un vettore unidimensionale di blocchi logici. Un blocco o cluster è l’unità minima di trasferimento. Il vettore è mappato sequenzialmente sui settori del disco. Il settore 0 è il primo settore della prima traccia del cilindro più esterno e la numerazione procede gerarchicamente per settore, tracce e piatti.

Disk scheduling

Un processo che necessita di eseguire un'operazione di I/O esegue una system call. In seguito, il sistema operativo utilizza la vista logica del disco per gestire le richieste I/O. Queste richieste contengono informazioni come l'indice del vettore (posizione di memoria) a cui accedere, il tipo di accesso (lettura o scrittura), l'indirizzo di memoria destinazione o di origine e la quantità di dati da trasferire. Tutto ciò consente al sistema operativo di effettuare operazioni di I/O efficienti e controllate.

Algoritmi di disk scheduling

In questi algoritmi bisogna sempre tenere conto del compromesso tra costo ed efficacia. Sono valutati tramite una sequenza di accessi.

First-come-first-served (FCFS)

In questo algoritmo le richieste sono processate nell’ordine di arrivo.

Esempio

Shortest seek time first (SSTF)

In questo algoritmo si fa la scelta più efficiente localmente: si seleziona la richiesta con il minimo spostamento rispetto alla posizione attuale della testina. Simile al SJF con possibilità di starvation di alcune richieste, visto che le richieste più lontane potrebbero essere ignorate all'infinito.

Esempio

SCAN

La natura dinamica delle richieste porta all’algoritmo SCAN, in cui la testina parte da un’estremità del disco, si sposta verso l’altra estremità servendo tutte le richieste correnti. Arrivato all’altra estremità riparte nella direzione opposta servendo le nuove richieste. Viene detto algoritmo dell’ascensore.

Esempio

SCAN circolare (CSCAN)

Come SCAN, ma quando la testina arriva ad un’estremità riparte immediatamente da 0 senza servire altre richieste. Il disco viene considerato come lista circolare e il tempo di attesa è più uniforme rispetto a SCAN. Alla fine di una scansione ci saranno più richieste all’altro estremo.

Esempio

(C-)LOOK, variante dello SCAN

La testina non arriva fino all’estremità del disco. Cambia direzione (LOOK) o riparte dalla prima traccia (C-LOOK) non appena non ci sono più richieste in quella direzione.

Esempio

N-step SCAN, variante dello SCAN

Per evitare che la testina rimanga sempre nella stessa zona, la coda delle richieste viene partizionata in più code di dimensione massima $N$. Quando una coda viene processata per il servizio (scan in una direzione), gli accessi in arrivo riempiono altre code. Dopo che una coda è stata riempita non è possibile riordinare le richieste. Le code sature vengono servite nello scan successivo. Per $N$ grandi degenera in SCAN, mentre per $N$ = 1 degenera in FCFS. FSCAN è simile ma con due sole code.

Esempio

Last-in-last-out (LIFO)

In certi casi può essere utile schedulare gli accessi in base all’ordine inverso di arrivo. È utile nel caso di accessi con elevata località, ma offre possibilità di starvation.

Analisi degli algoritmi

Nessuno degli algoritmi considerati è ottimo, in quanto quello ottimo sarebbe poco efficiente . L’analisi è influenzata dalla distribuzione di numero e dimensione degli accessi, in quanto più l’accesso è grande più il peso relativo del seek time diminuisce e dall’organizzazione delle informazioni su disco (il file system) e l’accesso alla directory essenziale tipicamente lontane dalle estremità del disco. In generale SCAN e C-SCAN sono migliori per sistemi con molti accessi a disco. Il disk-scheduling viene spesso implementato come modulo indipendente dal sistema operativo con diverse scelte di algoritmo.

Formattazione del disco

La formattazione è un processo che crea su un disco le strutture e le suddivisioni in settori necessarie per l’utilizzo da parte del SO. Tale operazione si suddivide in formattazione fisica e logica.

Formattazione fisica

Nella formattazione di basso livello o fisica, il disco viene diviso in settori che il controllore può leggere o scrivere.
Ogni settore è provvisto di un header contenente un numero di settore ed un trailer con un Error Correction Code (ECC), che fornisce un sistema limitato di correzione degli errori. Generalmente tale formattazione è effettuata in fabbrica.

Formattazione logica

Per quanto riguarda la formattazione logica, questa prevede la suddivisione del disco in partizioni e la definizione del file system montato su ciascuna di esse, con le relative strutture di supporto. Questo processo definisce anche eventuali partizioni speciali, come quella dedicata per i file di swap, i boot blocks del disco, le zone di memoria del bootstrap, contenenti le routine di avvio del SO.

Gestione dei blocchi difettosi (bad block)

L’ECC (error correction code) serve a capire in lettura o scrittura se un settore contiene dati corretti o meno. Come utilizziamo questo codice? Per esempio, nella fase di lettura, quello che avviene è che il controllore legge un settore (nel quale è incluso anche l’ECC) e calcola l’ECC per i dati appena letti. Se il risultato è diverso si trova un errore, ovvero un bad block. L’errore va segnalato e il bad block va gestito. Esistono principalmente due tecniche di gestione dei bad block.

Gestione offline dei bad block

Durante la formattazione logica del disco, vengono individuati i bad block e inseriti in una lista dedicata. Inoltre, vengono rimossi dalla lista dei blocchi disponibili per l'uso.
Successivamente, viene effettuata una modifica nell'entry della File Allocation Table (FAT) corrispondente a tali blocchi. Segnando l'entry corrispondente ai bad block nella FAT, si indica che questi blocchi non devono essere utilizzati per l'archiviazione di dati.
Successivamente, è possibile eseguire un'utilità specifica per isolare ulteriormente i bad block. Ciò significa che il sistema operativo non userà più questi blocchi per l'archiviazione di dati, evitando così possibili errori o corruzioni.
Questo algoritmo per la gestione dei bad block è tipico dei controllori IDE (Integrated Drive Electronics).

Gestione online dei bad block

Il controllore mappa il bad block su un blocco buono non usato. Si deve pertanto disporre di blocchi di scorta riservati (sector sparing). Quando il sistema operativo richiede il bad block, il controllore mappa in modo trasparente l’accesso al bad block sul blocco di scorta. Siccome questo potrebbe andare in conflitto con l'algoritmo di disk scheduling, si cerca di allocare degli spare block in ogni cilindro.

Gestione dello spazio di swap

Lo spazio di swap viene usato dalla memoria virtuale come estensione della RAM.

• Si può ricavare dal file system attraverso comuni primitive di accesso ai file, ma è inefficiente in quanto esiste un costo addizionale per l’attraversamento delle strutture dati per le directory e i file.
• Si può porre in una partizione separata che non contiene informazioni e strutture relative al file system e usa uno speciale gestore detto swap daemon. Lo spazio di swap può essere allocato quando il processo viene creato e viene assegnato spazio per pagine di istruzioni e di dati. Il kernel usa due mappe di swap per tracciare l’uso dello spazio di swap. Oppure può essere allocato quando una pagina viene forzata fuori dalla memoria fisica.

Infine, lo spazio di swap può essere allocato in due modi.

• Può essere assegnato durante la creazione di un processo, fornendo al processo stesso uno spazio iniziale nel quale memorizzare le sue pagine di istruzioni e dati.
• Può essere allocato dinamicamente quando una pagina viene "forzata" fuori dalla memoria fisica per liberare spazio.