Il loading dinamico è una tecnica non utilizzata più tanto spesso ai giorni d'oggi; Il programma veniva "spezzettato" in tanti moduli che venivano caricati in memoria uno alla volta, in modo da risparmiare memoria ed utilizzare programmi relativamente grandi che non entravano interamente nella ram.

Come fa il sistema dove allocare il programma e come gestire la memoria in modo da far convivere i vari programmi?

Una soluzione è quella di scegliere uno spazio di allocazione che sia contiguo, ovvero che ogni processo ha il suo spazio indirizzi, e si trovano tutti allo stesso posto.

Un'operazione del genere è complicata, perchè è esattamente come

L'allocazione dinamica della memoria: C'è uno spazio di memoria, ed ogni processo ha bisogno di un "pezzo" e lo rilascia a suo piacimento. Per questo motivo è chiamato heap, ovvero "mucchio". Funziona quindi in modo diverso dallo stack, dove la memoria deve essere rilasciata in un ordine ben preciso.

Il problema della memoria dinamica, è che i processi rilasciando la memoria a loro piacimento, ci ritroveremo con dei "buchi" di memoria libera, che non solo sono troppo piccoli, ma anche "sparpagliati".

Per intenderci, questo è quello che succede quando utilizziamo la free() della malloc in C.

Quando abbiamo lo spazio in memoria suddiviso in tanti piccoli pezzi, che sono troppo piccoli per essere utilizzati, entra in gioco il garbage collection.

Quello che il garbage collector effettua, in parole povere, è spostare tutta la memoria (o meglio ciò che la occupa) da una parte, in modo da avere lo spazio libero tutto concentrato in un punto.

Questo non è un problema semplice da risolvere, anzi, è uno dei più difficili dell'informatica.

• Frammentazione Esterna ci sono dei frammenti (buchi) di memoria, ma sono troppo piccoli per essere utilizzati (perchè non continui). Addirittura anche 1/3 della memoria diventa inutilizzabile. Si parla di frammentazione esterna quando ho della memoria non utilizzata, ma che non può essere usata. Questo è il problema più diffuso.

• Frammentazione interna Si parla di frammentazione interna quando ho della memoria che non è utilizzata, ma marcata come occupata.

Come già detto precedentemente, possiamo ridurre la frammentazione tramite la compattazione, ovvero porre tutta la memoria libera in un unico grande blocco.

La compattazione è possibile solo quando la rilocazione è dinamica, e viene effettuata a tempo di esecuzione.

Inoltre abbiamo il problema dell'I/O, ovvero se avessimo delle locazioni di memoria che ospitano buffer per I/O, questi non possono essere spostati, perchè altrimenti i dispositivi I/O non li troverebbero più.

Sostanzialmente, la frammentazione si verifica perchè alloco spazi di dimensioni variabili i quali vengono allocati in tempi diversi, per cui diventa difficile trovare dello spazio libero, che viene sprecato.

La paginazione è ciò che risolve il problema:

L'idea è di allocare spazi che siano di dimensione fissa; divido la memoria fisica in spazi di una certa dimensione detti frames. Lo spazio indirizzi del processo che devo allocare in memoria, viene così diviso in tante fette, che sono esattamente della dimensione del frame; queste fette sono dette pagine.

L'idea è quindi quella di porre le pagine all'interno dei frame, in modo da non sprecare spazio. Ovviamente anche in questo caso un minimo di spazio resta inutilizzato, infatti si presume che il frame che occupa l'ultima pagina della memoria del processo, non sia riempito completamente

La grandezza di un frame, è una potenza di 2, compresa tra 512 bytes e 16 Mb; la grandezza dei frame (e quindi delle pagine) dipende dal processore.

Il vero punto di forza di questa tecnica, è che tutti questi "moduli", non devono essere continui!

Grazie ad un sistema di risoluzione degli indirizzi, viene effettuata, al momento dell'accesso in memoria, una traduzione da indirizzo logico a fisico, che permette di avere, per un processo, delle pagine poste a distanza tra loro.

Come detto, il primo grande vantaggio è quello di non dover necessariamente sprecare la memoria, proprio perchè non è necessaria l'allocazione dinamica di memoria, e quindi il massimo di memoria che non viene utilizzata, è la restante parte del frame che non viene occupata dall'ultima pagina di un processo. Questa parte di memoria non utilizzata, è un esempio di frammentazione interna, proprio perchè la memoria è ritenuta occupata, ma non lo è.

Il secondo grande vantaggio è il fatto di poter posizionare le varie pagine di un processo ovunque io voglia (o più probabilmente dove vuole il sistema), senza dover avere l'allocazione della memoria di un processo continua. Questo è possibile grazie al fatto che avviene una "traduzione" da indirizzo logico ad indirizzo fisico; infatti la CPU continua a vedere uno spazio degli indirizzi continuo.

Ho degli indirizzi di memoria; l'indirizzo in memoria è una stringa di bits.

Supponiamo di avere delle pagine fatte "a fette" nello spazio indirizzi che parte da 0, e supponiamo di avere delle pagine di grandezza 1k (1024b).

Se prendo un indirizzo logico a 32 bit, come posso logicamente dividerlo?

'0' in binario a 32 bit: 0000 0000 0000 0000 | 0000 0000 0000 0000

Supponiamo di dividere il numero a 32 bit in modo che i 10 bit meno significativi rappresentino la posizione all'interno della pagina in cui mi trovo.

Mentre invece i 22 bit più significativi rappresentino il numero della pagina in cui mi trovo

'1023' in binario a 32 bit: 0000 0000 0000 0000 0000 00 | 11 1111 1111

In questo modo, tutti e 22 i bit più alti rappresentano 0, ovvero la prima pagina, mentre i 10 bit più bassi rappresentano gli indirizzi, che vanno da 0 a 1023.

Se l'indirizzo cresce di 1, ci portiamo al valore 1024, rappresentato in questo modo:

'1024' in binario a 32 bit: 0000 0000 0000 0000 0000 01 | 00 0000 0000

In questo caso la parte più significativa diventa ...0000 01, mentre la parte meno significativa torna a 0; in altre parole sono passato alla pagina successiva (1) dove ancora una volta gli indirizzi andranno da 0 a 1023.

Ovviamente la posizione della pagina deve essere a potenza di 2.

Nel momento in cui carico il processo in memoria, devo mettere nella tabella delle pagine, le posizioni in cui sono stati posti i numeri di frame in cui le pagine sono state poste.

La CPU mi da un indirizzo, utilizzo la parte più significativa come numero di pagina, per spostate di i posizioni nella tabella.

Arrivato nella i-esima posizione della tabella, trovo il numero del frame.

Ogni processo ha la propria tabella delle pagine, ed in ogni posizione è scritto il numero del frame in cui la pagina è stata caricata.

Con delle pagine di 2048B (2k), un processo di 72,766B, richiede 35 pagine, e restano quindi 1,086b persi. Mediamente la dimensione persa è di circa 1/2 frame;

Con il tempo la dimensione delle pagine tende a crescere, infatti solaris supporta due grandezze di pagina: 8KB e 4MB.

Siccome non c'è interesse nell'usare dei frames consegutivi, basta una semplice lista di frames liberi per consentire al sistema di trovare immediatamente uno spazio in memoria dove allocare lo spazio richiesto da un processo.

Ogni volta che devo effettuare un accesso in memoria, in realtà deve essere eseguito un accesso supplementare che legga sulla tabella delle pagine.

Quindi essenzialmente, anche in questo caso la CPU "perde tempo".

Come possiamo risolvere il problema?

Visto che i processi hanno i propri indirizzi relativamente vicini, e quindi probabilmente nella stessa pagina (dettata dai 22 bit più significativi), possiamo utilizzare una sorta di cache, che con una singola entry mi permette di contenere tutto ciò che è contenuto in un'intera pagina, ovvero 1024 indirizzi, coprendo l'intera pagina.

