Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Sistemi Operativi, 9 CFU => Topic started by: milos224 on 18-07-2012, 17:21:53



Title: Algoritmo NRU
Post by: milos224 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?


Title: Re:Algoritmo NRU
Post by: GenteGuasta 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.


Title: Re:Algoritmo NRU
Post by: milos224 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..


Title: Re:Algoritmo NRU
Post by: GenteGuasta 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...


Title: Re:Algoritmo NRU
Post by: milos224 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...


Title: Re:Algoritmo NRU
Post by: GenteGuasta 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


Title: Re:Algoritmo NRU
Post by: milos224 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!


Title: Re:Algoritmo NRU
Post by: StephCT 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


Title: Re:Algoritmo NRU
Post by: GenteGuasta 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.


Title: Re:Algoritmo NRU
Post by: corel_86 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 


Title: Re:Algoritmo NRU
Post by: corel_86 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....