Sistemi operativi

MMU

Per ora illustriamo un semplice schema di associazione degli indirizzi tramite mmu, che è una genera-

lizzazione dello schema con registro di base descritto nel Paragrafo 9.1.1.

Il registro di base è ora denominato registro di rilocazione: quando un processo utente genera un

indirizzo, prima dell’invio all’unità di memoria, si somma a tale indirizzo il valore contenuto nel registro

di rilocazione. Per esempio, se il registro di rilocazione contiene il valore 14000, un tentativo da parte

dell’utente di accedere alla locazione 0 è dinamicamente rilocato alla locazione 14000; un accesso alla

locazione 346 è mappato alla locazione 14346.

Rilocazione dinamica con un registro di rilocazione

Il programma utente non vede mai i reali indirizzi fisici. Il programma crea un puntatore alla locazione

346, lo memorizza, lo modifica, lo confronta con altri indirizzi, tutto ciò sempre come il numero 346.

Solo quando assume il ruolo di un indirizzo di memoria (magari in una load o una store indiretta),

si riloca il numero sulla base del contenuto del registro di rilocazione. Il programma utente tratta

indirizzi logici, l’architettura del sistema converte gli indirizzi logici in indirizzi fisici.

7.2 Allocazione contigua della memoria

Generalmente si vuole che più processi utenti risiedano contemporaneamente in memoria centrale.

Perciò è necessario considerare come assegnare la memoria disponibile ai processi presenti nella coda

d’ingresso che attendono di essere caricati in memoria. Con l’allocazione contigua della memoria,

ciascun processo è contenuto in una singola sezione di memoria contigua a quella che contiene il processo

successivo.

Ogni indirizzo logico deve cadere nell’intervallo specificato dal registro limite; la mmu fa corrispondere

dinamicamente l’indirizzo fisico all’indirizzo logico sommando a quest’ultimo il valore contenuto nel

registro di rilocazione (vedi figura sotto), e invia l’indirizzo risultante alla memoria.

56

Sistemi Operativi 7 Memoria centrale

Registri di rilocazione e limite

Lo schema con registro di rilocazione consente al sistema operativo di cambiare dinamicamente le

proprie dimensioni. Tale flessibilità è utile in molte situazioni; il sistema operativo, per esempio,

contiene codice e spazio di memoria per i driver dei dispositivi. Se un driver di periferica non è

attualmente in uso, ha poco senso mantenerlo in memoria.

Uno dei metodi più semplici per l’allocazione della memoria consiste nel suddividere la stessa in par-

tizioni di dimensione variabile, dove ciascuna partizione può contenere esattamente un processo.

In questo schema a partizione variabile il sistema operativo conserva una tabella in cui sono indicate

le partizioni di memoria disponibili e quelle occupate.

La figura sotto illustra questo schema. Inizialmente, la memoria è completamente utilizzata e contiene

i processi 5, 8 e 2. Dopo l’uscita del processo 8 si forma un unico buco. Successivamente, entra

in memoria il processo 9, per il quale viene allocata memoria. Quindi il processo 5 viene rimosso,

producendo due buchi non contigui. Schema a partizione variabile

Che cosa succede quando non c’è sufficiente memoria per soddisfare le esigenze di un processo in

arrivo? Un’opzione semplice è rifiutare il processo e fornire un messaggio di errore appropriato. In

alternativa, possiamo inserire il processo in una coda di attesa. Quando, in seguito, la memoria viene

rilasciata, il sistema operativo controlla la coda di attesa per determinare se può soddisfare le richieste

di memoria di un processo in attesa.

In generale è sempre presente un insieme di buchi di diverse dimensioni sparsi per la memoria. Quando

si presenta un processo che necessita di memoria, il sistema cerca nel gruppo un buco di dimensioni

sufficienti per contenerlo. I criteri più usati per scegliere un buco libero tra quelli disponibili nell’insieme

sono i seguenti:

• First-fit: si assegna il primo buco abbastanza grande;

• Best-fit: si assegna il piú piccolo buco in grado di contenere il processo;

• Worst-fit: si assegna il buco piú grande. 57

Sistemi Operativi 7 Memoria centrale

Con l’uso di simulazioni si è dimostrato che sia first-fit sia best-fit sono migliori rispetto a worst-fit in

termini di risparmio di tempo e di utilizzo di memoria.

Entrambi i criteri first-fit e best-fit di allocazione della memoria soffrono di frammentazione esterna.

Caricando e rimuovendo i processi dalla memoria, si frammenta lo spazio libero della memoria in tante

piccole parti. Si ha la frammentazione esterna se lo spazio di memoria totale è sufficiente per soddisfare

una richiesta, ma non è contiguo; la memoria è frammentata in tanti piccoli buchi.

Una soluzione al problema della frammentazione esterna è data dalla compattazione. Lo scopo è

quello di riordinare il contenuto della memoria per riunire la memoria libera in un unico grosso blocco.

Il più semplice algoritmo di compattazione consiste nello spostare tutti i processi verso un’estremità

della memoria: tutti i buchi si spostano nell’altra direzione formando un grosso buco di memoria.

Un’altra soluzione é data dalla paginazione.

7.3 Paginazione

La paginazione é uno schema di gestione della memoria che consente allo spazio di indirizzamento

fisico di un processo di essere non contiguo. La paginazione evita la frammentazione esterna e la

necessitá di compattazione. L’implementazione della paginazione è frutto della cooperazione tra il

sistema operativo e l’hardware del computer.

Il metodo di base per implementare la paginazione consiste nel suddividere la memoria fisica in blocchi

di dimensione fissa, detti frame, e nel suddividere la memoria logica in blocchi di pari dimensione,

detti pagine. Quando si deve eseguire un processo, si caricano le sue pagine nei frame disponibili.

Ogni indirizzo generato dalla cpu è diviso in due parti: un numero di pagina (p), e un offset di pagina

(d ):

Il numero di pagina serve come indice per la tabella delle pagine relativa al processo. La tabella delle

pagine contiene l’indirizzo di base di ciascun frame nella memoria fisica e l’offset è la posizione nel

frame a cui viene fatto riferimento. Pertanto, l’indirizzo di base del frame viene combinato con l’offset

della pagina per definire l’indirizzo di memoria fisica.

Hardware di paginazione

58

Sistemi Operativi 7 Memoria centrale

Descriviamo di seguito i passaggi adottati dalla mmu per tradurre un indirizzo logico generato dalla

cpu in un indirizzo fisico.

1. Estrarre il numero di pagina p e utilizzarlo come indice nella tabella delle pagine.

2. Estrarre il numero di frame f corrispondente dalla tabella delle pagine.

3. Sostituire il numero di pagina p nell’indirizzo logico con il numero di frame f.

L’offset d non cambia e pertanto non viene sostituito; il numero di frame e l’offset determinano insieme

l’indirizzo fisico.

La paginazione non è altro che una forma di rilocazione dinamica: a ogni indirizzo logico

l’architettura di paginazione fa corrispondere un indirizzo fisico.

7.3.1 Supporto hardware alla paginazione

La memorizzazione della tabella delle pagine nella memoria principale può favorire cambi di contesto

più rapidi, ma può anche comportare tempi di accesso alla memoria più lenti.

La soluzione tipica a questo problema consiste nell’impiego del TLB (translation look-aside buffer ),

una speciale, piccola cache hardware. Il tlb è una memoria associativa ad alta velocità in cui ogni

elemento consiste di due parti: una chiave (o tag) e un valore.

Quando si presenta un elemento, il tlb lo confronta contemporaneamente con tutte le chiavi; se trova

una corrispondenza, riporta il valore correlato.

Il tlb si usa insieme con le tabelle delle pagine nel modo seguente: il tlb contiene una piccola parte degli

elementi della tabella delle pagine; quando la cpu genera un indirizzo logico, si presenta il suo numero

di pagina al tlb; se tale numero è presente, il corrispondente numero del frame è immediatamente

disponibile e si usa per accedere alla memoria.

Se nel tlb non è presente il numero di pagina, situazione nota come insuccesso del tlb (tlb miss), si

deve consultare la tabella delle pagine in memoria. In questo caso, i numeri della pagina e del frame

vengono inseriti nel tlb in modo tale che al riferimento successivo la ricerca sará molto piú rapida.

Hardware di paginazione con TLB

59

Sistemi Operativi 7 Memoria centrale

Alcuni tlb memorizzano gli identificatori dello spazio d’indirizzi (address-space identifier, ASID)

in ciascun elemento del tlb. Un ASID identifica in modo univoco ciascun processo e si usa per fornire

al processo corrispondente la protezione del suo spazio d’indirizzi. Quando tenta di trovare i valori

corrispondenti ai numeri delle pagine virtuali, il tlb si assicura che l’asid per il processo attualmente

in esecuzione corrisponda all’asid associato alla pagina virtuale. La mancata corrispondenza dell’asid

viene trattata come un tlb miss.

La percentuale di volte che il numero di pagina di interesse si trova nel tlb è detta tasso di successi

(hit ratio).

Di solito si associa a ciascun elemento

della tabella delle pagine un ulteriore bit,

detto bit di validità. Tale bit, imposta-

to a valido, indica che la pagina corri-

spondente è nello spazio d’indirizzi logici

del processo, quindi è una pagina valida;

impostato a non valido, indica che la pa-

gina non è nello spazio d’indirizzi logici

del processo.

Il bit di validità consente quindi di ri-

conoscere gli indirizzi illegali e di noti-

ficarne la presenza attraverso un’eccezio-

ne. Il sistema operativo concede o impe-

disce l’accesso a una pagina impostando

in modo appropriato tale bit.

Un vantaggio della paginazione risiede nella possibilità di condividere codice comune, il che è

particolarmente importante in un ambiente con più processi.

Condivisione della libreria standard del C in un ambiente paginato

60

Sistemi Operativi 7 Memoria centrale

7.4 Struttura della tabella delle pagine

In questo paragrafo si descrivono alcune tra le tecniche più comuni per strutturare la tabella delle

pagine: la paginazione gerarchica, la tabella delle pagine di tipo hash e la tabella delle

pagine invertita.

7.4.1 Paginazione gerarchica

La maggior parte dei moderni calcolatori dispone di uno spazio d’indirizzi logici molto grande. In un

ambiente di questo tipo la stessa tabella delle pagine diventa eccessivamente grande. Chiaramente,

sarebbe meglio evitare di collocare la tabella delle pagine in modo contiguo in memoria centrale. Una

semplice soluzione a questo problema consiste nel suddividere la tabella delle pagine in parti più piccole.

Un metodo consiste nell’adottare un algoritmo di paginazione a due livelli, in cui la tabella stessa

è paginata. Schema di una tabella delle pagine a due livelli

Poic