24 Jun 2023, 12:49 PM

10. Memoria virtuale

Le tecniche viste in memoria prevedono che tutti i dati di un processo siano caricati in memoria al momento della sua esecuzione. Con l'evoluzione del software, caricare tutto in memoria, con software di grandi dimensioni, non sempre è possibile, ma soprattutto non è sempre necessario. Basti pensare che molti programmi moderni pesano molti più GB di quanto la RAM sia fisicamente in grado di contenere. E come se non bastasse, un programma pesa di più dentro la RAM perché diventando un processo verranno aggiunte informazioni aggiuntive, come la stack (vedi 4. Gestione dei processi e threads#Da cosa è formato un processo?).
Per risolvere questo problema è dunque stata introdotta la memoria virtuale, con cui è possibile considerare parte del disco come memoria primaria (quindi Memoria virtuale = RAM + parte di disco) e caricare in memoria solo le parti del programma necessarie per l'esecuzione attuale. Sebbene generalmente complessa da implementare, la memoria virtuale permette di caricare più processi in memoria, aumentando quindi il throughput, ed inoltre permette facilmente la condivisione di risorse fra processi. Esistono varie tecniche per realizzare la memoria virtuale, ma si vedrà che, come per la paginazione, la memoria virtuale sembri quasi una naturale evoluzione.

Paginazione su richiesta (on demand)

Sostanzialmente mi permette di eseguire programmi più grandi della RAM caricando dentro quest'ultima solo una parte delle pagine e solo quando necessario. Le pagine restanti vengono caricate su disco (backing store) e prese tramite swapping.
Per capire se una pagina è dentro la ram o su disco utilizzo i bit di validità presenti nella page table:

bit a 1: pagina in memoria
bit a 0: pagina NON in memoria

Inizialmente i bit di validità sono tutti 0. Dunque, ad ogni istruzione, se la pagina richiesta è presente in memoria si va avanti normalmente, altrimenti si verifica un cosiddetto page fault.

Page fault

Un page fault causa un interrupt al SO che avviene in queste 5 fasi:

Il S.O. stabilisce la validità del riferimento del processo chiamante. Se non è valido abortisce il page fault.
Cerca un frame vuoto nella RAM o dal quale rimuovere una pagina
Effettua lo swap dal disco della pagina richiesta
Modifica il bit di validità a 1 perché ora la pagina è in memoria
Ripristina l'istruzione che ha causato il page fault

Come detto sopra, il primo accesso in memoria di un programma risulta sempre in page fault (perché la tabella è ancora vuota).

Effective Access Time (EAT)

Ovviamente la paginazione su domanda influenza il tempo di accesso effettivo alla memoria (Effective Access Time, EAT), visto che la velocità dipende da quanti page fault avvengono, e quindi se trovo la pagina già in memoria o no. Possiamo allora calcolare il tempo di accesso effettivo alla pagina. Nella formula sottostante $p$ rappresenta il tasso di page fault, ovvero la probabilità che un page fault si verifichi. Ovviamente $0 \leq p \leq 1$ , dove $p = 0$ significa nessun page fault, mentre $p = 1$ ogni accesso è un page fault.

EAT = (1 - p) \cdot t_{m e m} + p \cdot t_{p a g e f a u l t}

Dove $t_{p a g e f a u l t}$ è dato da tre componenti: il servizio dell’interrupt, lo swap in (lettura della pagina),
e costo di riavvio del processo (e lo swap out (opzionale)). Invece $t_{m e m}$ rappresenta il tempo di accesso alla memoria.

Esempio

Dati:

$t_{m e m} = 100 n s$
$t_{p a g e f a u l t} = 1 m s (10^{6} n s)$

Dunque

EAT = (1 - p) \cdot 100 + p \cdot 10^{6} = 100 - 100 \cdot p + 10^{6} \cdot p = 100 \cdot (1 + 9999 \cdot p) n s

Vediamo quanto deve valere $p$ per mantenere un peggioramento al massimo del 10% rispetto al tempo di accesso standard:

\overset{Accesso standard alla memoria}{\overset{⏞}{100 \cdot (1.1)}} > 100 \cdot (1 + 9999 \cdot p) \leftrightarrow p < 0.0001 \approx 10^{- 4}

Dunque circa $1$ page fault ogni $10000$ accessi! Ne segue che è fondamentale tenere basso il livello di page fault.

Vediamo ora cosa succede se non ci sono pagine libere da rimpiazzare.

Rimpiazzamento delle pagine

Se non ci sono pagine libere si cercano pagine (frame) in memoria e si fa lo swap su disco di tali pagine. Per far questo è necessario un algoritmo che massimizzi le prestazioni minimizzando il numero di page fault.
Vediamo quindi il funzionamento del rimpiazzamento delle pagine.
In caso di assenza di frame liberi nel caso di un page fault il sistema operativo verifica su una tabella associata al processo se si tratta di page fault o violazione di accesso. Se è una violazione di accesso fa un abort, altrimenti cerca un frame vuoto e se non c’è usa un algoritmo di rimpiazzamento delle pagine per scegliere un frame vittima.
Saranno necessari quindi 2 accessi alla memoria, uno per per fare lo swap out della vittima (nel disco) e uno per fare lo swap in del frame da caricare (in memoria).
Quindi una volta scelta la vittima, fa lo swap out di essa su disco, lo swap in della pagina nel frame da disco, modifica le tabelle e ripristina l’istruzione che ha causato il page fault. Si noti come in assenza di frame liberi il tempo di page fault si raddoppia. Pertanto si ottimizza utilizzando un bit nella page table detto bit di modifica o dirty bit che vale 1 se la pagina è stata modificata dal momento in cui viene ricaricata e solo le pagine che vengono modificate vengono scritte su disco quando diventano vittime.

Problematiche

Dunque le problematiche della paginazione su domanda sono la scelta della pagina da rimpiazzare e l’allocazione del numero di frame ad un processo al momento dell’esecuzione. Vediamo ora come risolvere questi 2 problemi.

Algoritmi di rimpiazzamento delle pagine

Il tasso di page fault, che deve essere tenuto basso per non compromettere le prestazioni, dipende molto da come viene scelta la pagina da rimpiazzare. Dunque l’obiettivo di questi algoritmi è di minimizzare il numero di page fault. Si valuta l’esecuzione di una particolare stringa di riferimenti a memoria detta reference string e si calcolano il numero di page fault sulla stringa. È sempre necessario sapere il numero di frame disponibili per il processo. Il tasso di page fault è inversamente proporzionale al numero di frame (più frame $\to$ più spazio per tutti).

Algoritmo FIFO (first-in-first-out)

In questo algoritmo la prima pagina introdotta è la prima ad essere rimossa. L’algoritmo è cieco in
quanto non viene valutata l’importanza (frequenza di riferimento) della pagina rimossa. Tende ad
aumentare il tasso di page fault e soffre dell’anomalia di Belady.

anomalia di Belady

Nell’anomalia di Belady il numero di page fault non può decrescere all’aumentare del numero di frame usando FIFO, mentre a volte più frames equivalgono a più page fault.

Esempio 1

In questo esempio abbiamo 3 frame e con una reference string lunga solamente 20 abbiamo 15 page fault!

ADR-FIFO1.png|700

Esempio 2

In questo esempio abbiamo 3 frame e con una reference string lunga solamente 12 abbiamo 9 page fault!

ADR-FIFO2.png|700

Algoritmo ideale

Come sarebbe fatto quindi un algoritmo ideale?
Garantisce il minimo numero di page fault rimpiazzando le pagine che non saranno usate per il periodo di tempo più lungo. Questa informazione richiede una conoscenza anticipata della stringa dei riferimenti e ci si ritrova in una situazione simile a SJF e pertanto l’implementazione è impossibile a meno di approssimazioni. Rimane comunque un utile riferimento per altri algoritmi.

Esempio

In questo esempio abbiamo 3 frame e con una reference string lunga solamente 20 avremmo solamente 9 page fault. Viene rimpiazzata la pagina che sarà riusata in seguito alle altre 2 pagine nei frame.

ADR-Ideale.png|700

Algoritmo least recently used (LRU)

Questo algoritmo è un’approssimazione dell’algoritmo ottimo e usa il passato recente come previsione del futuro rimpiazzando la pagina che non viene usata da più tempo. È di difficile implementazione in quanto non è banale ricavare il tempo dell’ultimo utilizzo e può richiedere notevole hardware addizionale.

Esempio

In questo esempio abbiamo 4 frame e con una reference string lunga solamente 12 abbiamo 8 page fault.
Dunque è decisamente migliore del FIFO ma peggiore dell'algoritmo ideale (ovviamente).
ADR-LRU.png|700

Implementazioni

Vediamo ora delle possibili implementazioni di questo algoritmo.

Tramite contatore

Ad ogni pagina è associato un contatore e ogni volta che la pagina viene referenziata il clock di sistema è copiato nel contatore. Si rimpiazza la pagina con il valore più piccolo del contatore. Si noti come tale pagina vada cercata.

Tramite stack

Viene mantenuto uno stack di numeri di pagina e quando si fa riferimento ad una pagina questa viene estratta dalla sua posizione e messa in cima. L’aggiornamento richiede l’estrazione di un elemento interno allo stack. Al fondo dello stack si trova la pagina LRT. Si noti come in questo caso non è necessaria alcuna ricerca, in quanto la pagina designata è sempre in fondo, ma aggiornare il riferimento, rimuovendo un elemento dal centro, richiede una ricerca $O (n)$ .

ADR-LRU-Stack.png|400

Uso del bit di reference

Che viene associato ad ogni pagina inizialmente a 0. Quando la pagina è referenziata, il bit di reference viene impostato a 1 dall’hardware. Per il rimpiazzamento si sceglie una pagina che ha il bit a 0. Si noti come è approssimato in quanto non viene verificato l’ordine di riferimento delle pagine.

In alternativa, si usano più bit di reference (registro di scorrimento) per ogni pagina. I bit vengono aggiornati periodicamente e si usano i bit come valori interi per scegliere la LRU, ovvero quella con il valore più basso di registro di scorrimento.

Approssimazioni

Le tecniche viste sopra implementano deterministicamente il LRU, ma sono costose in termini di HW. Esistono implementazioni alternative meno costose, che sono tuttavia a loro volta delle approssimazioni.

Algoritmo LFU (Least Frequently Used)

Mantiene un conteggio del numero di riferimenti fatti ad ogni pagina e rimpiazza quella con il conteggio più basso. Può non corrispondere al “LRU”, visto che, se per esempio ho molti riferimenti iniziali, una pagina può avere conteggio alto e non essere eseguita da molto tempo.

Algoritmo MFU (Most Frequently Used)

È l'opposto di LFU, la pagina con il conteggio più basso è probabilmente stata appena caricata e dovrà essere presumibilmente usata ancora (località dei riferimenti).

Algoritmo second chance (clock)

Si basa su una FIFO circolare basata su bit di reference: se il bit è a 0 si rimpiazza, se a 1 si mette a 0 e si analizza la pagina successiva.
Variante: Si usano più bit di reference.

Allocazione dei frame

Data una memoria con $N$ frame e $M$ processi è importante scegliere quanti frame allocare ad ogni processo non violando il fatto che ogni processo necessita di un minimo numero di pagine per poter essere eseguito in quanto l’istruzione interrotta da un page fault deve esser fatta ripartire. Pertanto il numero di pagine deve essere uguale al massimo numero di indirizzi specificabile in un’istruzione. I valori tipici vanno da 2 a 4 frame. Inoltre lo schema di allocazione può essere fisso, in cui un processo ha sempre lo stesso numero di frame, o variabile, in cui il numero di frame allocati può variare durante l’esecuzione. Se il numero di pagine è minore al massimo numero di indirizzi specificabile in un’istruzione, si potrebbe verificare una situazione di costante page fault per il processo. Una volta specificato questo vincolo, è possibile classificare gli algoritmi in due famiglie, a seconda della politica di allocazione dei frame: rimpiazzamento locale o globale. Nel primo caso i frame vittima possono essere scelti solo tra i frame allocati dal processo stesso (sceglie la vittima tra i frame che ha); in questo modo il numero di frame per processo rimane fisso. Se si parla di rimpiazzamento globale, la vittima può essere scelta tra tutti i frame in memoria, quindi anche degli altri processi. In questo modo è più difficile tracciare il tasso di page fault, ma in generale questo metodo dinamico aumenta il throughput ed è per questo preferito. Vediamo un po' più in dettaglio la differenza tra allocazione fissa e variabile.

Allocazione fissa

Allocazione in parti uguali

Dati $m$ frame e $n$ processi si alloca ad ogni processo $\frac{m}{n}$ frame.

Allocazione proporzionale

Alloca secondo la dimensione del processo, parametro non sempre significativo in quanto la priorità può essere più significativa.

Allocazione variabile

Permette di modificare dinamicamente le allocazioni ai vari processi. Dobbiamo però capire in che modo effettuare le allocazioni. Esse avvengono in base al calcolo del working set o della page fault frequency (PFF).

Calcolo del working set

Si definisce working set la quantità di memoria che un processo richiede per svolgere le proprie funzioni in un dato istante $t$ . Il working set dipende dalla località del programma (un processo passa da una località di indirizzi all’altra durante la sua esecuzione come array, procedure e moduli) ed è per questo definito in funzione del tempo.
Quindi un criterio per rimodulare l’allocazione dei frame consiste nel calcolare quali sono le richieste effettive di ogni processo in base al modello della località. Idealmente un processo necessita di un numero di frame pari alla sua località. Ma come la misuro? Effettuando una stima!

Modello del working set

Per la stima del working set, un metodo semplice quanto veloce consiste nel considerare un dato intervallo di riferimenti $Δ$ : tutte le pagine che compaiono nell'intervallo (chiamato finestra del working set) fanno parte del working set ed il numero ne costituisce la cardinalità (dimensione). Ovviamente si deve prestare attenzione alla dimensione di $Δ$ . Se è troppo piccolo è poco significativo, se è troppo grande copre varie località e se vale infinito comprende tutto il programma. Vediamo ora come calcolare approssimativamente il working set.
Il working set viene calcolato approssimando tramite timer e bit di reference: si usa un timer che interrompe periodicamente la CPU; all’inizio di ogni periodo i bit di reference vengono posti a 0 e ad ogni interruzione del timer le pagine vengono scansionate; quelle con bit di reference a 1 si trovano nel working set, quelle con valore 0 vengono scartate.
L’accuratezza aumenta in base al numero di bit e alla frequenza di interruzioni. La richiesta totale di frame è $D = \sum_{i} W S S_{i}$ , dove $W S S_{i}$ è la dimensione del $W S_{i}$ . Se $D$ è maggiore del numero totale di frame si verifica un fenomeno chiamato thrashing in cui un processo spende tempo di CPU continuando a swappare pagine da e verso la memoria. Di conseguenza i nuovi processi "rubano" frame ai vecchi processi aumentando il numero di page fault, portando ad un declino costante dell'utilizzo della CPU. Si deve pertanto stimare con esattezza il numero di frame necessari a un processo per non entrare in thrashing.

Frequenza dei page fault

Una soluzione alternativa e più accurata del working set è la frequenza dei page fault: si stabilisce un tasso di page fault accettabile. Se quello effettivo è troppo basso il processo rilascia dei frame, se è troppo alto ne ottiene altri.

Conclusioni

La selezione della dimensione della pagina deve essere fatta accuratamente in quanto si deve sempre
fare un trade-off:

Pagine piccole:

Frammentazione.
Molte entry nella page table.
Costo di lettura e scrittura non ammortizzato.
Località.

Pagine grandi:

Frammentazione interna significativa.
Grande dimensione della page table.
I/O overhead.
Grande granularità, si deve anche trasferire ciò che non è necessario.

Naturalmente la struttura dei programmi influisce sul numero di page fault e in alcuni casi esistono frame che non devono essere mai rimpiazzati come frame corrispondenti a pagine del kernel e altri corrispondenti a pagine usate per trasferire dati da e verso I/O. Questi subiscono il blocco di frame (frame locking).