Marco Lapegna » 14.Gli algoritmi di avvicendamento delle pagine

Sistemi operativi

Gli algoritmi di avvicendamento delle pagine

Algoritmo FIFO

Idea di base: una pagina presente in memoria da molto tempo non verra’ piu’ refernziata

Vantaggi:

• Facile da implementare (coda FIFO)
• Basso overhead

Svantaggi

• Rischio di sostituire pagine molto utilizzate e per questo presenti in memoria da molto tempo
• Anomalia di Belady

Algoritmo ottimo (OPT)

Si puo’ dimostrare che minimizza il numero di page faults

Problema: Come si può conoscere l’identità della pagina?

Di solo interesse teorico: viene impiegato per misurare le prestazioni (comparative) degli algoritmi con valenza pratica

Esempio: FIFO/OPT = 10/6 = 1.67 ⇒ FIFO 67% piu’ lento di OPT

Algoritmo Least–Recently–Used (LRU)

LRU/OPT = 8/6 = 1.33 ⇒ LRU 33% piu’ lento di OPT

migliori prestazioni rispetto all’algoritmo FIFO ma con un maggiore overhead

Favorisce i processi che esibiscono il principio di localita’ temporale

Implementazione dell’algoritmo LRU

Implementazione con registro

• Ciascuna pagina ha un registro; ogni volta che si fa riferimento alla pagina si copia l’orologio nel registro.
• Quando si deve rimuovere una pagina, si analizzano i registri per scegliere quale pagina cambiare.
• Overhead per la ricerca della pagina “piu’ vecchia” non refernziata

Implementazione dell’algoritmo LRU

Implementazione con lista:

• Le pagine in memoria sono organizzate secondo una lista; ogni volta che si fa riferimento alla pagina, la si sposta in testa alla coda
• Quando si deve rimuovere una pagina, si elimina la pagina in coda alla lista
• Overhead per la gestione della lista.

Algoritmo LRU

Idea di base: una pagina presente in memoria che non e’ referenziata da molto tempo non verra’ piu’ referenziata

Vantaggi:

• Piu’ efficiente dell’algoritmo FIFO

Svantaggi

• Difficile da implementare
• Alto overhead

Algoritmo LFU

Idea di base: una pagina presente in memoria che non e’ molto referenziata sara’ poco referenziata anche in futuro

Vantaggi:

• Piu’ efficiente dell’algoritmo FIFO

Svantaggi

• Rischio di sostituire pagine da poco presenti in memoria e per questo poco referenziate rispetto ad altre (NO localita’ temporale)
• Alto overhead

1a variante dell’algoritmo FIFO: seconda chance

Il principale difetto dell’algoritmo FIFO e’ che sostituisce pagine presenti in memoria da molto tempo e che potrebbero essere molto utilizzate

IDEA: dare una seconda opportunita’ alle pagine prima di essere rimosse

2a variante dell’algoritmo FIFO: clock algorithm

• Simile all’algoritmo FIFO seconda chance
• Pagine organizzate secondo una lista circolare
• Si scorrono le pagine presenti nella lista:
• Se bit=1 :
  • Si pone il bit di riferimento a 0.
  • Si lascia la pagina in memoria.
  • Si esamina la pagina successiva (in ordine di clock), in base alle stesse regole.
• Se bit=0
  • Si rimpiazza la pagina

Esempio: clock algorithm

Esempio: clock algorithm

Modello gestione dei w.s.

I metodi di avvicendamento basati sul modello del working set, allocano in memoria solo le pagine del processo appartenenti ai working set con w fissato

Problema: Dimensione di w

• w troppo piccolo: continuo avvicendamento di pagine utili (trashing)
• w troppo grande: rischo di tenere in memoria pagine poco utilizzate

w.s. vs PFF

La strategia PFF ha alcuni vantaggi sul metodo basato su w.s. puro

• PFF determina le pagine da tenere in memoria solo all’occorrenza di un p.f., mentre il modello w.s. lo fa ad ogni riferimento _ minore overhead
• PFF si adatta dinamicamente all’andamento dell’utilizzo della memoria da parte del processo _ migliore utilizzo della memoria

Altre considerazioni

Altre considerazioni

Contenuti della prossima lezione

La gestione della memoria secondaria

• Struttura logica dei dischi
• Algoritmi di scheduling del disco