Sistemi Operativi - Gestione della memoria

Sistemi Operativi - Gestione della memoria

By Giovanni Pedroncelli

La memoria centrale

La memoria centrale

Situazione ideale: memoria infinita, veloce, poco costosa, non volatile

​

Gestione della RAM tramite ​virtualizzazione --> la fa sembrare infinita per soddisfare tutte le richieste dell'utente

Gestore della memoria

1. sa sempre quali parti della memoria sono libere e quali in uso

   ​

2. ​sceglie quali parti di memoria allocare ai processi che ne hanno bisogno e poi la dealloca

   ​

3. ​gestisce lo swapping tra memoria centrale e disco quando la memoria centrale non è sufficientemente grande

Gestore della memoria

Compito principale = ​trasformare il programma in esecuzione (statico, su memoria di massa) in processo (dinamico, su memoria centrale)

​

Problema: il compilatore e il linker, durante la fase di compilazione di un programma generano collegamenti tra istruzioni e indirizzi di memoria SENZA SAPERE dove il programma e i dati saranno esattamente caricati in memoria

Codice rilocabile

• Il compilatore e il linker generano ​indirizzi relativi (indirizzi logici)

  ​

• All'atto del caricamento in memoria centrale, gli indirizzi relativi (logici) ​saranno trasformati in indirizzi assoluti (indirizzi fisici) all'interno della memoria RAM

Codice rilocabile

Ogni ​processo dispone di uno spazio di indirizzamento logico [0,max] che dovrà essere poi caricato fisicamente nella RAM. Il compilatore suppone che il processo sarà sempre allocato a partire dall'indirizzo più piccolo, 0. A partire dal valore 0 sono generati tutti gli indirizzi

Codice rilocabile

Due modalità di rilocazione

​

• Rilocazione Statica: quando il processo è caricato in memoria, si individua l'indirizzo di base e si somma a tutti gli indirizzi logici (offset)

• Rilocazione Dinamica: ​il processo è caricato in una qualunque zona libera di memoria e in fase di esecuzione si salva nel registro base (di rilocazione RL) l'indirizzo effettivo di prima locazione di memoria. Durante l'esecuzione, istruzione per istruzione si calcola l'indirizzo assoluto sommando a ogni indirizzo logico il valore contenuto nel registro base RL

Codice rilocabile

Memory Management Unit (MMU)

Dispositivo hardware che associa indirizzi fisici a indirizzi logici

Address binding

Il registro RL contiene l'indirizzo fisico più piccolo, il registro limite contiene l'indirizzo logico più alto utilizzabile da un determinato processo --> controllo di protezione della memoria

Protezione della memoria

Riepilogo

Durante la fase di linking --> ​calcolo degli indirizzi logici

​

Binding (passaggio da indirizzo logico a indirizzo fisico) può avvenire:

​

1. durante la compilazione (​indirizzamento assoluto)

   ​

2. ​durante il loading del programma (rilocazione statica)

   ​

3. ​durante l'esecuzione del programma (rilocazione dinamica)

​

Problemi

• Per essere eseguito, un programma deve risiedere in memoria centrale e lo spazio libero deve​ essere sufficientemente grande e deve essere contiguo (impossibile con i programmi di oggi)

  ​

• ​Sistemi multiprogrammati: continuo caricamento e scaricamento dei programmi in memoria --> frammentazione della memoria: spazio libero sufficiente ma NON contiguo --> costosa ricompattazione​

Soluzioni

1. Swapping: liberare la RAM dai processi ​temporaneamente inattivi e salvarli su disco. Rallentamento e calo di prestazioni.

   1. Identificare i processi​ inattivi in memoria (waiting list)

   2. Salvare i loro dati su disco (contesto di questi processi)

   3. Rimuoverli dalla memoria centrale

   4. Caricare un nuovo processo nello spazio appena liberato

2. ​Caricamento dinamico: caricare in memoria solo ciò che serve effettivamente e il resto rimane su disco per poi essere successivamente caricato quando necessario

Soluzioni

3. Overlay: Frazionamento del programma eseguito a priori dal programmatore (alcune parti sono caricate alternativamente in memoria)

4. Partizionamento: riservare a ogni processo una dimensione fissa di memoria per evitare lo swapping e ridurre la frammentazione

Multiple Choice

Quale NON è un compito del memory manager?

• sapere sempre quali parti della memoria centrale sono in uso

• individuare il programma da caricare in memoria

• scegliere quale parte di memoria allocare ai processi

• gestire lo swapping tra memoria principale e disco

Multiple Select

L'indirizzo logico

• viene assegnato a partire dalla cella 0

• viene rilocato dal linker

• viene trasformato in indirizzo fisico dal linker

• viene trasformato in indirizzo assoluto dal loader

Multiple Choice

MMU significa

• Memory Management Utility

• Memory Maker Unit

• Memory Management Unit

• Memory Maker Utility

Multiple Choice

Nella rilocazione statica

• viene sommato a ogni istruzione l'offset

• viene utilizzato il registro base

• l'indirizzo base viene sommato durante l'esecuzione

• l'indirizzo base viene sommato durante la fase di link

Multiple Choice

La rilocazione statica avviene all'atto del caricamento in memoria

• Vero

• Falso

Multiple Choice

L'offset si ottiene sommando all'indirizzo di base i riferimenti

• Vero

• Falso

Multiple Choice

Nella rilocazione dinamica l'indirizzo assoluto è determinato dal loader

• Vero

• Falso

Multiple Choice

Lo swapping avviene quando la memoria principale libera non è sufficiente

• Vero

• Falso

Multiple Choice

Il gestore della memoria ha il compito di deallocare la memoria quando serve

• Vero

• Falso

Multiple Choice

Il compilatore genera degli indirizzi relativi (indirizzo fisico)

• Vero

• Falso

Tecniche di allocazione della memoria centrale

Partizionamento

Suddividere la memoria in partizioni e assegnare una partizione a un processo (indipendentemente dalle sue dimensioni), partendo dal SO

​

Problema: quanto deve essere grande una partizione?

Troppo piccola -->​ frammentazione

Troppo grande --> ​spreco memoria e necessità di swapping

​

Partizione fissa / Partizione variabile

​

​

Schema a partizione fissa

La memoria è suddivisa in partizioni di dimensioni anche diverse all'inizializzazione del sistema, staticamente, con una tabella con lo stato di ciascuna partizione (libera/occupata)

​

Ogni partizione ha una coda dei processi in attesa

​

Problemi di frammentazione interna/esterna​

Frammentazione interna

Processo molto più piccolo della partizione ​in cui viene salvato (succede se le code delle partizioni più piccole sono tutte occupate).

Frammentazione interna - soluzione

Una sola coda di ingresso.

Se si libera una partizione, due criteri possibili:

1. ​individuo il primo processo in coda che può essere contenuto

2. individuo il processo più grande in coda che può essere contenuto (--> possibile starvation dei processi più piccoli)

Frammentazione esterna

Complessivamente c'è abbastanza spazio per ospitare un processo in coda ma è frammentato in partizioni diverse --> non assegnabile al processo​

Schema a partizione variabile

Possibilità di modificare dinamicamente il numero e la dimensione delle partizioni, in base alla dimensione del processo da allocare tramite unione di blocchi contigui o suddivisione di un blocco troppo grande

​

​SO più complesso con 4 strategie risolutive:

1. ​first-fit

2. ​next-fit

3. best-fit

4. ​worst-fit

​

​

Frammentazione esterna

Necessità di defrag (--> decadimento prestazioni). 1 byte/ms

Area di swap

Strategia sfruttata per processi in waiting list oppure a bassa priorità​

Multiple Choice

Quale tra le seguenti NON è una strategia che risolve il problema dell'allocazione dinamica della memoria centrale?

• first-fit

• best-fit

• good-fit

• worst-fit

Memoria virtuale

Obiettivi: evitare la frammentazione, non ricorrere alla compattazione

​

​Tecniche di allocazione NON contigua: paginazione e segmentazione

​

Ulteriore vantaggio: ​sono caricate in memoria solo le parti effettivamente utili per l'esecuzione del processo (il resto è su disco)

​

​Principio di località: è molto probabile che l'istruzione successiva sia vicina a quella correntemente in esecuzione

Paginazione

Suddivisione del programma in pagine di dimensione fissa ​(pagine logiche)

