1

Lezione T17Algoritmi di sostituzionedelle pagineSistemi Operativi (9 CFU), CdL Informatica, A. A. 2013/2014Dipartimento di Scienze Fisiche, Informatiche e MatematicheUniversità di Modena e Reggio Emiliahttp://weblab.ing.unimo.it/people/andreolini/didattica/sistemi-operativi

2

Quote of the day(Meditate, gente, meditate ...)

“The running time of programs in a paging machine generally increases as the store in which programs are constrained to run decreases. Experiments, however, have revealed cases in which the reverse is true: a decrease in the size of the store is accompanied by a decrease in running time.”Laszlo Belady (1928-)Ingegnere meccanico ed aeronauticoPioniere degli algoritmi di caching

3

INTRODUZIONE

4

Il modello di sistema considerato(Lo scenario su cui valutare gli algoritmi)

Si consideri un sistema con le seguenti caratteristiche.

SO con demand paging e sostituzione delle pagine.Esiste un solo tipo di page fault: il major page fault.Tre frame rimasti liberi da allocare.Il SO è soggetto alla sequenza di accessi alle pagine(indirizzi semplificati)7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

5

Gli algoritmi considerati(FIFO è il peggiore, come al solito)

FIFO.Ottimale.LRU.Approssimazioni di LRU.

6

Criterio di valutazione(Numero di page fault)

Il criterio di valutazione è il numero di page fault.Tanto è minore il numero di page fault, tanto più efficace è l'algoritmo.

7

ALGORITMO FIFO

8

First In, First Out(La pagina vittima è quella presente in memoria da più tempo)

Funzionamento:Ad ogni pagina si associa l'istante temporale(timestamp) di caricamento in memoria.Non è necessario calcolare esplicitamente iltimestamp; si può costruire una coda FIFO con Ipuntatori alle strutture delle pagine inserite inmemoria.La pagina vittima è quella presente in memoriacentrale da più tempo (o in testa alla coda).Quando una pagina è acceduta, viene inserita infondo alla coda.

T17-simulazione-FIFO_luc.pdf

9

FIFO: vantaggi(Perché implementare ed usare FIFO)

È un algoritmo semplice da implementare.Il più semplice.

È eseguibile su piattaforme hardware non dotate di clock hardware.

10

FIFO: svantaggi(Perché NON implementare e NON usare FIFO)

Le prestazioni sono pessime se la memoria è acceduta “ciclicamente” con frequenza minore rispetto a quella di rimpiazzo.L'algoritmo FIFO soffre di una particolare anomalia, detta anomalia di Belady.

11

Anomalia di Belady(La frequenza di page fault aumenta con il numero di frame liberi)

Anomalia di Belady: la frequenza di page fault può aumentare con il numero di frame disponibili al SO.Fenomeno scoperto nel 1969 da un ricercatore ungherese, Laszlo Belady.Risultato controintuitivo: se si ha più memoria libera, ci si aspetta di ridurre i page fault!

12

Un esperimento(Che mostra l'anomalia in azione)

Si consideri la sequenza di riferimenti:1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Tale sequenza presenza un pattern di accesso ciclico ad 1, 2, 3 e 4, opportunamente distanziato.Si calcola il numero di page fault (sostituzioni) ottenuti dando in pasto la sequenza di riferimenti a FIFO con 1, 2, 3, 4, … frame liberi.T17-simulazione-Belady.odp

13

Visualizzazione dell'anomalia(Salta subito agli occhi)

Si grafica il numero di page fault ottenuti in ciascun esperimento, in funzione del numero di frame liberi.Si dovrebbe vedere una zona per cui il grafico è crescente.

14

Frequenza page fault vs. frame liberi(Eccolo, il grafico)Numero di

page fault

1

2

3

4

5

6

7

8

9

10

11

12

All'aumentare delnumero di frameliberi, il numerodi page faultaumenta!

1 2 3 4 5 6 7

Numero diframe liberi

15

Perché si verifica l'anomalia?(Accesso ciclico distanziato + FIFO senza memoria = page fault continui)

Un processo richiede consecutivamente un insieme di pagine in maniera ciclica.L'insieme delle pagine richieste ciclicamente ha una dimensione uguale o maggiore del numero di frame fisici liberi.Le sequenze cicliche sono distanziate in modo tale che FIFO “perda memoria” delle pagine accedute in precedenza.

→ Può capitare che FIFO stronchi di continuo lepagine accedute al passo successivo.

→ Con il numero di frame può aumentare anche ilnumero di sostituzioni (page fault).

16

ALGORITMO OTTIMALE

17

OPT(La pagina vittima è quella che sarà acceduta nel futuro più lontano)

Funzionamento:La pagina vittima è quella che non sarà acceduta per ilpiù lungo periodo di tempo nel futuro.

T17-simulazione-OPT.pdf

18

OPT: vantaggi(Perché implementare ed usare OPT)

L'algoritmo OPT minimizza il numero di page fault in ogni scenario.L'algoritmo OPT elimina l'anomalia di Belady.

19

OPT: svantaggi(Perché NON implementare e NON usare OPT)

L'algoritmo OPT è impossibile da implementare! Il kernel non è in grado di prevedere il futuro.

Si confronti quanto detto per SJF. → L'algoritmo OPT è utile come pietra di paragone

per gli altri algoritmi.Più ci si allontana da OPT in termini di page fault, piùl'algoritmo è peggiore.

20

Perché minimizza i page fault?(Si mantengono le pagine con probabilità di accesso più elevata possibile)

Si elimina la pagina meno utilizzata nel futuro.→ Le pagine rimanenti hanno la probabilità più

alta di essere accedute.→ Si massimizza la probabilità di trovare una

pagina in memoria centrale.→ Si minimizza la probabilità di avere un page

fault.→ Si minimizza il numero di page fault.

21

Perché non ha l'anomalia di Belady?(Perché vede nel futuro)

Le pagine accedute ciclicamente non hanno la probabilità di accesso più bassa (altrimenti, non sarebbero accedute ciclicamente).L'algoritmo ottimale “vede nel futuro” e, una volta portatele in memoria centrale, non le seleziona più come vittime.

22

Cosa succede aggiungendo frame?(La frequenza di page fault non può aumentare)

Si supponga di aggiungere frame liberi al SO.Il SO è in grado di tenere stabilmente in memoria centrale più pagine accedute ciclicamente.

→ Queste non provocano più page fault di quanti nevenivano provocati con meno pagine.

Le altre pagine accedute meno frequentemente tendono a non essere rimosse più dalla memoria.

→ Queste non provocano più page fault di quanti nevenivano provocati con meno pagine.

23

Una approssimazione di OPT(Si trasla all'indietro il tempo, virtualmente)

La differenza fondamentale fra FIFO e OPT è la seguente.

L'algoritmo FIFO guarda all'istante in cui la pagina èstata caricata in memoria centrale.L'algoritmo ottimale guarda all'istante in cui lapagina verrà usata.

Si può tentare il seguente esperimento concettuale; sostituire la frase:

“non verrà usata per il periodo più lungo”con la frase

“è stata usata di meno nel passato recente”.

24

Perché dovrebbe funzionare?(Per via del principio di località degli accessi)

Il processo che esegue un programma ben scritto segue il principio di località spazio-temporale.

Il codice appena acceduto ha elevata probabilità diessere acceduto nuovamente nell'immediato futuro.Il codice spazialmente vicino a quello appenaacceduto ha elevata probabilità di essere acceduto.

In tali condizioni, il processo tenderà a comportarsi, nel futuro, come si è comportato nel passato.Programma ben scritto: un programma il cui flusso è sequenziale a grandi tratti.

25

ALGORITMO LRU

26

Least Recently Used(La pagina vittima è quella acceduta di meno nel passato)

Funzionamento:Si associa a ciascuna pagina l'istante in cui è stataacceduta per l'ultima volta.La pagina vittima è quella acceduta di meno negliultimi k accessi di memoria.

T17-simulazione-LRU_luc.pdf

27

LRU: vantaggi(Perché implementare ed usare LRU)

L'algoritmo LRU è nettamente migliore di FIFO.L'algoritmo LRU non è così distante da OPT.L'algoritmo LRU elimina l'anomalia di Belady.

28

LRU: svantaggi(Perché NON implementare e NON usare LRU)

L'algoritmo LRU può sostituire pagine inattive da tempo in procinto di essere accedute nuovamente.L'algoritmo LRU richiede un supporto hardware per la marcatura efficiente dell'ultimo istante di uso delle pagine.

29

Supporto hw per LRU: contatori d'uso(La CPU scandisce un “tempo virtuale”)

Si introduce nell'elemento della tabella delle pagine un campo, detto “istante d'uso”.Si aggiunge alla CPU un registro contatore che si incrementa di uno ad ogni riferimento alla memoria.Ad ogni riferimento di pagina si copia il valore del registro contatore nel campo “istante d'uso”.

30

Contatori d'uso: vantaggi e svantaggi(LRU è facile da implementare, ma inefficiente)

Vantaggi.LRU si traduce in una semplice scansione della tabelladelle pagine, alla ricerca dell'elemento con l'istanted'uso più piccolo.

Svantaggi.Si richiede una scansione lineare della tabella.Si richiede una scrittura in memoria per ogni accesso.È necessario gestire gli overflow del contatore.

31

Supporto hw per LRU: stack(In cima pagina più recente, in coda pagina meno recente)→ →

Si introduce nella CPU una implementazione microprogrammata di uno stack di lunghezza finita.Gli elementi dello stack sono numeri di pagina.Ad ogni riferimento di pagina si estrae (se esiste) il numero di pagina dallo stack e si piazza in cima.

32

Funzionamento dello stack(Prima e dopo l'accesso ad una pagina)

Sequenza di accessi4 7 0 7 1 0 1 2 1 2 7 1 2

1

0

7

4

Stackprima di a

2

2

1

0

4

Stackdopo b

7

a b

33

Stack: vantaggi e svantaggi(Si trova subito la pagina LRU, ma a che costo!)

Vantaggi.L'individuazione della pagina meno recente è moltoefficiente (coda dello stack).

Svantaggi.È possibile l'estrazione in mezzo allo stack serve→una lista collegata di elementi, con puntatori specialialla cima ed alla coda.

34

Algoritmi basati su stack(Eliminano l'anomalia di Belady)

Gli algoritmi OPT e LRU non soffrono dell'anomalia di Belady. È un caso? No!Entrambi gli algoritmi fanno parte di una classe più ampia di algoritmi di sostituzione (stack algorithm) che non subiscono mai l'anomalia di Belady. Uno stack algorithm gode della seguente proprietà.Se S(n)=insieme delle pagine mantenute in memoria con n frame, allora S(n) ⊆ S(n+1).

35

APPROSSIMAZIONI DI LRU

36

Uso di un bit di riferimento(Ciò che veramente fornisce l'hardware odierno)

Quasi nessuna architettura hardware fornisce I registri contatore/clock o uno stack per la gestione efficiente dell'ordinamento temporale in LRU.Per evitare l'uso di FIFO, si usa un bit di riferimento.

Bit presente nell'elemento della tabella delle pagine.Bit impostato ad 1 dall'hardware ogniqualvolta lapagina corrispondente viene acceduta.

Inizialmente, tutti i bit di riferimento sono azzerati.

37

Le limitazioni di un singolo bit(Un bit è poco)

Con un solo bit di riferimento:si possono distinguere le pagine accedute da quellenon accedute.non si riesce a ricostruire l'ordine temporale di accessoalle pagine.

→ Servono più bit di riferimento.

38

Uso di più bit di riferimento(Più bit consentono di ricostruire la storia degli accessi)

IDEA: si registrano più bit di riferimento ad intervalli regolari.Ad esempio, ciascun elemento della tabella delle pagine contiene un byte di riferimento, segnaposto per 8 bit di riferimento.

Storia dell'uso della pagina negli ultimi 8 intervalli dicampionamento.00000000: la pagina non è stata acceduta negli ultimi8 intervalli di campionamento.11111111: la pagina è stata acceduta in ciascuno degliultimi 8 intervalli di campionamento.

39

Aggiornamento dei bit(Ad ogni interruzione di clock)

Ad intervalli di campionamento regolari (ad esempio, ogni 100ms), il clock di sistema genera una interruzione.La relativa Interrupt Service Routine invoca, fra le altre, una routine di aggiornamento dei bit di riferimento.

Shift del byte di riferimento di 1 bit verso il LeastSignificant Bit.Inserimento del valore del bit di riferimento nel MostSignificant Bit.

40

Approssimazione di LRU(Con otto bit di riferimento)

0 1 0 0 1 1 0 0

LSB MSB

8 intervalli fa adesso

Prima della routine di aggiornamento

Dopo la routine di aggiornamento

11 0 0 1 1 0 0

LSB MSB

1

Bit di riferimentodella pagina

...

Tabelladelle pagine

8 intervalli fa adesso

shift

41

Considerazioni 1/2(Per semplificarsi la vita)

I byte di riferimento possono essere interpretati come numeri interi unsigned. In tal caso, la pagina acceduta meno recentemente (LRU) è quella avente il valore del byte di riferimento più piccolo.Non è assolutamente garantita l'unicità dei valori dei byte di riferimento. Ad un dato istante, possono esistere più pagine accedute meno recentemente.

Possono essere rimpiazzate tutte.Se ne può scegliere una con il criterio FIFO.

42

Considerazioni 2/2(Per semplificarsi la vita)

Solitamente, il numero di bit di riferimento è pari alla lunghezza della parola definita dall'architettura.

In tal modo, le operazioni di shift e di inserimentosono velocissime.

Si può anche decidere di non usare alcun contenitore di bit di riferimento!

Si fa uso del solo bit di riferimento.Algoritmo second chance.

43

Second Chance (Clock)(La pagina vittima è quella presente in memoria da più tempo e non riferita)

Variante dell'algoritmo FIFO.Funzionamento:

Si sceglie la pagina presente in memoria centrale dapiù tempo, come in FIFO.Si controlla il bit di riferimento di tale pagina.Bit = 0: si sostituisce la pagina.Bit = 1:

si azzera il bit di riferimento della pagina e siaggiorna il suo istante di arrivo a quello attuale.si passa alla pagina successiva in ordine FIFO.

44

Motivazione dell'algoritmo(Perché si dà una seconda chance alla pagina)

Se ad una pagina è data una “seconda chance”, essa non sarà sostituita:

fino a quando tutte le altre pagine non siano statesostituite.oppure fino a quando tutte le altre pagine nonabbiano avuto la loro seconda chance.

→ Se una pagina è acceduta ciclicamente con frequenza sufficientemente elevata, ottiene sempre una seconda chance e non viene mai sostituita.

45

Implementazione tramite lista circolare(Implementazione efficiente)

Si usa una coda circolare di pagine, detta clock. Un puntatore indica la prossima pagina candidata vittima.Quando occorre liberare un frame fisico:

il puntatore scorre la coda fino a quando non trovauna pagina con il bit impostato a 0.durante l'avanzamento del puntatore, tutti i bit diriferimento vengono reimpostati a 0.

La pagina con il bit impostato a 0 è la vittima; essa viene rimossa e sostituita dalla nuova pagina

46

Funzionamento della lista circolare(Scelta della vittima)

paginebit diriferimento

0

0

1

1

0

1

1

prossimavittima

paginebit diriferimento

0

0

0

0

0

1

1

vittima

47

Second Chance: vantaggi e svantaggi(Second Chance è efficiente, tranne in un caso in cui degenera in FIFO)

Vantaggi.L'implementazione è efficiente.

Svantaggi.Nel caso peggiore (tutti i bit impostati ad 1), vienescandita l'intera coda, dando ad ogni pagina unaseconda chance. Second chance degenera in FIFO.

48

Second Chance migliorato(La vittima è quella in memoria da più tempo, non riferita e non modificata)

Si considera la coppia ordinata di bit seguente.(bit di riferimento, bit di modifica)

(0,0): pagina né recentemente usata né recentemente modificata; la migliore candidata alla sostituzione.(0,1): pagina non usata recentemente, ma modificata; non è una buona candidata perché prima andrebbe sincronizzata su disco.(1,0): pagina usata recentemente ma non modificata; non è una buona candidata perché sarà usata presto, probabilmente.(1,1): pagina usata e modificata recentemente; pessima candidata, perché sarà utilizzata nel prossimo futuro e dovrà essere scritta su swap.

49

Algoritmi basati su contatore: LFU(La pagina vittima è quella con il conteggio di riferimento più basso)

Algoritmo Least Frequently Used (LFU).Si sostituisce la pagina con il conteggio di riferimentopiù basso.

Vantaggi.Si sostituisce una pagina poco utilizzata e si lascianoin memoria quelle usate.

Svantaggi.Se una pagina è usata molto all'inizio e poi nonpiù, rimane in memoria.Esempio: codice di inizializzazione.

50

Algoritmi basati su contatore: MFU(La pagina vittima è quella con il conteggio di riferimento più alto)

Algoritmo Most Frequently Used (MFU).Si sostituisce la pagina con il conteggio di riferimentopiù alto.

Vantaggi.Si lasciano in memoria le pagine con il contatore piùbasso, ossia quelle presumibilmente appena inserite e,di conseguenza, ancora non usate.

Svantaggi.Si rischia la sostituzione di una pagina usata spesso.