Questa particolare forma di cache, viene detta TLB, anche detta memoria associativa; questo perchè grazie al fatto che avendo poche entry (pagine), è possibile avere una memoria di tipo associativo (da 64 a 1024 entries).

Entro nell'hardware paging:

Se nel TLB (cache) pongo una coppia pagina-frame utilizzo la pagina come chiave di accesso, ed ottengo quindi il numero del frame.

Siccome il TLB non è ad accesso random, ma di tipo cache (quindi più veloce) non aumento di troppo di accesso in memoria.

Se non riesco a trovare l'indirizzo di memoria nella cache, non c'è molto altro da fare, e devo accedere alla memoria the old fashioned way e quindi sprecare tempo.

Tuttavia, se quella è la prima volta che effettuo l'accesso a quella specifica cella di memoria, probabilmente in un prossimo futuro mi servirà nuovamente, quindi viene salvata nel TLB per un accesso più veloce.

Il TLB, ovvero la tabella coppia chave-valore (pagina-numero frame) deve essere svuotata ogni qualvolta il processo perde la CPU.

Questo per l'ovvio motivo che il TLB contiene la tabella degli indirizzi associata a quello specifico processo, e non al nuovo.

Questo è uno dei motivi per cui il context switching tra un processo e l'altro è lento; perchè quando arriva un altro processo e trova il TLB vuoto (perchè è stato svuotato dal processo precedente), i primi accessi alla memoria saranno tutti miss; essendo tutti miss, i tempi prima di "riempire" il TLB, sono lunghi.

🏁 05-21 00:54

Posso condividere una parte di memoria tra processi?

Sicuramente lo schema è fattibile se ogni processo ha la propria tabella delle pagine; se però voglio che dei processi abbiano un'area di memoria comune, come gestisco il tutto?

Supponiamo che il frame n1 sia un frame associato a più processi, ed è quindi un'area shared che i processi possono utilizzare.

Questo frame deve comparire, sulla tabella delle pagine, sia su un processo che sull'altro.

E' certamente fattibile gestire la condivisione delle pagine.

Quanto è grande una tabella delle pagine? Molto!

La tabella deve avere un entry per ogni possibile numero di pagina; supponiamo di avere delle pagine della grandezza di 4KB (212), se l'indirizzo è fornito con 32 bit, possiamo avere 232 / 212 = 220 ; dove i 12 bit meno significativi vengono usati come offset nella pagina, e i 20 bit più significativi sono il numero delle pagine. Con 20 bit posso avere più di un milione* di pagine!

Se ogni entry è di 4 bytes, ogni processo potrebbe avere 4MB di indirizzi fisici per solo la tabella delle pagine, che è un sacco di spazio.

Se invece di avere delle tabelle di 4MB, ho tante tabelle più piccole (per processo) il sistema riesce a gestire meglio lo spazio della memoria.

All'atto pratico possiamo avere "diverse" tabelle delle pagine, organizzate in modo gerarchico:

In questo caso abbiamo una tabella di primo livello che punta ad una di secondo livello, la quale punta alla tabella effettiva.

La prima tabella è chiamata tabella delle pagine esterne, che è quella esposta; la seconda è chiamata tabella delle pagine (l'effettiva tabella delle pagine), la quale punta direttamente alla memoria fisica.

Questo tipo di tabelle vanno a risolvere il problema dell'unica tabella enorme; infatti queste essendo suddivise in ordine gerarchico, sono nettamente più piccole.

Prima l'indirizzo a 32 bit era diviso in due parti, in questo caso, che abbiamo diverse tabelle, l'indirizzo deve essere diviso ulteriorimente.

Avremo quindi che i bit più significativi servono a posizionarmi all'interno della outer page table; i bit intermedi servono per la tabella delle pagine ed i bit meno significativi servono per la memoria effettiva.

🏁 05-21 1:06

Molti processori utilizzano una soluzione basata su tabelle hashed, ovvero il campo chiave (numero di pagina), in hardware viene calcolata una traduzione (mediante una funzione di hashing, sperando non ci siano collisioni), in modo da poter indicizzare in modo molto più veloce:

Per evitare le collisioni utilizziamo un'array di liste con la tecnica del separate chaining.

Ogni processo ha la sua tabella delle pagine; ogni tanto questa copre tutto lo spazio indirizzabile.

L'idea della tabella delle pagine invertita, è quella di "ragionare al contrario": invece di avere per ogni processo la traduzione pagina-frame, avere invece un'unica tabella per tutti in cui vengono riportate tutte le appartenenze dei frame (i processi posseggono i frame di memoria).

Questa è una soluzione brillante perchè permette di ridurre di molto la grandezza della tabella delle pagine, la quale viene mappata sulla grandezza fisica (e non quella massima installabile nel sistema), e quindi non c'è possibilità che essa "ecceda".

Inoltre la tabella è unica, quindi comune a tutti i processi.

Ovviamente il problema risiede nella ricerca, che non può assolutamente essere sequenziale, e di conseguenza sarà necessario adottare un certo meccanismo che trasformi il pid di ogni processo in un hash, dove poi andare a salvare il frame.

La paginazione è una tecnica ottima per ridurre la quantità di memoria sprecata, ma non è l'unica soluzione possibile.

Storicamente, ancora prima della paginazione, il metodo adottato era quello della segmentazione.

Lo svantaggio maggiore della tecnica vista prima (paginazione), è il fatto di dover dividere lo spazio indirizzi di un processo in grandezza uguale alla dimensione delle pagine; questo significa che non è detto che in un'unica pagina capitino lo stesso tipo di dati: ad esempio lo stack potrebbe trovarsi diviso in due pagine.

La soluzione potrebbe essere quella di dividere la memoria non in pagine, ma in segmenti, in modo tale che in ogni segmento vengano posti dei dati che "stanno bene tra di loro"; potremmo avere quindi una divisione in segmenti del tipo:

• Programma principale

• procedure

• funzioni

• metodi

• oggetti

• ...

Il problema di questo metodo, è che ovviamente tutti questi segmenti sono di dimensione variabile, il che significa che quando vado a salvare in memoria i segmenti, troviamo nuovamente il problema della gestione dinamica della memoria!

Un indirizzo deve essere composto nel seguente modo:

< numero-segmento, offset >

Inoltre, Invece della tabella delle pagine, Abbiamo la tabella dei segmenti: Entro nella tabella con il numero di segmento, prendo l'indirizzo di inizio, sommo l'offset ed ottengo l'indirizzo finale (traduzione simile alla paginazione).

Avere delle protezioni con la segmentazione è più semplice, perchè posso, giustamente, dichiarare un segmento come sola lettura, il segmento non è eseguibile, ecc.

Le protezioni sono molto importante, perchè molti degli exploit che bucano il sistema operativo, funzionano proprio in questo modo:

viene iniettato (injected) del codice esterno mediante un meccanismo, e questo viene eseguito (ad esempio dallo stack), da una zona che non è l'area text!

Andando a dire, quindi, che il codice può essere eseguito solo nel segmento che contiene l'area text, abbiamo una protezione aggiuntiva contro gli exploit.

In un epoca passata (ancora una volta), la memoria principale era molto piccola. Quando l'utente voleva alternare molti processi (interattivi, con diversi terminali remoti) velocemente, capitava spesso che la memoria finisse.

Per risolvere questo problema, si usava la tecnica dello swapping, ovvero, per fare spazio in memoria, si prendeva l'intero processo con il suo spazio indirizzi, e lo scaricava su una memoria di appoggio; questa memoria era il disco più veloce presente all'interno della macchina.

In questo modo si fa spazio per un nuovo processo da eseguire.

Questa tecnica, ai nostri giorni, non viene praticamente più utilizzata; Microsoft chiama la memoria virtuale "Spazio Di Swap" impropriamente, in questo schemo lo swap vero e proprio si verifica quando l'intero processo esce dalla ram ed un intero processo entra.

Multics era un sistema operativo abbastanza elaborato, così elaborato da far "perdere le speranze" ai suoi programmatori, che decisero di creare un nuovo sistema operativo molto più semplice: UNIX.

---

FINE CAPITOLO 9

Nei sistemi moderni non si utilizza ne la paginazione ne la segmentazione, ciò che realmente viene usato è la memoria virtuale suddivisa a pagine.

Il programma per poter essere eseguito deve essere caricato in memoria centrale del sistema, perchè dal disco non può essere eseguito nulla.

La domanda sorge spontanea: serve che tutto il programma venga caricato in memoria?

• Probabilmente ci sono dei "pezzi" che non mi serviranno: ad esempio nel programma c'è una porzione di codice che serve ad un compito specifico che non viene utilizzato spesso, non è meglio lasciarlo sul disco e portarlo in memoria solo quando serve? ovviamente si.

• Mi serve tutto il programma contemporaneamente in memoria? Ovviamente no.

Se riuscissi a portare in memoria solo dei "pezzi" di programmi così grandi, il vantaggio sarebbe quello di non sprecare spazio in memoria con porzioni di codice che probabilmente non verrà mai eseguito. Come conseguenza, ho il fatto che posso mandare in esecuzione più programmi in esecuzione.

L'idea, quindi, è quella di avere la maggior parte del programma sul disco, e portare solo su richiesta in memoria la parte di codice che realmente mi serve in quel momento.

Questa può essere vista come una forma di caching.

Tutti i sistemi operativi utilizzano questa tecnica per il caricamento dei programmi in memoria.

I vantaggi sono:

• Ogni programma occupa meno spazio durante la sua esecuzione, quindi posso eseguire un maggior numero di programmi.

• E' richiesta una minore quantità di operazioni I/O per caricare e scambiare programmi nella memoria, quindi ogni programma utente gira più velocemente.

• Visto che in memoria vengono caricate solo delle porzioni di programma, posso avere un programma anche più grande della memoria fisica a disposizione!

La memoria virtuale realizza l'estrema separazione tra la vista logica della memoria e l'indirizzo fisico; la CPU continua a vedere degli indirizzi fisici di memoria, anche se magari quella porzione di codice (o atro) è sul disco.

L'idea che solo parte del programma è in memoria, permette che spazio logico possa essere molto più grande dello spazio fisico.

La CPU vede uno spazio indirizzi virtuale, che solitamente inizia da 0. Nel frattempo, la memoria fisica è organizzata in pagine (quindi frames).

La memoria virtuale può essere implementata in due modi (che abbiamo visto precedentemente):

• Pagine    (soluzione utilizzata nei sistemi odierni)

• Segmenti

In questo schema si può notare come la memoria virtuale sia quella esposta, che fa riferimento alla mappa della memoria; nella mappa sono presenti gli indirizzi, che potrebbero far riferimento a dei dati realmente presenti nella memoria fisica, oppure potrebbero essere sul disco.

Si nota inoltre, che c'è uno scambio di dati, ma bisogna notare che i dati sul disco, per essere eseguiti, devono prima arrivare in RAM;

Attenzione: questo scambio di dati tra RAM e disco, non è uno swap; questo perchè per essere uno swap tutto lo spazio indirizzi di un processo esce dalla ram, e tutto lo spazio indirizzi di un altro entra.

In questo caso, quelle che vengono scambiate sono delle pagine.

Una memoria virtuale implementata a pagine (non a segmenti), utilizza il demand paging, ovvero la paginazione su richiesta; le pagine vengono quindi portate in ram solo quando servono.

Una pagina è richiesta quando la CPU deve accedere ad un indirizzo (di memoria) contenuto nella pagina.

Per le pagine non esistenti, nella tabella delle pagine viene scritto "i" - invalido; questo valore "i" può essere anche utilizzato per le pagine che esistono ma non sono state caricate in memoria, per cui non esiste il numero di pagina (frame) corrispondente.

Il processo è il seguente:

• La CPU rilascia un indirizzo

• L'MMU tenta la traduzione ma nel TLB non trova nulla perchè l'indirizzo non è ancora presente

• Consulta la tabella delle pagine

• Trovato l'indirizzo si reca in quella posizione ma trova "i"; abbiamo due possibilità (determinate dal SO):

  • La pagina non esiste per quel processo

  • La pagina esiste ma è sul disco e va caricata in memoria.

Come detto anche prima, questi vari processi non sono categorizzati come swapping, proprio perchè per essere uno swap, l'intero spazio indirizzi di due processi diversi devono essere scambiati tra loro;

In questa immagine, infatti, si nota che il programma A che viene rimosso dalla ram, ma non tutto il programma B viene caricato.

Nella tabella delle pagine è presente il bit valid-invalid; quando un frame è marcato come valid vuol dire che quel frame è caricato in memoria ed il sistema è perfettamente a conoscenza della sua locazione in memoria.

Se invece un frame è marcato come invalid (i), potrebbe essere che quella pagina non esiste per quel processo, oppure la pagina non è stata caricata in memoria, perchè non utilizzata fino a quel momento.

Quando si effettua la traduzione dell'indirizzo tramite MMU, se quel frame trovato si ha una page fault, ovvero un "errore" nella traduzione pagina-frame

Come si vede in questa immagine, le pagine che sono in backing store, ovvero sul disco, sono le pagine che sono marcate con "i", invalid; questo non perchè non esistono, ma perchè ancora non sono state caricate in memoria.

Quando si ha un page fault, a differenza dei sistemi di caching visti precedentemente, si attua un meccanismo misto tra hardware e software: quando si trova un indirizzo marcato con "i", scatta l'intervento del sistema operativo (soluzione software).

Il SO deve controllare su una sua tabella interna per capire se "i" in quel caso significa che si ha una pagina inesistente, oppure non è ancora stata caricata in memoria.

Se la pagina si rivela inesistente, il processo deve essere abortito, perchè potrebbe aver sfondato un array o altri errori; se ci facciamo caso, quando si programma male e si sfonda un array, si ha come errore segmentation fault, anche se non abbiamo più la tecnica della segmentazione! Questo errore deriva da quando i SO adottavano una divisione della memoria a segmenti, e storicamente, è rimasto invariato.

Se invece la pagina si trova ancora sul disco, deve portarla in memoria:

• Deve trovare un frame libero.

• Effettuare lo swap della pagina lanciando un'operazione sul disco

• portare la pagina in memoria

• modificare la tabella delle pagine ponendo sia l'indirizzo corretto del frame sia aggiornando il bit da invalid a valid.

• Rilanciare l'istruzione che ha provocato il page fault.

Questo significa che dopo il page fault, l'istruzione deve ripartire come se nulla fosse. Un processore che ha delle istruzioni molto complicate (ovvero che per eseguire una singola istruzione compiono diverse operazioni) non si trovano bene con questa tecnica!

Serve un processore che non faccia modifiche permanenti finquando l'istruzione non è stata completata, perchè solo allora si ha la certezza di poter andare avanti con la prossima istruzione.

I processori destinati all'utilizzo della memoria virtuale, per via del fatto che con un page fault devono riavviare da zero l'istruzione che l'ha provocato, non effettuano modifiche permanenti finchè l'istruzione non è stata eseguita.

1. Riferimento alla memoria -> tabella delle pagine e trovo invalid

2. Trap ovvero un software interrupt che chiama il siste operativo; il sistema operativo decide se il riferimento è davvero invalid oppure non è ancora stato caricato in RAM

3. Pagina in backing store (sul disco e non su RAM)

4. Caricamento della pagina mancante in RAM

5. Reset della tabella delle pagine ponendo l'indirizzo corretto del frame e il bit su valid

6. Restart dell'istruzione.

Questa operazione non è delle più veloci. Infatti, la CPU mentre questo processo avviene (ovvero mentre la pagina viene caricata in RAM), passa ad un altro processo.

Quando la CPU torna a questo processo, ripartirà direttamente dall'istruzione che ha causato il Page Fault.

---

FINE LEZIONE 11