G estione della memoria

1. I processi e la memoria

Un processo per essere eseguito deve essere collocato in memoria centrale. La memoria è una risorsa condivisa tra i processi. Per aumentare del numero dei processi in memoria serve diminuire la probabilità che essi siano tutti bloccati in attesa di un'operazione di I/O e la CPU rimanga inattiva.

Un processo può essere:

rimosso dalla memoria trasferito su disco (swap out) per permettere l'esecuzione di un altro processo e dopo riportato in memoria (swap In) per proseguire nell'esecuzione.

Quando il sistema operativo riporta il processo in memoria può collocarlo nella posizione che occupava prima dello swap out oppure in una qualsiasi zona libera della memoria. La possibilità di collocare il processo in una nuova posizione della memoria migliora l’utilizzazione della memoria e aumenta l’efficienza del sistema.

Rilocazione del processo è lo spostamento di un processo in memoria e la sua esecuzione richiede di modificare gli indirizzi del codice in modo opportuno. La rilocazione può essere attuata in diversi modi che dipendono:

dalle possibilità dello specifico sistema operativo, dall’hardware dalle caratteristiche della catena di programmazione, cioè come, nel corso dello sviluppo del software, sono

generati gli indirizzi di memoria .

2. La rilocazione dei processi e la catena di programmazione

La rilocazione di un processo richiede:

a) di cambiare il suo codice, b) di modificare gli indirizzi nelle istruzioni, per adeguarlo alla nuova collocazione del processo nella memoria.

La rilocazione di un processo in memoria può avvenire in diversi modi a seconda di come è prodotto il codice del programma.

La catena di programmazione è le trasformazioni che avvengono nel codice per passare dal programma sorgente al programma in esecuzione.

I riferimenti alla memoria sono gli indirizzi numerici che corrispondono alla posizione fisica del processo nella memoria.

Il seguente programma è questo che:

a) composto da un programma principale (Main) b) usa le due procedure EstraiDati e StampaDati.

A causa delle compilazioni separate, la traduzione del programma in codice macchina non può essere effettuata completamente. L'esecuzione di questo programma avviene dopo una serie di trasformazioni che compongono la catena di programmazione:

a) il primo passo della catena di programmazione: la compilazione del programma è la traduzione del programma in linguaggio macchina. Per attuare la traduzione, il compilatore traduce il programma principale e le due procedure in tre moduli , separati e non collegati tra di loro. Gli indirizzi all'interno di ogni modulo partono da 0:

Main occupa la memoria dall'indirizzo 0 all’indirizzo M. EstraiDati da 0 a ad E StampaDati da 0 ad S.

La compilazione di Main produce un codice oggetto nel quale il salto al sottoprogramma (JSB, jump to subroutine) è indicata simbolicamente: DSB EstraiDati. EstraiDati è specificato in una tabella dei riferimenti esterni posta nel codice oggetto del modulo Main. Questo avviene per ogni modulo oggetto (sottoprogrammi utente, sottoprogrammi di libreria (libreria del linguaggio, di sistema o di specifiche librerie applicative) che compone l’applicazione.

b) Il secondo passo della catena di programmazione: Il Link Editor collega i moduli oggetto in una struttura lineare per costruire un modulo pronto per il caricamento:

1. il codice e ai dati del modulo Main 2. codice e dati del modulo Estrai Dati 3. codice e dati del modulo StampaDati 4. le routine prelevate dalle librerie esterne che devono essere nel modulo pronto per il caricamento.

Il Link Editor è risolvere le referenze esterne perché ha la visione di tutti i moduli dell'applicazione e ne conosce le dimensioni. Cosi per costruire un modulo pronto per il caricamento, il link editor esegue due operazioni:

il collegamento dei moduli (link) la modifica (editing) del codice macchina.

Il modulo generato dal link editor prevede la collocazione dell’applicazione a partire dell'indirizzo 0 di memoria.

1. La tecnica delle compilazioni “compila e vai”: link editor genera direttamente il codice eseguibile dell'applicazione. Lo svantaggio: per ogni modifica fatta a uno qualsiasi dei moduli che la compongono deve essere ricompilata l'intera applicazione.

2. La tecnica delle compilazioni separate: si usa per ragioni di efficienza, che permette di compilare i soli moduli modificati. Poi necessario usare di nuovo il link editor per collegare le nuove versioni dei moduli oggetto con gli altri moduli dell’applicazione.

c) Il passo terzo della catena di programmazione: serve caricare in memoria un programma pronto per l’esecuzione tramite un programma di sistema detto loader (caricatore). Il loader trasforma un programma nell'immagine di un processo.

