Memory management
49
Gestione della memoria
• I processi Unix lavorano su uno spazio di indirizzamento virtuale
(E 0,
(Es.
0 . . . , 232 − 1 su iindirizzi
di i i a 32 bit)
bit);
• Ogni processo ha uno spazio indirizzi separato per i segmenti Text,
Data e Stack;
• Le dimensioni di Stack e Data possono cambiare durante l’esecuzione;
• Gli indirizzi di Data crescono a partire dalla parte bassa degli indirizzi
virtuali (0 →..);
• Gli indirizzi dello Stack crescono a partire dalla parte alta degli indirizzi
virtuali (..→ 232);
42
Gestione della memoria
• Il sistema operativo Unix è pensato per essere indipendente dalla
macchina ->
> Lo schema di gestione della memoria varia tra piattaforme
piattaforme.
• Prime versioni : partizionamento variabili senza memoria virtuale.
• Attuali: memoria virtuale paginata (on demand).
demand)
• Due schemi separati per la gestione della memoria:
- Paging system: realizza la memoria virtuale
virtuale, allocando ai processi
i frame (pagine fisiche) della memoria principale ed anche i buffer
del disco alle pagine di memoria virtuale.
- Allocatore di memoria per il Kernel: alloca memoria per i buffer, le
primitive di comunicazione, gli streams del Kernel etc.
47
Configurazione della memoria fisica
P.S.: se la pagina è di 1K e il descrittore della core map è di 16byte, la core map (1 desc. per pagina) occupa meno del 2% della memoria.
48
Spazio fisico e logico
47
Strutture dati
• Un processo in memoria (ready-to-run) necessita solo delle seguenti
strutture dati:
- User-area, o U-area;
- Tabelle delle pagine; (una per i segmenti Data/Text, una
per i segmenti
per i segmenti
U-Area/Stack).
U Are)
• Le pagine di Data, Text e Stack sono portate in memoria dinamicamente
via
i paginazione.
i
i
• U-area (tutte le pagine) e Tabelle delle Pagine sono portate in memoria
dinamicamente via swapping.
• Ogni volta sono attive: la tabella delle Pagine del Kernel (in memoria
residente; entries contigue; mappa Data e Stack del Kernel; le pagine del
Kernel in memoria non residente sono marcate non-swappabili) e quelle
del processo in esecuzione (mappate in entries non necessariamente
contigue della tabella del Kernel;le pagine del processo sono quasi sempre
marcate come swappabili).
43
Strutture Dati (in BSD 4.4)
FIG 1: Kernel address space maps
FIG 2: Generic user process address space maps
43
machine-independent virtual address space
structures that describe the use of a range of addresses
kernel text, initialized data, uninitialized data, and
initially allocated data structures reside in the range
Information machine
dependent/independent
Describe process address space
malloc area
To avoid intermixing of unrelated
allocations within an address range
kernel I/O staging area
network buffer area
Executable file
Text area
Initialized data of the
program that follows the
program text in the file
uninitialized data
stack areas
Paginazione e Swapping
• La memoria principale viene gestita da due demoni:
- Swapper (processo 0) che si occupa di rimuovere processi
dalla memoria/riportarli in memoria da disco;
User-area e Tabelle delle pagine sono portate dinamicamente in
memoria/disco dal processo Swapper.
- Pagedaemon o Demone di Pagina (processo 2) che si occupa
del rimpiazzamento delle pagine;
Le pagine di Text, Data e Stack sono portate dinamicamente in
memoria/disco, una alla volta quando servono (cioè a seguito di
un page fault) /quando vengono rimpiazzate dal processo
Pagedaemon.
Pagedaemon
50
Swapper
PageDaemon
Paginazione e Swapping
• I due
d d
demonii llavorano sulla
ll b
base di alcuni
l
i parametri
t i di sistema:
i t
- Lotsfree: indica il numero minimo di frame per evitare
ll’intervento
intervento del Pagedaemon;
- Minfree: indica il numero minimo di frame per evitare
l’intervento dello Swapper;
- Desfree: numero di frame liberi desiderabile per un buon
funzionamento del sistema;
• La relazione tra i parametri è: Minfree < Desfree < Lotsfree.
51
Paginazione e Swapping
Un processo può richiedere memoria nei seguenti casi:
1. Al momento della creazione tramite fork (allocazione di memoria
per i segmenti
ti Data
D t e Stack);
St k)
2. Chiamata della funzione di sistema malloc (estende il segmento
Data);
3. Lo stack cresce oltre le dimensioni prefissate del segmento Stack;
4. Si accede in scrittura ad una pagina condivisa tra due processi e
gestita il metodo “copy-on-write”;
5. Può essere necessario caricare memoria ad un processo che era
swapped da troppo tempo.
46
Strutture dati del kernel (Paging System)
• Page Tables: per i segmenti Data, Text, U-Area e Stack.
• Disk Block Descriptor: (BSD 4.4) ad ogni page table entry con bit validità 0 è
tabella Una entry descrive la copia su disco
associata una entry di questa tabella.
della pagina virtuale. (BSD 4.3) ...sono associati esplicitamente i rif di swap.
Core
e map
ap ((Frame
a e Data
ata Table):
ab e) u
una
ae
entry
t y desc
descrive
eu
un frame
a e de
della
a memoria
e o a
• Co
fisica. La tabella ha come indici i numeri di frame.
• Swap-use Table: una per ogni dispositivo su cui si trasferiscono i
processi.
Una entry d
descrive
dispositivo
i U
i una pagina
i swappata sull di
ii
associato alla tabella.
47
Numero del page frame
Age
Copy
on
Write
Modify
Reference
Valid
Protection Bit
(a) Entry della tabella delle pagine
N° dispositivo di swap
Numero di blocco del dispositivo
Tipo di memorizzazione
(b) Descrittore del blocco disco
Stato della pgina
Contatore ai
riferimenti
Dispositivo logico
Numero di blocco
(c) Entry della tavola dei dati del frame
Contatore di
riferimenti
Numero di unità
disco/pagina
(d) Entry della Swap-use table
Puntatore pfdata
Entry della Page Table
Numero di page frame
Si riferisce ai frame della memoria reale.
Age
Indica per quanto tempo la pagina è rimasta in memoria senza che il processo facesse riferimento ad essa. La lunghezza e I
contenuti di questo campo dipendono dal processore.
Copy on write
E’ porto a 1 quando più di un processo condivide una pagina. Se uno dei processi scrive nella pagina, deve essere fatta una
copia della pagina per tutti gli altri processi che la condividono. Questo consente di rimandare l’operazione di copiatura
finchè è necessaria ed evitarla quando non è necessaria.
Modify
Indica se la pagina è stata modificata.
Reference
indica se ci sono stati riferimenti alla pagina. Questo bit è posto 0 quando la pagina è caricata per la prima volta in memoria
e può essere periodicamente reimpostato a 0 dall’algoritmo di page replacement.
Valid
Indica la presenza della pagina nella memoria principale.
Protect
Indica se l’operazione di scrittura è consentita.
Descrittore del blocco disco
Numero del dispositivo di Swap
Numero di dispositivo logico del dispositivo di memoria secondaria che contiene la pagina corrispondente. Questo consente
di utilizzare più di un dispositivo per memorizzare pagine trasferite su disco.
Numero del blocco del dispositivo
Locazione del blocco che contiene la pagina sul dispositivo.
Tipo di memorizzazione
La memorizzazione può essere un unità di swap o un file eseguibile. Nell’ultimo caso c’è indicazione sulla necessità di pulire
la memoria virtuale prima di allocarla.
Entry della Frame Data Table
Stato della pagina
Indica se questo frame è disponibile in memoria oppure ha una pagina ad esso associata. In quest’ultimo caso lo stato della
pagina è specificato: sul device di swap, nel file eseguibile o DMA in corso
Contatore si riferimenti
Numero dei processi che fanno riferimento alla pagina.
Dispositivo logico
Disposirivo logico che contiene una copia della pagina.
Numero di blocco
Locazione del blocco che contiene la copia della pagina sul dispositivo.
Puntatore Pfdata
Puntatore agli altri entry della pfdata table su una lista di pagine libere o su una coda hash di pagine.
Entry della Swap-user Table
Contatore ai riferimenti
Numero delle entry della page table che puntano ad una pagina nel dispositivo di swap.
Numero di unità disco/pagina
Identificatore di pagina sull’unità di memoria.
Visione dinamica
• Quando un processo viene lanciato, molte pagine vengono precaricate e
poste
t sulla
ll free
f
list
li t (prepaging);
(
i )
• Quando un processo termina, le sue pagine vengono rimesse sulla free list;
• Il sistema
i t
usa allocazione
ll
i
lib
libera ((quindi
i di anche
h iin celle
ll non consecutive)
ti ) per
gestire la richiesta di pagine da parte di un processo;
kernel), il kernel
• Se la free list scende sotto una certa soglia (parametro del kernel)
si rifiuta di allocare nuove pagine di memoria;
• La free list viene anche utilizzata come memoria cache: le pagine richieste
da un processo che risultano invalide vengono cercate sulla free list, prima
di essere caricate da disco;
• Quando un processo termina
termina, le sue pagine vengono messe sulla free list
list.
49
Algoritmo di Paginazione (1)
• Le pagine vengono allocate dalla lista libera con strategia “copy-on-write”;
• La free list viene mantenuta “piena” entro un certo livello;
• Il demone delle pagine viene lanciato al tempo di boot e si attiva ad intervalli
regolari
l i (ti
(tipicamente
i
t 2
2–4
4 volte
lt all secondo)
d ) o su richiesta
i hi t d
dell kernel;
k
l
• Quando viene risvegliato: Sia NFL il numero di frame liberi,
lotsfree torna inattivo;
- Se NFL ≥ lotsfree,
- Se NFL < lotsfree, inizia a scorrere le pagine cercando di spostare
pagine su disco fino a che non ci sono lotsfree pagine libere;
- La velocità di scansione cresce al diminuire di NFL;
• Il demone utilizza una politica di rimpiazzamento globale;
56
Algoritmo di Paginazione (2)
• Algoritmo di sostituzione delle pagine: variante dell’ algoritmo dell’orologio
(
(con
due
d lancette
l
tt invece
i
che
h una).
)
L’algoritmo usa due puntatori (lancette) per scorrere la lista delle pagine
allocate nella core map.
map
While (NFL < lotsfree)
- la prima lancetta azzera il reference bit R della pagina a cui punta;
- la seconda sceglie la pagina vittima:
if R = 0 (cio`e la pagina non è stata usata nel periodo trascorso
t il passaggio
tra
i d
delle
ll d
due llancette),
tt ) questa
t è lla pagina
i vittima
itti
if M=1, il frame viene salvato su disco;
il frame viene aggiunto alla free-list;
- Si fanno avanzare i due puntatori;
57
Algoritmo di Paginazione (3)
• La
L di
distanza
t
ttra i puntatori
t t i (h
(handspread)
d
d) viene
i
decisa
d i all boot,
b t per liberare
lib
frame abbastanza rapidamente:
- Se le lancette sono vicine: solo le pagine realmente usate
rimarranno in memoria;
- Se le lancette sono distanti 359◦ = algoritmo dell’orologio
((la seconda passa
p
dopo
p un g
giro);
)
• Possibile variante:
- ulteriore parametro maxfree > lotsfree: quando il livello di pagine
scende sotto lotsfree, il pagedaemon libera pagine fino a maxfree.
(Permette di evitare una potenziale instabilità del CLOCK a due
lancette).
lancette)
58
Swapping (1)
• Lo Swapper (o schedulatore di medio termine), lanciato anch’esso al tempo
di boot), decide quale processo deve essere swappato su disco/riportato in
memoria;
i
• Lo Swapper si sveglia ogni 1–2 secondi, e interviene solo se il sistema di
paginazione è sovraccarico:
- il numero di frame liberi è sotto la soglia minima ammissibile minfree;
- il numero medio di frame liberi nell’unità di tempo è minore di desfree.
59
Swapping (2)
Regole di scelta del processo uscente
• Si cerca tra i processi in Asleep, senza considerare quelli in memoria
da meno di 2 secondi;
• Se ce ne sono
sono, si prende q
quello
ello con il valore
alore priorità+tempo di
residenza in memoria più alto (nota: tempo CPU= tempo in memoria);
• Altrimenti, si cerca tra quelli in Ready, con lo stesso criterio;
• Per il processo selezionato:
- i suoi segmenti Data e Stack (non il Text) vengono scaricati sul
device di swap ed i frame vengono aggiunti alla free list;
- nel PCB, viene messo lo stato Swapped e agganciato alla lista
dei processi swappati;
• Si ripete fino a che sufficiente memoria viene liberata.
60
Swapping (3)
Regole di scelta del processo entrante
• cerca nella lista dei PCB dei processi swappati e ready, il processo
swappato da più tempo, ma almeno 2 secondi (per evitare thrashing);
• se lo trova
trova, determina se c’è
c è sufficiente memoria libera per la page
table e la u-area (easy swap) oppure no (hard swap);
• se è un hard swap, libera memoria swappando qualche altro processo;
• carica le page table e la u-area in memoria e mette il processo in
Ready-to-run in memory;
• Si ripete finché non ci sono processi da caricare.
61
Considerazioni
Interazione tra scheduling a breve termine, a medio termine e paginazione:
• minore è la priorità, maggiore è la probabilità che il processo venga
swappato;
• per ogni processo in esecuzione, la paginazione tende a mantenere in
memoria il suo working set;
• quindi
quindi, processi che non sono idle tendono a stare in memoria
memoria, mentre si
tende a swappare solo processi idle da molto tempo;
p
, il sistema massimizza l’utilizzo della memoria e la multiprop
• nel complesso,
grammazione, limitando il thrashing e garantendo l’assenza di starvation
per i processi swappati.
62