Appunti sistemi operativi

HARDWARE DI SEGMENTAZIONE

Sebbene un programmatore può specificare una coppia di valori per un segmento, tale segmento è

comunque salvato in memoria come un valore unidimensionale, occorre quindi un hardware che si occupi

di unire queste due informazioni per generare l’indirizzo fisico. Tale hardware si chiama tabella dei

segmenti e contiene tutti gli indirizzi base dei segmenti con le relative lunghezze. Un’istruzione è divisa in

due parti, s (20 bit) e d (12 bit). La parte “s” indica il numero di segmento e viene utilizzata come indice

all’interno della tabella dei segmenti, mentre “d” indica l’offset del segmento. Quando si esegue

un’istruzione si controlla che l’offset sia compreso tra 0 e l’indirizzo limite, se così non fosse il sistema

genera un segmentation fault, altrimenti l’offset viene sommato al registro base e viene calcolato l’indirizzo

della memoria fisica.

PAGINAZIONE DELLA MEMORIA

La segmentazione ci permette di rendere la memoria centrale non contigua, ma mantiene il problema della

frammentazione. La stessa cosa ci consente la paginazione, con la differenza che con la paginazione

rimuoviamo il problema della frammentazione esterna, ma non solo, risolviamo il ben più grave problema

della sistemazione di blocchi di taglia variabile in memoria ausiliaria. Gli stessi principi di compattazione che

valgono per la memoria centrale valgono anche per la memoria ausiliaria. Nel momento in cui si deve

scrivere un segmento in memoria ausiliaria si deve prima trovare lo spazio necessario per contenere tutto il

segmento. La memoria ausiliaria però è molto più lenta e non ci consente di eseguire la compattazione. Per

questo motivo la maggior parte dei sistemi operativi utilizza la paginazione.

COME FUNZIONA

La paginazione consiste nel dividere la memoria fisica in frame e la memoria logica in pagine. I frame e le

pagine hanno una dimensione fissata e sono di uguali dimensioni. In questo modo lo spazio degli indirizzi

fisici è totalmente separato dallo spazio degli indirizzi logici. L’hardware che si occupa della paginazione è

composto da una tabella delle pagine che contiene i base address degli indirizzi fisici. Ogni indirizzo

generato dalla CPU viene diviso in due parti, “p” e “d”. La parte “p” indica il numero di pagina mentre la

parte “d” indica l’offset all’interno della pagina. Una volta trovato il numero di pagina con la parte “p” viene

esteso con la parte “d” e insieme formano l’indirizzo fisico.

Le dimensioni della pagina variano in base al sistema operativo e vanno da 512 byte a 1GB. In ogni caso

sono sempre potenze del 2, perché l’utilizzo della potenza del 2 semplifica molto la traduzione dell’indirizzo

logico nel corrispondente base address e offset. m n

Se la dimensione dello spazio degli indirizzi logici è 2 e la dimensione di una pagina è 2 allora gli m – n bit

più significativi di un indirizzo logico saranno il numero di pagina, mentre gli n bit meno significativi saranno

l’offset. Numero di pagina offset di pagina

p d

m-n n

Secondo la tabella delle pagine (che è a 4 byte), la pagina 0 si trova nel frame 5. Quindi all’indirizzo logico 0

corrisponde l’indirizzo fisico 20 [= (5 x 4) + 0]. All’indirizzo logico 3 (pagina 0, offset 3) corrisponde l’indirizzo

fisico 32 [= (5 x 4) + 3]. All’indirizzo logico 4 (pagina 1, offset 0) corrisponde il frame 6, quindi all’indirizzo

logico 4 corrisponde l’indirizzo fisico 24 [= (6 x 4) + 0]. All’indirizzo logico 13 corrisponde l’indirizzo fisico 9.

Con la paginazione si evita la frammentazione esterna, ma non quella interna. Nel caso peggiore possiamo

avere quasi tutto un frame vuoto perché per una sola istruzione è stato assegnato tutto un frame. Ridurre

troppo le pagine non conviene per via della frammentazione, perché potremmo avere più pagina quasi

vuote. Aumentare la grandezza delle pagine invece può tornare comodo durante le operazioni di I/O per la

lettura o la scrittura dalla memoria ausiliaria. Solaris utilizza 4KB o 8MB a seconda del tipo di dati

memorizzati nelle pagine.

Spesso su una CPU a 32 bit ogni voce della tabella delle pagine è grande 4 byte, e ci consente di indirizzare

32 12

2 bit. Se la dimensione di un frame è di 4kb (2 ), un sistema con voci della tabella delle pagine a 4 byte

44

può indirizzare 2 byte (16TB) di memoria fisica.

La paginazione ci consente di utilizzare più memoria di quanta se ne abbia a disposizione.

Quando si esegue un processo viene esaminata la sua grandezza e se ci sono sufficienti pagine disponibili

per mandarlo in esecuzione lo si lancia. Si carica prima la pagina e poi si inserisce il numero del frame nella

tabella delle pagine.

In questo caso però la visione della memoria da parte del programmatore non coincide con la visione della

memoria del sistema operativo. L’hardware di traduzione degli indirizzi si occupa di far combaciare queste

due viste.

Siccome un processo non può accedere a dati che non sono nel suo spazio di indirizzamento il sistema

operativo deve essere a conoscenza di questa suddivisione dei dati per permettere il corretto caricamento

dei dati:

• quali frame sono assegnati

• quali frame sono disponibili

• il numero di frame totali

• ecc…

In genere queste informazioni sono contenute nella tabella dei frame, che contiene un elemento per ogni

frame, indicante se il frame è libero o no e se non lo è a quale pagina di quale processo è assegnato.Inoltre

il sistema operativo deve sapere che deve tradurre gli indirizzi logici in indirizzi fisici. Il sistema operativo

conserva una copia della tabella delle pagine per ciascun processo, insieme a una copia dei valori contenuti

nel contatore di programma e nei registri. Questa copia viene utilizzata ogni volta che il sistema operativo

deve far corrispondere gli indirizzi logici in indirizzi fisici e dal dispatcher della CPU per impostare

l’hardware di paginazione quando si sta per assegnare la CPU ad un processo. La paginazione aumenta la

durata dei cambi di contesto.

SUPPORTO HARDWARE ALLA PAGINAZIONE

Ogni sistema operativo ha un proprio metodo per la gestione delle tabelle delle pagine. Alcuni sistemi

operativi ne utilizzano una sola mentre altri ne utilizzano una per ogni processo. Il PCB contiene un indirizzo

contenente un puntatore alla tabella delle pagine che viene caricato insieme a tutti gli altri registri durante

la fase di attach.

L’implementazione si può realizzare in diversi modi, uno di questi è l’utilizzo di registri rapidi. Vengono cioè

utilizzati dei registri per mappare gli indirizzi logici in indirizzi fisici. Questa tecnica però non è utilizzabile

per tabelle troppo grandi, e può andare bene per valori fino a 256.

Per tabelle più grandi viene creata una tabella per ogni processo e viene assegnato il puntatore di quella

tabella ad un registro di base della tabella delle pagine (page-table base register, PTBR). Quando si esegue

un context switch viene cambiato il puntatore del PTBR e viene fatto puntare alla tabella di interesse,

riducendo considerevolmente il tempo del cambio di contesto. Questa soluzione presenta un problema

connesso al tempo necessario di accesso a una locazione della memoria utente. Per accedere all’elemento

in posizione “i” si deve far riferimento alla tabella delle pagine utilizzando il valore contenuto nella PTBR

aggiungendo l’offset relativo alla posizione “i”, in questo modo effettuiamo 2 letture in più dal disco (un

accesso per la lettura dell’elemento della tabella delle pagine e uno per il byte stesso). Nella maggior parte

dei casi questo ritardo è intollerabile.

La soluzione migliore è inserire una TLB (translation look-aside buffer). La TLB è una memoria associativa ad

alta velocità (cache). Il numero di pagina viene cercato all’interno della TLB, e se non viene trovato allora

viene cercato nella tabella delle pagine. La TLB contiene i dati più utilizzati dal programma, quando viene

caricato un dato non presente se ne deve eliminare uno dalla tabella se è piena. Alcune CPU eliminano

un’istruzione casuale, altre rimuovono l’elemento meno utilizzato, altre implementano l’eliminazione in

base ad un algoritmo round-robin.

Alcune CPU implementano più livelli di TLB, come la CPU Intel Core i7. In generale le cache non sono molo

grandi, la CPU i7 aveva 2 livelli di cache L1 da 64 elementi e L2 da 512 elementi.

Alcune TLB implementano gli identificatori dello spazio di indirizzo (address-space identify, ASID) in ciascun

elemento della TLB. L’ASID identifica in modo univoco un processo e permette di poter salvare più elementi

nella TLB. Quando si cercano gli elementi viene fatto il match in base all’ASID per assicurarsi che si stia

caricando l’istruzione del giusto processo. Nei sistemi che non lo implementano è necessario svuotare ogni

volta tutta la cache per evitare di caricare dati di un altro processo.

Le TLB sono caratteristiche hardware, ma è importante conoscerle per poter progettare un buon sistema

operativo in base al tipo di TLB che è implementata. A volte cambiamenti di TLB su diverse architetture

dello stesso processore possono rendere meno efficiente il sistema.

PROTEZIONE

In un ambiente paginato la protezione della memoria avviene tramite un bit di protezione. Tale bit ci fa

capire se una zona di memoria è di sola scrittura, sola lettura o sola esecuzione. Inoltre combinandoli tra di

loro si può ottenere qualsiasi combinazione. Questo bit solitamente si trova nella tabella delle pagine, e

visto che tutti i riferimenti alla memoria passano attraverso la tabella delle pagine si possono controllare i

bit di protezione.

È associato ad ogni elemento della tabella delle pagine anche un bit di validità che è impostato a valido se

la pagina corrispondente è nello spazio degli indirizzi logici del processo (cioè è una pagina di quel

processo), a non valido altrimenti.

Supponiamo che in un sistema a 14 bit (da 0 a 16383) si abbia un programma che deve usare soltanto gli

indirizzi da 0 a 10.468. Con una dimensione delle pagine di 2 KB si ha la situazione mostrata nella Figura

8.15. Le pagine 0, 1, 2, 3, 4, 5 vengono tradotte normalmente e impostate a valide, mentre le pagine 6 e 7

vengono impostate a non valide ed ogni accesso a qualche pagina non valida genera un’eccezione.

Questo schema ha creato un problema, perché il programma utilizza gli spazi fino al 10.468, però il

riferimento alla pagina 5 è classificato come valido e ciò rende facili gli accessi fino all’indirizzo 12.287. Gli

indirizzi da 12.288 a 16.383 sono non validi. Questo problema &e