La rilocazione statica è rilocazione di un modulo di caricamento, che viene effettuata immediatamente prima dell'esecuzione del programma, a programma fermo. Il loader deve sistemare gli indirizzi del modulo generato dal link editor all'effettivo posizionamento in memoria del processo. Il vantaggio della generazione di un modulo di caricamento rilocabile:

la rilocazione del codice è meno costosa perché le operazioni da eseguire sono più semplici. Un modulo di caricamento rilocabile può essere collocato in qualsiasi

posizione della memoria in quanto gli indirizzi di memoria effettivi sono decisi immediatamente prima dell'esecuzione dal loader.

La rilocazione assoluta: link editor produce un modulo di caricamento assoluto, che consiste nella precisa immagine del processo in esecuzione. Il difetto della generazione di un modulo di caricamento assoluto: se è necessario collocare il processo in un'altra zona della memoria, il codice del processo dovrebbe essere rigenerato partendo dai moduli oggetto dell'applicazione.In un ambiente multiprogrammato la rilocazione statica comporta una delle due scelte:

il processo sospeso viene riportato in memoria nella posizione originaria. Il difetto di questa strategia è un uso inefficiente della memoria.

il processo sospeso viene collocato in una posizione differente ma, prima di riportarlo in memoria, bisogna rilocarlo per adeguare gli indirizzi alla nuova posizione del processo in memoria. Il difetto di questa strategia: rallentamento delle operazioni di swap in e swap out.

La rilocazione dinamica: calca dell'Indirizzo effettivo al momento dell'esecuzione. Con questa strategia un processo è inserito in memoria in una certa posizione: in seguito può essere rimosso, scaricato su disco e riportato in memoria in una posizione arbitraria, ma gli indirizzi delle istruzioni che lo compongono sono sempre gli stessi.

La rilocazione dinamica usa in modo efficiente la memoria SE il calcolo degli indirizzi al momento dell'esecuzione non rallenti l'esecuzione del processo. Per questa ragione il calcolo dell'indirizzo effettivo è realizzato a livello hardware, sfruttando un registro (registro base), che contiene l'indirizzo di partenza del codice del processo.

Il mapping tra indirizzo logico e indirizzo fisico: durante l'esecuzione i riferimenti alla memoria generati dal processo, non sono utilizzati direttamente, ma sono inviati a un dispositivo che somma il valore dell'Indirizzo logico contenuto nel registro base.Un registro limite:

contiene il valore dell'ultima parola di memoria occupata dai dati del processo.

Protegge la memoria: se nel corso dell'esecuzione il processo genera indirizzi di valore più grande di quello contenuto dal registro limite, si realizza una situazione di errore e il processo è interrotto.

Gli indirizzi relativi sono gli indirizzi logici che indicano la distanza di una parola di memoria dall'origine del codice.

la MMU (Memory Management Unii, unità di gestione della memoria) è il dispositivo hardware che avviene il mapping tra indirizzi logici e indirizzi fisici.

I tipi dei indirizzi di memoria nel corso della catena di programmazione:

indirizzi assoluti generati dal link editor, indirizzi rilocati staticamente dal loader al momento del caricamento; indirizzi rilocati dinamicamente dalla MMU al momento dell'esecuzione.

Nel caso di indirizzi assoluti e indirizzi rilocati staticamente, non serve l'hardware della MMU, perché gli indirizzi generati dalla CPU durante l'esecuzione del processo sono già indirizzi effettivi nella memoria fisica;

DLL (Dynamic Linked Libraries) è librerie a collegamento dinamico: il collegamento di una routine non avviene con l'esecuzione del link editor, ma al momento dell'esecuzione dell'applicazione che ne fa uso.

Il collegamento dinamico è caratterizzato da alcuni vantaggi rispetto al collegamento statico eseguito dal link editor:

Il collegamento dinamico permette la condivisione del codice. L’uso di librerie a collegamento dinamico semplifica la manutenzione delle applicazioni che le utilizzano: per

aggiornare un'applicazione non è necessario collegare tutti i moduli che la compongono con il link editor, ma è sufficiente sostituire le vecchie librerie con le nuove versioni. Tutti i programmi che richiamano una routine della libreria useranno automaticamente la versione aggiornata del codice.

Le applicazioni occupano minor spazio di memoria perché nel corso dell’esecuzione sono caricate solo le routine effettivamente usate: se una routine non è usata, non è caricata in memoria.

3. Multiprogrammazione e gestione della memoria

Nella gestione della memoria il sistema operativo deve allocare il maggior numero di processi in memoria centrale per aumentare la probabilità che ci sia sempre un processo pronto per essere eseguito.

Nei moderni sistemi operativi la gestione della memoria avviene con tecniche di memoria virtuale attuate con la paginazione e la segmentazione.

La memoria è parzialmente occupata dal sistema operativo e lo spazio restante è disponibile per i processi utente. I processi devono essere in memoria al momento dell'esecuzione ma, mentre sono sospesi o bloccati in attesa dei dati, possono essere spostati in un supporto di memoria esterna.

Il swapping dei processi avviene quando un processo è spostato temporaneamente sul disco e il suo posto può essere occupato da un altro processo in attesa di esecuzione.

Swap out e swap sono le due operazioni di rimozione dalla memoria e di ritorno in memoria.

La condivisione della memoria tra più processi è attuata usando diverse tecniche:

con la memoria suddivisa in partizioni fisse, con la memoria suddivisa in partizioni variabili

(o dinamiche), con allocazione della memoria mediante

paginazione, con allocazione della memoria mediante

segmentazione, con memoria virtuale a pagine o a segmenti.

Le tecniche di allocazione contigua: per assegnare la memoria a un processo, occorre trovare uno spazio di memoria libera abbastanza grande per contenerlo completamente.

A. Memoria a partizioni fisse : suddivide lo spazio di memoria a disposizione dei processi utente in un insieme di sottomemorie allocagli a

differenti processi. In una memoria con n partizioni possono essere quindi caricati n processi. La dimensione delle singole partizioni e il loro numero sono definiti al momento dell'installazione del sistema

operativo in base alle caratteristiche dei lavori che devono essere eseguiti. Sono possibili differenti strategie: la memoria può essere suddivisa in partizioni della stessa dimensione

oppure di dimensione differente. Numero e dimensione delle partizioni sono modificabili a freddo, cioè all'accensione del sistema, da un

operatore. Un processo può essere collocato in una partizione solo se questa è sufficientemente grande per contenerlo. I processi in attesa della memoria possono essere assegnati a un'unica coda, oppure possono essere inseriti

in code differenti, una per ogni partizione. Se i processi usano indirizzi di memoria assoluti, essi possono essere collocati nella sola partizione decisa al momento dell'esecuzione del link editor. In caso di indirizzamento rilocabile, invece, un processo può essere assegnato a qualsiasi partizione.

Il processo P6 non può essere messo in memoria perché non ci sono altre partizioni libere. L'ultima riga della tabella, mostra che, pur disponendo di una memoria utente di 52 MB, è possibile collocare in memoria solo cinque processi per un totale di 22 MB.

Gli esempi precedenti evidenziano i limiti che si incontrano con le partizioni di dimensione fissa:

uso inefficiente della memoria a causa della frammentazione interna; i processi devono essere di dimensione minore delle partizioni e lo spazio inutilizzato in ogni partizione forma un insieme di frammenti di memoria non utilizzabili;

notevoli limitazioni alla dimensione dei processi (non superare la dimensione della partizione più grande).

B. Memoria a partizioni variabili

La memoria utente è un'unica partizione della memoria libera: un processo è inserito in memoria in una qualsiasi zona libera, a condizione che sia abbastanza grande per contenerlo, creando così una partizione di dimensione pari a quella del processo.

La creazione di partizioni, grandi quanto i processi, evita la frammentazione interna ed è possibile ospitare processi di dimensione pari all'intera memoria utente.

La gestione della memoria è PIÙ complicata perché è necessario tenere conto dello stato di un numero variabile di partizioni.

P5 termina e parte dello spazio liberato dal processo è allocato a P6. Di seguito a P6 si formano due spazi liberi adiacenti che non sono riconosciuti come tali. Si formano gli spazi liberi tra i processi di memoria.

La frammentazione esterna è Il tipo di frammentazione con le partizioni variabili per indicare che è esterna alle partizioni. La frammentazione esterna può essere eliminata con il compattamento della memoria: si spostano i programmi in memoria in modo da creare un unico spazio libero in coda a tutti i processi.

Il compattamento della memoria è un'operazione faticosa e può essere eseguita raramente per evitare eccessivi sovraccarichi di lavoro per il sistema.

La gestione della memoria con le partizioni variabili richiede :

Apposite strutture dati per la gestione dello spazio libero e occupato. I diversi spazi vuoti di memoria possono essere descritti con un elenco che riporta l'indirizzo di partenza e la dimensione dello spazio libero. Lo spazio occupato dai processi può essere memorizzato in un elenco con l'indirizzo di partenza e la dimensione del processo.

È necessario operare la rilocazione dinamica del codice, per non appesantire gli overhead causati dal compattamento.

Purtroppo con le tecniche di allocazione contigua si formano molti spazi liberi di piccola dimensione che non sono in grado di accogliere alcun processo.

C. La paginazione: Lo spazio di memoria (memoria fisica) è suddiviso in blocchi, aventi tutti la

stessa dimensione, detti frame (cornici). Lo spazio di memoria dei processi (memoria logica) è suddiviso in blocchi di

dimensione uguale a quella dei frame, detti pagine. La dimensione delle pagine di memoria dipende dallo specifico sistema di gestione della memoria;

L'allocazione della memoria a un processo viene fatta assegnando alle pagine del processo frame di memoria liberi non necessariamente contigui.

Il page table (tabella delle pagine) è tabella dove è abbinato al numero di pagina logica il trame in cui essa è inserita. Ad ogni processo è associata una tabella delle pagine che può essere rappresentata con un array di puntatori ai trame delle pagine fisiche.

Per gestire lo stato della memoria servono le strutture dati opportune:

Una mappa di bit dell'elenco dei trame liberi: si utilizza un array di bit, uno per trame, dove uno 0 nell’array identifica un trame occupato, mentre un 1 rappresenta un trame libero. La mappa di bit mostra che i trame 4, 6, 8, 12, 13 e 14 sono liberi, mentre i rimanenti sono allocati ai processi.

Gli blocchi di trame contigui per elencare i trame liberi : tramite un elenco composto da una coppia di valori che descrivono il blocco con la posizione del primo trame e dal numero di trame di un blocco. Per esempio, una memoria dove sono liberi i trame: 4, 6, 8, 12,13, 14, è descritta dall'elenco: (4,1) (6,1) (8,1) (12,3)

Le intormazioni nella tabella delle pagine sono usate dall’hardware della MMU per trasformare gli indirizzi logici, generati dai processi, nei corrispondenti indirizzi fisici in memoria centrale.

Generalizzando, se la dimensione della pagina è una potenza di 10,10n (nell'esempio si ha 1000= 103). un indirizzo di memoria può essere scomposto in due parti:

Con indirizzi di memoria di 5 cifre decimali si può descrivere una memoria con 100 pagine, identificate con numeri di pagina da 00 a 99, avente ciascuna 1000 parole di memoria.

Gli indirizzi prodotti dal processo sono indirizzi logici che devono essere trasformati nel corrispondente indirizzo fisico:

numero di trame posizione nel trame.

La traduzione nell’indirizzo fisico viene attuata dall'hardware della MMU dividendo il campo indirizzi, di 16 bit, in due parti:

i 4 bit più significativi rappresentano il numero di pagina, i 12 bit a destra indicano la posizione all'interno della pagina.

I 16 bit di un indirizzo sono suddivisi dalla MMU in due parti per identificare il numero di pagina, tramite i 4 bit di ordine più elevato, e la posizione dentro la pagina, detta offset (sbilanciamento), mediante i 12 bit meno significativi.

Il numero di pagina, rappresentato con 4 bit, può variare da 0 a 15, per un totale di 16 pagine, mentre la posizione nella pagina, di 12 bit, può variare da 0 a 4095, cioè per 4 K indirizzi distinti.

Ogni pagina del processo è collocata in un frame di pari valore: la pagina 0 è nel frame 0, la pagina 1 nel frame 1 e così via. Questo significa, in pratica, che indirizzo logico e indirizzo fisico coincidono.

Passando dal valore decimale alla rappresentazione binaria, l'indirizzo 6248 diventa:

L’indirizzo fìsico è quindi 0111 1000 0110 1000 che corrisponde al valore decimale 30824.

Per ragioni di efficienza la traduzione è eseguita direttamente dall'hardware della MMU che usa la tabella delle pagine del processo per trasformare il numero di pagina nel corrispondente numero di frame.

Quando un nuovo processo è collocato in memoria, il sistema operativo:

registra nella page table del processo i corrispondenti trame di allocazione,

scrive in un apposito registro della MMU la posizione in memoria della tabella delle pagine,

esegue il processo scrivendo nel program counter l’indirizzo di partenza del processo.

L'esecuzione del processo ha inizio. Gli indirizzi generati dalla CPU non sono inviati direttamente alla memoria, ma alla MMU per essere trasformati.

Nella MMU gli indirizzi, di n bit, sono scomposti in due parti:a. gli m bit di ordine inferiore (m bit per pagine di

dimensione 2m), specificano la posizione s dell'indirizzo logico nella pagina;

b. gli ri-m bit rimanenti precisano il numero di pagina dell'indirizzo logico, indicato con #p.

La MMU usa il valore #p come indice per accedere alla tabella delle pagine del processo, dove è registrato il numero di frame #f di allocazione della pagina.

La MMU costruisce l'indirizzo fisico, componendo #f con la posizione nella pagina s. L'indirizzo fisico è usato per accedere alla memoria.

Durante la paginazione: la memoria è usata in modo efficiente, perché non c'è frammentazione esterna, salvo una trascurabile frammentazione interna dovuta al fatto che l'ultima pagina del processo non è completamente riempita.

Gli svantaggi della paginazione sono dovuti: ai costi, in termini di spazio e di tempo:

• Lo spazio dedicato a un processo cresce per la presenza in memoria della tabella delle pagine. Per esempio un processo di 200 MB con pagine di 4 KB richiede una page table di 200 • 220 / 4 • 210 = 50 • 210, cioè 50 K, elementi. Supponendo che ogni riga della page table occupi 4 byte, la tabella delle pagine occupa 200 KB.

• Il tempo di accesso alla memoria aumenta, perché per accedere a un dato in memoria è necessario effettuare due accessi fisici alla memoria: il primo per leggere nella page table il numero di frame dove si trova il dato, il secondo per leggere o scrivere il dato vero e proprio.Per risolvere questo problema la MMU include hardware aggiuntivo rappresentato da una speciale memoria cache.

La memoria virtuale

La memoria virtuale è il modo standard di gestire la memoria negli attuali sistemi. La memoria virtuale sfrutta il meccanismo della paginazione, ma non richiede la presenza in memoria del codice dell’intero processo.

L'idea alla base della memoria virtuale è:

non è necessario che un processo sia collocato interamente in memoria; è sufficiente che in memoria centrale è presente la porzione di codice in esecuzione in quel momento, il resto del codice del processo può rimanere sul disco, pronto per essere caricato quando è necessario.

L'inutilità di portare in memoria l'intero processo è evidenziata anche dal fatto che probabilmente certe parti del codice non saranno mai eseguite. Si pensi, per esempio, alle diverse routine per la gestione degli errori. Avere in memoria solo una frazione dell'intero processo presenta i vantaggi:

A memoria fisica installata si possono caricare un maggior numero di processi aumentando così il grado di multiprogrammazione del sistema e migliorando l'utilizzazione della CPU.

È possibile eseguire processi di dimensione superiore a quella delle memoria fisica: A. il programmatore non ha bisogno di conoscere la dimensione della memoria sulla quale sarà

eseguito il programma che sta scrivendo. B. La progettazione del software è semplificata e la sua portabilità tra sistemi è garantita.

Nella gestione della memoria virtuale ci sono due modi di gestire le parti nelle quali è suddiviso un processo:

memoria virtuale a pagine quando il processo è suddiviso in blocchi della stessa dimensione; memoria virtuale a segmenti se il processo è suddiviso in parti aventi dimensione diversa.

La gestione della memoria virtuale a pagine:

Con la memoria virtuale la dimensione di un processo è limitata dalla capacità di indirizzamento del processore.

Se il processore prevede istruzioni macchina con indirizzi di n bit, è possibile indirizzare una memoria virtuale di 2n parole.

Lo spazio degli indirizzi virtuali è definito dal numero di bit dell'indirizzo:a. la memoria con indirizzi di 32 bit si ha una memoria virtuale di: 232 byte = 4 • 230 byte = 4

GB b. mentre con indirizzi di memoria a 64 bit la memoria virtuale è: byte = 24 • 220 • 240 byte,

circa 16.000.000 TB

Cosi si dice che il numero di pagine è molto più grande del numero di trame di memoria reale installata.

Supponiamo che un processo abbia uno spazio di indirizzi virtuale di N parole: la memoria fisica, di M parole, costituisce lo spazio di memoria reale ed è composta da un certo numero di blocchi della stessa dimensione di quella delle pagine.

Page fault o fault di pagina (assenza di una pagina) avviene quando la MMU opera il mapping tra pagine di memoria virtuale e trame di memoria reale e trova che il processo non è tutto in memoria >>> La MMU segnala l'assenza in memoria di una pagina virtuale >>> la MMU invia un segnale di interruzione che provoca l'intervento del sistema operativo per caricare in memoria la pagina mancante.

Per esempio: la pagina 2 del processo si trova nel trame 5 della memoria, mentre la pagina x non è caricata in memoria. Il tentativo di accedere alla pagina x genera un page fault. Il sistema operativo deve allora ricopiare la pagina mancante in un trame libero eseguendo un’operazione di swap in:

Se non ci sono trame liberi, il sistema operativo deve liberare un trame salvando la pagina su disco con un'operazione di swap out. Lo swapping delle pagine è lunga, per la necessità di operare trasferimenti da e per il disco.

Se il numero di pagine in memoria è troppo basso ci sono molti fault di pagina e il sistema operativo deve eseguire molti swapping di pagina provocano una condizione di thrashing.

Thrashing : sistema passa il tempo a spostare pagine tra la memoria e il disco invece di eseguire istruzioni.

Il resident set (insieme residente) del processo sono le pagine di un processo in memoria in un certo momento. La dimensione del resident set è un parametro critico per il funzionamento della memoria virtuale:

se il resident set è troppo piccolo, si ha un sovraccarico del sistema che causa il thrashing, se invece il resident set è troppo grande, ci sono in memoria molte pagine inutilizzate e il grado di

multiprogrammazione diminuisce.

I vantaggi della memoria virtuale sono confermati dall'esperienza di molti sistemi operativi che ne fanno uso. La memoria virtuale funziona con modalità analoghe alla memoria cache:

Principio di località temporale , se un programma accede a una parola di memoria è probabile che in un breve intervallo di tempo acceda di nuovo alla stessa cella di memoria.

Principio di località spaziale , un programma che accede a una parola di memoria accederà probabilmente, entro breve tempo, a celle di memoria vicine. In particolare il principio di località spaziale sta alla base della tecnica di gestione della memoria virtuale: quando un processo usa certe pagine continuerà a usarle per un certo periodo, senza accedere alle altre.

La tabella delle pagine

Il bit di validità o bit di presente/assente c’e in ogni riga della tabella delle pagine e indica se quella riga della tabella delle pagine è valida (V=7), oppure non è valida (V=0) perché la pagina non è in memoria.

L'assenza della pagina in memoria causa la chiamata della routine per la gestione dell'interruzione da page fault e l’esecuzione delle seguenti azioni:

Il sistema operativo mette nello stato bloccato il processo che ha causato il fault di pagina e identifica un altro processo da eseguire, scegliendolo tra quelli nello stato ready.

Il sistema operativo controlla lo stato della memoria per scegliere un frame dove collocare la pagina richiesta. Se in memoria non ci sono frame liberi, deve identificare, con un opportuno algoritmo, il frame da liberare. Per effetto della rimozione della pagina, dovrà essere aggiornata la riga della tabella delle pagine liberata, mettendo a 0 il bit di validità. Il frame con la pagina da rimuovere è ricopiato su disco.

Il sistema operativo attiva il trasferimento dei dati da disco in memoria, per ricopiare la pagina richiesta nel frame prescelto. Attivato il trasferimento.

Dopo aver completato il trasferimento da disco a memoria, il sistema operativo aggiorna la tabella delle pagine del processo e lo mette nello stato ready.

Le azioni descritte per la gestione della pagina mancante sono rappresentati dal seguente diagramma di flusso.

Un bit di pagina modificata M, dirty bit: Ogni riga delle tabella delle pagine spesso lo contiene , oltre al bit di validità, ed è impostato a 0 al momento del caricamento della pagina in memoria.

Il sistema operativo, prima di liberare il frame, controlla il valore di M: se il valore di M è 0, allora la pagina non è mai stata modificata e lo spazio in memoria può essere sovrascritto.

Con la paginazione:

aumenta il tempo di accesso alla memoria, perché con la tabella delle pagine in memoria, ogni accesso alla memoria si traduce in due accessi,

lo spazio riservato a un processo cresce per la presenza della tabella delle pagine.

Per ridurre il tempo di accesso alla memoria, si usa una speciale memoria cache, molto veloce, posta nella MMU detta TLB (Translation Lookaside Buffer), funziona come ogni altra memoria cache.

L’elemento necessario è cercato nel buffer TLB:

se si trova in TLB è immediatamente usato; invece, l'elemento è prelevato dalla tabella delle pagine posta in memoria e ricopiato nel TLB.

Nel TLB, come avviene in tutte le memorie cache, non c'è l’intera tabella delle pagine, ma solo una sua parte. Per sapere se una riga della tabella è in TLB, senza scorrere l’intera tabella, l’accesso al TLB avviene in parallelo.

Nel caso della memoria virtuale il problema dello spazio occupato dalla tabella delle pagine non è trascurabile. Per esempio, con uno spazio di indirizzamento virtuale di 4 GB e pagine di 4 KB, la tabella delle pagine è composta da:

4 GB / 4 KB = 4 • 230 byte / 4 • 210 byte = 220 = 1 M ovvero circa 1.000.000 di elementi per processo. Il problema dello spazio occupato dalla tabella della pagine è risolto in diversi modi: in particolare si utilizza una tecnica che prevede la possibilità di organizzare la tabella delle pagine in una struttura ad albero e di portare in memoria le sole foglie con le informazioni sulle pagine effettivamente usate dal processo.

La segmentazione è:

una tecnica di allocazione dei processi in memoria che differisce dalla paginazione perché i processi sono suddivisi in blocchi, detti segmenti, di differente dimensione.

Analogamente a quanto succede alle pagine con la paginazione, un processo segmentato è allocato in memoria per segmenti non necessariamente adiacenti.

La segmentazione riflette la visione che il programmatore ha del proprio programma. Per esempio un programma potrebbe essere composto da un certo numero di segmenti secondo la strutturazione dei moduli che lo compongono: un segmento per il programma principale, uno per ogni sottoprogramma, un altro ancora per un blocco di dati e così via. Nel caso della paginazione, invece, un processo è formato da un unico spazio di memoria che è suddiviso artificialmente in un certo numero di blocchi.

La segmentazione presenta, rispetto alla paginazione, i seguenti vantaggi:

la gestione di spazi memoria condivisi è più semplice perché i dati (o il codice) da condividere possono essere inseriti in un unico segmento che viene condiviso tra i processi;

la protezione della memoria può essere effettuata in modo puntuale secondo le esigenze del singolo segmento;

la gestione delle strutture dati dinamiche è semplificata perché, se nell'esecuzione del processo lo spazio occupato dai dati aumenta, basta aumentare la dimensione di quello specifico segmento. Nel caso della paginazione è invece impossibile aumentare la dimensione delle pagine.

Per usare al meglio i vantaggi della segmentazione senza incorrere nei problemi della frammentazione esterna si usano i sistemi di indirizzamento che combinano segmentazione e paginazione. In tal caso avviene la paginazione dei segmenti che compongono un processo.

Gestione delle pagine nella memoria virtuale

L'efficienza della memoria virtuale è notevolmente influenzata dalla qualità delle scelte del sistema operativo nell'allocazione delle pagine in memoria.

Se il numero di frame assegnati a un processo, cioè la dimensione del resident set del processo, è troppo basso, ci sono molti fault di pagina con elevati costi di sistema che possono portare a una condizione di thrashing.Occorre quindi assegnare a un processo un numero di frame adeguato.

Scelto il numero N di trame da allocare a un processo, il sistema operativo deve gestire due situazioni simmetriche:

strategia di prelevamento : la strategia di portare in memoria una nuova pagina,

strategia di sostituzione: la strategia della scelta da rimuovere della pagina dalla memoria per fare posto a nuove pagine.

Strategia di prelevamento: definisce il momento di allocazione di una pagina in memoria. Ci sono due politiche opposte:

1.La paginazione a richiesta (Demand Paging) che porta una pagina in memoria solo quando si fa riferimento ad un indirizzo in quella pagina. Questa politica provoca un elevato numero di page fault.

2.La prepaginazione è una strategia di tipo anticipatorio che, cerca di prevedere le esigenze del processo, portando in memoria un certo numero di pagine per volta. Per esempio, in caso di fault di pagina il sistema operativo porta in memoria la pagina richiesta e altre pagine vicine ad essa. Con questa strategia avviene il lavoro inutile a causa della difficoltà di conoscere in antìcipo se una pagina sarà richiesta.

Strategia di sostituzione: Riguarda la selezione della pagina da rimuovere dalla memoria per far posto ad una nuova pagina da caricare.

La strategia di sostituzione deve in primo luogo definire qual è l'insieme delle pagine tra le quali scegliere la pagina da scaricare.

N on rientrano nella sostituzione :

le pagine che costituiscono il nucleo del sistema operativo, le pagine delle principali strutture dati per il controllo dei processi e per la gestione dei buffer di I/O.

La politiche di sostituzione:

1.Strategie di sostituzione locali, cioè per allocare un frame a un processo il sistema operativo libera un frame scelto tra quelli allocati al processo.

2.Strategie di sostituzione globali, per allocare un frame a un processo il sistema operativo libera un frame scelto tra tutti i frame allocati a qualsiasi processo.

Il sistema operativo deve usare opportuni criteri per la scelta della pagina da rimuovere dalla memoria: gli algoritmi. Gli algoritmi di sostituzione sono le tecniche con le quali è attuata la scelta.

Il seguente esempio illustra come lavorano gli algoritmi utilizzati dal sistema operativo per scegliere la pagina da rimuovere dalla memoria.

Il miglior algoritmo possibile è quello che genera il minor numero di fault di pagina, è l'algoritmo ottimo, indicato spesso come algoritmo OPT:

La pagina scelta per la sostituzione è quella che sarà referenziata il più in là possibile nel tempo.

L'algoritmo OPT non esiste , è un algoritmo di riferimento эталонный алгоритм, sta alla base di altri algoritmi.

Algoritmo FIFO (First-ln First-Out) le pagine sono rimosse con uno schema round robin, secondo il quale la pagina da eliminare è quella che è stata il più a lungo in memoria. È semplice da implementare, ma non c'è alcuna possibilità di prevedere quali saranno le pagine richieste in futuro. La pagina rimossa dalla memoria può essere poi richiesta molto presto.

Algoritmo LRU (Least Recently Used, usata meno di recente) rimossa è la pagina che non è stata usata da maggior tempo.

Algoritmo della seconda opportunità è una variante dell’algoritmo FIFO ma che NON elimina una pagina dalla memoria solo perché è stata caricata da molto tempo. L'algoritmo usa il bit di controllo U della tabella delle pagine. Il valore di questo bit, è posto a 1 dall'hardware quando la pagina è referenziata (letta o scritta).

L'algoritmo della seconda opportunità esamina la coda gestita in modalità FIFO ma, prima di rimuovere la pagina che si trova in cima alla coda, controlla il valore del bit U: se U=0 la pagina è rimossa, se invece U=1 la pagina è messa in fondo alla coda con il valore di U riportato a 0 e la pagina che segue nella coda diventa la pagina candidata alla rimozione. L'algoritmo della seconda opportunità è considerato un algoritmo che approssima efficientemente le prestazioni dell’algoritmo LRU.

Processi e memoria in Linux Ubuntu

In Linux la memoria fisica è suddivisa in pagine e la memoria virtuale è suddivisa in segmenti. Ogni processo dell'utente occupa diversi segmenti di memoria virtuale. Ogni segmento di memoria virtuale è mappato in una o più pagine di memoria fisica.

Il programma Monitor di sistema di Linux Ubuntu è un’applicazione grafica che permette di avere una visione istantanea delle risorse, hardware e software, del sistema.

La scheda Risorse visualizza:

informazioni in tempo reale sulla CPU, l'uso della memoria e della rete,

Nella sezione Cronologia memoria e swap sono visualizzati due grafici di quantità di memoria RAM e di quantità di memoria swap.

La finestra del grafico presenta la situazione dell'ultimo minuto di attività del sistema. Sotto il grafico temporale ci sono due piccoli grafici a torta che rappresentano la percentuale di utilizzo della memoria RAM e della memoria swap. L'osservazione di queste informazioni è importante per controllare quando l'occupazione di memoria diventa troppo alta:

apri la scheda Processi del Monitor di sistema e identificare i processi che richiedono più memoria.

Nella scheda Processi, come abbiamo visto nel capitolo precedente, facendo clic con il tasto destro del mouse sul nome di un processo e scegliendo Proprietà, si apre una finestra con tutte le proprietà del processo.

Tra esse, sei proprietà riguardano la memoria utilizzata dal processo: Memoria indica la quantità di memoria fisica richiesta dal processo.

Memoria virtuale indica la quantità di memoria virtuale allocata per il processo, una memoria richiesto dalle librerie e dagli oggetti eseguibili mappati nel processo.

Memoria residente è la quantità di memoria fisica attualmente utilizzata nella RAM. Questo valore è normalmente superiore alla memoria richiesta dal processo, una pagina di memoria può essere non completamente utilizzata.

Memoria scrivibile è la quantità dello spazio di indirizzi che il processo ha allocato con i privilegi di scrittura. Memoria condivisa è la quantità di memoria che il processo può condividere con altri processi . Memoria server X è la memoria utilizzata dal server X, il server per l'interfaccia grafica del processo (GUI).

Nella scheda Processi, facendo clic con il tasto destro del mouse sul nome di un processo e scegliendo Mappe memoria, si apre la finestra delle mappe di memoria associate al processo. Le informazioni sono visualizzate in formato tabellare. Le figure seguenti mostrano le mappe di memoria relative al programma gedit (editor di testi): le prime 3 colonne della tabella sono nella prima figura e le colonne successive nella seconda figura.

Nome file: il percorso del modulo delle librerie software utilizzate dal processo. Se Nome file è vuoto, le posizioni di memoria appartengono al processo indicato come intestazione della tabella.

Inizio VM (Virtual Memory) : l’indirizzo di memoria (in esadecimale) dove inizia il segmento.

Fine VM: l'indirizzo di memoria (in esadecimale) dove termina il segmento.

Dimensione VM: la dimensione del segmento di memoria. Flags: descrivono i diversi tipi di accesso al segmento di

memoria da parte del processo (la presenza della lettera indica l'accesso attivato, il segno meno la disattivazione).

a. p (private), segmento privato del processo; b. r (read), permesso di lettura; c. s (share), condivisione con altri processi; d. w (write), permesso di scrittura;e. x (execute), permesso di esecuzione delle istruzioni contenute nel segmento.

Privata clean (letteralmente pulita): quantità di memoria privata non modificata (quindi non necessita di aggiornamento quando viene paginata nell'area di swap).

Privata dirty (letteralmente sporca): quantità di memoria privata modificata (quindi necessita di aggiornamento quando viene paginata nell’area di swap).

Condivisa clean: quantità di memoria condivisa non modificata. Condivisa dirty: quantità di memoria condivisa modificata. Offset VM: offset del segmento di memoria. Device: il nome del dispositivo dove si trova il modulo delle librerie condivise. Inode: l'identificativo del dispositivo.

La lista può essere ordinata usando come criterio una delle colonne della tabella: basta fare clic con il mouse sul nome della colonna per ottenere l'ordinamento in un verso (crescente o decrescente) e un secondo clic per ottenere l’ordinamento nel verso opposto.