Teoria di Sistemi operativi

Indirizzi logici e fisici

1. INDIRIZZI LOGICI (INDIRIZZI VIRTUALI)
Sono gli indirizzi generati dalla CPU, cioè quelli che vengono messi nel registro indice della CPU (Rlp).

2. INDIRIZZI FISICI
Sono gli indirizzi visti dall'unità di memoria, cioè quelli che vengono messi nel registro indice della memoria (MAR - Memory Address Register).

Indirizzi logici e fisici coincidono quando il binding viene fatto in fase di compilazione o caricamento. Il programma utente ha a che fare con gli indirizzi logici e non vede mai gli indirizzi fisici.

Memory Management Unit

L'hardware che traduce gli indirizzi logici in fisici è il MMU (Memory Management Unit). Ci sono infatti due registri: il registro limite e il registro di rilocazione. Una volta che la CPU produce l'indirizzo logico, viene confrontato con il registro limite e dopodiché aggiunto al valore del registro di rilocazione.

Gestione della memoria (Come si alloca la memoria?)

Allocazione contigua
È una tecnica di allocazione secondo la...

• Partizioni fisse: La memoria viene suddivisa in partenza in un certo numero di partizioni di dimensione fissa. Ogni processo viene caricato in una partizione. Quando un processo termina l'esecuzione, libera una partizione che può essere occupata da un altro processo in attesa nella coda di ingresso che può essere singola o multipla. Il grado di multiprogrammazione è limitato al numero di partizioni. Problema: Frammentazione Interna. La memoria allocata può essere più grande di quella che effettivamente serve, la memoria in più è interna alla partizione e non può essere usata.
• Partizioni variabili: La memoria non viene partizionata in partenza. Infatti all'inizio ho solo due partizioni,

Una parte della memoria è allocata al SO e l'altra (il resto della memoria) è libera. Il SO conserva in una tabella le partizioni libere (buchi) e le partizioni allocate, ognuna con dimensioni diverse dalle altre. Quando arriva un processo, a questo gli viene allocato esattamente lo spazio di memoria di cui ha bisogno, la parte di buco non utilizzata viene lasciata invece come partizione libera per un altro processo. Andando avanti alcuni processi termineranno lasciando una lista di buchi nella memoria.

Problema: Frammentazione Esterna

La somma totale di tutti gli spazi liberi è sufficiente per contenere un nuovo processo, ma il processo non può essere caricato in memoria perché questi spazi non sono contigui.

compattazione

La frammentazione esterna può essere eliminata con la compattazione che consiste nel riordinare il contenuto della memoria per riunire la memoria libera in un unico buco. È una tecnica abbastanza costosa.

Algoritmi per l'allocazione di una serie di richieste

• First-Fit: alloca il primo buco di dimensioni sufficiente (è il più veloce).
• Best-Fit: alloca il buco più piccolo in grado di soddisfare la richiesta (migliore in termini di utilizzo della memoria).
• Worst-Fit: alloca il buco più grande (il peggiore).

È una tecnica per l'allocazione della memoria che rinuncia al concetto di allocazione contigua. Secondo la paginazione, la memoria fisica è divisa in blocchi di dimensioni fisse e tutte uguali tra pagine fisiche (frame), mentre la memoria logica è divisa in blocchi chiamati pagine logiche, le cui dimensioni sono pari a quelle dei frame. Per eseguire un programma di dimensioni pari ad n pagine, bisogna trovare n frame liberi e caricare le pagine in quei frame anche se non sono contigui.

Viene usata una tabella delle pagine (una per processo) per tradurre gli indirizzi logici in indirizzi fisici.

Questo punto presenta solo il problema della frammentazione interna ma riguarda solo l'ultimo frame.

Come funziona la tabella delle pagine?

Il numero di pagina logica deve essere diviso in due parti: il numero di pagina (che indica in quale pagina si trova la mia locazione di memoria) e l'offset (che indica a che distanza dall'inizio di quella pagina logica si trova l'allocazione che mi interessa).

Ci sono due problemi:

• Problema di velocità di accesso, infatti con lo schema che abbiamo visto ci sarebbero due accessi in memoria, uno alla tabella delle pagine e l'altro ai dati veri e propri. Questo problema si può in parte mitigare utilizzando una speciale memoria associativa usata come cache (ovvero la TLB). Questa memoria ci permette di cercare in parallelo su tutti gli elementi quale sia uguale ad un valore dato.
• All'interno di una pagina possono esserci informazioni non omogenee tra di loro. Infatti possono capitare insieme istruzioni, codice,

variabili statiche, ...

La segmentazione è uno schema di gestione della memoria secondo il quale uno spazio di indirizzi di un processo è diviso in tanti segmenti ognuno dei quali contiene un'informazione omogenea. A questo punto si ripropone il problema dell'allocazione dei segmenti, e a questo punto posso replicare gli algoritmi visti sopra (BF, FF, WF).

Qui c'è la tabella dei segmenti, che permette la traduzione dello spazio bidimensionale degli indirizzi logici (costituiti dalla coppia numero di segmento - offset) allo spazio unidimensionale degli indirizzi fisici. Anche qui, come per il caso precedente, per sapere dove trovare la tabella dei segmenti, utilizzo il registro base e il registro limite.

MEMORIA VIRTUALE

Analizza il caso in cui nonostante la nostra segmentazione con paginazione, il numero di pagine fisiche che ho a disposizione è inferiore alla richiesta che ho. Ovvero se non ho abbastanza spazio.

Swapping

• First In First Out (FIFO): Sostituire la prima pagina caricata in memoria, questo algoritmo presenta la cosiddetta Anomalia di Belady.
• Algoritmo Ottimo: Sostituire la pagina che si utilizzerà il più tardi possibile, è impossibile da realizzare nella pratica in quanto non posso prevedere il futuro.
• Least Recently Used (LRU): Sostituire la pagina che è stata usata meno di recente.
• Least Frequently Used (LFU): Sostituire la pagina che è stata usata meno di frequente.

1. Con i contatori (sia per LRU che LFU): Ogni

elemento delle pagine ha un contatore.LRU,Per quanto riguarda ogni volta che c’è un riferimento alla pagina, il valore del clock vieneLFU,copiato nel contatore, mentre per quanto riguarda ogni volta che c’è un riferimento allapagina, il valore del contatore viene incrementato di 1.Quando bisogna selezionare una pagina, si sceglie quella che ha il valore più piccolo delcontatore.

2. Con lo stack (solo per LRU)I numeri delle pagine sono organizzati in una lista doppiamente concatenata. Ogni volta chec’è un riferimento alla pagina, questa viene spostata in cima allo stack. Quando bisognascegliere una pagina vittima, si sceglie quella presente in fondo allo stack.

Algoritmi che approssimano LRU e LFU• Bit di riferimentoAd ogni pagina è associato un bit di riferimento inizialmente posto a 0. Ogni volta che c’è unaccesso alla pagina il bit viene posto ad 1. La lista delle pagine è gestita FIFO, viene sostituita

La pagina che ha il bit di riferimento a 0 (se esiste).

• Seconda chance (Algoritmo dell'orologio)

Anche qui viene utilizzato un bit di riferimento inizialmente posto a 0. La lista delle pagine è una lista circolare gestita FIFO. Quando viene selezionata una pagina, se il bit di riferimento è a 0, la pagina viene sostituita, se invece il bit di riferimento è a 1, il bit viene messo a 0, la pagina viene lasciata in memoria (e quindi gli viene data una seconda chance) e viene selezionata la pagina successiva alla quale vengono applicate le stesse regole.

Assegnazione dei blocchi di memoria

Nella paginazione su richiesta pura, inizialmente tutti i frame sono posti nella lista dei frame liberi. Quando il primo processo deve essere caricato in memoria, si generano una sequenza di pagefault. Un metodo più efficiente, consiste nell'assegnare al processo direttamente in fase di caricamento un certo numero di frame liberi.

Ci sono 3 algoritmi per fare

ciò:
• Algoritmo di assegnazione uniforme: I frame vengono assegnati in base al numero di processi in modo uniforme. Quindi se il numero di frame liberi è m e il numero di processi è n, ogni processo riceve m/n frame. Tuttavia in questo modo piccoli processi ricevono molti frame e grandi processi ricevono pochi frame.
• Algoritmo di assegnazione proporzionale: I frame vengono assegnati ai processi in modo proporzionale in base alle dimensioni del processo.
• Algoritmo di assegnazione per priorità: Si basa su una assegnazione proporzionale alla priorità dei processi invece che alla loro dimensione (come nell'algoritmo precedente).
Se un processo P genera un page fault, possono avvenire due casi:
• Assegnazione locale: per la sostituzione viene selezionato un frame del processo che ha generato il page fault.
• Assegnazione globale: per la sostituzione viene selezionato un frame tra tutti i processi.