​

Suddivisione della memoria in pagine di dimensione fissa (​frame o pagine fisiche)

Paginazione

Le pagine logiche NON devono essere necessariamente contigue

​

Per caricare un programma basta una pagina fisica libera in cui salvare la prima pagina logica del programma (non va caricato interamente in memoria)

Paginazione - vantaggi

• Mantenere in memoria solo le parti necessarie

• ​Gestire solo piccole parti di memoria

• ​No frammentazione esterna

• ​Pochissima frammentazione interna

• ​Possibilità di usare porzioni di memoria non contigue per un programma

Tabelle delle pagine

Una tabella delle pagine con gli indirizzi e le info di tutte le pagine fisiche

​

Una tabella per ogni processo​: quali parti in RAM e quali su disco​

Binding nella paginazione

Fetch policy

Il SO deve determinare quando una pagina va caricata in RAM​

​

• demand page: pagina caricata solo quando viene fatto riferimento ad una sua locazione

• ​prepaging: sfruttando il principio di località spaziale, quando si carica una pagina si caricano anche quelle adiacenti (senza esagerare)

Protezione della memoria

Nella tabella a ogni frame associati dei bit di protezione (sola lettura, lettura/scrittura, esecuzione)

​

Tentativo di accesso illegale --> trap al SO​ --> sospensione processo

​

Un bit indica se la pagina appartiene allo spazio del processo (valid) oppure no (invalid)​ --> segment violation

Page fault

Bit di validità:

0 = pagina non in memoria

1 = pagina in memoria

​

Fetch pagina ma bit di validità = 0 --> page fault​

​

Se c'è pagina libera OK, altrimenti ​page replacement

Page fault

​(3) page fault può essere per riferimento illegale (protezione memoria) o legale --> caricamento nuova pagina in memoria

Località spazio-temporale

• Località spaziale: ​è altamente probabile che la prossima area di memoria a cui accedere sia vicina a quelle a cui abbiamo acceduto di recente (codice sequenziale)

• ​Località temporale: è altamente probabile che si acceda nuovamente a locazioni di memoria a cui si è acceduto recentemente (cfr. cicli, funzioni ricorsive)

​

Il 90% del tempo è speso sul 10% del codice

Replacement policy

Scegliere la pagina vittima ​da rimuovere dalla memoria per far posto alla nuova pagina da caricare

​

1. ​Resident set management: sceglierla tra le pagine del processo da caricare o da pagine di altri processi?

2. Page replacement algorithm: ​algoritmi per scegliere la pagina con l'obiettivo di minimizzare il numero di page fault

3. ​Optimal page replacement algorithm: qual è la pagina vittima migliore? Qual è il tempo massimo da impiegare per cercarla?

Replacement policy

1. Individuazione della Pvitt

2. ​Salvataggio di Pvitt sul disco

3. ​Caricamento di Pnew nel frame appena liberato

4. ​Aggiornamento tabelle

5. Ripresa del processo​

​

Se ​la versione di Pvitt è identica a quella già presente nel disco, il passo 2 si salta (dirty bit: = 0 Pvitt su disco è già aggiornata --> saltiamo il passo 2, = 1 Pvitt su disco non è aggiornata --> eseguiamo il passo 2)

Algoritmi di sostituzione

Obiettivo: minimizzare il numero di page fault​

Strategia: sostituire ​le pagine la cui probabilità di essere accedute a breve termine è bassa (principio​ di località)

​

1. ​FIFO Page Replacement Algorithm

2. ​Least Recently Used

3. ​Not Recently Used

4. Algoritmi di conteggio​

​

FIFO Page Replacement Algorithm

Sostituisce la pagina che occupa da più tempo la memoria, indipendentemente dal suo uso (NON si usa il principio di località)

​

Necessario il time stamping dei riferimenti per ​conoscere la cronologia dei caricamenti in memoria

Least Recently Used (LRU)

Si basa sul principio di località: si sostituisce la pagina che è stata usata meno recentemente

​

Necessario il time-of-use, l'istante in cui è avvenuto l'ultimo accesso

​

Struttura di tipo stack: quando si accede ​alla pagina la mettiamo al top e quindi al bottom c'è la pagina vittima

