Vai al contenuto
Home » Notes » Appunti Sistemi Operativi: Capitolo Memoria Virtuale

Appunti Sistemi Operativi: Capitolo Memoria Virtuale

copertina appunti sistemi operativi capitolo memoria virtuale e paging

Raccolta di appunti universitari di sistemi operativi con domande e risposte sul capitolo della memoria virtuale e della paginazione (paging).
Fonte: il mio libro di sistemi operativi Operating System Concepts with Java, di Silberschatz, Galvin e Gagne.

Appunti Sistemi Operativi: Capitolo Memoria Virtuale e Paginazione

Quali sono i vantaggi e gli svantaggi della memoria virtuale?

Il principale vantaggio è la possibilità di eseguire programmi che sono anche solo parzialmente caricati in memoria centrale. Ciò significa che più programmi possono eseguirsi contemporaneamente e che un programma non è limitato dalla dimensione reale della memoria centrale fisica.

Tra gli svantaggi ci sono il rischio di trashing e il rischio di page fault incontrollati che potrebbero peggiorare drasticamente le performance del sistema.

In una tabella di pagine (pagetable), cosa sono il valid/invalid bit e il dirty bit? A cosa servono?

Il valid/invalid bit viene usato nella demand paging (una pagina è portata in memoria solo se è effettivamente necessaria) e permette di verificare se la pagina corrispondente al bit è stata caricata in memoria (valid) oppure no (invalid). In questo secondo caso, la pagina non è valida, cioè o non appartiene allo spazio degli indirizzi logici del processo oppure è attualmente in memoria secondaria.

Il dirty bit (o bit di modifica) viene usato negli algoritmi di page replacement e indica se la pagina corrispondente è stata modificata da quando è stata caricata in memoria (=1) oppure no (=0). Quando si va a scegliere la pagina da sostituire, se si sceglie una con dirty bit =1 sarà necessario scriverla nel disco perché sono state effettuate delle modifiche, se invece il dirty bit è =0 non è necessario scriverla sul disco, perché è già presente.

Come funziona LRU? Perché LRU non è utilizzabile in pratica?

L’algoritmo Least Recently Used, LRU, consiste nel sostituire la pagina che non è stata usata per il periodo più lungo. Il problema principale di LRU riguarda la sua implementazione, perché può richiedere una notevole assistenza da parte dell’hardware. Il problema è quello di determinare un ordine per i frame definito dal momento dell’ultimo uso: si possono utilizzare dei contatori o uno stack, ma sono entrambi pesanti da implementare e quasi impossibile senza l’uso del TLB. L’aggiornamento dei campi del contatore o dello stack, infatti, si deve fare per ogni riferimento alla memoria, generando un notevole sovraccarico per la gestione della memoria.

Cosa è e come funziona l’algoritmo della seconda chance? Perché è considerato un’approssimazione di LRU e che vantaggi ha rispetto a LRU?

Gli algoritmi che usano il reference bit come discriminante tra pagine differite e non differite di recente sono delle approssimazioni di LRU. In particolare, l’algoritmo della seconda chance sostituisce la pagina se il valore del reference bit è 0, altrimenti lo imposta a 0 e passa ad analizzare la pagina e il relativo bit successivi. In questo modo, una pagina a cui si offre una seconda chance non è mai sostituita finché tutte le altre pagine non siano state sostituite, oppure non sia stata data loro una seconda chance. Per implementare questi passi, si utilizza una coda circolare, in cui un puntatore indica la prima pagina da sostituire.

È possibile che un processo P che gira su un sistema A con memoria virtuale venga eseguito più velocemente che su un sistema B identico ad A ma senza memoria virtuale?

Sì, se ad esempio P non genera mai page fault e non è necessario caricare in memoria tutto il codice di P per eseguirlo. Ma in generale non si sa, potrebbe essere più veloce su A perché si potrà caricare solo una parte del programma, ma potrebbe essere più veloce su B se l’esecuzione su A produce molti page fault e il caricamento dell’intero programma non è troppo penalizzante.

Quali sono gli elementi fondamentali della tecnica della memoria virtuale? Perché è importante?

La memoria virtuale è importante perché permette di oltrepassare il limite fisico della memoria. Lo spazio di indirizzamento logico può essere molto più grande di quello fisico, perché in memoria sarà caricata solamente una parte del processo in esecuzione. In questo modo, lo spazio degli indirizzi è condiviso da più processi, aumentando così il livello di multiprogrammazione e risulta più efficiente anche la creazione di nuovi processi.

Cos’è un algoritmo di page replacement? Cosa si cerca di ottimizzare con un algoritmo del genere?

Quando si ha un page-fault, la pagina richiesta viene caricata in memoria. Se non ci sono frame liberi, inizia l’operazione di page replacement, ovvero la scelta di una pagina vittima che non è usata al momento e la si sostituisce con la pagina richiesta dal processo. Un algoritmo di page replacement è un algoritmo che si occupa di scegliere quali pagine vittima liberare in caso di uno o più page fault. Alcuni esempi di algoritmi di page replacement sono il FIFO page replacement, il LRU page replacement e il Second Chance page replacement

Come funziona l’optimal page replacement?

L’optimal page replacement è un algoritmo ottimale che non soffre della cosiddetta anomalia di Belady (anomalia per cui in alcuni algoritmi di page replacement, all’aumentare dei frame assegnati al processo, il tasso di page fault aumenta) ed è l’algoritmo che, teoricamente, offre il rate di page fault più basso di tutti. L’optimal page replacement consiste nel rimpiazzare la pagina che non sarà usata per il più lungo periodo. È un algoritmo prevalentemente teorico (metterlo in atto richiederebbe leggere il futuro per sapere quale pagina è effettivamente l’ultima ad essere usata), ma ne esiste una approssimazione: l’algoritmo LRU.

Cos’è il problema della frame allocation?

Il problema della frame allocation consiste nello stabilire un criterio per l’allocazione della memoria libera ai diversi processi. Questo criterio è soggetto ad alcuni vincoli: non si possono assegnare più frame di quanti disponibili ed è necessario assegnare almeno un numero minimo di frame a processo, perché al decrescere del numero di frame allocati a ciascun processo aumenta il tasso di page fault, causando un rallentamento nell’esecuzione del processo. Il numero minimo di frame è definito dall’architettura del calcolatore, mentre il numero massimo è definito dalla quantità di memoria fisica disponibile.

Cos’è un algoritmo di “frame allocation”? indicare due possibili modi di effettuare frame allocation. Qual è la differenza tra allocation di tipo “local” e di tipo “global”?

Un algoritmo di frame allocation stabilisce il numero di frame da allocare a ciascun processo. L’allocazione può essere fissa o con priorità. La fixed allocation si divide in equal (ogni processo ha lo stesso numero di frame allocati) oppure proportional (i frame liberi vengono suddivisi tra i processi in base alla loro taglia a=m*si/S). La priority allocation si basa invece sulla priorità dei processi e non sulla loro dimensione.

La differenza tra allocazione locale e globale è che in quella locale l’algoritmo seleziona per replacement un frame già allocato al processo, mentre in quella globale il frame può essere uno qualsiasi, sia esso libero, già del processo oppure allocato ad un processo con priorità minore.

Un sistema (hardware + SO) soffre spesso del problema del thrashing. Cosa è questo fenomeno? Indicate due modifiche al sistema, un hardware e una software, che potrebbero migliorare la situazione

Nei sistemi che implementano la memoria virtuale, il thrashing è un fenomeno per il quale i processi passano la maggior parte del loro tempo a generare page fault e aspettando che la pagina mancante sia caricata in memoria primaria per poter riprendere l’esecuzione, utilizzando così la CPU a livelli minimi (scarsamente utilizzata).

Per evitarlo, si può monitorare il numero di page fault per processo e quindi concedendo dei frame ad un altro processo o togliendoli quando tale numero supera o è inferiore a certe soglie predeterminate. In caso, comunque, si dovesse raggiungere una situazione problematica occorre diminuire il livello di multiprogrammazione.

Una soluzione hardware che potrebbe migliorare la situazione è quella di aumentare le dimensioni della RAM, perché, così facendo, si avranno più frame a disposizione da distribuire e allocare ai vari processi.

Cosa vuole dire che una pagetable è paginata su più livelli?

