ESERCIZI
DETTAGLIO → STRINGA DI RIFERIMENTO
- è un concetto teorico e uno strumento di simulazione utilizzato per studiare e testare gli algoritmi di gestione della memoria
- sequenza di pagine (numeri o identificatori di pagine) che il processo richiede in un ordine specifico. Ogni numero nella stringa rappresenta una richiesta di accesso a una pagina da parte del processo.
- consente di determinare l’efficienza di un algoritmo, misurando il numero di page fault che si verificano per quella sequenza specifica
- il numero di page fault è pari al numero di volte in cui sostituisco una pagina con un altra, e devo farlo il meno possibile
- la sequenza di barre laterali in basso indicano page fault
Quale pagina rimuovere dalla RAM?
ALGORITMO OTTIMO (bench-mark)
STEP INIZIALE
quando la memoria è vuota (fase iniziale), ovviamente si verificano continui page fault, finchè si riempie tutta dall’alto al basso (la velocità di allocazione è maggiore della velocita di terminazione di un processo ovviamente, quindi nn ci vuole tanto)
CRITERIO DI SELEZIONE
al prossimo page fault si seleziona una vittima: l’algoritmo ottimo prevede di scegliere come vittima la pagina che non verrà più utilizzata per il periodo di tempo più lungo nel futuro
SCENARIO: PERDITA DI LOCALITA’
Quando il processo cambia completamente set di pagine (esempio, passa a un'altra fase o parte del codice), si verifica una perdita di località, e quindi può essere necessario sostituire più pagine in memoria in rapida successione. In questo caso, la scelta delle vittime diventa più “libera”, perché il set di pagine precedentemente utilizzato non è più rilevante.
FIFO → elimina il più vecchio → anomalia di Belady
è una coda sia nel modo in cui si accodano le pagine sia nella logica rimozione
PROPRIETA’ DI INCLUSIONE
a parità di tempo t, carico meno o uguale pagine di quando ho m+1 frames
- Questa proprietà garantisce che un aumento dei frame non porterà mai a un aumento del numero di page fault per gli algoritmi che rispettano la proprietà di inclusione
- in alcuni algoritmi come FIFO, un numero maggiore di frame può paradossalmente causare più page fault)
SECONDA CHANCE
Algoritmo di Sostituzione delle Pagine "Second Chance"
- cerca di individuare una pagina vecchia che non è stata referenziata recentemente. Questo lo rende più efficiente di FIFO, poiché evita di rimuovere pagine che sono ancora in uso.
- FIFO elimina il più vecchio in RAM senza interessarsi se è stata referenziata recentemente
Meccanismo
- La sua logica si basa sul controllo di un bit di riferimento (R) della pagina più vecchia.
Quando si verifica un page fault, il sistema operativo analizza la pagina più vecchia (in ordine FIFO).
- Se il bit R della pagina è 0
- la pagina è sia vecchia sia non utilizzata recentemente, quindi viene rimossa immediatamente dalla memoria.
- Se il bit R è 1
- la pagina, indipendentemente da quanto sia vecchia, è stata utilizzata di recente.
- Essendo la vittima potenziale secondo l’iterazione in ordine FIFO, Il bit R viene azzerato (set a 0) → gli tolgo la seconda chance e lo marco visivamente per esplicitarlo
- La pagina viene accodata alla fine della lista, come se fosse stata appena caricata in memoria.
- questo però nn lo fa l’immagine (vedi ultima colonna il 4)
- Il suo tempo di caricamento viene aggiornato al momento corrente.
- La ricerca continua con la pagina successiva nella lista.
Esempio
Immaginiamo una situazione in cui le pagine A, B, C, ecc., siano organizzate in una lista FIFO. Ogni pagina ha un tempo di caricamento che indica quando è stata caricata in memoria.
- Page fault al tempo 20:
- La pagina più vecchia è A, caricata al tempo 0.
- Se il bit R della pagina A è 0, questa viene rimossa.
- Se il bit R di A è 1, la pagina A viene spostata alla fine della lista, e il suo tempo di caricamento viene aggiornato a 20 (tempo in cui questa è stata referenziata). Il bit R viene azzerato.
- Proseguimento della ricerca:
- La ricerca continua con la pagina successiva nella lista, ad esempio la pagina B. La stessa logica si applica: se il bit R di B è 1, anche questa viene spostata in fondo alla lista e il suo bit viene azzerato.
Comportamento nel caso peggiore
Se tutte le pagine hanno il bit R impostato a 1, l'algoritmo diventa simile a un FIFO puro. In questo caso:
- Ogni pagina viene spostata alla fine della lista una per una.
- Alla fine, il sistema operativo ritorna alla prima pagina, che avrà il bit R azzerato (dopo essere stata "perdonata" nel primo ciclo) e viene rimossa.
SCORCIATOIA: nell’immagine d’esempio, ogni volta che hanno tutti la seconda chance per scorciatoia la toglie a tutti pk è la stessa cosa, e si riduce a FIFO
OROLOGIO → second chance in ordine OROLOGIO
L’unica differenza tra Seconda Chance e Orologio è che l’algoritmo della Seconda Chance è come se fosse un orologio che però parte sempre da mezzogiorno (PK segue l’ordinamento FIFO), quindi dall’elemento presente da più tempo in memoria.
LRU (LEAST RECENTLY USED) → sequenza linkata si pagina
L'algoritmo LRU si basa sull'idea che le pagine utilizzate più di recente saranno probabilmente utilizzate di nuovo presto
IMPLEMENTAZIONE
Implementazione Teorica di LRU
Per implementare LRU nella sua forma ideale, sarebbe necessario mantenere una lista collegata di tutte le pagine in memoria.
La pagina utilizzata più di recente sarebbe posizionata all'inizio, mentre quella meno utilizzata sarebbe alla fine (prime vittime) .
Tuttavia, aggiornare questa lista ad ogni riferimento della memoria è un'operazione molto costosa, sia in termini di tempo che di hardware. Questo rende l'implementazione diretta di LRU poco pratica.
NFU (Not Frequently Used) → 2 VERSIONI
VERSIONE 2 (Aging → etichetta)
Usa la tecnica di aging
- Ogni pagina ha una sequenza di bit binari che sostituisce il contatore numerico.
Ad ogni tick di clock (chiamata in memoria):
- Ogni sequenza di 8 bit associata a ogni pagina viene shiftata a destra
- la cifra più a destra scompare dalla sequenza
- Il valore di R viene aggiunto a sinistra (come bit più significativo).
l'algoritmo identifica la pagina da sostituire:
- Esaminando i contatori binari delle pagine.
- Scegliendo la pagina con il valore più basso (pk è un numero binario) nel contatore binario (cioè, la sequenza con più zeri verso sinistra)
VERSIONE 1→ (Contatore
Un metodo che rispecchia il concetto di eliminare il meno recente, più semplice seppur non equivalente consiste nell'utilizzare un contatore a 64 bit che viene incrementato automaticamente dopo ogni istruzione.
Ogni voce nella tabella delle pagine deve contenere
- un campo sufficiente a memorizzare il valore del contatore
R in NFU
Nel contesto di NFU (Not Frequently Used):
- Il bit R (Referenced) viene usato per incrementare un contatore assegnato a ogni pagina.
- Ad ogni tick di clock (o intervallo di tempo), il sistema operativo:
- Legge il valore di R (1=referenziato o 0=non referenziato) per ogni pagina.
- Somma il valore di R al contatore della pagina.
- Resetta R = 0 per prepararlo al prossimo tick.
Quando si verifica un page fault, l'algoritmo sostituisce la pagina con il valore del contatore più basso, che rappresenta la pagina meno recentemente utilizzata.
PROBLEMA
il contatore non si azzera mai, quindi le pagine che sono state frequentemente utilizzate in passato continueranno ad avere un valore di contatore alto, anche se non vengono più utilizzate da tempo.
ESEMPIO
- La pagina A venga referenziata 20 volte all'inizio.
- Il suo contatore cresce a 20.
- Successivamente, la pagina A non viene più referenziata per lungo tempo, mentre altre pagine vengono utilizzate frequentemente.
- Al momento del page fault, il sistema valuta i contatori.
- La pagina A avrà comunque un contatore alto (20) e non sarà sostituita, anche se non è più rilevante.
- Invece, una pagina che ha un contatore più basso ma che potrebbe essere stata utilizzata di recente, rischia di essere sostituita.
CARATTERISTICHE
- Non soffre dell’ANOMALIA DI BELADY
QUANDO CONVERGE A FIFO
- Quando ci sono pochissimi frame disponibili rispetto al numero totale di pagine, l'algoritmo Aging non può fare affidamento sulla frequenza di referenziamento (in quanto nessuna è mai referenziata), quindi seleziona il più vecchio → guarda un solo criterio su 2 come il FIFO
- Esempio: Hai solo 2 frame, ma ci sono 10 pagine che vengono continuamente referenziate in modo alternato.
- Risultato: Anche le pagine recentemente utilizzate verranno sostituite, perché non riescono a rimanere in memoria abbastanza a lungo per essere utili
- in caso di numero di frame sufficiente a contenere tutte le pagine, non ci saranno più page fault, perché tutte le pagine attive rimangono sempre in memoria. (ma questo vale per qualsiasi algoritmo di rimpiazzamento)
- Se le referenze alle pagine sono distribuite in modo uniforme
- Esempio: Hai 5 frame e ci sono 5 pagine che vengono referenziate alternativamente in modo ciclico (es. A → B → C → D → E → A...).
- Poiché nessuna pagina viene referenziata più frequentemente di altre, l'algoritmo Aging non riesce a trarre vantaggio dalla sua capacità di distinguere recenza e frequenza.
tutte le pagine sono referenziate con la stessa frequenza
NRU (Not Recently Used) → 4 categorie
Obiettivo di NRU
L'algoritmo NRU è un'approssimazione di LRU (Least Recently Used), come Aging e NFU, che utilizza un approccio più semplice per gestire la memoria. Invece di mantenere un ordine preciso delle pagine in base alla frequenza di utilizzo, NRU:
- Classifica le pagine in base a due bit: bit di referenziazione e bit di modifica.
- Sfrutta questa classificazione per decidere quali pagine espellere dalla memoria (scegliendo tra le meno recenti o meno utili).
I due bit utilizzati
- Bit di referenziazione (R):
- È impostato a 1 ogni volta che la pagina viene acceduta (letta o scritta).
- Viene periodicamente azzerato dal sistema operativo, così da capire se la pagina è stata usata recentemente.
- Bit di modifica (M):
- È impostato a 1 ogni volta che il contenuto della pagina viene modificato.
- Serve per identificare se la pagina deve essere salvata sul disco prima di essere rimossa (un'operazione costosa).
Le 4 classi di pagine
In base ai valori di R e M, le pagine vengono classificate in 4 categorie:
- MINIMA PRIORITA’: Classe 0 (R = 0, M = 0): Pagine non referenziate e non modificate.
- Sono le migliori candidate per essere rimosse, poiché non sono state utilizzate di recente e non richiedono salvataggio sul disco.
- Classe 1 (R = 0, M = 1): Pagine non referenziate ma modificate.
- la modifica è più importante pk la referenza dopo un po’ è azzerata
- Non usate di recente, ma devono essere salvate sul disco prima di essere rimosse.
- Classe 2 (R = 1, M = 0): Pagine referenziate ma non modificate.
- Usate di recente, ma non modificate; sono meno preferibili rispetto alle classi precedenti.
- Classe 3 (R = 1, M = 1): Pagine referenziate e modificate.
- Usate di recente e devono essere salvate sul disco; sono le ultime candidate per essere rimosse.
Processo di selezione della pagina vittima
Quando si deve liberare spazio in memoria, NRU segue questi passi:
- MMU scansiona le pagine
- Scelta della vittima
- Si seleziona una pagina a caso dalla classe con il valore più basso disponibile (da Classe 0 a Classe 3).
- Classe 0 ha la priorità massima (migliore vittima).
- Classe 3 ha la priorità minima (peggiore vittima).
- Aggiornamento e rimozione
- Se la pagina scelta è modificata (M = 1), viene salvata sul disco prima di essere rimossa.
- La pagina viene quindi rimossa dalla memoria.
Periodico reset dei bit di referenziazione
- Periodicamente, il sistema operativo:
- Azzera i bit di referenziazione (R) per tutte le pagine.
- Questo reset permette di capire quali pagine vengono effettivamente usate di recente.
- Le pagine con R = 0 nella prossima scansione saranno considerate "non recenti".
Limitazioni e punti deboli
- "Approssimazione grossolana":
- L'algoritmo è semplice ma non accurato come LRU, poiché classifica le pagine in sole 4 categorie.
- Caso casuale:
- all'interno della stessa classe, la pagina da rimuovere è scelta casualmente, il che potrebbe non essere sempre ottimale.
ALGORITMI BASATI SU WORKING SET → referenza e timestamp
OBIETTICO = stabilizzare l’asse y del grafico al crescere di x
SPIEGAZIONE
Il working set è definito come l'insieme minimo di pagine (in termini di numero e scelta pagine) che devono essere presenti in memoria, in un determinato istante, affinché il processo possa essere eseguito senza generare page fault. È un concetto fondamentale per ottimizzare l'uso della memoria e migliorare le prestazioni del sistema operativo.
Funzionamento dell'Algoritmo Working Set
L'algoritmo utilizza due strumenti principali:
- Bit di Referenziazione (R) → frequenza di recenza
- Indica se una pagina è stata referenziata di recente (R=1).
- Viene azzerato periodicamente per aggiornare lo stato delle pagine.
- Timestamp (Marcatore Temporale) → età
- Ogni pagina ha un timestamp che registra l'ultimo momento in cui è stata utilizzata.
- Questo aiuta a identificare se una pagina fa ancora parte del working set attuale.
Quando si verifica un page fault, l'algoritmo:
- Esamina le pagine presenti in memoria.
- Determina quali pagine non sono state utilizzate da un tempo significativo (tramite il timestamp e il bit R).
- Sostituisce la pagina non necessaria con la nuova.
Grafico del Working Set
- Nell'immagine, il grafico mostra:
- L'asse x: il numero di pagine utilizzate dal processo nel tempo
- L'asse y: la dimensione minima del working set necessaria per evitare page fault (dimensione = numero di pagine necessarie per eseguire il processo senza causare page fault)
- il working set ottimale contiene le pagine effettivamente richieste in un determinato istante di tempo
- La curva indica che il numero di pagine necessarie non cresce linearmente con il numero totale di pagine del processo, ma tende ad assestarsi su un valore stabile → stabile = politica di rimpiazzamento funzionante
Made with Bullet