Not Recently Used (NRU)

Versione semplificata di LRU​

​

Per ogni pagina un bit di uso R inizializzato a 0, messo a 1 quando si accede alla pagina, periodicamente resettato a 0

​

Versione modificata con il dirty bit M

​

Viene rimpiazzata la pagina con R = 0 e M = 0​

Algoritmi di conteggio

​​

Least Frequently Used (LFU): sostituisce la pagina con il minor numero di riferimenti (una pagina con molti riferimenti è molto usata e quindi serve)

​

Most Frequently Used (MFU): ​sostituisce la pagina con il maggior numero di riferimenti (pochi riferimenti perché caricata da poco e quindi serve)

​

Working set

​​Memoria di massa molto più lenta della memoria centrale

Tanti swapping --> forte rallentamento del sistema​ --> trashing

​

​

​

​​Δ è la dimensione del working set o finestra di lavoro, una stima del numero di pagine necessarie al processo per evolvere correttamente

​

​

​

Working set

​​Attenzione al valore del working set Δ

• ​troppo basso --> troppi page fault

• ​troppo alto --> caricamento di pagine non necessarie​

​​D è la richiesta totale di frame del processo

WSS è il numero di pagine referenziate dal processo al riferimento i

​

​

​

• D < num pagine libere --> il nuovo processo viene avviato

• ​D > num pagine libere --> swapping

Working set

​​Metodo alternativo

Riepilogo paginazione

​​

Permette di eliminare del tutto la frammentazione esterna perché size(pagina fisica) = size(pagina logica) ed è possibile allocare in modo non contiguo

​

Segmentazione

​​Come la paginazione ma i segmenti sono di dimensione variabile

​

La memoria centrale viene suddivisa come il codice (in funzioni)​

​

Ogni funzione del codice = un segmento​

​

A ogni segmento è associato un numero e la sua lunghezza

Segmentazione

Segmentazione

Segmentazione - vantaggi

• ​​più semplice la gestione di strutture dati dinamiche

  ​

• ​facilitata la condivisione di segmenti tra processi

  ​

• più semplice il linking di procedure compilate separatamente

  ​

• ​ogni segmento può avere un diverso tipo di protezione

Segmentazione - problema

Frammentazione esterna (checkerboarding)​

Segmentazione con paginazione

​Memoria centrale suddivisa in ​pagine fisiche (frame) di dimensione fissa

Spazio di indirizzamento del processo suddiviso in segmenti logici di dimensioni diverse che sono ulteriormente suddivisi in pagine logiche della stessa dimensione dei frame

​

Struttura dell'indirizzo logico

Multiple Choice

Il page fault si verifica quando

• le pagine di memoria sono tutte occupate

• in memoria non ci sono pagine libere

• il sistema operativo non trova la pagina da caricare

• un programma indirizza una pagina non presente in memoria

Multiple Choice

Quale tra i seguenti NON è un page replacement algorithm?

• Least Recently Used

• Least Frequently Used

• Not Recently Used

• Not Frequently Used

• Most Frequently Used

Multiple Choice

Quale tra le seguenti affermazioni è falsa in merito alla paginazione?

• La memoria fisica è divisa in blocchi chiamati frame o pagine fisiche

• Il programma è diviso in blocchi di uguale dimensione dette pagine

• Il numero di pagine logiche è uguale al numero delle pagine fisiche

• Il codice deve essere rilocabile dinamicamente

• Si risolve il problema della frammentazione esterna

Multiple Choice

La strategia di sostituzione FIFO Page Replacement Algorithm tiene conto del principio di località

• Vero

• Falso

Multiple Choice

Least Frequently Used e Most Frequently Used sono algoritmi di conteggio

• Vero

• Falso

Multiple Choice

Il fenomeno del trashing è dovuto alla lentezza dello swapping

• Vero

• Falso

Multiple Choice

Il fenomeno del trashing è dovuto al fatto che la memoria secondaria è molto più lenta rispetto alla memoria principale

• Vero

• Falso

Multiple Choice

Il working set è un'approssimazione della dimensione dell'area di località del programma

• Vero

• Falso

Multiple Choice

Un working set troppo largo non include l'intera località e non riesce a minimizzare il numero di page fault

• Vero

• Falso