|
|
L’area di swap viene usata anche (e soprattutto) per ospitare temporaneamente pagine tolte dalla MP per fare spazio ad altre pagine che devono essere caricate in MP perché la loro assenza ha provocato un page fault. Ma quale pagina scegliamo come pagina vittima? Se una pagina vittima che è appena stata rimossa viene riferita da qualche processo si genera un page fault: la pagina deve essere ricaricata in MP, quindi abbiamo sprecato un sacco di lavoro!!! Viceversa, se scegliamo una pagina vittima che non verrà più usata da alcun processo non dovremo più preoccuparci di ricaricarla in MP. Un buon algoritmo di rimpiazzamento minimizza quindi il numero di page fault. Di seguito alcuni algoritmi di rimpiazzamento:
Algoritmo di rimpiazzamento FIFO
Come pagina vittima sceglie quella arrivata da più tempo in Memoria Principale (non c’è bisogno di associare a ogni pagina il tempo di arrivo, ci basta una coda FIFO). E’ in idea semplice, ma non necessariamente buona, infatti: se la pagina contiene del codice di inizializzazione del processo, usato solo all’inizio, OK, non servirà più ma se la pagina contiene una variabile inizializzata all'inizio e usata per tutta l’esecuzione del codice? Che l’algoritmo FIFO non sia una buona strategia di rimpiazzamento è confermato dal fatto che soffre della cosiddetta Anomalia di Belady. Aumentando il numero di frame (pagine), e usando l’algoritmo FIFO, il numero di page fault (pagine richieste i n MP) può addirittura aumentare!!! Per esempio osservando la seguente stringa di pagine richieste in memoria principale: 1 2 3 4 1 2 5 1 2 3 4 5, avremo le seguenti page fault in relazione al numero di frame utilizzati:
Algoritmo di rimpiazzamento ottimale
E’ un algoritmo che non soffre come l’ algoritmo FIFO dell' anomalia di Belady. Esso produce il numero minimo di page fault (richiesta di pagine) a parità di frame disponibili. In questo algoritmo la pagina vittima è quella che sarà usata più in là nel tempo. Si deve quindi conoscere anticipatamente la serie di pagine che verrà richiesta. Di seguito un esempio:
Visto che però il futuro non si può ancora conoscere questo algoritmo nella realtà non è concretizzabile. Realizzabile è invece l’ algoritmo di rimpiazzamento LRU.
Algoritmo di rimpiazzamento LRU
Questo algoritmo di rimpiazzamento cerca di approssimare quello ottimale sostituendo la pagina che non è stata usata da più tempo. Guarda all'indietro anziché che in avanti in quanto almeno il passato lo conosciamo! LRU è un buon algoritmo di rimpiazzamento, ma è difficile da implementare in modo efficiente.
Una possibile implementazione di LRU può essere realizzata mediante uno stack. Si deve tenere uno stack dei numeri di pagina inseriti in memoria. La dimensione dello stack sarà uguale numero di frame del processo. Ad ogni accesso il numero di pagina viene spostato in. cima allo stack e la pagina in fondo allo stack è la LRU, la vittima! La gestione dello stack è però costosissima se fatta via softwere (lo stack va aggiornato ad ogni riferimento alla memoria).
Un’ altra implementazione è mediante un contatore. Ad ogni pagina è associato un campo. Un contatore viene incrementato ad ogni riferimento (chiamata) di pagina, e il valore del contatore è scritto nel campo di quella pagina. La pagina con il campo contatore più piccolo è la vittima (quella che viene richiamata meno spesso). Sia il contatore che lo stack devono essere aggiornati ad ogni riferimento in memoria: se facciamo tutte le operazioni via software l’overhead che ne risulta è inaccettabile! Molti processori forniscono un semplice supporto hardwere che che permette di approssimare LRU: il Reference bit, un bit associato ad ogni pagina di un processo. Quando un processo parte, i reference bit delle sue pagine sono tutti inizializzati a 0 dal sistema. Quando viene riferita una pagina (in lettura o in scrittura) l’architettura mette a 1 il reference bit di quella pagina. Dopo un certo tempo un timer azzera tutti i bit reference. Quindi, in ogni istante, possiamo sapere quali pagine di un processo sono state usate recentemente e quali no. Non possiamo però sapere in quale ordine è stato fatto riferimento alle pagine usate. Nonostante tutto questa tecnica garantisce una grande velocità di elaborazione che compensa i suoi difetti di efficienza.
Algoritmo della Seconda Chance
E’ un misto tra l’ algoritmo di rimpiazzamento FIFO e LRU col reference bit. In caso di page fault, si considera la pagina in fondo alla coda (la più vecchia): se il suo reference bit è (ancora) a 0, allora la pagina viene rimossa. Se il reference bit della pagina è a 1, allora lo si azzera: diamo alla pagina una seconda chance. Si passa quindi ad esaminare la seconda pagina più vecchia della FIFO. Nel caso peggiore, l’algoritmo trova che tutte le pagine della coda hanno il reference bit a 1. Allora, una volta percorsa tutta la coda ritorna alla pagina più vecchia e la sceglie come vittima. In questo caso la sostituzione con seconda chance si riduce ad una sostituzione FIFO. Se l’ hardwere fornisce sia il reference che il dirty bit, le pagine possono essere raggruppate in 4 classi:
(0, 0) né usata né scritta: ottima da rimpiazzare
(0, 1) non usata di recente: ma modificata: meno buona
(1, 0) usata di recente: è ancora meno opportuno rimpiazzarla
(1, 1) in uso e modificata: la peggiore candidata al rimpiazzamento.
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.