Sistemi Operativi - Lezione del 14.04.2008

 :: Sistemi Operativi - Lezione del 14.04.2008 ::

Torna alla pagina di Sistemi Operativi

Paginazione

Lo swapping costa molto, per l'utilizzo della memoria secondaria. Caricare tutto il processo è inutile. L'overlaying è a carico del programmatore e non va bene.

Insomma, con la paginazione voglio risolvere questi problemi, con i seguenti obiettivi:

• caricare e scaricare solo piccole porzioni di memoria, per evitare l'overhead dello swapping
• mantenere in memoria solo le parti che mi servono
• non sprecare spazio, per quanto possibile
• poter utilizzare anche porzioni di memoria non contigue per lo stesso programma
• e tutto ciò indipendentemente dal programmatore

Paginazione

Facciamo qualche definizione:
FRAME = pagina fisica della memoria, ovvero una ripartizione arbitraria dello spazio di indirizzamento. Tutti i frame hanno le stesse dimensioni.
PAGINA LOGICA = suddivisione dello spazio di indirizzamento di un processo, di dimensioni uguali a quelle del frame.

Avendo la stessa dimensione, non ci sono problemi di spreco nel caricare le pagine nei frames.

Ogni processo ha la sua tabella delle pagine, per mappare le sue pagine logiche nelle pagine fisiche. Gli indirizzi logici e fisici sono dati da:

 p = numero di pagina logica
 d = offset nella pagina logica
 f = tabella[p]
 => da logico a fisico sarebbe p + d = tabella[p] + d

Metto in memoria centrale le pagine che mi servono nell'immediato futuro, per i processi ready. Avendo la tabella, non ho più l'obbligo della continuità in memoria. Le pagine che non servono stanno nell'area di swap.

Il SO fa tutto in modo automatico, sceglie chi caricare e chi no, ed esegue da solo l'operazione.

Quando un processo chiede un certo suo indirizzo logico, il SO vede subito, tramite la tabella, se quella pagina è correntemente in memoria. Se non lo è, avviene un page fault, e il SO dovrà provvedere a caricare la pagina corretta e a metterla su.

Questo riconoscimento non è fatto in software, bensì in hardware, se no sarebbe troppo lento. Ci deve pensare una MMU che sappia gestire le pagine di memoria, e per ogni processo la MMU deve essere caricata con la tabella di quel processo.

Se le tabelle sono troppo grosse, non è fattibile copiarle ogni volta nella MMU. Pertanto, le lascio in memoria centrale, anche se poi raddoppio gli accessi in memoria per ogni indirizzo (uno lo fa la tabella per verificarlo, e poi lo fa il SO per caricare effettivamente il dato).

Posso anche fare in modo di spezzare la tabella in parti più piccole, così che ci stiano in una MMU. Ci sono alcune tecniche che fanno ciò.

Memoria ausiliaria di traduzione (Transition Look-Aside Buffer, TLB)

Tiene un elenco di pagine più frequentate, e controlla per prima cosa in questo elenco. Come per la cache, ci saranno gli hit e i miss. Se c'è un miss, allora ricorro al tabellone in memoria centrale, e metto quella pagina nel TLB ad uso futuro, eventualmente cacciando una pagina già presente se non c'è più posto.

Ma allora, non posso più usare il numero di pagina direttamente come indice per trovare, nella tabella, il frame. Infatti, se NON ho tutte le pagine caricate in memoria, ma solo alcune, come faccio a distinguerle? Quindi, nel TLB devo salvare la coppia pagina-frame, così quando scandisco per una ricerca ho subito il nome del frame accanto.

Il TLB viene realizzato in hardware tramite una particolare memoria detta associativa, a cui non si accede per indirizzo, ma dandogli il nome di una sua riga. Se ce l'ha, la restituisce, se no nisba.

Tabella gerarchica delle pagine

In memoria centrale ho la Gran Tabella. Nella MMU invece metto una tabella esterna. E che me ne faccio? Beh, raggruppo le pagine in gruppi, e nella tabella esterna metto il nome dei gruppi. Se cerco una pagina, la tabella in MMU mi dice a quale gruppo appartiene, e poi ricorro alla memoria centrale per trovare il frame effettivo.

Se uso questo sistema, l'indirizzo logico deve contenere il numero di pagina esterno, quello interno e l'offset:

 p1 + p2 + d

dove

 p1 = pagina esterna
 p2 = pagina interna
 d = offset

Tabella delle pagine con hashing

Avendo il p e il d di un indirizzo, li do in pasto ad una funzione di hashing, che me li trasforma in una cifra più corta. Poi nella MMU salvo queste cifre corte, che occupano meno spazio, e vedo subito se l'indirizzo c'è o non c'è.

Trattandosi di una restrizione di dominio, può accadere che 2 indirizzi diversi, dati in pasto alla stessa funzione di hashing, possano dare luogo allo stesso valore di hash. Ecco quindi che per ogni valore ripetuto occorre che la tabella si estenda in orizzontale. Faccio un esempio:

 hash  frame
 1010  A23F
 1100  B001
 1001  C345
 1110  B456 FCA2 AA34
 1111  ABCD

Se il mio indirizzo genera un hash 1110, a quella riga ho diversi indirizzi che hanno generato lo stesso hash. Provo col primo, poi col secondo etc. finché non trovo il mio. La funzione di hash deve essere quindi ben fatta.

Tabella invertita delle pagine

Finora ho mantenuto l'idea di avere una tabella per processo. Se il processo ha uno spazio di indirizzamento ciccio, allora la tabella diventa ciccia a sua volta.

Invertendo la prospettiva, mi metto dal pdv della memoria centrale e creo una tabella indicizzata con le pagine logiche. Un processo vuole una certa pagina logica? Scandisco la tabella, e se c'è, lo mando al frame, se no la carico.

Sappiamo che lo spazio di indirizzamento dei processi viene diviso in pagine logiche: pagina 0, 1, 2 etc. Quello che succede è che tutti i processi avranno la pagina logica 0, etc. etc. Quindi quando faccio la ricerca nella tabella qui sopra, devo salvare ogni riga con le informazioni sul pid, p e d, dove pid è l'id del processo.

Protezione

La paginazione garantisce implicitamente la protezione della memoria, tramite appunto queste tabelle.

Per andare oltre, e garantire correttezza al programma, potrei segnare alcune pagine con dei bit che mi dicano se a quella pagina si può accedere in read/write, read only o se la pagina contiene solo codice (execute).

In questo modo impedisco che un programma, accidentalmente o maliziosamente, vada a modificare se stesso o cose del genere.

Condivisione delle pagine

Tramite questo accorgimento, posso anche condividere le pagine. Se due processi usano la stessa porzione di codice, semplicemente nella tabella faccio puntare le pagine dei diversi processi allo stesso frame. Se poi marco quel frame come solo eseguibile, ecco che nessuno dei due potrà modificarlo, pur condividendolo.

Happy Ending

La paginazione è cosa quasi del tutto buona e giusta. Un processo ha a disposizione uno spazio logico ben più grande dello spazio fisici effettivamente a lui assegnato: ha virtualmente l'intero spazio di indirizzamento del processore, e ci pensa poi il SO ad illuderlo mandandolo qua e là. È gestita in modo automatico dal SO, ed è efficiente perché sposta piccole pagine di memoria.

Segmentazione

I problemi che voglio risolvere sono sempre i soliti, citati all'inizio della pagina. Inoltre, osserviamo che la paginazione tratta tutte le pagine come sostanzialmente simili, dal punto di vista funzionale. Certo, posso usare il bit di protezione per stabilire che qui si può scrivere, là no e così via. Ma il SO non può capire da solo dove stia il codice e dove i dati e quindi quali pagine condividere (il che sarebbe cosa ottima).

E allora, per condividere bene, abbandono la pretesa di avere frame di dimensioni uguali tra di loro.

Lo spazio di un processo viene diviso in segmenti logici, raggruppati per tipo. Posso avere quindi, ad esempio, il segmento dello stack, quello del codice, quello della tabella dei simboli e così via. Questi segmenti vengono generati dal compilatore, e non dall'utente, a scanso di equivoci.

Quando carico un segmento, il SO gli assegna un frame delle stesse dimensioni, che abbiamo visto non essere più necessariamente uguali. E per ripescare il tutto, uso una tabella dei segmenti.

Un indirizzo è composto dal numero di segmento e dallo spiazzamento. Per distinguere i frame fisici, non posso usare semplicemente il numero di segmento, perché qui il numero non c'è, c'è solo il tipo. Devo quindi salvare, per ogni segmento, l'indirizzo di base in cui esso si trova in memoria, e devo anche salvare la dimensione del frame, così so dove finisce e so riconoscere gli accessi illeciti (basta vedere se l'offset è superiore alla dimensione del frame...).

Al solito, in memoria centrale stanno solo segmenti usati nell'immediato futuro etc. etc. E occorre una MMU che sappia gestire i segmenti.

Condivisione

Visto che sono divisi per tipo, la condivisione è nativa e funzionante.

Problemi

Il problema che nasce è quello della frammentazione esterna della memoria. Mi spiego con un esempio.

All'indirizzo 100 carico il segmento A lungo 130. All'indirizzo 230 carico il segmento B lungo 70. Poi per qualche motivo devo togliere il segmento A dalla memoria, e al suo posto carico il segmento C che è lungo 100. Ho quindi:

 100: inizia C
 200: finisce C
 230: inizia B
 300: finisce B

E lo spazio tra 200 e 230? Ecco, questa è la frammentazione. Dopo un po' che tolgo e levo, mi rimangono degli sfridi (il prof li chiama così) che alla lunga possono diventare tanti ed ingombranti.

Mi serve un garbage collector, che si metta a fare la rilocazione della memoria per riorganizzare i segmenti, un po' come il defrag di uinzozz.

Segmentazione con paginazione

Il passo successivo è mettere insieme le buone idee viste prima, e ottenere il non plus ultra: segmentazione con paginazione. Della paginazione usa i frame uguali per dimensione alle pagine. Della segmentazione sfrutta la tipizzazione dei segmenti e la condivisione.

I segmenti vengono divisi a loro volta in pagine logiche, della stessa dimensione dei frame in cui è divisa la memoria centrale. L'indirizzo logico è composto da

 s = segmento
 p = pagina logica
 d = offset

e quello fisico da

 f = frame
 d = offset

Partendo dal segmento e dall'offset, ricavo la mia pagina logica, e dalla pagina logica ricavo il frame.

Quindi evito anche la frammentazione esterna, quella vista sopra.

Rimanne la frammentazione interna, ovvero: se i segmenti non hanno dimensioni che sono multipli delle dimensioni delle pagine, posso avere pagine non completamente sfruttate. Ma tanto se sono piccole è poca roba, quindi va tutto bene:)

Generazione furba degli indirizzi

Piccola nota. Se uso una dimensione delle pagine abbastanza furba, ho dei vantaggi. In particolare, se uso potenze di due, le moltiplicazioni avvengono semplicemente con degli shift, a cui concatenerò poi l'offset. Va beh niente di che.

Concetti e tecniche fondamentali

Tutto quanto abbiamo visto finora ci serve per creare la Chimera: la memoria virtuale!
Quello che io voglio è:

• multiprogrammazione
• condivisione della memoria con protezione
• efficienza nell'assegnamento della memoria
• efficienza nel time-sharing

La memoria virtuale è astratta, perché è più grande di quella fisica, indipendente, da essa ed efficiente. Inoltre, la virtualizzazione mi permette di dare ad un processo tutto lo spazio di indirizzamento che vuole, ignorando bellamente gli altri processi e i loro spazi di indirizzamento.

Nota sulla dimensione della memoria fisica: se ho un processore a 32 bit, esso può gestire al massimo 2³² indirizzi diversi, ovvero 4.294.967.296. Ma in una macchina ho installata RAM che rende disponibili molti indirizzi in meno.

La memoria virtuale è un insieme di meccanismi e politiche che ci permettono le astrazioni di cui parlavo prima. Divido lo spazio di indirizzamento del processo in porzioni, e poi mappo queste porzioni nei frame. Solo le porzioni che mi servono vengono caricate, le altre rimangono nello swap (al solito).

E sempre come al solito ho una tabella che mi dice quale parte della memoria centrale è associata all'indirizzo virtuale. Se non c'è in tabella quella porzione, vuol dire che devo pescarla dall'area di swap.

Ne deduco quindi che per realizzare la memoria virtuale mi serve una delle tre tecniche viste sopra, ovvero paginazione, segmentazione o segmentazione con paginazione. Mi servono poi sia politiche che meccanismi per rilevare il frame mancante, scegliere quale caricare e quali sostituire.

Tecniche di sostituzione della pagina

Caricamento della pagina

L'ideale sarebbe sapre prima le pagine a cui il processo accederà nel futuro. Ma questo purtroppo non posso saperlo in modo deterministico. Mantengo però una stringa di riferimento, che contiene la storia delle pagine a cui il processo ha acceduto nel passato. Poi vediamo come usarla.

In generale, tuttavia, dobbiamo dire che il tempo di accesso effettivo ad una pagina non è deterministico, anzi, è probabilistico: dipende dalla probabilità di avere una pagina già in memoria centrale o no.

 p = probabilità che manchi la pagine => 1 - p = probabilità che la pagina ci sia
 ma = tempo di accesso alla memoria centrale
 spf = gestione della trap (un segnale di page fault è una trap)
 tempo di accesso effettivo = (1 - p) * ma + p * spf

e la cosa triste è che spf è molto grande, rispetto a ma, e quindi la probabilità che manchi una pagina ha molto più peso rispetto alla probabilità che la pagina ci sia.

Nel mondo della felicità, p è un valore basso.

Scaricamento

Un frame che non è stato modificato viene scartato e amen.

Un frame modificato invece posso:

• salvarlo nello swap, e poi scartarlo dalla memoria
• salvarlo nel buffer delle pagine, e poi scartarlo dalla memoria

Questo secondo punto va interpretato così: un SO mantiene un gruppo di frames liberi. Ho selezionato un frame vittima: se PRIMA di scrivere quel frame su disco, carico il frame nuovo in uno di questi frames liberi, il processo può partire anche prima di completare la scrittura su disco.
Quello che succede dopo è che il frame vittima viene scritto su disco in un momento opportuno, e va a infoltire la schiera dei frames liberi. La furbata qui è salvare, per questo frame, il numero della pagina e del processo a cui apparteneva: in questo modo, se quello stesso processo vuole quella stessa pagina, non devo star lì a caricarla, ma ce l'ho già in memoria.
Più difficile da spiegare che da capire, mi sa...

Ho inoltre dei frame che marco come residenti: questi vengono usati frequentemente, e quindi è bene che non vengano mai tolti. Un esempio sono i frame assegnati al kernel.

Sostituzione della pagina

Quando devo mettere in memoria una pagina, ma non ci sta, devo scegliere una vittima.

Posso seguire 2 strategie:

• la scelgo tra le pagine dello stesso processo che richiede la pagina nuova
• la scelgo tra tutte le pagine in memoria, anche se appartengono ad altri processi

Politiche per la sostituzione

Come al solito, devo scegliere la vittima ideale, e ho diverse politiche in proposito.

FIFO

Il più vecchio frame (First In) viene scartato (First Out). Come faccio ad identificare il più vecchio? Come dicevo sopra, se ho la stringa di riferimento, con la storia di tutte le pagine accedute, parto dall'inizio della stringa e levo la prima pagina che è ancora presente.

Si intuisce subito che non sia il massimo della furbizia, cmq.

Sostituzione Ottima

Scarico il frame che non sarà usato per il più lungo periodo di tempo.

In attesa di ottenere i poteri di Hiro Nakamura, vado a cercare nella mia stringa il frame il cui periodo di utilizzo è il più lungo, in rapporto alla mia posizione attuale nella stringa stessa.

Tutto ciò si basa sul presupposto che "i conti tornano", ovvero che un processo si comporta più o meno sempre allo stesso modo. Fa una cosa, poi l'altra, poi l'altra in sequenza e poi riprende da capo.

Least Recently Used (LRU)

Scarico il frame meno usato recentemente. Nella stringa, attacco ad ogni numero di frame un contatore o un orario. Quando accedo ad una pagina, aggiorno il suo contatore, e quindi scarico quella con il contatore più basso o la data più vecchia.

Reference Bits (RB)

Ogni frame ha un bit, e quando vi accedo quel bit si accende. Periodicamente azzero i bit. Scelgo la pagina con questo bit a 0.

Posso anche estendere questa idea carina, usando più bit, e periodicamente facendo lo shift in modo da diminuire il numero.

Ciò vuol dire che, se ho l'RB a 1110, dopo un po' vado a 0111, poi a 0011, 0001 ed infine 0000. Al contrario, se ho un accesso incremento. Questo processo di decrementazione avviene periodicamente.

In questo modo vedo subito qual'è la pagina che è stata usata meno negli ultimi tempi, cioè nella sua storia recente.

Second Chance

Uso due bit. Quando ho necessità di togliere una pagina, imposto a 1 il bit che dice "da rimuovere in futuro", ma non la rimuovo. Se successivamente ho necessità di togliere un'altra pagina, metto a 1 anche il secondo bit. Al terzo giro, se ha entrambi i bit a 1, è una vittima.

Se invece vi accedo, tolgo un bit alla volta.

Least Frequently Used (LFU)

Ho un contatore di accessi, e scarto il frame con questo contatore basso.

Qual'è il problema? Il problema è che se all'inizio dell'esecuzione di un processo uso tanto un frame, quello accumulerà tanti punti, e poi non viene più tolto. È un po' come vincere tutte le prime gare del campionato, e perdere la seconda metà, ma arrivare comunque in zona Champions senza merito.

Per ovviare, periodicamente divido per due questo punteggio, così penalizzo i vecchi.

Most Frequently Used (MFU)

Scarto la pagina più usata. Perché? Perché se l'ho usata già tanto, probabilmente in futuro non la userò poi così molto.

Politiche di selezione delle pagine da caricare

L'idea è di caricare le pagine che userò in futuro, così sono già belle in memoria. Posso:

• scegliere le n pagine successive
• scegliere le n pagine che seguono la pagina che devo caricare attualmente nella mia stringa di riferimento.

n è un valore così.

Torna alla pagina di Sistemi Operativi