Esercizio - Anomalia di Belady e limiti sui page fault (slide di memoria virtuale, eserciziario, esercizi 33 e 84)
In questa pagina 4
Testo.
- Slide di memoria virtuale. Stringa
1 2 3 4 1 2 5 1 2 3 4 5: con FIFO, quanti page fault con 3 frame e con 4 frame? Cosa si osserva? - Esercizio 33 (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD). Si è progettato un nuovo algoritmo di sostituzione delle pagine che si pensa sia ottimo. In alcuni casi di prova si verifica l'anomalia di Belady. L'algoritmo è ottimo? Spiegare.
- Esercizio 84. Un processo ha pagine e una stringa di riferimenti di lunghezza (tutte le pagine sono riferite). Indipendentemente dall'algoritmo, quali sono il limite inferiore e il limite superiore del numero di page fault?
L'anomalia di Belady con FIFO
Stringa 1 2 3 4 1 2 5 1 2 3 4 5.
3 frame: 9 fault.
| rif. | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| frame 1 | 1 | 1 | 1 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 5 | 5 |
| frame 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | |
| frame 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | ||
| fault | F | F | F | F | F | F | F | F | F |
4 frame: 10 fault.
| rif. | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| frame 1 | 1 | 1 | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 4 | 4 |
| frame 2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 5 | |
| frame 3 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | ||
| frame 4 | 4 | 4 | 4 | 4 | 4 | 4 | 3 | 3 | 3 | |||
| fault | F | F | F | F | F | F | F | F | F | F |
Con più frame i fault aumentano (da 9 a 10): è l'anomalia di Belady. La causa è che FIFO non è un algoritmo a pila: l'insieme delle pagine in memoria con 3 frame non è un sottoinsieme di quello con 4. Qui, con 4 frame, FIFO toglie proprio le pagine 1 e 2 appena prima che servano di nuovo.
Gli stessi dati con tutti gli algoritmi e da 1 a 6 frame (calcolati e verificati con un programma):
| frame | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| FIFO | 12 | 12 | 9 | 10 | 5 | 5 |
| LRU | 12 | 12 | 10 | 8 | 5 | 5 |
| OPT | 12 | 9 | 7 | 6 | 5 | 5 |
FIFO sale tra 3 e 4 frame; LRU e OPT non salgono mai: sono algoritmi a pila. Da 5 frame in su i fault sono 5, cioè le pagine distinte (1, 2, 3, 4, 5): una volta caricate tutte non c'è più nulla da sostituire.
Esercizio 33
No, l'algoritmo non è ottimo. L'algoritmo ottimo sostituisce per definizione la pagina che non sarà usata per il periodo più lungo nel futuro. L'anomalia di Belady si verifica quando un algoritmo toglie una pagina che serve nell'immediato futuro, e un algoritmo ottimo non farebbe mai questa scelta. Quindi un algoritmo ottimo non può avere l'anomalia (è un algoritmo a pila). Se in qualche caso di prova si verifica l'anomalia, l'algoritmo non è ottimo.
Esercizio 84
Limite inferiore: . Ogni pagina, la prima volta che è riferita, non è in memoria (si parte senza pagine con la paginazione su richiesta pura): servono almeno fault, uno per pagina distinta. Si raggiunge quando i frame bastano a tenere tutte le pagine (nessuna sostituzione).
Limite superiore: . Ogni riferimento causa al massimo un page fault, quindi i fault sono al più (la lunghezza della stringa). Si raggiunge nel caso peggiore, per esempio quando i frame sono pochi e si riferisce sempre la pagina che l'algoritmo ha appena tolto: con la stringa 1 2 3 4 1 2 3 4 e 3 frame, FIFO e LRU hanno 8 fault (OPT ne ha 5).
In sintesi: , per qualunque algoritmo.
Errori tipici
- Dire che "più frame, meno fault" vale sempre: vale per LRU e OPT, non per FIFO.
- Dire che OPT si può realizzare: richiede la conoscenza del futuro, serve solo come termine di confronto.
- Come limite inferiore indicare 0: con la paginazione su richiesta pura ogni pagina riferita causa almeno un fault.
Versione ripasso
Belady. FIFO su 1 2 3 4 1 2 5 1 2 3 4 5: 3 frame 9 fault, 4 frame 10. Tabella per 1-6 frame: FIFO 12, 12, 9, 10, 5, 5; LRU 12, 12, 10, 8, 5, 5; OPT 12, 9, 7, 6, 5, 5. LRU e OPT sono algoritmi a pila (l'insieme con frame quello con ): nessuna anomalia.
Ex. 33. Un algoritmo con l'anomalia non è ottimo: l'ottimo toglie la pagina usata più in là nel futuro e non può mai togliere una pagina che serve subito.
Ex. 84. : almeno un fault per pagina distinta (paginazione pura), al più uno per riferimento. Esempio del massimo: 1 2 3 4 1 2 3 4, 3 frame, FIFO e LRU: 8 fault.
Tabella FIFO (1 2 3 4 1 2 5 1 2 3 4 5): 3 frame 9 fault (1, 2, 3, 4, 1, 2, 5, 3, 4); 4 frame 10 fault (1, 2, 3, 4, 5, 1, 2, 3, 4, 5). Da 5 frame i fault sono 5 (pagine distinte).
Errori tipici: "più frame, meno fault" per FIFO; OPT realizzabile; limite inferiore 0.