Sistemi Operativi - Appunti Teoria Seconda Parte

ALLOCAZIONE CONTIGUA DELLA MEMORIA

La memoria centrale deve contenere due partizioni: sia il SO sia i vari processi utenti. Perciò è necessario assegnare le diverse parti

Ci sono due metodi per l’allocazione

della memoria centrale nel modo più efficiente. della memoria:

MFT: suddivide la memoria in partizioni di dimensione fìssa e ognuna deve contenere esattamente un processo, quindi il grado di

multiprogrammazione è limitato dal numero di partizioni. Si usava nel sistema IBM OS/360, ma non e più in uso.

generalizzazione dell’MFT.

MVT: suddivide la memoria in partizioni di dimensione variabile ed è una Come si procede:

 Si usa una tabella di partizioni di memoria occupate e libere: inizialmente tutta la memoria è a disposizione dei processi utente.

Si tratta di un grande blocco di memoria disponibile, un buco (hole).

 Al caricamento di un processo si cerca un buco abbastanza grande, la parte rimanente si usa in futuro

 Si crea una alternanza di zone occupate da processi e buchi

 Quando entrano nel sistema, i processi vengono inseriti in una coda d’ingresso (scheduling). La memoria si assegna ai processi

c’è

in coda finchè si possono soddisfare i requisiti del processo (cioè finchè un buco grande abbastanza)

 Se non c’è un buco grande si attende, altrimenti si cerca nella coda un altro processo.

Questa strategia prevede una allocazione dinamica della memoria. Il sistema cerca nella memoria un buco di dimensioni sufficienti

per contenere un processo che necessita di tale memoria. Se il buco è più grande della memoria richiesta (cioè sempre) si divide in

due: un nuovo buco più piccolo e un segmento di memoria allocata per il processo. Quando termina, un processo rilascia il blocco di

dei buchi; se si trova accanto ad altri buchi, si uniscono tutti i buchi adiacenti per formarne

memoria, che si reinserisce nell’insieme

uno più grande. Si crea però il problema della frammentazione esterna: Per n blocchi assegnati se ne perdono 0,5*n per la

frammentazione. Quando si caricano e si rimuovono 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. Questo problema può essere molto grave: nel caso peggiore può verificarsi un blocco di memoria libera sprecata. Se tutti

questi piccoli pezzi di memoria costituissero in un unico blocco libero di grandi dimensioni, si potrebbero eseguire molti più processi.

Una soluzione è la compattazione, cioè riunire la memoria libera in un unico grosso blocco. Tuttavia non è sempre possibile.

Ci sono strategie per scegliere il buco [la 1 e la 2 sono migliori della 3]: dell’insieme di buchi sia dal

1. First-fit. Si assegna il primo buco abbastanza grande. La ricerca può cominciare sia dall’inizio

punto in cui era terminata la ricerca precedente (velocità +, efficienza +)

2. Best-fìt. Si assegna il più piccolo buco in grado di contenere il processo. Si deve compiere la ricerca tutta la lista sempre che

questa non sia ordinata per dimensione. (velocità -, efficienza +)

3. Worst-fìt. Si assegna il buco più grande. Si esamina tutta la lista,

se non è già ordinata per dimensione (velocità -, efficienza -)

PAGINAZIONE

La paginazione è un metodo di gestione della memoria che permette

che lo spazio degli indirizzi fisici di un processo non sia contiguo.

Elimina il problema della sistemazione di blocchi di memoria di

diverse dimensioni in memoria ausiliaria, che riguarda la maggior

parte dei metodi di gestione della memoria analizzati.

La memoria logica viene suddivisa in blocchi di pari dimensione

(pagine) mentre la memoria fisica in blocchi di dimensione fissa

(frame o pagine fìsiche). Quando si deve eseguire un processo, si

caricano le sue pagine nei frame disponibili dello spazio fisico, prendendole dalla memoria

ausiliaria (Figura 1). Ogni indirizzo generato dalla CPU diviso in due parti:

 l’indirizzo di

Numero di pagina (p): indice di riga per la tabella delle pagine, contenente

base in memoria fisica di ogni pagina

 Scostamento di pagina (d).

c’è l’indirizzo del frame

Dentro la tabella delle pagine che si combina

con lo scostamento di pagina per definire l’indirizzo della

poi s’invia all’unità di memoria.

memoria fisica, che La dimensione di

frame, è definita dall’architettura del calcolatore ed

una pagina e di un

è una potenza di 2, compresa tra 512 byte e 16 MB. Se la dimensione

m

dello spazio degli indirizzi logici è 2 e la dimensione di una pagina è

n

di 2 unità di indirizzamento (byte o parole), allora gli m-n bit più

significativi di un indirizzo logico indicano il numero di pagina, e gli

n bit meno significativi indicano lo scostamento (Figura 2).

Esempio (Figura 3): con pagine di 4 byte e una memoria fisica di 32

L’indirizzo logico

byte (8 frame). 0 è la pagina 0 con scostamento 0.

Secondo la tabella delle pagine, la pagina 0 si trova nel frame 5.

all’indirizzo logico 0 corrisponde l’indirizzo fisico 20 (= (5

Quindi *

4) + 0). All’indirizzo corrisponde l’indirizzo fisico

logico 3 (p 0, d 3)

23 (= (5 * 4) + 3) ecc. Quindi la paginazione è una forma di

a ogni indirizzo logico l’architettura

rilocazione dinamica: di

paginazione fa corrispondere un indirizzo fisico.

Paginazione e frammentazione: Con la paginazione si può evitare la frammentazione esterna: qualsiasi frame libero si può

l’ultimo

assegnare a un processo che ne ha bisogno. Non si può evitare la frammentazione interna poiché frame assegnato può non

essere completamente pieno. Esempio: Se le pagine sono di 2048 byte, un processo di 72.766 byte necessita di 35 pagine più 1086

byte. Si assegnano 36 frame, quindi si ha una frammentazione interna di 2048 - 1086 = 962 byte. Se la dimensione del processo è

indipendente dalla dimensione della pagina, ci si deve aspettare una frammentazione interna media di mezza pagina per processo.

 

Quindi conviene usare pagine di piccole dimensioni Meno frammentazione interna Aumenta il carico per gli elementi della



tabella I/O su disco più efficiente se è maggiore il numero.

Informazioni di paginazione: Il SO mantiene le

informazioni sui frame (blocchi di memoria), ognuno

contenente un elemento che indica se sia libero oppure se è

assegnato e a quale processo. Il SO mantiene una copia della

tabella delle pagine di ciascun processo, che viene usata

impostare l’architettura HW di

anche dal dispatcher per

paginazione quando a un processo sta per essere assegnata la

CPU. La paginazione fa quindi aumentare la durata dei cambi

di contesto.

Aspetto importante: La netta distinzione tra la memoria vista

e l’effettiva memoria fisica

dall’utente è colmata

dall’architettura di traduzione degli indirizzi, che fa

corrispondere gli indirizzi fìsici agli indirizzi logici generati

dai processi utenti. Il programma utente vede la memoria come un unico spazio contiguo, contenente solo il programma stesso; in

realtà è sparso in una memoria fisica contenente anche altri programmi. Queste trasformazioni sono controllate dal SO e non sono

visibili agli utenti perchè non possono accedere alle zone di memoria che non gli appartengono. Quando si deve eseguire un processo,

si esamina la sua dimensione espressa in pagine. Poiché ogni pagina necessita di un frame, se il processo richiede n pagine, devono

essere disponibili almeno n frame che, se ci sono, si assegnano al processo stesso. Si carica la prima pagina del processo in uno dei

frame assegnati e s’inserisce il numero del frame nella tabella delle pagine relativa al processo in questione. La pagina successiva si

s’inserisce

carica in un altro frame e, anche in questo caso il numero del frame nella tabella delle pagine, e così vià (Figura).

Architettura HW di supporto alla paginazione

Ogni SO segue metodi propri per memorizzare le tabelle delle pagine e la maggior parte ne impiega una per ciascun processo. La

paginazione richiede il supporto HW. Come viene gestito il rapporto tra indirizzo logico e fisico? Ci sono 3 possibilità:

Set di registri: Si può utilizzare un set di registri dedicati per contenere le associazioni fra pagina logica e frame (tabella delle

pagine). La tabella delle pagine deve essere piccola (256 pagine). La maggior parte dei SO oggi usa tabelle molto grandi, quindi non



possono impiegare i registri veloci è una architettura superata.

Tabella in memoria e PTBR (Page Table Base Register): Si può tenere la page table in memoria e utilizzare un registro che punti

alle locazioni di una tabella

alla tabella PTBR. L’accesso passa attraverso il PTBR, in questo modo al cambio di contesto devo solo

modificare un PTBR per switchare alla page table di un nuovo processo. Il problema è che per ogni accesso ad un dato in memoria

uno per sostituire l’indice della tabella con l’effettivo riferimento, e uno per l’accesso al dato vero e proprio,

devo fare 2 accessi:

quindi l’accesso alla memoria è rallentato del doppio.

E’ la soluzione al problema del PTBR e consiste nell’impiego di una

TLB (Translation Look-Aside Buffer): piccola cache di

ricerca veloce, detta TLB. La TLB è una memoria associativa dedicata, ad alta velocità, in cui ogni suo elemento consiste di due parti:

una chiave (identificatore o tag) e un valore. Le TBL sono molto costose e una di solito ha tra 64 e 1024 elementi. Quando si

presenta un elemento in ingresso, la TBL lo confronta contemporaneamente con tutte le chiavi presenti (i num di pagina della TLB).

 Se il numero è presente si ha un successo TLB (TLB hit), il corrispondente numero del frame è immediatamente disponibile e si

usa per accedere alla memoria. L’operazione ha una incidenza sul tempo di accesso di circa il 10% del tempo totale di accesso.

 Se non è presente si ha un insuccesso (TLB miss) e si deve consultare la tabella delle pagine in memoria. Il numero del frame

così ottenuto si può eventualmente usare per accedere ala memoria.

è già piena d’elementi, il

Se la TLB SO deve sceglierne un algoritmo per

sostituirlo: si usano LRU o random. Alcune TLB consentono che certi elementi

siano vincolati (wired down), cioè non si possano rimuovere dalla TLB (in

genere si vincolano gli elementi per il codice del kernel).

Per la protezione dello spazio di memoria si usano degli identificatori univoci

dello spazio di indirizzi (ASID), associati univocamente a ciascun processo. La

mancata corrisponden