Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Marco Lapegna » 14.Gli algoritmi di avvicendamento delle pagine


Sistemi operativi

Gli algoritmi di avvicendamento delle pagine

Algoritmo First–In–First–Out (FIFO)

Viene sostituita la pagina presente in memoria da piu’ tempo

Esempio: processo di 8 pagine (0,..,7)

3 frame (3 pagine per ciascun processo possono trovarsi in memoria contemporaneamente).

Algoritmo First–In–First–Out (FIFO)

Algoritmo First–In–First–Out (FIFO)


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

Anomalia di Belady

Esempio: sequenza: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Anomalia di Belady

Anomalia di Belady


Algoritmo ottimo (OPT)

Viene sostituita la pagina che non verrà usata per il periodo di tempo più lungo.

Esempio: 4 frame, con stringa dei riferimenti 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Algoritmo ottimo (OPT)

Algoritmo ottimo (OPT)


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 ottimo

Con la stessa sequenza l’algoritmo FIFO produce 15 page faults

FIFO/OPT = 15/9 = 1.66 ⇒ FIFO 66% piu’ lento di OPT

Algoritmo ottimo

Algoritmo ottimo


Algoritmo Least–Recently–Used (LRU)

Viene sostituita la pagina che non e’ referenziata da piu’ tempo

Esempio: 4 frame con stringa di riferimenti 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Algoritmo Least–Recently–Used (LRU)

Algoritmo Least–Recently–Used (LRU)


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

ESEMPIO algoritmo LRU

LRU/OPT = 12/9 = 1.33 = LRU 33% piu’ lento di OPT

ESEMPIO algoritmo  LRU

ESEMPIO algoritmo LRU


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 Least–Frequently–Used (LFU)

Viene sostituita la pagina meno frequentemente utilizzata

Esempio: 4 frame con stringa di riferimenti 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

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

Algoritmo Least–Frequently–Used (LFU)

Algoritmo Least–Frequently–Used (LFU)


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

1a variante dell’algoritmo FIFO: seconda chance

Implementazione con un bit di accesso

Quando una pagina viene referenziata si pone bit=1

Quando le pagine raggiungono la testa della lista

  • Se bit=1 si sposta la pagina in fondo alla lista e si pone bit=0
  • Se bit=0 la pagina viene rimossa
1a variante dell’algoritmo FIFO: seconda chance

1a variante dell'algoritmo FIFO: seconda chance


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

Esempio: clock algorithm


Allocazione dinamica di frame

Modello “working set”

Avvicendamento “Page Fault Frequency (PFF)”

Numero di frame variabile (allocazione variabile di frame)

Allocazione dinamica di frame

Allocazione dinamica di frame


Working set

Il working set di un processo W(t, w), e’ l’insieme delle pagine referenziate dal processo nell’intervallo di tempo [t – w , t ]

Working set

Working set


Dimensione del working set

Il working set di un processo e’ caratterizzato da

  • w (intervallo temporale di osservazione fissato)
  • t (istante di osservazione variabile)
Insieme dinamico

Insieme dinamico


Dimensione del working set

La dimensione del working set cresce asinoticamente al crescere di w

Dimensione del working set

Dimensione del working set


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

Page Fault Frequency

Si stabilisce una frequenza di page fault “accettabile”.

  • Se la frequenza effettiva è troppo bassa, il processo rilascia dei frame.
  • Se la frequenza è troppo elevata, il processo acquisisce nuovi frame.
Dimensione del working set

Dimensione del working set


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

Struttura dei programmi C

  • Pagine di 4096 byte (4×1024)
  • A[ ] [ ] = new int[1024] [1024];
  • Ciascuna riga viene memorizzata in una pagina (1024 pagine)
Struttura dei programmi C

Struttura dei programmi C


Altre considerazioni

Altre considerazioni

Altre considerazioni


Contenuti della prossima lezione

La gestione della memoria secondaria

  • Struttura logica dei dischi
  • Algoritmi di scheduling del disco
  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion