[ALGORITMO] Sostituzione pagine LRU

[elly00]

Ciao,

qualcuno sa spiegarmi questa soluzione?
• La memoria di un calcolatore è gestita con una tecnica di ‘paginazione su richiesta’.
• Si consideri la seguente richiesta di pagine: 1, 3,2, 4, 5, 3, 1, 3, 3, 2, 4, 1.
• Mostrare il “page trace” e calcolare il numero di “page fault” e l’ hit ratio per una memoria di dimensione pari a quattro pagine, nei seguenti due casi:
—Strategia di rimpiazzamento delle pagine LRU;

e qui la soluzione sarebbe:

tempo 1 2 3 4 5 6 7 8 9 10 11 12
richieste 1 3 2 4 5 3 1 3 3 2 4 1

pagine 1 3 2 4 5 3 1 3 3 2 4 1
/ 1 3 2 4 5 3 1 1 3 2 4
/ 1 3 2 4 5 5 5 1 3 2
/ 1 3 2 4 4 4 5 1 3
fault x x x x

Come si arriva a questa sequenza???
GRAZIE

[Casper87]

già il termine LRU spiega tutto "Last Recently Used" quindi dalla memoria (è un algoritmo di rimozione usato soprattutto nelle memorie cahce) vengono eliminate le pagine meno usate per far posto a quelle nuove...

[andbin]

Originariamente inviato da elly00
Ciao,

qualcuno sa spiegarmi questa soluzione?

Ma all'inizio come è la situazione della mappatura?

[elly00]

Ciao,

beh LRU ci siamo..quello che non capisco è come si arriva a questa tabella

Non ho altri dati se non quelli che vi ho già dato..

La memoria di un calcolatore è gestita con una tecnica di ‘paginazione su richiesta’.
• Si consideri la seguente richiesta di pagine: 1, 3,2, 4, 5, 3, 1, 3, 3, 2, 4, 1.




GRAZIE
CIAO

[elly00]

la domanda è simile a quest'altra..
http://forum.html.it/forum/showthrea...readid=1073951

CIAO

[andbin]

Presupponendo che all'inizio nessuna pagina fisica sia mappata:

t   P            Risultato
                 mappatura
-----------------------------
0                - - - -
1   1   fault    1 - - -
2   3   fault    1 3 - -
3   2   fault    1 3 2 -
4   4   fault    1 3 2 4
5   5   fault    5 3 2 4  (5 sostituisce 1, meno recente)
6   3   hit      5 3 2 4
7   1   fault    5 1 2 4  (1 sostituisce 3, meno recente)
8   3   fault    5 1 3 4  (3 sostituisce 2, meno recente)
9   3   hit      5 1 3 4
10  2   fault    5 1 3 2  (2 sostituisce 4, meno recente)
11  4   fault    4 1 3 2  (4 sostituisce 5, meno recente)
12  1   hit      4 1 3 2

Spero di aver ragionato giusto ... non faccio 'ste cose tutti i giorni.

[elly00]

ci credo che non le fai tutti i giorni e ...meno male

fino al tempo 6 concordo con le sostituzioni..
poi mi dici che 1 sostituisce 3 meno recente...

come verifichi che il 3 è il meno recente se è stato referenziato al tempo 6?


CIAO

[andbin]

Originariamente inviato da elly00
fino al tempo 6 concordo con le sostituzioni..
poi mi dici che 1 sostituisce 3 meno recente...

come verifichi che il 3 è il meno recente se è stato referenziato al tempo 6?

Infatti ho toppato io. Toppo pure io, eh! .... poche volte, fortunatamente, ma toppo.

Così dovrebbe essere corretto, dimmi se ti "quadra":

t   P            Risultato
                 mappatura
-----------------------------
0                - - - -
1   1   fault    1 - - -
2   3   fault    1 3 - -
3   2   fault    1 3 2 -
4   4   fault    1 3 2 4
5   5   fault    5 3 2 4   (5 sostituisce 1, meno recente)
6   3   hit      5 3 2 4
7   1   fault    5 3 1 4   (1 sostituisce 2, meno recente)
8   3   hit      5 3 1 4
9   3   hit      5 3 1 4
10  2   fault    5 3 1 2   (2 sostituisce 4, meno recente)
11  4   fault    4 3 1 2   (4 sostituisce 5, meno recente)
12  1   hit      4 3 1 2

[elly00]

sei un ottimo compagno di studi "virtuale" ..grazie

così mi pare OKKK

riesci anche a dareun okkio all'atro post simile a questo
http://forum.html.it/forum/showthre...hreadid=1073951

VVoVe:
CIAOOOOOOOOO

[andbin]

Originariamente inviato da elly00
riesci anche a dareun okkio all'atro post simile a questo
http://forum.html.it/forum/showthre...hreadid=1073951

Il link l'hai messo sbagliato ma l'avevo letto il post. Se ho capito bene, è praticamente la stessa cosa di questo. Ti dà una sequenza di accesso e devi trovare il numero di page fault nel caso di 3 pagine e di 4 pagine fisiche.