3.1

Nell'algoritmo LRU, all'atto di un page fault, se é necessario rimpiazzare una pagina, si opera lo swap out della pagina che non é stata riferita da piú tempo.

I primi tre accessi comportano un page fault ciascuno, ma senza rimpiazzamento, in quanto inizialmente la memoria fisica é vuota. Al tempo 4 viene riferita la pagina 7 che é giá in memoria. Al tempo 5 si porta in memoria la pagina 5 senza rimpiazzare alcuna pagina: a questo punto la memoria fisica é piena, e contiene le pagine ${\cal M}_5=\left\{0,7,2,5\right\}$. Al tempo 6 si tenta di accedere alla pagina 8: é necessario rimpiazzare una pagina e la scelta cade sulla pagina 0, riferita al tempo 1. Avremo perció ${\cal M}_6=\left\{8,7,2,5\right\}$. Al tempo 7 é necessario rimpiazzare una pagina per poter portare in memoria fisica la pagina 9. La scelta cade sulla pagina 2, che pur essendo stata caricata dopo la 7, é stata riferita meno recentemente. Continuando con l'applicazione dell'algoritmo avremo:

$${\cal M}_7=\left\{8,7,9,5\right\} \quad {\cal M}_8=\left\{8,2,9,5\right\} \quad {\cal M}_9=\left\{8,2,9,4\right\}$$

per un totale di 8 page fault rispettivamente agli istanti $\left\{1,2,3,5,6,7,8,9\right\}$.