Home

Federica EU

1/32

Marco Lapegna » 12.Allocazione non contigua dei processi in memoria centrale

Sistemi operativi

Allocazione non contigua dei processi in memoria centrale

Soluzione 1: coalescenza

Unisce blocchi adiacenti liberi in un unico blocco di dimensioni maggiori
Applicabile raramente e non sufficiente a recuperare rapidamente sufficienti quantità di memoria

Schema della soluzione 1

Soluzione 2: compattamento

Chiamata anche “garbage collection” (raccolta rifiuti):

Unisce tutti i buchi in un singolo blocco contiguo di memoria libera e sposta tutti i blocchi occupati
Overhead maggiore rispetto alla coalescenza

Schema della soluzione 2

Allocazione non contigua

Un’altra soluzione alla frammentazione esterna è ottenuta consentendo la non contiguità degli indirizzi fisici, permettendo così di allocare la memoria fisica ai processi ovunque essa sia disponibile.
Si divide la memoria fisica in blocchi di dimensione fissa chiamati blocchi (o frame)

Allocazione non contigua

Si divide il processo in blocchi della stessa dimensione chiamati pagine
Per eseguire un processo di n pagine, è necessario trovare n frame liberi prima di caricare il programma
Si ha solo frammentazione interna (relativa all’ultimo frame)

Esempio

Si vuole allocare un processo di 3421 byte in una memoria con blocchi di 1024 byte.

Schema dell'esempio

Tabella delle pagine

Il s.o. conserva in memoria una tabella delle pagine per ogni processo che contiene gli indirizzi dei blocchi utilizzati dalle pagine di quel processo in memoria.

Schema esplicativo (tabella delle pagine)

Schema di traduzione degli indirizzi

Ogni indirizzo generato dalla CPU (indirizzo logico) viene suddiviso in:

Numero di pagina ( p ) — impiegato come indice nella tabella delle pagine per trovare l’indirizzo del blocco
Scostamento nella pagina ( d ) — sommato con l’indirizzo del blocco per definire l’indirizzo fisico di memoria

Schema di traduzione degli indirizzi

In figura si mostra uno schema grafico relativo alla traduzione degli indirizzi.

Schema esplicativo

Due osservazioni

1: Il numero dei blocchi e la dimensioni dei blocchi sono potenze di 2
Esempio (immagine):

m = 16 bit a disposizione per gli indirizzi
m-n = 8 bit per il numero di pagina p
n = 8 bit per lo scostamento d

In generale:

2^m-n blocchi di 2ⁿ byte

Schema dell'esempio

Due osservazioni

2: La paginazione è una forma di rilocazione dinamica e la protezione dei blocchi avviene mediante i valori di p e d analogamente ai registri base e limit

Tabella dei blocchi

Il sistema operativo tiene traccia sull’uso dei blocchi di memoria (libero, occupato e a chi assegnato) mediante una tabella dei blocchi
Quando un nuovo processo richiede memoria viene consultata la tabella dei blocchi e viene creata la tabella delle pagine del nuovo processo

Tabella dei blocchi

In figura si mostra lo schema relativo alla tabella dei blocchi e un esempio numerico.

Schema esplicativo (tabella dei blocchi)

Supporto hw per la paginazione

Le tabella delle pagine (una per ogni processo) risiedono in memoria centrale.
Un registro della CPU identifica una tabella in memoria
- Page–Table Base Register (PTBR) punta all’inizio della tabella.
Al cambio di contesto il dispatcher aggiorna solo tale registro

Supporto hw per la paginazione

In figura si mostra uno schema grafico relativo al supporto hw per la paginazione.

Schema esplicativo

Supporto hw alla paginazione

Il problema dei due accessi alla memoria può essere risolto con dei registri associativi (altrimenti detti translation look–aside buffer, TLB)
Tali registri sono caricati dal dispatcher al momento del cambio di contesto e attraverso i quali si effettua una ricerca parallela veloce su una piccola tabella (senza scorrerla tutta)
Tali registri, realizzati nella CPU o nella MMU, sono molto veloci ma economicamente costosi

-> Vengono usati per memorizzare un sottinsieme della tabella delle pagine

Uso dei registri associativi

Se p si trova nei TLB, si estrae il corrispondente numero di blocco
Altrimenti, occorre fare un riferimento in memoria alla tabella delle pagine

Schema esplicativo (uso dei registri)

Effective access time (EAT)

Esempio

Tempo di accesso alla memoria = 100 nsec
Tempo di accesso alla TLB = 20 nsec
Tempo di accesso (EAT):
- 120 nsec se TLB hit
- 220 nsec se TLB miss

Effective access time (EAT)

Se percentuale di successi (TLB ratio) = 80%

-> Tempo di accesso = 0.8 x 120 + 0.2 x 220 = 140 nsec

In generale:

a = tempo acc alla TLB
b = tempo acc alla memoria
e = TLB ratio

EAT = e (a+b) + (1-e)(a+2b)

Problema

Quando lo spazio degli indirizzi logici è grande, lo schema descritto diventa inefficiente

Esempio indirizzamento a 32 bit (es. Pentium)

Numero di pagina 20 bit
Scostamento 12 bit

Un’unica tabella di 4MB per le pagine (ma i blocchi sono di 4KB)

Schema dell'esempio

Paginazione gerarchica (a livelli)

Una soluzione è “paginare” la tabella delle pagine.

Il numero di pagina viene ulteriormente suddiviso in:

un numero di pagina di p1 bit
un offset di p2 bit

Un indirizzo logico è costituito dallo schema in immagine.

P1 è un indice nella tabella esterna, e P2 è lo spostamento all’interno della pagina indicata dalla tabella esterna.

Schema dell'indirizzo logico

Paginazione gerarchica (a livelli)

P1 è un indice nella tabella esterna, e P2 è lo spostamento all’interno della pagina indicata dalla tabella esterna.

Paginazione gerarchica

Schema di tabella delle pagine a due livelli

Dato che ciascun livello viene memorizzato come una tabella separata in memoria, la traduzione di un indirizzo logico in uno fisico può richiedere tre accessi alla memoria.
Anche se il tempo richiesto per un accesso alla memoria è triplicato, la presenza di cache consente di mantenere prestazioni ragionevoli.
Per archietture a 64bit servirebbero ulteriori livelli.

Segmentazione

La paginazione alloca la memoria in blocchi di dimensioni fissate (i frame)
La segmentazione alloca la memoria in blocchi di dimensioni variabili (i segmenti) , assecondando la visione utente

Segmentazione

Un programma è una collezione di segmenti, dove ogni segmento contiene un’unità logica del programma:

programma principale (main)
procedura
funzione
variabili locali, variabili globali
blocco common
stack
tabella dei simboli, matrici

Schema esplicativo (segmentazione)

Schema logico di segmentazione

In figura si mostra uno schema grafico relativo alla segmentazione.

Schema logico di segmentazione

Architettura per la segmentazione

Gli indirizzi logici sono rappresentati da:

s = Numero del segmento
d = Spiazzamento all’interno del segmento

Tabella dei segmenti — mappa gli indirizzi fisici bidimensionali; ciascun elemento della tabella contiene:

base — indirizzo fisico iniziale del segmento
limite — specifica la lunghezza del segmento

Architettura per la segmentazione

In figura è illustrata la relazione tra CPU e memoria fisica in fase di segmentazione.

Architettura per la segmentazione

Segmentazione / paginazione

E’ possibile la condivisione: analogamente alla paginazione si ottengono segmenti condivisi, puntando allo stesso numero di segmento.
Protezione: analoga alla paginazione
E’ possibile combinare paginazione e segmentazione (es.: Intel 80386, Motorola 68000)
Dato che i segmenti variano di dimensione, l’allocazione della memoria è dinamica.