La tabella delle pagine, o page table, è una struttura tabellare composta da pagine. Se una pagetable contiene una gerarchia di altre pagetable, parliamo di pagetable paginata su più livelli. In breve, le entry della pagetable primaria contengono riferimenti alle pagetablet secondarie, e così via.

É necessaria una paginazione di secondo livello quando la dimensione della page table primaria (numero di entry * dimensione di ogni entry) è strettamente maggiore della taglia di un frame (offset). A questo punto l’indirizzo logico avrà un aspetto del tipo:
numero pagina page table primo livello \ numero pagina page table secondo livello \offset

Quelli sotto sono alcuni tra gli algoritmi per page-replacement. Indicare per tutti il problema principale che comporta.

 First-In First-Out
Optimal Algorithm
LRU (Least Recently Used)

Per il FIFO, il rischio è quello di togliere dalla memoria una pagina ancora fortemente usata, e questo andrebbe quindi a causare un altro page fault di lì a poco tempo.
L’algoritmo ottimale è un algoritmo solamente teorico, non implementabile perché richiederebbe di conoscere a priori in anticipo le pagine che saranno referenziate.
Il LRU necessita di un’importante assistenza hardware ed è comunque costoso a causa delle modifiche da apportare ad ogni accesso in memoria (bisognerebbe registrare l’ordine in cui le pagine vengono referenziate tramite una stack o dei counters), infatti vengono implementate nella realtà sue approssimazioni.

Perché i moderni sistemi operativi implementano la memoria virtuale?

Perché permette di raggiungere un livello di multiprogrammazione più elevato: attraverso la memoria virtuale è possibile eseguire programmi non interamente caricati in memoria e i processi non sono più limitati dalla dimensione della memoria fisica.

In un sistema con una memoria virtuale, supponiamo che il grado di utilizzazione del processore (cpu) e del disco per la paginazione siano i seguenti:

Cpu 15%, disco 95%                             
Cpu 95%, disco 10%                     
Cpu 20%, disco 5%

Ognuno di questi casi è una situazione ottimale o no? Perché? Se la situazione non è ottimale, cos’è ragionevole faccia il sistema operativo?

Nel primo caso, siamo in presenza di thrashing ed è quindi necessario ridurre il livello di multiprogrammazione. Nel secondo caso, i parametri possono essere definiti come corretti ed è quindi una soluzione ottimale. Nel terzo caso, è possibile aumentare il livello di multiprogrammazione.

Cos’è un page fault? Nella sua gestione, qual è il passo più costoso in termini di tempo?

Un page fault è una occorrenza nella quale un processo richiede l’accesso ad una pagina che non si trova caricata in memoria. Il passo più costoso è lo swapping, ovvero lo spostamento della pagina richiesta dalla memoria secondaria alla memoria centrale o viceversa.

Come si calcola il Tempo medio di accesso (EAT) in caso di optimal page replacement?

Formula per il calcolo di EAT = (#page fault * tempo swap + #pagine utilizzate * tempo accesso memoria * #accessi medi) / (#pagine utilizzate / #accessi medi)

EAT = (1-p)*(tempo di accesso alla RAM)+ p*(tempo page fault di swap in e swap out)

p= rate di page fault in percentuale

Come funziona l’algoritmo di optimal page replacement? Perché non è implementabile?

L’algoritmo di optimal page replacement è un algoritmo teoricamente ottimale per la gestione del page replacement in un sistema. Per ottimale si intende che è in grado di generare sempre il minor numero di page swap. L’algoritmo funziona sostituendo ad ogni nuova richiesta di page fault la pagina che per più tempo non sarà utilizzata dal sistema. Esempio:

Sistema con 3 frame, inizialmente caricati a 1 2 3:

4,1,1,2,1,5,6,4,3,2,1

Al primo page fault di 4 andrò a fare page replacement con la pagina 3, ovvero la pagina che in quel momento caricata in memoria viene usata più tardi. Se più pagine, durante un page replacement, dovessero non essere più richiamate in futuro, è indifferente la scelta della pagina da rimuovere.

Altri capitoli:
Struttura e architettura del Sistema operativo
CPU scheduling
Processi e Thread

Grazie per la lettura

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *