CEFRIEL Consorzio per la Formazione e la Ricerca in Ingegneria dell’Informazione Politecnico di...

© 2001 - William Fornaciari© 2001 - William Fornaciari

CEFRIELCEFRIELConsorzio per la Formazione e la RicercaConsorzio per la Formazione e la Ricercain Ingegneria dell’Informazionein Ingegneria dell’Informazione

PolitecnicoPolitecnicodi Milanodi Milano

La Gestione della memoriaLa Gestione della memoria

IntroduzioneIntroduzione

Docente:Docente:

William FornaciariWilliam Fornaciari

Politecnico di MilanoPolitecnico di [email protected]@elet.polimi.it

www.elet.polimi.it/~fornaciawww.elet.polimi.it/~fornacia

Gestione della memoriaGestione della memoria © 2001 - William Fornaciari© 2001 - William Fornaciari- - 22 - -

SommarioSommario

IndirizzamentoCaricamento del codiceIndirizzi logici e fisiciSistemi MultiprogrammatiSegmentazione e paginazioneEsempi


IndirizzamentoIndirizzamento

La CPU esegue programmi che elaborano insiemi di dati in base ad una sequenza di istruzioni

La CPU genera i riferimenti in memoria per dati e istruzioni, cioè gli indirizzi logici

Gli indirizzi cambiano formato nei vari passi:Compilazione

Linking

Caricamento

Esecuzione


IndirizzamentoIndirizzamento

Si parla di codiceAssoluto: in compilazione vengono generati solo indirizzi con riferimento a dove esattamente il codice dovrà risiedere in memoria durante l'esecuzione

Eseguibili .COM di DOS

Rilocabile: in compilazione gli indirizzi fanno riferimento ad un indirizzo base non specificato. Verrà fissato dal loader durante il caricamento

Eseguibili .EXE di DOS/Windows

Dinamicamente rilocabile: codice rilocabile che contiene solo riferimenti relativi a se stesso; può essere spostato durante l'esecuzione

Eseguibili di Windows NT


Caricamento del codiceCaricamento del codice

Caricamento dinamicoUna funzione viene caricata solo quando ne è richiesta l'esecuzioneOgni funzione è memorizzata separatamente in formato rilocabileQuesta tecnica è utilissima in caso di programmi con molte funzioni usate raramente

Esempio: Routine di gestione di errori

Il sistema operativo fornisce le primitive per il caricamento dinamico La corretta implementazione di questa tecnica è delegata al programmatore dell'applicazione



Linking dinamicoUna libreria di funzioni viene caricata solo quando ne e' richiesta l'esecuzione.Il codice compilato contiene solo uno stub

Stub: parte di codice che permette al compilatore di generare la chiamata corretta ad una funzione esterna, gestita dal sistema operativo

Al primo riferimento alla funzione, il codice nello stub controlla la disponibilità della libreria ed in caso ne richiede il caricamento al sistema operativo Per i riferimenti successivi, la libreria è disponibile e la chiamata alle sue funzioni è immediata

Esempio: le librerie .DLL in Windows



OverlaysIl codice eseguibile è spezzato in più parti, dette overlay, che si richiamano all'occorrenzaIl caricamento degli overlay è coordinato dal programma stessoNon c'è alcun supporto nel sistema operativo

Esempio: vecchi programmi DOS, costretti nei 640 KB della memoria dei primi PC


Indirizzi logici e indirizzi fisiciIndirizzi logici e indirizzi fisici

Un indirizzo generato dalla CPU è detto indirizzo logico o virtuale

Un indirizzo logico viene fissato (binding) durante la compilazione/linking per il codice assoluto o durante il caricamento per il codice rilocabileL'insieme degli indirizzi logici generati da un programma è detto spazio di indirizzamento logico

Un indirizzo presentato alla memoria per il trasferimento di un valore è detto indirizzo fisicoDurante l'esecuzione, l'associazione tra indirizzi logici e fisici è realizzata da un dispositivo hardware dedicato

Memory Management Unit (MMU)


Indirizzi logici e indirizzi fisiciIndirizzi logici e indirizzi fisici

Schema di funzionamento della MMUL'utente non vede mai gli indirizzi fisici, ma sempre e solo quelli logici

CPU

MMU

Registro di rilocazione

14000

+

MEMORIA

Indirizzologico

Indirizzofisico

346 14346


Sistemi multiprogrammatiSistemi multiprogrammati

In un sistema multiprogrammato più processi sono contemporaneamente pronti per essere eseguiti I processi nel sistema devono coesistere nello stesso spazio di indirizzamento fisicoUn programma deve risiedere in memoria (almeno in parte!) per essere eseguito dalla CPUQuando un programma non è in esecuzione, non è strettamente necessario che stia in memoriaLa tecnica per cui un processo viene tolto dalla memoria per fare posto per un altro che verrà schedulato è detta swapping


SwappingSwapping

Il processo uscente subisce uno swap out Il sistema operativo copia i dati del processo su memoria di massa, in un'area riservata, detta area di swap È inutile salvare le istruzioni: basta ricaricarle dal testo del programma memorizzato nel file system

Quando il processo può rientrare nel sistema per essere a sua volta schedulato per continuare l'esecuzione, subisce uno swap in

Il sistema operativo lo ricarica in memoria ed il processo viene inserito nella lista dei processi pronti per essere eseguiti


SwappingSwapping

Se gli indirizzi del processo sono dinamicamente rilocabili

Lo swap in può avvenire in qualunque punto della memoriaIn ogni altro caso, il processo deve essere riportato in memoria nella stessa posizione in cui era avvenuto il caricamento iniziale e il conseguente binding degli indirizzi

L'area di swap si trova su un dispositivo veloce e ad accesso diretto, possibilmente separato dal file system

Non è necessaria un'organizzazione gerarchica o una protezione dei blocchi di swap, essendo utilizzati direttamente dal sistema operativo


SwappingSwapping

Un processo può subire uno swap out se È completamente inattivoNon ha operazioni I/O in attesa di completamento

Come fare?Non swappare processi con I/O pendenti Realizzare I/O in aree di sistema

Swapping in Windows 3.XMantiene in memoria fisica tanti processi quanti ce ne stannoQuindi inizia a scaricare interi processi in "memoria virtuale" in ordine Least Recently Used (LRU)


Swapping in Windows 3.xSwapping in Windows 3.x


Sistema operativo e processi Sistema operativo e processi utenteutente

Alcuni esempiDOS, Windows 3.X e Windows 95

Utilizzano un unico spazio di indirizzamento per il sistema operativo e le applicazioni utenteCattiva soluzione

Windows NTUtilizza spazi di indirizzamento separati 2 GB in modalità kernel, per il sistema operativo2 GB in modalità utente, per le applicazioni di differente tipo

Win32, OS/2, Posix


Esempio: WindowsNTEsempio: WindowsNT

Executive

I/O Manager

File System

Device Drivers

Process ManagerVirtual Memory Manager

Microkernel

Hardware Abstraction Layer

Hardware

WindowManager

GraphicsDriver

PosixWin16Win32 DOS OS2


Esempio: WindowsNTEsempio: WindowsNT

Un processoIn modalità kernel può eseguire ogni istruzione In modalità utente solo le istruzioni non privilegiate

Se un processo in modalità utente cerca di eseguire un'istruzione privilegiata

La CPU genera una interruzione (trap) al processoEsempio: cambiare la modalità di risposta alle interruzioniEsempio: un processo utente ha cercato di accedere ad un'area di memoria al di fuori del proprio spazio di indirizzamento (General Protection Fault)


In memoria devono coesistere Il sistema operativo I processi utente

Ciò comportaCondivisione della memoria

La memoria è logicamente partizionata in un'area di sistema e una per i processi utente

Separazione degli spazi di indirizzamentoI differenti spazi di indirizzamento è bene che siano separati, in modo da non permettere ad un processo utente di corrompere il sistema operativo o addirittura bloccare il sistema



Il sistema operativo, in genereRisiede nella parte bassa dello spazio di indirizzamentoIn questa zona vi sono i vettori per le interruzioni

Spazi di indirizzamento dei processi delimitati tramiteUn registro di rilocazione Un registro limite


CPU

RegistroLimite

Registro diRilocazione

Memoria

< +

TRAP: Errore di indirizzamento

Indirizzologico

Indirizzofisicosi

no


Partizione singolaPartizione singola

La memoria è divisa in due partiUna per il sistema operativo Una per un processo utente

Quando il processo è schedulato per l'esecuzione, i registri di rilocazione e limite vengono inizializzatiIl sistema operativo è protetto dalle azioni del programma utenteLe dimensioni dei processi e del sistema operativo stesso possono cambiare dinamicamenteÉ limitante permettere un solo processo utente in memoria


Partizioni multiple fissePartizioni multiple fisse

La memoria è divisa in aree contigue di dimensione fissa dette partizioni

Ognuna delle partizioni può contenere un processoQuando c'è una partizione libera un processo è caricato ed è pronto per essere schedulato per l'esecuzione

É necessario conoscere la dimensione del processo prima di attivarloProcessi piccoli causano spreco di spazio di memoriaProcesso più grande della partizione, non possono essere eseguiti

Esempio: IBM OS/360, sui mainframe (1970-1980)


Partizioni multiple variabili Partizioni multiple variabili

Il sistema operativo tiene traccia in una tabella di quali parti della memoria sono occupate e quali no

All'inizio è libera una unica area pari a tutta la memoria, eccetto la parte occupata dal SO stesso

Quando un processo deve essere caricato, il SOSeleziona un'area in memoria di dimensioni sufficienti a contenerlo completamenteLa alloca al processo, finché il processo, terminando, la rilascia

Non viene allocato spazio che sarà inutilizzato

È necessario conoscere la dimensione del processo prima di attivarlo


Partizioni multiple variabiliPartizioni multiple variabili

Ci può essere complessivamente abbastanza spazio libero per contenere un processo in attesa, ma non in un unica area

Si ha frammentazione esterna

Se, dato un processo da caricare, più aree sono sufficienti per contenerlo, quale sceglie il sistema operativo?Esistono diverse soluzioni possibili


Partizioni multiple variabiliPartizioni multiple variabili

Tecniche di allocazioneFirst fit: La prima area che trova

La scelta è rapidaNon si fanno analisi sulla bontà della scelta

– è la politica utilizzata genericamente poiché rappresenta un ottimo rapporto tra complessità e risultato

Best fit: L’area di dimensioni minimeIl frammento generato è “piccolo”Occorre tenere ordinata per dimensione la lista delle aree libere, oppure scandirla tutta

Worst fit: L’area di dimensioni massimeIl frammento generato è “grande” (meglio utilizzabile?)Occorre tenere ordinata per dimensione la lista delle aree libere, oppure scandirla tutta


Frammentazione Interna ed Frammentazione Interna ed EsternaEsterna

Frammentazione internaLo spazio allocato in eccesso rispetto alle esigenze dei processi, inutilizzabile perché allocato

Frammentazione esternaLo spazio libero in aree troppo piccole per essere utili

Tutte le tecniche di gestione della memoria soffrono di frammentazione interna, in varia misuraLa frammentazione esterna può essere ridotta:

Tecniche di compattamento basate sulla rilocazione I processi devono essere rilocabili


Frammentazione Interna ed Frammentazione Interna ed EsternaEsterna

La rilocazione è particolarmente vantaggiosa se associata allo swapping

Il processo da spostare viene trasferito dalla memoria centrale (swap out) alla regione di swapQuando è il momento di ricaricarlo (swap in), lo si posiziona in una nuova areaAl gestore della memoria non resta altro da fare che tenere traccia e gestire le aree libere.


Partizioni: conclusioniPartizioni: conclusioni

Le tecniche di allocazione basata sulle partizioni

Sono flessibili, ma migliorabiliSono piuttosto complesse negli algoritmi di gestioneRichiedono una stima preventiva della dimensione del processoIl punto critico è che l'area allocata ad un processo deve essere contigua


PaginazionePaginazione

Il sistema operativo alloca ai processi aree di memoria non contigueLa memoria fisica è suddivisa in blocchi di dimensione fissata, detti frameLo spazio di indirizzamento logico è suddiviso in pagine di dimensione pari a quella dei frameIl sistema operativo:

Alloca ai processi pagineTiene traccia dello stato di allocazione dello spazio

di indirizzamento

A tale scopo utilizza una tabella delle pagine, la page table



Ogni indirizzo logico generato dalla CPU è diviso in due parti

Il numero di pagina Lo spiazzamento, o offset, all'interno della pagina

Il numero di pagina è usato come indice nella tabella delle pagine, per ottenere il numero di frame corrispondente alla pagina richiestaL'indirizzo fisico è composto

Dal numero di frame ricavato dalla page table Dall'offset contenuto nell'indirizzo logico



Traduzione di indirizzi logici in indirizzi fisici

CPU

Offset

Memoria

Indirizzologico

Indirizzofisico

Page OffsetFrame

Page Table

...f...

P M Altri bit FrameP = presenteM = modificata

...f...

PuntatorePage Table

+registro



Non c'è frammentazione esternaOgni pagina libera può essere allocata

Rimane la frammentazione internaPagine di grandi dimensioni

Maggiore frammentazione interna

Pagina di piccole dimensioniMinore frammentazione internaAumenta il carico di gestione della paginazione in quanto si ha page table più grande)I/O meno efficiente in caso di trasferimento di molti blocchi piccoli, piuttosto che pochi grossi



L'utente vede la memoria logica come un unico spazio contiguo di indirizzi

Il gestore della memoria tratta pagineLa memoria fisica è organizzata a frame

un frame è anche detto pagina fisica

La paginazione separa completamente il punto di vista dell'utente sulla memoria dalla sua realizzazione fisicaIl meccanismo che permette questo tipo di gestione è la combinazione di

Sistema operativo Alcuni accorgimenti nell'hardware


Paginazione: dimensione Paginazione: dimensione paginapagina

Fattori da considerareRidurre la frammentazione interna

Suggerisce pagine piccole per ottimizzare l’uso della memoria

Ridurre la richiesta di pagine dal processosuggerisce pagine grandi per evitare continue richieste da parte del processo

Contenere la dimensione della tabella delle paginesuggerisce pagine di grandi dimensione per averne un numero ridotto da gestire.

– Pagine molto grandi che risiedono in memoria virtuale potrebbero generare un doppio page fault.

» il primo per caricare la parte di tabella desiderata. » il secondo per caricare la pagina del processo.



Fattori da considerare (continua)Sfruttare le caratteristiche dei trasferimenti dati dei dispositivi di I/O

suggerisce pagine ampie.

Usare efficientemente il principio di localitàsuggerisce pagine o grandi o piccole ma non di medie dimensioni.

– Pagine piccole: saranno disponibili molte pagine per processo che, dopo un periodo di assestamento, conterranno le parti del processo vicine agli accessi recenti. Ne consegue un’alta probabilità di avere un ridotto numero di page fault.

– Pagine molto grandi: tanto più la pagina si avvicina alla dimensione del processo tanti meno page fault si avranno



Ulteriore aspetto:la politica di gestione del working set (software) influenza la progettazione della dimensione della pagina (hardware).

– Working set: numero di pagine allocate ad un processo.

Infatti, aumentando la dimensione del working set decresce il numero di page fault.

Progettazione della dimensione della pagina:ipotizza, oggi giorno, dimensioni di memoria da 4MB a 256 MBconsidera compromessi tra dimensione del TLB, Cache, numero di accessi alla memoria per ciclo istruzioni.



Esempi di dimensione di pagina:IBM 370/XA e 370/ESA: 4KBIBM AS/400: 512 BFamiglia VAX: 512 BDEC Alpha: 8 KBPowerPC: 4 KB

Diverse architetture supportano dimensioni di pagina variabile.

L’uso di pagine di dimensioni differenti consente un uso efficace della TLB.

Esempio di pagine variabili:– R4000: sette dimensioni di pagina da 4 KB a 16 MB


Paginazione: Page TablePaginazione: Page Table

Ne esiste una per ogni processoFa parte del contesto del processo, come, ad esempio, il program counterPer tenere traccia in tutto il sistema di quali frame/pagine sono allocati, il sistema operativo gestisce una tabella (frame table) Ogni accesso alla memoria (dati, istruzioni) comporta un accesso alla page tableSe la page table fosse realizzata esclusivamente via software, tempi di accesso per i programmi utente (e in parte anche per il s.o.) sarebbero raddoppiatiÉ necessario un supporto nell'hardware



Registri dedicati all'intera page table nella CPUEsempio: DEC PDP 11 (1970-1980)

64 KB di memoria organizzata in pagine da 8 KB Indirizzi a 16 bitIndirizzamento ai singoli byte attraverso un insieme di 8 registri che realizzavano la page table direttamente nel processore

Accesso veloceNon scalabileOggi le memorie sono molto, molto più grandi (GB) ma la dimensione delle pagine resta dell'ordine dei KB, quindi la page table ha migliaia, milioni di elementi



Registri associativi dedicati alla parte di page table in uso (Translation Lookaside Buffer o TLB)

Ogni registro è una coppia chiave/valoreQuando una chiave è presentata al TLBLa ricerca avviene contemporaneamente su tutti gli elementiRestituisce il valore, se presenteAltrimenti innesca il caricamento dalla page table complessiva dell'elemento corretto

TLB hit: successo nella ricerca associativa nel TLBTLB miss: mancato ritrovamento nel TLB



Funzionamento dell’hardware di paginazionePunto di partenza è l’indirizzo virtualePasso primo: esame del TLB

Se si ha un TLB Hit allora si recupera l’indirizzo del frame e si costruisce l’indirizzo fisico.Se si ha un TLB miss allora il processore utilizza il numero di pagina come indice nella tabella delle pagine.

Passo secondo: esame della tabella delle paginese il bit Present ha valore 1 allora la pagina è in memoria e il processore aggiorna il TLB il quale consentirà di costruire l’indirizzo fisicose il bit Present è 0 si ha un page fault e si attiva il SO.



CPU

Offset

MemoriaPrincipale

Indirizzologico

Indirizzofisico

Page OffsetFrame

TLB

Page Frame

...

...

...

...

...

...

Page Table

...f...

TLBhit

TLBmiss

Memoriasecondaria

Fault di pagina (risolto dal SO)

Carica la pagina

Aggiorna lapage table

+



inizio

CPU controlla il TLB

Esiste nel

TLB?

Accesso alla page table

Esiste la

pagina in

memoria

no

La CPU generaL’indirizzo fisico

si

Aggiorna il TLBsi

Memoria

piena?

Sostituzione

pagina

•Il SO chiede la lettura della pagina da disco;•La CPU attiva l’hardware per l’I/O;•la pagina è trasferita nella memoria principale;•si aggiorna la tabella delle pagine;

no

si

no

Routine gestione fault di pagina


Paginazione: EsempioPaginazione: Esempio

Supponiamo che un sistema abbia100 ns per l'accesso alla memoria 20 ns per l'accesso al TLB Con un hit rate del 80 %

Il tempo medio di accesso alla memoria è:(100 + 20) x 0.80 + (100 + 100 + 20) x 0.20 = 140 ns

Senza TLBIl tempo medio di accesso alla memoria è: 100 + 100 = 200 ns

Guadagno: 200/140 1,43 cioè 43%Il meccanismo di base della paginazione comporta

Peggioramento delle prestazioni piuttosto contenutosenza paginazione/paginazione con TLB= 100/140 0,71 cioè –29%

Aumento di complessità dell'hardware e del SO



La paginazione permette di condividere le pagineLa page table può contenere informazioni aggiuntive sulle pagine

Bit di protezioneIndica se la pagina è in sola lettura

Bit valido/non validoIndica se il contenuto della pagina è valido per il processo (Esempio: nel suo spazio di indirizzamento)

In sistemi multiprocessore è di supporto alla gestione della coerenza per la memoria distribuita

Contatore di riferimentiIn caso di condivisione di pagine



Nella maggior parte dei sistemi è presente una tabella delle pagine per processo.Ogni processo può occupare enormi quantità di memoria virtuale.

Esempio: supponendo che un processo possa avere uno spazio di indirizzamento di 2GB (231B) e supponendo pagine da 210 Byte, la tabella delle pagine possiede 221 elementi.

Soluzione: memorizzazione della tabella delle pagine in memoria virtuale e non in memoria reale.

Implica che le tabelle delle pagine sono paginate!



Una organizzazione tipica è attraverso uno schema a due livelli:

Una directory delle pagineogni elemento punta ad una tabella delle pagine

Un insieme di sotto tabelle delle pagine.Tipicamente una sotto tabella delle pagine è ampia quanto una pagina al fine di essere completamente contenuta.


SegmentazioneSegmentazione

Un programma può essere visto come una collezione di diverse entità

Codice, dati statici, dati locali alle procedure, stack...

Il compilatore può costruire il codice oggetto in modo da rispecchiare questa ripartizioneOgni entità viene caricata dal loader

SeparatamenteIn aree di dimensione variabile dette i segmenti

Ogni indirizzo logico consiste di due partiIl numero di segmentoLo spiazzamento (offset) nel segmento stesso



Base: Indirizzo fisico del segmentoLimite: Dimensione del segmento

CPU

Memoria

< +

TRAP: Errore di indirizzamento

si

no

Segment Table

Limite Base

...

...

...

...

...

...

OffsetSegment



La tabella dei segmenti è realizzata con le stesse tecniche utilizzate per la tabella delle pagineValgono le considerazioni su hit/miss/tempi di accesso alla memoria presentate per la paginazioneVengono memorizzati nella tabella dei segmenti, per ogni segmento, i bit di protezione/valido/ contatore di condivisione esaminati per la paginazioneLa segmentazione è complessa

Si ha il problema della frammentazione esterna

SoluzioniRilocazione con aggiornamento della segment table

Usare tanti segmenti piccoli


Segmentazione con Segmentazione con paginazionepaginazione

La segmentazione con paginazione unisce i vantaggi dei due approcci

Vantaggi della paginazione:Trasparente al programmatoreElimina la frammentazione esterna

Vantaggi della segmentazione:Modulare.Supporto per la condivisione e protezione.

Un indirizzo virtuale è formato dal numero di segmento dal numero di pagina e dallo spiazzamento

Numero di segmentoNumero di

paginaoffset



Offset

MemoriaPrincipale

Page OffsetFrame

Segment Table

s

Paginazione

+

Segm

Puntatoresegment Table

Page Table

...f...+

Segmentazione

Indirizzo virtuale

Indirizzo fisico



Si implementano i segmenti con pagineIntel i80386 e i80486

Al più 214 segmentiSegmenti al massimo di 232 byte (4 GB)La pagina è di 212 B (4 KB )

Windows NT suIntel, MIPS, PowerPC: pagine da 4 KB DEC Alpha: pagine da 8 MB gestite con la

segmentazione con paginazioneLa memoria virtuale è vista come tre pool di pagine

il pool delle pagine libere Il pool paginato, con pagine swappabiliil pool non paginato, pagine non swappabili (es. il s.o.)


Esempio: Windows NTEsempio: Windows NT

Impostazione del file di paginazioneArea di swap

File: pagefile.sysSi può definire un page file per ogni unità logicaLa dimensione consigliata

è orientativaVa scelta in base al numero e al tipo di applicazioni e servizi che si vuole avere contemporaneamente attivi



Task ManagerÉ un processo che permette di interagire con tutti gli altri processi di sistema in modo da

Analizzare l'occupazione di risorse di ognuno Cambiare le priorità di esecuzione Terminare i processi

In basso i valori riassuntivi per

Uso di CPU Uso di memoria RAM Uso di memoria virtuale


Demand paging/segmentationDemand paging/segmentation

Non è indispensabile che tutto il processo sia in memoria

Il SO tiene in memoria solo le parti di dati e codice necessarie per continuare l'esecuzione del processoAll'occorrenza, le parti non caricate (o swappate) vengono portate in memoria

Questa tecnica è dettaDemand paging, nei sistemi paginati Demand segmentation, nei sistemi segmentati

Il demand paging è più diffuso in quantoPiù efficace Implementazione più semplice del demand segmentation


Demand paging/segmentationDemand paging/segmentation

Al caricamento, il loader caricaSolo le strutture di gestione del processo

Demand paging puro

Alcune pagineDemand paging con preallocazione

Durante l'esecuzione del programmaSe un indirizzo fa riferimento a pagine in memoria

L'esecuzione procede normalmente

Se il riferimento è ad una pagina non caricataSi verifica un page faultIl processo viene sospeso con un trap al SO (page fault)Il SO gestisce il caricamento della pagina e la rischedulazione del processo sospeso


Page faultPage fault

Evento che genera un trap al sistema operativo da parte di un processo che fa riferimento ad una pagina di memoria non disponibileIl sistema risponde così1. Trap al sistema operativo2. Il SO salva lo stato del processo3. Il SO determina che il trap è un page fault4. Il SO controlla che il riferimento in memoria fosse

legale in modo da distinguere i page fault dagli errori di indirizzamento

5. Il SO localizza la pagina su disco6. Il SO inizia la copia della pagina dal disco ad

un frame libero


Page faultPage fault

Nel frattempo, la CPU è allocata ad un altro processoLa lettura della pagina viene completata e viene sollevato un interruptIl SO salva lo stato del processo schedulato nel frattempoIl SO determina che l'interrupt è un completamento di una operazione di I/OIl SO aggiorna la page table, e le eventuali altre tabelle, con l'informazione sulla disponibilità della nuova paginaIl SO rimette nella lista dei processi pronti il processo sospeso per il page fault


Page replacementPage replacement

Nel demand pagingLa memoria disponibile è solitamente molto più piccola della somma degli spazi di indirizzamento logici dei programmi presenti nel sistemaAd un certo punto, ci sarà un page fault per servire il quale non ci saranno frame liberi nel sistema

Soluzioni Effettuare uno swap out di pagine, possibilmente quelle “che serviranno meno in futuro” ...

Diversi criteri di scelta di tali pagineÉ conveniente rimpiazzare le pagine in sola lettura

Non è necessario copiarle nell'area di swapÉ rapido rimpiazzare le pagine non ancora modificate


Page replacementPage replacement

Criteri di scelta delle pagine da scaricareFirst In First Out

Scaricare le pagine nel sistema da più tempo Least Recently Used

Scaricare le pagine non usate da più tempoSecond Chance

La page table di sistema è scandita una prima volta per identificare le potenziali pagine per uno swap outI corrispondenti reference bit vengono azzeratiSuccessivamente, con l'esecuzione di processi, le pagine accedute avranno il reference bit impostato a 1Alla successiva scansione, se il reference bit è ancora a zero la pagina viene rilasciata altrimenti viene lasciata nella lista delle pagine "utili"


Esempio: UNIXEsempio: UNIX

UNIX è il nome di una famiglia di sistemi operativi, con profonde differenze di struttura. Di seguito sono elencate alcune caratteristiche comuni alle varianti

HP/UXDigital UNIX SUN Solaris

Memoria virtualeDemand paging

Il tipo di demand paging (puro o con preallocazione) è configurabile

Swapping



Page replacementBasato su una variante dell'algoritmo second chance

Quando il numero di frame liberi scende sotto un certo limite lo scheduler risveglia un processo di sistema detto pagedaemon o swapper, che realizza l'algoritmoTale limite minimo sul numero di frame è detto low-water-mark o min-free ed è configurabile

SchedulerPuò decidere per lo swap out di un intero processo

Esempio: quando è in attesa di un evento, in condizioni di carico elevato nel sistema



Swapping Avviene su disco in una partizione dedicataTale partizione è priva di file system (raw mode)Alcuni sistemi supportano lo swap su file (flessibilità)

Si noti l'interazione fra SchedulingSwappingGestione della memoria virtuale



Statistiche di uso della memoria virtuale

cdc8g5:/root> swapinfo -a Kb Kb Kb PCT START/ KbTYPE AVAIL USED FREE USED LIMIT RES PRI NAMEdev 262144 9764 252380 4% 0 - 1 /dev/vg00/lvol2dev 262144 10592 251552 4% 0 - 1 /dev/vg01/lvol1reserve - 50356 -50356memory 93724 72208 21516 77%cdc8g5:/root>

Uso progressivo della memoria virtuale

cdc8g5:/root> vmstat 5 procs memory page faults cpu r b w avm free re at pi po fr de sr in sy cs us sy id 2 80 0 3567 2961 4 1 0 0 0 0 0 162 1132 87 76 17 7 1 82 0 3598 2931 6 0 0 0 0 0 0 171 239 59 99 1 0 2 81 0 3664 2931 0 0 0 0 0 0 0 159 123 52 99 1 0cdc8g5:/root> vmstat 5



Alcuni processi nel sistema

cdc8g5:/root> ps –efl F S UID PID C PRI NI ADDR SZ WCHAN STIME TTY TIME COMD 3 S root 0 0 128 20 41ea88 0 3bd050 Dec 11 ? 0:19 swapper41 S root 1 0 168 20 123088 81 7ffe60 Dec 11 ? 0:49 init 3 S root 2 0 128 20 10d4d0 0 4211a0 Dec 11 ? 3:05 vhand 3 S root 3 0 128 20 123000 0 3bd050 Dec 11 ? 4:07 statdaemon 1 S root 514 0 155 20 131148 0 43bd58 Dec 11 ? 0:00 ptydaemon 1 S root 343 0 154 20 131f60 3 41cde4 Dec 11 ? 4:49 syncer 1 S pez0 796 0 158 20 15e248 66 92ef40 09:19:15 pts/0 0:00 -bash 1 S pez0 797 0 154 20 18ea80 22 420944 09:19:15 pts/0 0:00 ftp cdc 1 S pez0 774 0 158 20 180898 66 93efc0 09:19:04 pts/0 0:00 -bash 1 S root 184 0 154 20 1b5ff8 16 420944 08:59:38 ? 0:00 tftpdcdc8g5:/root>


Esempio: WinNT Process Esempio: WinNT Process ViewerViewer

WindowsNT mantiene contatori per monitorare i parametri di funzionamento

Del sistema operativo (auditing) Dei singoli processi

WindowsNT è multithreadedOgni processo può contenere più thread in esecuzione cooperanteI thread di un processo operano nello stesso spazio di indirizzamento logicoPer ogni thread è definita una priorità

Esempio: il processo EudoraStatistiche di uso delle risorse di sistema



Un processo in WindowsNT Ha un proprio codice

Memorizzato in pagine di memoria proprie (private)

Si appoggia a librerie e device driver condivisiMemorizzati in pagine di memoria comuni (mapped)

L'allocazione è dinamicaDemand segmentation Paging

I contatori di sistema sulle statistiche d'uso della memoria e sul comportamento dei processi sono indispensabili a NT stesso per implementare l'algoritmo di pool replacement

CEFRIEL Consorzio per la Formazione e la Ricerca in Ingegneria dell’Informazione Politecnico di...

Documents

Transcript of CEFRIEL Consorzio per la Formazione e la Ricerca in Ingegneria dell’Informazione Politecnico di...