Pages: [1]   Go Down
Print
Author Topic: Algoritmo NRU  (Read 4116 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
milos224
Forumista
***
Offline Offline

Posts: 830


« on: 18-07-2012, 17:21:53 »

Su internet ho trovato sempre la stessa cosa, mi spiego:

Algoritmo NRU
• NRU (Not Recently Used)
• Ogni pagina ha un Reference bit e un Modified bit
• Le pagine vengono classificate
0. Non referenziate e nonmodificate
1. Non referenziate e modificate
2. Referenziate e non modificate
3. Referenziate e modificate
La pagina da buttare viene selezionata random dalla classe non vuota più bassa
Non ho capito molto bene la parte in grassetto: se dice che la pagina da buttare è prima quella non vuota più bassa non dovrebbe essere in ordine, classe 1,2,3 e poi 0?

Ho pure un esercizio svolto:

Numero Pagina          BIT R       BIT M
0                                  1             0
1                                  0             1
2                                  0             0
3                                  1             1

• Le pagine vengono scelte nell’ordine:
– 2: non referenziata e non modificata  (classe 0)
– 1: non referenziata ma modificata      (classe 1)
– 0: referenziata e non modificata         (classe 2)
– 3:referenziata e non modificata          (classe 3)

Perchè parte dalla classe 0? Non è una classe vuota?
Logged
GenteGuasta
Matricola
*
Offline Offline

Posts: 28


« Reply #1 on: 18-07-2012, 21:05:03 »

Le pagine di classe 0 sono quelle pagine che non sono state modificate e nemmeno referenziate, quindi le candidate ad essere sostituite per prime...facendo riferimento all'esercizio che hai postato, la pagina 2 appartiene alla classe 0 e quindi viene sostituita per prima. L'ordine delle classi è: 0 1 2 3.
« Last Edit: 18-07-2012, 21:09:52 by GenteGuasta » Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #2 on: 18-07-2012, 21:08:07 »

Le pagine di classe 0 sono quelle pagine che non sono state modificate e nemmeno referenziate, quindi le candidate ad essere sostituite...cosa vuol dire che la classe 0 è una classe vuota?
Non so esattamente cosa vuol dire classe vuota (forse ne referenziato ne modificato), ma non capisco allora perchè il primo candidato è una classe NON vuota con il minor indice..
Logged
GenteGuasta
Matricola
*
Offline Offline

Posts: 28


« Reply #3 on: 18-07-2012, 21:11:34 »

Per classe non vuota più bassa intende dire che se nn vi sono pagine di classe 0, allora scarterà pagine di classe 1 e cosi via...
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #4 on: 18-07-2012, 21:15:19 »

Per classe non vuota più bassa intende dire che se nn vi sono pagine di classe 0, allora scarterà pagine di classe 1 e cosi via...
Allora è sempre in ordine in pratica.. 0,1,2,3...
Logged
GenteGuasta
Matricola
*
Offline Offline

Posts: 28


« Reply #5 on: 18-07-2012, 21:19:43 »

si però.. classe 0 1 2 3 e basta. Ti consiglio di leggere la teoria dell'NRU sul tanembaum
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #6 on: 18-07-2012, 21:25:27 »

si però.. classe 0 1 2 3 e basta. Ti consiglio di leggere la teoria dell'NRU sul tanembaum
Si si ovvio, sono solo 4 le classi! Grazie comunque!
Logged
StephCT
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 417



« Reply #7 on: 18-07-2012, 21:29:44 »

semplicemente ad ogni intervallo viene fatto un controllo:
ci sono pagine di classe 0? si, ne scelgo una e la sostituisco, no, passo alla classe 1.
ci sono pagine di classe 1? stesso discorso, si passa in caso alla classe 2 ecc...

immaginalo come se fosse una serie di costrutti if else a catena del tipo:
Code:
if ( !classe0.isEmpty() )
classe0.eliminaPag();
else if ( !classe1.isEmpty() )
classe1.eliminaPag();
else if ( !classe2.isEmpty() )
classe2.eliminaPag();
else
classe3.eliminaPag();

infatti questo non è proprio un algoritmo perfetto. perchè capiterà molto spesso che le pagine di classe 2 e 3 non vengano eliminate e staranno li a fare "muffa" perchè magari continuamente troveranno pag di classe 0 o 1
Logged

"Che la Forza sia con Te"
GenteGuasta
Matricola
*
Offline Offline

Posts: 28


« Reply #8 on: 18-07-2012, 21:40:22 »

si ma essendo che nelle classi 2 e 3 ci sono le pagine referenziate nell'ultimo interrupt del clock è giusto che stiano li a fare la muffa se necessario, dato che è molto probabile che vengano di nuovo richieste.
Logged
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #9 on: 18-07-2012, 21:42:44 »

Su internet ho trovato sempre la stessa cosa, mi spiego:

Algoritmo NRU
• NRU (Not Recently Used)
• Ogni pagina ha un Reference bit e un Modified bit
• Le pagine vengono classificate
0. Non referenziate e nonmodificate
1. Non referenziate e modificate
2. Referenziate e non modificate
3. Referenziate e modificate
La pagina da buttare viene selezionata random dalla classe non vuota più bassa
Non ho capito molto bene la parte in grassetto: se dice che la pagina da buttare è prima quella non vuota più bassa non dovrebbe essere in ordine, classe 1,2,3 e poi 0?

Ho pure un esercizio svolto:

Numero Pagina          BIT R       BIT M
0                                  1             0
1                                  0             1
2                                  0             0
3                                  1             1

• Le pagine vengono scelte nell’ordine:
– 2: non referenziata e non modificata  (classe 0)
– 1: non referenziata ma modificata      (classe 1)
– 0: referenziata e non modificata         (classe 2)
– 3:referenziata e non modificata          (classe 3)

Perchè parte dalla classe 0? Non è una classe vuota?


Ciao manco a farlo apposta sto studiando adesso adesso questo algoritmo.

Allora come ben sai questo algoritmo la soluzione ottimale è:

Se il processo proprietario della pagina in esame non ha utilizzato di recente quella determinata pagina allora probabilmente non lo sarà per il prossimo futuro

Per realizzare questa soluzione si ricorre a questi due bit

nella classe 0 sono presenti quelle pagine che da quando sono state caricate in memoria non sono state modificate ed inoltre che questa pagina non è stata referenziata dall'ultimo azzeramento


Tu sai a cosa serve il bit di referenziamento?
Oltre ad avere un comportamento simile alla scrittura quindi viene aggiornato nel momento in cui si verifica un referenziamento, serve per sapere alcune informazioni temporali

Ad esempio viene azzerato ogni tot di tempo per sapere un informazione statistica sull'utilizzo di tutte le pagine in questo tot di tempo

non so se mi sono spiegato bene 
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #10 on: 18-07-2012, 21:57:15 »

La scelta di utilizzare una classe di livello 0 da scartare risulta più appetibile rispetto ad una di classe superiore perché si ha solamente un solo accesso al disco.

Mentre se scarto una pagina di livello 1 bisognerebbe effettuare due accessi al disco perché il bit di modifica è stato aggiornato e quindi sarebbe un'operazione più lenta

E cosi via....

Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
Pages: [1]   Go Up
Print
Jump to: