Domande e risposte sull'allocazione della memoria del sistema operativo # 3
Question:Quando si verifica un errore di pagina? Spiega varie strategie / algoritmi di sostituzione della pagina.
Answer:Nella tecnica di gestione della memoria di paging su richiesta, se una pagina richiesta per l'esecuzione non è presente nella memoria principale, si verifica un errore di pagina. Per caricare la pagina richiesta nella memoria principale, un frame di pagina libero viene cercato nella memoria principale e allocato. Se nessun frame della pagina è libero, il gestore della memoria deve liberare un frame scambiando il suo contenuto nella memoria secondaria e quindi fare spazio per la pagina richiesta. Per scambiare le pagine, vengono utilizzati molti schemi o strategie.
Varie strategie / algoritmi di sostituzione delle pagine
The Optimal Page Replacement Algorithm- Questo algoritmo sostituisce la pagina che non verrà utilizzata per il periodo di tempo più lungo. Nel momento in cui si verifica l'errore di pagina, alcune serie di pagine sono in memoria. Si farà riferimento a una di queste pagine nelle istruzioni successive. Non è possibile fare riferimento ad altre pagine fino a 10.100 o forse 1000 istruzioni. Queste informazioni possono essere memorizzate con ogni pagina nella PMT (Page Map Table).
P # base Compensare MISC 1 10 2 NIL 3 1000 ... 10 100 L'algoritmo di pagina ottimale rimuove semplicemente la pagina con il maggior numero di istruzioni di questo tipo, il che implica che sarà necessario in un futuro più lontano. questo algoritmo è stato introdotto da molto tempo ed è difficile da implementare perché richiede una conoscenza futura del comportamento del programma. Tuttavia è possibile implementare la sostituzione ottimale della pagina alla seconda esecuzione utilizzando le informazioni di riferimento della pagina raccolte alla prima esecuzione.
NRU(Not Recently Used) Page Replacement Algorithm- Questo algoritmo richiede che ogni pagina abbia due bit di stato aggiuntivi "R" e "M" chiamati bit di riferimento e bit di cambio rispettivamente. Il bit di riferimento (R) viene impostato automaticamente su 1 ogni volta che si fa riferimento alla pagina. Il bit di cambio (M) è impostato a 1 ogni volta che la pagina viene modificata. Questi bit vengono memorizzati nel PMT e vengono aggiornati su ogni riferimento di memoria. Quando si verifica un errore di pagina, il gestore della memoria ispeziona tutte le pagine e le divide in 4 classi in base ai bit R e M.
Class 1: (0,0) - né usato di recente né modificato - la migliore pagina da sostituire.
Class 2: (0,1) - non usato di recente ma modificato - la pagina dovrà essere scritta prima della sostituzione.
Class 3: (1,0) - usato di recente ma pulito - probabilmente verrà riutilizzato presto.
Class 4: (1,1) - usato e modificato di recente - probabilmente verrà utilizzato di nuovo e sarà necessario scrivere prima di sostituirlo.
Questo algoritmo rimuove una pagina a caso dalla classe non vuota con il numero più basso.
Vantaggi:
È facile da capire.
È efficiente da implementare.
FIFO (First in First out) Page Replacement Algorithm- È uno dei più semplici algoritmi di sostituzione della pagina. La pagina più vecchia, che ha trascorso più tempo in memoria, viene scelta e sostituita. Questo algoritmo è implementato con l'aiuto della coda FIFO per mantenere le pagine in memoria. Una pagina viene inserita all'estremità posteriore della coda e viene sostituita all'inizio della coda.
Nella figura, la stringa di riferimento è 5, 4, 3, 2, 5, 4, 6, 5, 4, 3, 2, 6 e ci sono 3 frame vuoti. I primi 3 riferimenti (5, 4, 3) causano errori di pagina e vengono inseriti in frame vuoti. Il riferimento successivo (2) sostituisce la pagina 5 perché la pagina 5 è stata caricata per prima e così via. Dopo 7 errori di pagina, il riferimento successivo è 5 e 5 è già in memoria, quindi nessun errore di pagina per questo riferimento. Allo stesso modo per il riferimento successivo 4. Il segno + mostra l'ingresso di una pagina mentre il cerchio mostra la pagina scelta per la rimozione.
Vantaggi
FIFO è facile da capire.
È molto facile da implementare.
Svantaggio
Non sempre bravo nelle prestazioni. Può sostituire una pagina attiva per portarne una nuova e quindi può causare immediatamente un errore di pagina di quella pagina.
Un altro effetto collaterale inaspettato è l'anomalia FIFO o l'anomalia di Belady. Questa anomalia indica che la percentuale di errori di pagina può aumentare all'aumentare del numero di frame di pagina allocati.
Ad esempio, la figura seguente presenta la stessa traccia di pagina ma con una memoria maggiore. Qui il numero di frame della pagina è 4.
Qui gli errori di pagina sono 10 invece di 9.
LRU(Least Recently Used) Algorithm- L'algoritmo Meno di recente (LRU) sostituisce la pagina che non è stata utilizzata per il periodo di tempo più lungo. Si basa sull'osservazione che le pagine che non sono state utilizzate per molto tempo probabilmente rimarranno inutilizzate per molto tempo e dovranno essere sostituite.
Inizialmente, 3 frame di pagina sono vuoti. I primi 3 riferimenti (7, 0, 1) causano errori di pagina e vengono inseriti in questi frame vuoti. Il riferimento successivo (2) sostituisce la pagina 7. Poiché il riferimento alla pagina successiva (0) è già in memoria, non vi è alcun errore di pagina. Ora, per il riferimento successivo (3), la sostituzione di LRU vede che, dei tre frame in memoria, la pagina 1 è stata usata meno di recente, e quindi è stata sostituita. E così il processo continua.
Vantaggi
L'algoritmo di sostituzione della pagina LRU è silenzioso ed efficiente.
Non soffre dell'anomalia di Belady.
Svantaggi
La sua implementazione non è molto semplice.
La sua implementazione potrebbe richiedere una notevole assistenza hardware.