Descrivere i vantaggi di un sistema a memoria virtuale ...cicalese/SO/2012/MemoriaVirtuale_1.pdf ·...

1!

9.2! Silberschatz, Galvin and Gagne ©2005!Operating System Concepts – 7th Edition, Feb 22, 2005!

  Descrivere i vantaggi di un sistema a memoria virtuale

  Concetti fondamentali!  Paginazione su richiesta (Demand paging)!  Algoritmi di sostituzione delle pagine!  Algoritmi di allocazione dei frame!  Il problema del thrashing (paginazione degenere)!

2!


  Memoria Virtuale – separazione tra spazio di memoria logico (utente) e spazio di memoria fisico (sistema).!  Solo parte del programma deve necessariamente risiedere in

memoria durante lʼesecuzione!  Lo spazio degli indirizzi logici puoʼ essere molto piuʼ grande

dello spazio degli indirizzi fisici!  Lo spazio degli indirizzi puoʼ essere condiviso da piuʼ processi!  I processi possono essere gestiti in maniera piuʼ efficiente

  Implementazione della Memoria Virtuale:!  Paginazione su richiesta (Demand paging) !  Segmentazione su richiesta (Demand segmentation)!


⇒!

3!



4!


  Portare una pagina in memoria solo quando necessario!  Riduzione dellʼ I/O!  Riduzione della memoria necessaria!  Tempi di risposta piuʼ rapidi!  Piuʼ utenti

  Una pagina eʼ necessaria ⇒ esiste un riferimento!  Se il riferimento eʼ illegale ⇒ abort!  Se non eʼ in memoria ⇒ caricamento della pagina!

  Lazy swapper – una pagina non viene mai portata in memoria se non quando eʼ necessaria!  Swapper che gestisce le pagine prende il nome di pager!


5!


  Ogni elemento della tabella delle pagine ha un bit di validitaʼ associato (v ⇒ in-memoria, i ⇒ non-in-memoria)!

  Inizialmente ogni bit di validitaʼ eʼ posto a i!

  Quando un indirizzo viene tradotto, se il bit di validitaʼ di un riferimento eʼ! !i ⇒ page fault!

v!v!v!v!i!

i!i!

….!

Frame #! valid-invalid bit!

page table!


6!


  Quando si indirizza una pagina per la prima volta (non in memoria) si genera unʼinterruzione (trap):!

page fault!1.  SO controlla se:!

  Riferimento illegale ⇒ abort!  Riferimento non in memoria!

2.  Sceglie un frame libero!3.  Swap della pagina nel frame!4.  Aggiorna le tabelle delle pagine !5.  Pone il bit di validazione a v!6.  Ricarica lʼistruzione che ha causato il page fault!


  Ripristino dellʼistruzione – possibili complicazioni!  Esempio: Istruzione che muove dati oltre il limite delle pagine!

  block move

  Operazioni autoreferenziali!

7!



  Tasso di Page Fault 0 ≤ p ≤ 1.0!  if p = 0 nessun page fault!  if p = 1, ogni indirizzamento causa page fault

  Tempo Effettivo di Accesso (EAT)!! !EAT = (1 – p) x accesso in memory!! ! !+ p (overhead di page fault!! ! ! + swap page out!! ! ! + swap page in!! ! ! + overhead di ripristino!

)!

8!


  Tempo di accesso in Memoria = 200 nanosec.!

  Tempo medio di servizio di page-fault = 8 msec.

  EAT = (1 – p) x 200 + p (8 msec) !! = (1 – p) x 200 + p x 8,000,000 !

= 200 + p x 7,999,800 nanosec.!

  Se un indirizzamento ogni 1,000 causa page fault, allora! EAT = 8.2 microsec. ! Cioeʼ un fattore di rallentamento pari a 40 !


  La memoria virtuale determina ulteriori vantaggi. !  Es.: creazione dei processi con !

  Copy-on-Write

9!


  Copy-on-Write (CoW): processo padre e processo figlio condividono, inizialmente, le stesse pagine di memoria

solo se uno di loro modifica una pagina condivisa, di tale pagina viene creata copia privata!

  CoW velocizza la fase di creazione dei processi, in quanto solo le pagine modificate vengono ricopiate!


10!


Copy page C!


  Sostituzione delle pagine!  Cerca una pagina in memoria ma non in uso e copiala

nellʼarea di swap del disco (swap out)! algoritmi! performance – lʼalgoritmo ottimale dovrebbe

minimizzare il numero di page fault!  Una stessa pagina puoʼ venire caricata in memoria in diversi

momenti ed occupare frame differenti in istanti differenti!

11!


  Uso di un bit di modifica (dirty bit) per ridurre lʼoverhead dovuto allo swap out delle pagine – solo pagine modificate vengono ricopiate su disco

  In virtuʼ del criterio di sostituzione delle pagine, la memoria virtuale e fisica possono avere dimensioni anche notevolmente differenti!


12!


1.  Trova la locazione della pagina desiderata su disco

2.  Trova un frame libero: - se ne esiste uno, usalo - se tutti i frame sono occupati, usa un algoritmo di sostituzione delle pagine per selezionare il frame da liberare

3.  Copia la pagina desiderata nel frame liberato; aggiorna le tabelle delle pagine e dei frame

4.  Ripristina il processo per lʼesecuzione!


13!


  Scopo: minimizzare il tasso di page-fault!

  Valutazione fatta considerando sequenze campione di riferimenti alle pagine (stringa dei riferimento) e calcolando il numero di page fault determinati da tale sequenza!

  Consideriamo le stringhe dei riferimenti:!

Es.1: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1!

Es.2: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5!


14!


  Stringa dei riferimenti: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1!  3 frame (3 pagine possono essere in memoria contemporaneamente)!


  Stringa dei riferimenti: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5!  3 frame (3 pagine possono essere in memoria contemporaneamente)!

1!

2!

3!

9 page fault!

0!t!

1! 1!

2!

1!

2!

3!

4!

2!

3!

4!

4!

1!

3!

5!

4!

1!

2!

6!

5!

1!

2!

7!

5!

1!

2!

8!

5!

1!

2!

9!3!2!1!

5!

3!

2!

10!

5!

3!

4!

11!

5!

3!

4!

12!

15!



1!

2!

3!

9 page fault!

0!t!

1! 1!

2!

1!

2!

3!

4!

2!

3!

4!

4!

1!

3!

5!

4!

1!

2!

6!

5!

1!

2!

7!

5!

1!

2!

8!

5!

1!

2!

9!3!2!1!

5!

3!

2!

10!

5!

3!

4!

11!

5!

3!

4!

12!

2!

3!

4!

10 page fault!

0!t!

2! 2!

3!

2!

3!

4!

4!

2!

3!

4!

5!

2!

3!

4!

6!

2!

3!

4!

7!

1!

3!

4!

8!

1!

2!

4!

9!3!2!1!

1!

2!

3!

10!

1!

2!

3!

11!

5!

2!

3!

12!

1! 1! 1! 1! 1! 1! 5! 5! 5! 5! 4! 4!1!



  4 frame

  Anomalia di Belady: piuʼ frame e piuʼ page fault!

1!

2!

3!

1!

2!

3!

4!

1!

2!

5!

3!

4!

9 page fault!

1!

2!

3!

1!

2!

3!

5!

1!

2!

4!

5! 10 page fault!

4!4! 3!

16!



  Sostituisce la pagina che, tra quelle presenti in memoria, verraʼ usata piuʼ tardi!

17!


  Sostituisce la pagina che, tra quelle presenti in memoria, verraʼ usata piuʼ tardi!

  Esempio con 4 frame!! ! 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

  Problema: dovremmo sapere i riferimenti futuri!  Performance di riferimento per il confronto degli algoritmi!

1!

2!

3!

4!

6 page fault!

4! 5!


  Sostituisce la pagina che, tra quelle presenti in memoria, non ha ricevuto riferimenti da piuʼ tempo.!

18!


  Stringa dei Riferimenti: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

5!

2!

4!

3!

1!

2!

3!

4!

1!

2!

5!

4!

1!

2!

5!

3!

1!

2!

4!

3!

1!

2!

3!

4!

1!

2!

3!

1!

2!

1!

Implementazione mediante contatori!Un contatore per pagina; ad ogni riferimento, si copia il clock nel contatore!

1!

2!

3!

4!

1!

2!

5!

4!

1!

2!

5!

4!


  Implementazione mediante Stack !  stack dei numeri di pagina implementato mediante una lista

doppiamente linkata!  Ad ogni riferimento di pagina giaʼ in memoria:!

 Muovi lʼelemento corrispondente al top dello stack!

  tempo di ricerca ridotto!

19!


Descrivere i vantaggi di un sistema a memoria virtuale ...cicalese/SO/2012/MemoriaVirtuale_1.pdf ·...

Documents

Transcript of Descrivere i vantaggi di un sistema a memoria virtuale ...cicalese/SO/2012/MemoriaVirtuale_1.pdf ·...