Appunti per l'esame di Sistemi operativi

MMU

logici del programma vengono mappati dalla 31

sugli indirizzi fisici, visibili solo dalla memoria ed in

comune per ogni programma che risiede in essa.

Nella versione più semplice l'associazione avviene

sommando l’indirizzo logico al registro di rilocazione

ed effettuando un controllo per verificare che

l’indirizzo fisico non vada oltre il registro limite.

OSS Per ottimizzare l’utilizzo della memoria è

dynamic loading

possibile utilizzare il (caricamento dinamico) che permette di caricare

solo porzioni del programma in memoria durante l’esecuzione, quando necessarie.

Il linking dinamico si utilizza anche per sfruttare le librerie di sistema delle quali si salva

solo un riferimento e non tutto il codice.

Swapping (avvicendamento processi)

Per aumentare gli indirizzi fisici della memoria è possibile creare aree di swapping sul

disco nelle quali spostare temporaneamente

processi momentaneamente inattivi.

Quando il sistema schedula un processo dalla

ready queue, controlla prima se questo è

presente nella memoria principale, altrimenti

lo carica dall’area di swap. swap out

Sa la memoria è piena esegue uno swap in

di un processo già presente ed uno

del processo richiesto, questo però aumenta

di molto il tempo di context switch.

Lo swapping non è presente su dispositivi

mobili, i quali chiudono direttamente altri

processi attivi.

MMU = memory-management unit, componente hardware per la mappatura degli indirizzi

31 29

Allocazione contigua della memoria

La prima parte della memoria fisica è riservata per il sistema operativo, il resto viene

lasciato ai processi, ognuno dei quali possiede una sezione contigua di memoria.

L’utilizzo degli indirizzi di rilocazione perme al sistema operativo di cambiare le sue

dimensioni semplicemente alterando il loro valore.

Esistono diversi modi per effettuare l’allocazione:

- Schema a partizioni fisse => implementazione più semplice (non più in uso), consiste

nel dividere la memoria in sezioni di dimensione fissa ad ognuna delle quali si associa

un processo, limita multiprogrammazione.

- Schema a partizione variabile => la grandezza della sezione di memoria viene

calcolata al momento di avvio del processo aumentando la flessibilità, inoltre il SO

mantiene una tabella con posizione e grandezza degli spazi vuoti.

Avendo che processi diversi necessitano di una quantità diversa di memoria nasce

problema di allocazione dinamica della memoria,

il ovvero in quale buco libero

allocare i dati dei nuovi processi, si

possono usare 3 diversi criteri:

First-fit

• => il primo spazio libero

abbastanza grande

Best-fit

• => il più piccolo buco

abbastanza grande

Worst-fit

• => il più grande tra quelli disponibili

frammentazione

OSS si crea inoltre il problema della che implica un utilizzo

inefficiente dello spazio libero

La frammentazione

Ne esistono 2 tipi:

- Frammentazione esterna => Ne soffrono first-fit e best-fit , si verifica quando, pur

avendo spazio sufficiente in memoria, non è possibile allocare dati poiché le sezioni

libere non sono contigue.

Infatti caricando e rimuovendo dalla memoria dati di diverse dimensioni, si

possono creare tanti piccoli buchi frammentati.

Una soluzione a questo problema è data dalla compattazione che permette di

spostare le locazioni di memoria utilizzando solamente l’indirizzo di rilocazione

- Frammentazione interna => si verifica quando la memoria allocata è superiore a

quella realmente necessaria a causata dall’allineamento dei dati.

L’allineamento è utile poiché permette

di ridurre le strutture necessarie per la

memorizzazione di posizioni e

grandezze, inoltre semplifica molte

operazioni. 30

Segmentazione

Con questo approccio non si vede più la memoria come un grande array lineare ma si

associa un segmento di memoria ad ogni componente del programma (ex. stack, heap).

<numero segmento, offset>,

A livello logico si usano indirizzi bidimensionali del tipo dove

numero segmento specifica il componente del programma e offset specifica l’indirizzo

logico all’interno dell’elemento.

La traduzione da indirizzi logici bidimensionali a indirizzi fisici unidimensionali si effettua

tabella dei segmenti, base segmento

tramite la ogni suo elemento è una coppia ordinata

limite segmento,

e la base contiene l’indirizzo iniziale del segmento e il limite la fine.

Quindi riprendendo la coppia

<numero segmento, offset>:

- Numero segmento estrae l’elemento

base con l'indirizzo

- Offset viene confrontato con il limite

corrispondente al componente

IF (offset < limite) offset si somma a

base e genera indirizzo fisico

ELSE si genera errore

OSS soffre del problema della

frammentazione esterna 31

Paginazione frame,

Consiste nel suddividere la memoria fisica in blocchi di dimensione fissa, detti su

tabella delle pagine pagine.

cui mappare (tramite la ) blocchi di memoria logica, detti

32

Ogni processo possiede una propria tabella delle pagine che si ricollega ad una tabella

tabella di frame,

principale, detta visibile solo al kernel, e nella quale sono indicati tutti i

frame già occupati e il/i processo/i a cui sono assegnati.

Questa completa separazione tra indirizzi

fisici ed indirizzi logici è ciò che permette

ad ogni processo di avere un immagine

di memoria (memoria virtuale) con spazio

degli indirizzi pari all’architettura

(ex. 64 bit) anche se la memoria reale è

nettamente inferiore.

La dimensione dei frame, e quindi delle

pagine, dipende dall’hardware e dal

sistema operativo, generalmente nei

sistemi di linux è di 4KB.

OSS Frame fissi evitano il problema della

frammentazione esterna ma possono

portare a problemi di frammentazione

interna.

indirizzamento

Dato uno spazio degli indirizzi logici di 2 bit (dove n è pari all’architettura) con pagine di

n

dimensione 2 bit, si ha che ogni indirizzo logico viene diviso in 2 componenti:

k

- Numero della pagina => contiene un indice

della tabella delle pagine tramite il quale è

possibile ricavare l’indirizzo base del frame,

n-k

dato dagli bit più significativi

- Offset di pagina => rimane invariato,

determina l’offset all’interno del frame, dato

k

dai bit meno significativi

Ex. Avendo un architettura a 32 bit, si ha:

Spazio indirizzi logici = 2 bit (n = 32)

32

Pagina = 4KB = 2 bit (k = 12)

12

=> tabella delle pagine = 2 /2 = 2 pagine

32 12 20

Nei sistemi moderni avendo che la quantità di pagine disponibili è molto grande, per

TLB

velocizzare l’accesso si utilizza una piccola cache associativa detta (translation

look-aside buffer) che contiene solo una parte della tabella delle pagine.

Così come per le normali cache ad ogni interazione si controlla prima la presenza della

pagina nella TLB, altrimenti in caso di TLB miss si accede in memoria e si controlla la

page table.

Avendo più processi che la utilizzano contemporaneamente, si associa ad ogni elemento

un ASID (address-space identifier) che indica univocamente il processo a cui si riferisce.

page table = array lineare con i riferimenti alle pagine del processo caricate in memoria,

32 contiene inoltre informazioni su validità riferimento e permessi di lettura scrittura su frame

32

La memoria virtuale

La memoria virtuale si basa sulla distinzione tra indirizzi logici e fisici, permette di astrarre

dalla quantità reale di memoria del calcolatore ed associare ad ogni processo uno spazio

degli indirizzi virtuale (immagine di memoria del processo) pari a 2 , dove n dipende

n

dall’architettura (ex. 32, 64, …).

Inoltre isola ogni blocco permettendo l’accesso ai dati solo a processi con permesso

esplicito, aumentando la protezione e permettendo condivisione della memoria.

Paginazione su richiesta

Estende il concetto di paginazione anche all’utilizzo in memoria secondaria, permette di

caricare in memoria solo le pagine realmente utili, le altre rimangono su disco.

Ad ogni accesso a memoria le operazioni sono:

1. Si controlla nella tabella delle pagine il bit di validità del riferimento

2. IF (riferimento valido) carica da memoria la pagina corrispondente, exit

ELSE controlla l’esistenza del riferimento nella tabella interna al processo (in PCB):

page fault,

IF (riferimento esiste) goto 3

ELSE errore, segmentation fault

3. Si individua un frame libero e la pagina in

memoria secondaria

4. Si trasferisce la pagina dal disco alla

memoria principale

5. Completato il trasferimento si modifica la

tabella delle pagine

6. Si riavvia l’istruzione interrotta

Teoricamente un processo potrebbe iniziare

l’esecuzione caricando solo la prima pagina e

poi caricare le altre, una alla volta.

Sebbene questo modo permetta di risparmiare

molto spazio in memoria, ogni caricamento di

pagina è molto costoso, ed avendo anche solo

un page fault ogni 1000 accessi l’esecuzione del programma può rallentare di 40 volte.

OSS la generazione di nuovi processi avviene duplicando il genitore, ma poiché gran

parte dei processi figli non necessita di tutte le pagine del padre, è possibile utilizzare il

sistema di copy-on-write che duplica solo le pagine che vengono modificate dal figlio.

In linux e diverse versioni UNIX questo si effettua tramite la vfork().

La continua allocazione di nuove pagine da parte

di più processi comporta il riempimento della

memoria, si necessita quindi di un sistema di

sovrallocazione che vada a modificare il punto 3.

I. Se la memoria è piena si sceglie un frame

vittima tra quelli inutilizzati.

dirty bit

II. Se il corrispondente è posto a 1 si

33

esegue un swap out del frame nel disco e

swap in del nuovo frame, altrimenti

direttamente lo swap in.

dirty bit = (bit di modifica) indica se frame è stato sovrascritto dopo inserimento in memoria

33 33

Gestione della paginazione su richiesta

Per il funzionamento ottimale di questa sistema è richiesta la presenza di 2 algoritmi:

- Sostituzione delle pagine => scelgono quali frame sostituire, minimizzano la

frequenza di page fault

- Allocazione dei frame => determinano numero di frame da associare al processo

Algoritmi di sostituzione delle pagine

La valutazione degli algoritmi si effettua tramite una reference string, ovvero una stringa

composta dai soli riferimenti alle pagine.

Si considera solo il numero della pagina e non tutto l’indirizzo, poiché l’accesso