Sistemi Operativi Lezione XXXIV: Gestione della...
7
Sistemi Operativi Bruschi Martignoni Monga Memoria virtuale Overlay Paginazione Gestione dei page fault Algoritmo ottimo NRU FIFO Second chance Clock LRU 1 Sistemi Operativi 1 Mattia Monga Dip. di Informatica e Comunicazione Universit` a degli Studi di Milano, Italia [email protected] a.a. 2008/09 1 c 2009 M. Monga. Creative Commons Attribuzione-Condividi allo stesso modo 2.5 Italia License. http://creativecommons.org/licenses/by-sa/2.5/it/. Immagini tratte da [?] e da Wikipedia. Sistemi Operativi Bruschi Martignoni Monga Memoria virtuale Overlay Paginazione Gestione dei page fault Algoritmo ottimo NRU FIFO Second chance Clock LRU 562 Lezione XXXIV: Gestione della memoria Sistemi Operativi Bruschi Martignoni Monga Memoria virtuale Overlay Paginazione Gestione dei page fault Algoritmo ottimo NRU FIFO Second chance Clock LRU 563 Memoria virtuale La memoria ` e virtuale in almeno due sensi diversi: Gli indirizzi usati nei programmi fanno riferimento allo spazio di indirizzamento del processo, anzich` e all’indirizzo fisico assoluto in memoria centrale. Lo stesso indirizzo numerico si riferisce a parole di memoria differenti in differenti processi Gli indirizzi potrebbero fare riferimento a porzioni di memoria non ancora caricate in memoria centrale: il caricamento avviene al momento dell’esecuzione dell’istruzione La stessa parola di memoria ` e utilizzata da due processi differenti (molto probabilmente riferendovisi con due indirizzi numerici differenti) Sistemi Operativi Bruschi Martignoni Monga Memoria virtuale Overlay Paginazione Gestione dei page fault Algoritmo ottimo NRU FIFO Second chance Clock LRU 564 Localit` a Il late-binding fra indirizzo e parola di memoria centrale pu` o comunque funzionare in maniera ragionevolmente efficiente grazie al principio di localit` a dei programmi Localit` a Localit` a temporale se un elemento x viene referenziato all’istante t , la probabilit` a che x venga referenziato anche all’istante t + t 0 , cresce al tendere di t 0 → 0 Localit` a spaziale se un elemento x di posizione s viene referenziato all’istante t , la probabilit` a che venga referenziato un elemento x 0 di posizione s 0 tale che |s 0 - s |≤ δ all’istante t + t 0 , cresce al tendere di t 0 → 0 Non ` e quindi necessario caricare un programma interamente in memoria per poterlo eseguire, ma ` e sufficiente caricarlo “localit` a per localit` a”
-
Upload
truonghanh -
Category
Documents
-
view
216 -
download
0
Transcript of Sistemi Operativi Lezione XXXIV: Gestione della...
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
1
Sistemi Operativi1
Mattia Monga
Dip. di Informatica e ComunicazioneUniversita degli Studi di Milano, Italia
a.a. 2008/09
1c© 2009 M. Monga. Creative Commons Attribuzione-Condividi allo stesso modo 2.5 Italia License.
http://creativecommons.org/licenses/by-sa/2.5/it/. Immagini tratte da [?] e da Wikipedia.
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
562
Lezione XXXIV: Gestione della memoria
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
563
Memoria virtuale
La memoria e virtuale in almeno due sensi diversi:
Gli indirizzi usati nei programmi fanno riferimento allospazio di indirizzamento del processo, anziche all’indirizzofisico assoluto in memoria centrale.
Lo stesso indirizzo numerico si riferisce a parole di memoriadifferenti in differenti processi
Gli indirizzi potrebbero fare riferimento a porzioni dimemoria non ancora caricate in memoria centrale: ilcaricamento avviene al momento dell’esecuzionedell’istruzione
La stessa parola di memoria e utilizzata da due processidifferenti (molto probabilmente riferendovisi con dueindirizzi numerici differenti)
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
564
Localita
Il late-binding fra indirizzo e parola di memoria centrale puocomunque funzionare in maniera ragionevolmente efficientegrazie al principio di localita dei programmi
Localita
Localita temporale se un elemento x viene referenziatoall’istante t, la probabilita che x venga referenziato ancheall’istante t + t ′, cresce al tendere di t ′ → 0
Localita spaziale se un elemento x di posizione s vienereferenziato all’istante t, la probabilita che vengareferenziato un elemento x ′ di posizione s ′ tale che|s ′ − s| ≤ δ all’istante t + t ′, cresce al tendere di t ′ → 0
Non e quindi necessario caricare un programma interamente inmemoria per poterlo eseguire, ma e sufficiente caricarlo“localita per localita”
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
565
Overlay
Meccanismo molto primitivo per realizzare la memoriavirtuale: affidato al programmatore
Il programmatore suddivide il programma in porzioni la cuiesecuzione non si sovrappone nel tempo
Ogni porzione e chiamata overlay
Gli overlay vengono caricati in istanti successivi
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
566
Demand paging
La paginazione puo essere utilizzata per gestire lavirtualizzazione della memoria: paginazione a richiesta
La risoluzione delle pagine logiche in page frame vienesfruttata per caricare in memoria centrale una pagina escaricarne un’altra nella memoria secondaria swapping
Lazy swapping Si carica la prima pagina del programma daeseguire e solo quando nuova pagina viene referenziata lasi carica in memoria
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
567
Page fault
La precedente strategia richiede pero che sia possibilestabilire a priori la presenza o meno di una pagina inmemoria
Uso un bit present/absent (validita) nella tabella dellepagine
L’evento di pagina non trovata in memoria e denominatopage fault
Gestire il page fault significa preoccuparsi di recuperare lapagina da disco e portarla in memoria
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
568
Tabella delle pagine
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
569
Supporti alla paginazione
Un sistema che offre la paginazione deve gestire le seguentistrutture dati
Tabella dei frame
Tabella delle pagine, che definisce l’associazione pagina →frame
una per ogni processo in esecuzione o in attesa diesecuzione
Per ogni riferimento a memoria e necessario accedere allatabella della pagine
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
570
MMU
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
571
Tabella delle pagine
La dimensione della tabella puo essere molto elevata
Con pagine di 4K:1 milione di pagine con indirizzi di 32bit, quindi 1 milione di elementi nella tabella
L’associazione pagina-frame deve essere molto efficienteperche viene eseguita per ogni riferimento alla memoria
Un’istruzione richiede sempre almeno 1 accesso
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
572
Tabella delle pagine a 2 livelli
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
573
Gestione dei due livelli
1 Verifica disponibilita dei frame in memoria centrale
2 Caricamento in memoria centrale agganciando la tabelladelle pagine al PCB
3 Quando il processo diventa running la sua tabella dellepagine viene caricata in quella del sistema
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
574
Tabella di sistema
Esistono tre alternative per implementarla1 Esiste un registro che indirizza la tabella delle pagine del
processo in esecuzione, tra quelle di tutti i processi delsistema; la tabella sta in memoria
Lenta richiede due accessi a memoria centrale perrecuperare le informazioni
2 Registri specializzati
Molto efficiente in esecuzione ma molto costosa per tabelledi grosse dimensioni, soprattutto in context switch
3 Registri specializzati associativi
Implementano un Translation Lookaside Buffer (TLB)Costose: ma generalmente 8-64 elementi sono sufficientiper il principio di localitaGeneralmente nella MMU
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
575
TLB
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
576
TLB
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
577
Tabella delle pagine invertita
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
578
Page fault
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
579
Algoritmi di rimpiazzo
Durante la gestione di un page fault puo essere necessario:
Individuare le pagine da scaricare su disco
Salvare le pagine modificate durante l’esecuzione, quellenon modificate possono invece essere sovrascritte
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
580
L’algoritmo ottimo
La strategia ottima sarebbe quella di sostituire, tra quellepresenti in memoria, la pagina che sara referenziata il piu tardipossibile
Ottimale ma non realizzabile
Possibili stime
Tenere traccia dell’uso passato delle pagine e inferire ilfuturo dal passatoAnche questa euristica e molto difficile da realizzarepraticamente
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
581
Not recently used
Per ogni pagina lo hardware gestisce un Reference bit e unModified bit
I bit vengono settati quando la pagina e acceduta e/omodificata
Le pagine vengono suddivise in quattro classi1 not referenced, not modified2 not referenced, modified3 referenced, not modified4 referenced, modified
NRU rimuove la pagine casualmente a partire dalla classecon l’indice piu basso non vuota
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
582
FIFO
Mantiene una lista delle pagine che rispetta l’ordine concui le stesse sono state caricate in memoria (le pagine piuanziane sono all’inizio della lista)
Le pagine piu anziane sono le prime ad essere sostituite
Si rischia di sostituire una pagine che e referenziata spesso(principio di localita)
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
583
Second chance
Le pagine sono ordinate FIFO con un bit d’uso R
Le pagine selezionate per il rimpiazzo vengono rimesse incoda se R e settato
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
584
Clock
Come seconda chance, ma si usa una lista circolare: la lancettapunta alla pagina candidata
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
585
LRU
Una buona approssimazione dell’algoritmo ottimale
Assume che le pagine usate recentemente saranno usateanche in un futuro prossimo
Elimina le pagine che non sono usate da piu tempo
Mantiene una lista linkata di pagine
Quelle usate piu recentemente all’inizio,E necessario aggiornare questa lista ad ogni riferimento apagina
SistemiOperativi
BruschiMartignoni
Monga
Memoriavirtuale
Overlay
Paginazione
Gestione deipage fault
Algoritmoottimo
NRU
FIFO
Second chance
Clock
LRU
586
Simulazione LRU tramite aging
Alternativamente e possibile mantenere un contatore perpagina che si incrementa ad ogni tick: la pagina vittima equella con il contatore piu basso
