Laboratorio di Sistemi Operativi
Docente: Prof. Alfredo Petrosino
Gestione della memoria in Unix:
system calls
Autori:
Calzetta Emilia
Cervone Vincenzo
Programmazione didattica
Classe Quarta I.T.I.
UNITA’ DIDATTICA: LA GESTIONE DELLA MEMORIA IN UNIX:
SYSTEM CALLS
Contenuti in sintesi: Concetti introduttivi (gerarchie di memoria, gestore
della memoria); Modello della memoria in Unix; Paginazione e swapping in
Unix; L’algoritmo Buddy System; L'algoritmo dell'orologio a due lancette;
Memoria condivisa; Sistem calls; Esercizi e prove di laboratorio.
Tempi previsti: 6 ore complessive così suddivise:
2 ore di teoria
3 ore di esercitazioni, laboratorio
1 verifica e valutazione
Modalità di lavoro: Spiegazioni in classe, utilizzo del laboratorio d’
informatica, studio e svolgimento di esercizi a casa, attività di
approfondimento e ricerca.
2
Livelli di Partenza
La rilevazione dei livelli di partenza viene effettuata all’inizio del corso
mediante un colloquio mirante ad individuare per i singoli allievi il
consolidamento della precedente esperienza curriculare, ed eventuali altre
esperienze extra-curriculari nel settore.
LIVELLI MINIMI ACCETTABILI
Utilizzare le risorse di sistema operativo (in particolare Unix)
Conoscere i concetti base, le funzioni e la struttura dei sistemi operativi
Conoscere le diverse tipologie dei sistemi operativi
Conoscere la visione dell'elaborazione a livello macchina
Conoscere il linguaggio C
Verifica
Si svolge in modo continuativo durante il corso sotto forma di dialogo o
sperimentazione. E’ prevista una verifica scritta al termine del corso costituita
da esercizi e prove pratiche sia di gruppo che individuali
3
Strumenti e riferimenti
Strumenti: Testi in adozione, manuali di programmazione, laboratorio di
informatica, materiale didattico vario (appunti on line e cartacei, slide, etc.)
Riferimenti:
W. Stallings, Operating Systems, 4th ed., Prentice-Hall, 2000
A. Silberschatz, P. Galvin, Operating Systems Concepts, 6th ed., John
Wiley & Sons, 2001
A. Tanenbaum, Modern Operating Systems, 2nd ed., Prentice-Hall,
2001
The C Programming Language, Second Edition Brian W. Kernighan,
Dennis M. Ritchie Prentice Hall 1988
System call di Unix e Linux (man page)
4
Introduzione
La memoria è una risorsa fondamentale: ogni processo in esecuzione
occupa una parte della memoria centrale (RAM) in cui risiedono le sue
istruzioni codificate ed i suoi dati.
Memoria illimitata, infinitamente veloce, economica non esiste, si cerca
di superare questi limiti con la GERARCHIA DELLA MEMORIA
Nanosec
p
i
ù
v
e
l
o
c
i
decine ns
50-70 ns
5-15 ms
100 ms
Registri
Cache
Memoria principale
Dischi magnetici
Dischi ottici
La filosofia della gerarchia della memoria consiste nel portare verso il vertice della piramide le
informazioni più utilizzate dalla porzione di programma in esecuzione così che nella maggior
5
parte dei casi il tempo di accesso coincide con quello delle memorie più rapide.
Gestore della memoria
La parte del Sistema Operativo (SO) che si occupa della gestione della memoria
si chiama GESTORE DI MEMORIA
Gestire la memoria significa:
Sapere quali parti della memoria sono in uso e quali libere
allocare e deallocare memoria ai processi che la richiedono
Effettuare lo swapping di processi con il disco
Garantire protezione ai processi impedendo loro di modificare zone di
memoria che non gli appartengono
6
Unix: un po’ di storia (1)
Unix e' nato nel 1969-70, su iniziativa di K. Thompson e D. Ritchie nei
laboratori AT\T (Bell Labs). A parte il nucleo, scritto in assembler, tutto
il resto e' in linguaggio C.
Attualmente Unix e' un trademark della USL (Unix System Labs.) della
Novell ma è prodotto da varie aziende con licenza commerciale nel rispetto
di standard comuni (Open Systems)
Gli standard Open Systems sono insiemi di norme pubbliche che
specificano le regole che il software deve rispettare e differenziano
questi sistemi operativi dai sistemi proprietari le cui regole di
funzionamento invece non sono rese note dal produttore.
Esistono due versioni di Unix:
 BSD
(versione Berkeley System),
 System V
7
Unix: un po’ di storia (2)
Un passo importante e' stato fatto a partire dal 1984, anno in cui il MIT
sviluppa il sistema X-Window System. che fornisce un'interfaccia
grafica all'utente.
Caratteristiche principali di Unix:
 multitasking: nel sistema
contemporaneamente
ci
sono
piu'
processi
(task)
 multiuser: piu' utenti possono usare contemporaneamente un
sistema, in modo protetto
 modularità: possibilità di aggiungere e modificare i programmi di
supporto
 indipendenza dall'hardware
 associazione con X-Window per interfaccia utente grafica
 strumenti per la comunicazione via rete basati sui protocolli TCP/IP
(Transmission Control Protocol/Internet Protocol)
8
Gestione della memoria in Unix
Unix sistema operativo multiprogrammato e multiutente: la memoria e
suddivisa tra più processi e viene offerto un servizio interattivo a più utenti
contemporaneamente.
I processi Unix lavorano su uno spazio di indirizzamento virtuale di 32 bit
Il sistema operativo fornisce ai processi un’area di memoria virtuale ottenuta
da un opportuno spazio riservato nella memoria di massa.
La memoria virtuale appare al processo come se fosse memoria centrale ma
questa apparenza è dovuta a cointinui ‘spostamenti’ fatti dal sistema operativo
tra memoria centrale fisica e blocco di memoria virtuale della memoria di
massa (hard disk).
9
Gestione della memoria in Unix
Il meccanismo della memoria virtuale spiega perché uno dei fattori
principali nelle prestazioni di un computer è la quantità della memoria
centrale.
Infatti con molta memoria centrale gli accessi alla memoria virtuale (hard
disk) sono meno frequenti e quindi le prestazioni in condizioni di
multiprocesso più elevate, mentre con poca memoria centrale anche una
CPU molto veloce sarà continuamente impegnata a commutare da/a memoria
centrale/memoria di massa sprecando gran parte delle sue potenzialità.
10
Gestione della memoria in Unix
Ogni processo UNIX ha uno spazio degli indirizzi formato da tre segmenti: il
testo, i dati e lo stack di sistema.
Il segmento testo (text segment): contiene le istruzioni macchina che
formano il codice eseguibile del programma e può essere condiviso da più
utenti (shared text segments). Il codice eseguibile è read-only
Il segmento dati (data segment): contiene la memoria per le variabili del
programma. E' formato da due parti: i dati inizializzati e quelli non
inizializzati (BSS). La parte inizializzata del segmento dati contiene le
variabili e le costanti di compilazione che hanno bisogno di un valore iniziale
quando il programma parte
Lo stack di sistema (stack): contiene, quando un programma inizia
l'esecuzione, tutte le variabili di ambiente insieme alle linee di comando
digitate per invocare il programma.
I dati non inizializzati si chiamano BSS, da “Block Started by Symbol”
(pseudo istruzione assembler IBM 7090)
11
Gestione della memoria in Unix
Il file eseguibile contiene tutte le variabili inizializzate dopo il testo del
programma. Le variabili non inizializzate (BSS) sono tutte raccolte insieme
dopo quelle inizializzate e permettono di salvare lo spazio nel file
eseguibile
Esempio: Le BSS evitano di memorizzare 4K di memoria pieni di zero nel
file eseguibile.
Spazio logico del processo
Stack
20K
16K
8K
BSS
Dati
Testo
0K
eseguibile 16K
12
Organizzazione della memoria
Processo A
Processo B
 Spazio logico dei processi A e B e memoria fisica
 Condivisione dell’area testo
 Unix supporta spazi separati per istruzioni e dati
13
Paginazione e swapping
In Unix la memoria principale viene gestita da due processi demoni:
 Lo swapper che si occupa di rimuovere processi dalla memoria
 Il demone delle pagine (pagedaemon) che si occupa del rimpiazzamento
delle pagine
I demoni sono processi permanentemente in esecuzione, normalmente
inattivi, ma pronti a "risvegliarsi" e ad eseguire le operazioni richieste nel
caso di eventi particolari (come la richiesta di un utente) oppure di condizioni
prefissate (ad esempio ad intervalli di tempo regolari)
I primi sistemi UNIX fino al 3BSD (1978) erano basati sullo swapping.
Se i processi esistenti sono più di quelli che possono risiedere in memoria
centrale, alcuni di essi vengono trasferiti su disco.
Le versioni 3BSD, 4BSD e System V sono basate principalmente sulla
paginazione e secondariamente sullo swapping
14
Swapping in Unix
Lo swapping di processi tra la memoria ed il disco inizia se non c’è memoria
sufficiente per uno dei seguenti eventi:
1.
una chiamata di sistema FORK ha bisogno di memoria per un processo
figlio;
2. una chiamata di sistema BRK ha bisogno di espandere un segmento di
dati;
3. uno stack diventa troppo grande e supera lo spazio ad esso riservato.
4. per portare in memoria un processo che è stato troppo a lungo sul disco,
per cui bisogna rimuovere un altro processo per predisporre lo spazio
necessario in memoria centrale
15
SWAP OUT
Per scegliere il processo da scaricare, lo swapper prima esamina i processi in
attesa di un evento (Es. I/O) (se ci sono) viene scelto quello con il valore
priorita + tempo di residenza in memoria piu alto.
Un buon candidato è un processo che ha consumato molto tempo di CPU, o uno
che è stato in memoria troppo a lungo.
Se non è disponibile alcun processo bloccato, allora si sceglie un processo in
“ready” basandosi sugli stessi criteri
16
SWAP IN (1)
Ogni 2 secondi, lo swapper esamina l'elenco dei processi sul disco per vedere
se uno di essi è disponibile per essere eseguito; in caso affermativo seleziona
quello che è stato sul disco più a lungo
Uno swap facile (easy swap) si verifica quando si dispone di sufficiente
memoria, per cui non c‘è bisogno di rimuovere dalla memoria alcun processo
per fare posto a quello nuovo
Uno swap difficile (hard swap) richiede che prima venga liberata sufficiente
memoria attraverso uno swap out di uno o più processi e successivamente
viene portato in memoria il processo prescelto.
17
SWAP IN (2)
Questo algoritmo viene ripetuto finché non si verifica una delle seguenti
condizioni:
1. nessun processo su disco è pronto a girare;
2. la memoria è piena di processi appena caricati per cui non c‘è alcuno
spazio libero.
Per prevenire il thrashing (eccessivo movimento tra memoria e disco), nessun
processo viene riportato su disco prima che non abbia trascorso almeno 2
secondi in memoria.
Due liste tengono traccia degli spazi liberi in memoria e sul disco; così,
quando c‘è bisogno di spazio, l'algoritmo visita la lista appropriata e
restituisce il primo spazio sufficientemente grande per poter inserire il
processo in esame, rimuovendo dalla lista degli spazi liberi quello appena
occupato
18
Algoritmo Buddy System
Per allocare memoria in Unix si usa l’algoritmo Buddy System. La memoria è
allocata a blocchi di dimensione pari alla potenza di 2 (fino alla dimensione
massima della memoria)
All’inizio si ha un unico blocco pari alla dimensione massima della memoria
(2n)
Per allocare un area di dimensione D, se 2n-1<D<=2n allora viene allocato
l’intero blocco di dimensione 2n
Altrimenti il blocco viene suddiviso in due parti (buddies) di dimensione 2n-1
ciascuna e si ripete il confronto
Se 2n-2<D<=2n-1 allora il blocco 2n-1 è allocato per intero, altrimenti il blocco
di 2n-1 viene diviso in due blocchi di 2n-2
Si ripete il procedimento fino ad ottenere il più piccolo blocco di dimensione
>=D
I blocchi (buddies) adiacenti della stessa dimensione vengono riuniti per
fusione quando si liberano
19
Algoritmo Buddy System
Allocazione (1)
0
128
256
384
512
640
768
A da 70
A
128
256
512
B da 35
A
B 64
256
512
896
1M
A=70K B=35K C=80K D=60K
20
Algoritmo Buddy System
Allocazione (2)
0
128
384
256
A da 70
A
128
B da 35
A
B 64
256
C da 80
A
B 64
C
Finisce A 128 B 64
D
512
256
C
640
768
896
1M
512
512
128
512
128
512
D da 60
A=70K B=35K C=80K D=60K
21
Algoritmo Buddy System
Fusione (1)
Quando viene liberato un blocco di memoria corrispondente la ricerca dei
possibili "merge" è limitata alla lista dei blocchi liberi della stessa dimensione
0
128
384
256
512
640
768
D da 60
128 B 64
D
C
128
512
Finisce B
128 64 D
C
128
512
Finisce D
128 64 64
C
128
896
1M
512
128 128
256
Non si può compattare perché
non esiste un blocco contiguo da 64 libero
22
Algoritmo Buddy System
Fusione (2)
dopo la fine di D abbiamo la seguente situazione
0
Fine D
Finisce C
128
384
256
128 256
64 64
256
256
512
640
768
C
128
512
128
128
512
256
896
1M
512
1024
Tutta la memoria è stata liberata!
23
L' algoritmo di swap del 4BSD
Swap out: lo swapper controlla se ci sono processi inutilizzati per 20 sec o
più, e quello che è stato inattivo più a lungo viene scaricato.
Swap in: lo swapper controlla l'esistenza su disco di qualche processo in
stato di pronto da portare in memoria.
Ad ogni processo su disco è assegnato un valore che è una funzione del
tempo passato dal momento in cui esso è stato scaricato, della sua
dimensione e del tempo in cui è rimasto inattivo prima di essere scaricato.
Tale funzione è poi pesata per portare in memoria di solito il processo che è
stato fuori più a lungo, a meno che esso non sia troppo grande.
Lo swapper porta in memoria solo la struttura utente e la tabella delle
pagine mentre il testo, i dati e le pagine dello stack vengono caricate solo al
momento in cui sono usate.
24
Paginazione
Un processo non ha bisogno di stare tutto in memoria, per l'esecuzione sono
necessarie solamente la struttura dell'utente e la tabella delle pagine.
le pagine del testo, i dati e i segmenti di stack sono portati dinamicamente in
memoria, uno alla volta, quando vengono richiesti.
La paginazione è implementata da:
Il kernel (processo 0)
Il demone di pagina (page daemon) (processo 1)
Il demone di pagina è attivato periodicamente così se il numero di pagine
libere in memoria è troppo basso, provvede a liberarne qualcuna.
25
In 4 BSD la memoria principale è formata da tre parti: le prime due
contengono il kernel e la mappa di memoria (core map) e non sono mai
paginate su memoria di massa; la parte rimanente viene divisa in pagine
(page frame), ognuna delle quali può contenere un testo, i dati, una pagina di
stack, una pagina della tabella delle pagine o essere in lista libera.
La core map contiene l'informazione sul contenuto delle pagine.
Alla core map è riservata una pagina di 1K e i suoi elementi sono di 16 byte.
26
Le prime due locazioni di un elemento della core map vengono usati solo quando
la pagina è nella lista libera;
le tre locazioni successive servono per trovare la locazione della pagina
memorizzata su disco e vengono usate quando la pagina contiene informazioni.
l'ultimo elemento contiene alcuni flag necessari all'algoritmo di paginazione.
27
L'algoritmo di rimpiazzamento di pagina
L'algoritmo di rimpiazzamento di pagina viene eseguito dal demone di pagina;
questi viene attivato per controllare se il numero di pagine libere corrisponde
al parametro di sistema lotsfree (di solito pari a 1/4 della memoria).
 Se non ci sono abbastanza pagine libere, il demone inizia il
trasferimento dalla memoria sul disco finché il parametro lotsfree non
raggiunge il suo valore giusto.
 Se ci sono più pagine libere di quelle indicate dal parametro lotsfree, il
pagedemon ritorna inattivo.
Il demone di pagina usa una versione modificata dell'algoritmo dell’orologio
usando 2 puntatori (lancette) per scorrere la lista delle pagine allocate nella
core map
28
Algoritmo orologio a due lancette
Sia NFL=numero di frame liberi
Fino a che NFL < lotsfree si eseguono i seguenti passi:
1. la prima lancetta azzera il reference
bit R della pagina a cui punta
2. la seconda sceglie la pagina vittima: se
trova R = 0 (cioe la pagina non e stata
usata nel periodo trascorso tra il
passaggio delle due lancette) il frame
viene aggiunto alla free-list
infine si fanno avanzare i due puntatori.
Ogni pagina nella lista libera mantiene il suo
contenuto, che si può recuperare nel caso sia
riutilizzata.
Se il numero delle pagine libere è ancora al di sotto di lotsfree, lo
swapper inizia a rimuovere uno o più processi dalla memoria affinché
essi non debbano competere più per le pagine.
29
Clock a 2 lancette
R=1
D
R=0
F
R=1
R=0
G
A
B
F
E
M
La prima lancetta
Analizza G
Se R = 1
 mette R=0
avanza lancetta
La seconda lancetta
Analizza F
Se R = 0
 scarica pagina
avanza lancetta
30
La paginazione nel System V
 System V usa l'algoritmo dell' orologio originale ad una lancetta, invece che
quella a due lancette; inoltre invece di mettere nella lista libera una pagina non
usata, essa vi viene inserita solo se non è stata usata per un numero n di passi
consecutivi.
 System V utilizza due variabili min e max al posto della sola variabile
lotsfree: quando il numero delle pagine libere scende al di sotto del valore di
min, il demone delle pagine inizia a liberare più pagine e continua a liberarne
finché non ha raggiunto il valore max.
L'introduzione di min e max assicura che il demone, al momento della sua
attivazione, predisporrà abbastanza pagine in modo da non dover essere
riattivato per una quantità di tempo significativa.
31
Memoria condivisa
La possibilita' di condividere memoria e' stata aggiunta nella versione
System V e poi utilizzata anche nelle altre versioni di Unix.
Il segmento di memoria condivisa è caratterizzato da un identificatore
(detto chiave, key). Quindi se piu' processi vogliono usare lo stesso
segmento di memoria condivisa, questi devono conoscere il valore di key
Se i processi che devono condividere il segmento di memoria sono tutti figli
di uno stesso processo, il padre prima di creare i figli potrà mappare la
memoria condivisa, ed i figli avranno automaticamente in eredità una copia
della chiave di accesso alla memoria condivisa.
32
System Call
Per ottenere l’esecuzione di istruzioni privilegiate, un programma di utente
deve effettuare una System Call (chiamata di sistema):
1.
Invio di un’interruzione software al S.O.
2.
Salvataggio dello stato (PC, registri, bit di modo, etc.) del
programma chiamante e trasferimento del controllo al S.O.
3.
Il S.O. esegue l’operazione richiesta
4.
Al termine dell’operazione, il controllo ritorna al programma utente
Per utilizzare i servizi del sistema operativo, il programmatore dispone di una
serie di funzioni system calls
33
Esempio: La System call read
34
Memoria condivisa: System calls
Ad un segmento di memoria condivisa si accede tramite le system calls:
int shmget (key_t key, int size, int shmflg);
void *shmat (int shmid, void *shmaddr, int shmflg);
int shmdt ( char *shmaddr);
int shmctl ( int shmid, int cmd, struct shmid_ds*buf);
Sono usate per:
Allocazione: un processo richiede al SO di riservare uno spazio di memoria per
scambiare dati con altri processi
 Attach: un processo aggancia un’area di memoria condivisa al proprio spazio di
indirizzi (per accedervi e scambiare dati)
 Detach: il processo rinuncia ad accedere a un’area condivisa
35
System calls shmget e shmat
 shmget permette di creare un
segmento di memoria condiviso e
restituisce l’ identificatore di tale
segmento. Il parametro shmflg, se
posto a zero, assegna capacità di
leggere e scrivere nel segmento di
memoria condivisa
Puntatore all’area (segmento) allocata.
Restituisce null in caso di errore
 shmat restituisce un puntatore
all’area di memoria condivisa, che
potrà essere utilizzato per i
successivi accessi. Se il parametro
shmaddr e' NULL (consigliato),
l’indirizzo viene scelto dal sistema,
altrimenti dall’utente.
36
System calls shmdt e shmctl
 shmdt
scollega l’area di
memoria condivisa puntata da
shmaddr dallo spazio di memoria
indirizzabile dall’utente ma non
rimuove l’area condivisa
 shmctl serve per rimuovere un
segmento di memoria condivisa.
Qualsiasi processo può rimuovere
il segmento di memoria condivisa,
a patto che questi possa scrivere
nel segmento, e non solo quello che
l’ha creato.
37
ESEMPI
//variabile usata per memorizzare l’ID
del segmento condiviso
// allocazione di un segmento avente dimensione 2048 bytes accessibile solo
dall’utente corrente
int shm_id;
shm_id = shmget(100, 2048, IPC_CREAT | IPC_EXCL | 0600);
if (shm_id == -1) {
perror("shmget: ");
exit(1);}
Nell’esempio di seguito il segmento verrà distrutto solo dopo che tutti i
processi lo avranno rilasciato.
struct shmid_ds shm_desc;
if (shmctl(shm_id, IPC_RMID, &shm_desc) == -1) {
perror("main: shmctl: ");
exit(1);}
38
System Calls per la gestione della memoria
System Call
Descrizione
S=brk(addr)
Cambia la dimensione del data
segment
A=mmap(addr, len, prot, flags, fd, offset)
Mappa un area di memoria per un
file
S=unmap(addr, len)
Rimuove un area di memoria
mappata per un file
Quando un processo è in esecuzione il valore del campo brk della tabella
dei processi punta
fine
delindirizzi
segmento
BSS. Modificando questo
 aalla
e addr
sono
di memoria
puntatore il processo
può
liberare
e allocare memoria dinamicamente
 len
è una
lunghezza
La system call brkpuò
essere
usatalaper:
prot
controlla
protezione
 flags
bit varidel puntatore
 trovare il valore
effettivo
 fd è un descrittore di file
 impostare il puntatore ad un nuovo valore
 offset è un offset all’interno di un file
Se si richiede di allocare uno spazio di memoria più grande della
dimensione attualmente disponibile in memoria, tale valore sarà rifiutato.
39
Esempio di file mappato in memoria
#include
#include
#include
#include
#include
#include
#include
<stdio.h>
<stdlib.h>
<unistd.h>
<sys/mman.h>
<sys/types.h>
<sys/stat.h>
<fcntl.h>
int main (void) {
int fd;
char *mem;
int bytes_in_page;
bytes_in_page = getpagesize();
/* numero di byte nella pagina */
fd = open(”nomeFile",O_RDWR);
mem = mmap (0,bytes_in_page,PROT_READ | PROT_WRITE,MAP_SHARED,fd,0);
strcpy(mem,”una stringa");
printf("%s\n", mem);
…..
…...
return 0;
}
40
Esercizi
Esercizio1 (buddy system): Dato un sistema con 1 MB di memoria e il buddy
system come metodo di allocazione, dire quale tra le seguenti richieste sarà
la prima a fallire per mancanza di memoria:
50kB, 150kB, 90kB, 130kB, 70kB, 80kB, 120kB, 180kB, 60kB
Soluzione: La prima richiesta che non può essere soddisfatta è 120kB
0
64
128
256
64KB 128KB
256KB
512
521KB
50KB
150KB
90KB
130KB
70KB
256KB
128KB
80KB
41
Esercizio2 (buddy system): In un sistema con 1MB di memoria gestita
usando l'algoritmo del buddy system, dire cosa succede quando:
a) processo A chiede 50k
h) termina processo E
b) processo B chiede 150k
i) termina processo A
c) processo C chiede 60k
j) processo F chiede 125k
d) processo D chiede 60k
k) processo G chiede 150k
e) processo E chiede 60k
l) termina processo F
f) termina processo D
m)termina processo G
g) termina processo C
n) termina processo B
Soluzione:
a
A
128K
b
256K
512
B
c
C
d
D
e
E
f
g
h
i
j
F
k
G
256K
l
m
n
1M B
42