Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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

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

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

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 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

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:

2m-n blocchi di 2n byte

Schema dell’esempio

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)

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

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)

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

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

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

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 esplicativo (segmentazione)


Schema logico di segmentazione

In figura si mostra uno schema grafico relativo alla segmentazione.

Schema logico di 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

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.

Esempio: MULTICS

Lo schema illustra la relazione tra segmentazione e paginazione (MULTICS).

Schema dell’esempio

Schema dell'esempio


Esempio: Intel 80386

Lo schema illustra la relazione tra segmentazione e paginazione (INTEL 80386).

Schema dell’esempio

Schema dell'esempio


Prossima lezione

La memoria virtuale

  • Paginazione su richiesta
  • Algoritmi di sostituzione delle pagine
  • Allocazione dei frame
  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion