Processi e Thread
Processi e thread in Unix
1
UNIX/Linux
• Molte versioni di UNIX
– trattiamo le caratteristiche più comuni)
• Ci riferiamo allo standard POSIX
– Portable Operating System + I X
– Insieme di SC che devono essere supportate dai
sistemi conformi (IEEE 1003.1)
• Trattiamo a parte le caratteristiche di Linux
che si discostano maggiormente
2
UNIX: struttura generale
Utenti
Interfaccia
delle chiamate
di sistema
Programmi di utilità standard
(shell, editori, compilatori etc.)
Interfaccia
di libreria
Modo
utente
Libreria standard
(Open, close, read, write …)
Sistema operativo Unix
(gestione processi, memoria, file system, I/0..)
Hardware
Modo
kernel
3
Processi in UNIX
• Adottano il modello a processi sequenziali
• Ogni processo nasce con un solo thread
• Descriveremo alcune tipiche SC legate alla
gestione dei processi e all’IPC e poi parleremo
della loro implementazione
4
Creazione e terminazione di processi
• Analizziamo le seguenti SC :
– fork : crea un nuovo processo (figlio/child), copia
esatta del processo invocante (padre/parent)
– waitpid : permette al padre di attendere la
terminazione di un figlio
– exec : permette di specializzare un processo con
un eseguibile
– exit : termina il processo che la esegue
5
Creazione di Processi
• Avviene in due passi fork() + execve()
• x = fork()
– crea una copia esatta del processo invocante
• testo, dati, stack, descrittore dei file aperti
– viene generato un un nuovo pid (PID) per il
processo figlio
– se ha successo, restituisce x=0 nel processo figlio
ed x uguale al PID del figlio nel processo padre
– se fallisce, restituisce x=-1
• es. la tabella dei processi non ha più spazio ...
6
Creazione di processi (2)
• Spazio di indirizzamento di padre e figlio dopo
una fork terminata con successo
copia
232 - 1
0
Stack
232 - 1
Stack
Area vuota
Area vuota
heap
Data
heap
Data
Text
Text
SI padre
0
SI figlio
7
Creazione di processi (2.1)
• Come prosegue l’esecuzione nei processi padre e
figlio
232 - 1
&x
45
232 - 1
Stack
&x
0
Area vuota
heap
Data
0
Stack
Area vuota
PC = istruzione
successiva a fork
Text
SI padre (pid=34)
0
heap
Data
Text
SI figlio (pid = 45)
8
Creazione di Processi (3)
• s = execve(pathexe, argv, envp)
– differenzia un processo rimpiazzando il suo spazio
di indirizzamento con quello dell’eseguibile
passato come parametro (pathexe)
• char * argv[] è un array di stringhe (quelle
passate sulla linea di comando quando abbiamo
invocato làeseguibile)
• char * envp[] è un array di stringhe del tipo
nome = valore
• se execve ha successo non ritorna!!!!!
• s : stato in caso di fallimento (non trova il file
eseguibile, il file pathexe non è un eseguibile etc…)
9
Creazione di processi (4)
• Formato di un file eseguibile
– risultato di compilazione, linking etc ...
Numero che contraddistingue
il file come eseguibile
Magic number
Altre info
Ampiezza area di
memoria occupata dalle variabili
globali NON inizializzate
Ampiezza BSS
Variabili globali
I-Data segment inizializzate
Text segment
Codice del programma
(assemblato)
10
Creazione di processi (5)
– La execve() : (1) usa il contenuto del file eseguibile
per sovrascrivere lo spazio di indirizzamento del
processo che la invoca
Variabili di ambiente (envp)
Agomenti (argv)
FRAME per la funzione main
env
argv
Stack
Area vuota
232 - 1
BSS-segment
Ampiezza BSS
I-Data segment
I-Data segment
Text segment
Text
pathexe
Data
0
11
Creazione di processi (6)
– La execve() : (2) carica in PC l’indirizzo iniziale X
• non può più ritornare ….
env
argv
Stack
Area vuota
Indirizzo della prima istruzione compilata
di main()
X
Ampiezza BSS
I-Data segment
Text segment
pathexe
232 - 1
BSS-segment
I-Data segment
X
Text
0
12
Terminazione di processi (1)
• pid=waitpid(pid,&status,opt)
– attende la terminazione di un processo figlio (pid)
– dopo l’esecuzione di waitpid, status contiene l’esito
della computazione del processo figlio
– status = 0 terminazione normale, != 0 terminazione
in presenza di errore
• exit(status)
– termina il processo e restituisce il valore di status al
padre (nella variabile status restituita da waitpid)
13
Terminazione di processi (2)
• Processi zombie
– processi terminati il cui padre non ha (ancora)
eseguito la waitpid()
– attendono di restituire il codice di terminazione
e svanire
14
Una shell semplificata
int pid, status;
while (TRUE) {
/*ciclo infinito*/
type_prompt();
/* stampa prompt*/
read_comm(com,par); /* legge command line */
pid = fork();
/*duplicazione*/
if (pid < 0) {
printf(“Unable to fork”);
continue;}
if (pid != 0)
waitpid(-1,&status,0); /* codice padre */
else
execve(com,par,0); /*codice figlio*/
}
15
Stati dei processi in UNIX
Idle
Fork
iniziata
Fork
terminata
Runnable
L’evento accade
scheduling
Sleeping
Running
Attesa di
un evento
exit
waitpid
Zombified
16
Meccanismi IPC di Unix (1)
• I sistemi Unix forniscono vari meccanismi di
IPC
• Sono comuni a tutti :
– pipe
– segnali (signals)
• Altri meccanismi forniti
– semafori
– scambio messaggi (con varie caratteristiche)
– regioni di memoria condivisa (shmem)
17
Pipe
• Pipe : file speciali utilizzati per connettere due processi
con un canale unidirezionale di comunicazione
B
A
pipe
• Se B cerca di leggere da una pipe vuota si blocca
• Quando la pipe è piena A viene automaticamente
sospeso
• L’ampiezza della pipe dipende dal sistema
18
Segnali
• Sono ‘interruzioni’ software
– comunicano al processo il verificarsi di una certo
evento
– possono essere inviati solo antenati, discendenti
(gruppo)
– generalmente possono essere ignorati, catturati o
possono terminare il processo (default per molti
segnali)
– per i segnali catturabili si può specificare un signal
handler che viene mandato in esecuzione appena il
segnale viene rilevato
19
Segnali (2)
• Ogni segnale corrisponde a un certo tipo di
evento
• Lo standard POSIX stabilisce un insieme di
segnali riconosciuti in tutti i sistemi conformi
• es :
– SIGFPE : si è verificata una eccezione floating point
(es. ho diviso per 0)
– SIGKILL : il processo viene terinato (non può essere
intercettata)
– SIGALRM : è passato il tempo richiesto
20
Alcuni segnali previsti da POSIX
The signals required by POSIX.
21
Segnali (3)
• I segnali possono essere inviati
– da un processo all’altro
– dall’utente con particolari combinazioni di tasti (al
processo in foregroud)
• Control-C corrisponde a SIGINT
• Control-Z corresponde a SIGSTOP
– dal SO per a comunicare al processo il verificarsi di
particolari eventi (es. SIGFPE, errore floating-point)
22
Segnali (4)
• SD del kernel relative ai segnali
– signal handler array : descrive cosa fare quando
arriva un segnale di un certo tipo
• ignorare, trattare + indirizzo del codice della funzione da
eseguire (handler)
– pending signal bitmap (signal mask): che contiene un
bit per ogni tipo di segnale
• il bit X è a 1 se c’è un segnale pendente di tipo X
– ogni processo ha signal handler array ed una pending
signal bitmap
23
Segnali (5)
• Come si fissa l’azione da compiere quando viene
rilevato un segnale?
– Ci sono azioni predefinite
– s = sigaction(signum,&act,&oldact)
• signum : segnale da trattare
• &act : struttura che definisce che cosa fare quando arriva
un segnale, in particolare contiene il puntatore ad un
funzione di tipo void -> int, che verra invocata
all’arrivo di un segnale di tipo signum. &act viene copiata
nel signal handler array
• &oldact : ritorna il contenuto precedente del signal
handler array (può servire per ritornare al comportamento
precedente)
24
Segnali (6)
• Come ci si accorge della presenza di un segnale ?
– Quando un segnale viene inviato il kernel mette a 1 il
corrispondente bit nella signal bitmap
• più segnali sello stesso tipo in rapida sequenza possono
essere visti come uno solo
– Il kernel controlla la signal bitmap ogni volta che
ritorna da stato kernel a stato utente
• es al ritorno da una SC, o dalla gestione di una interruzione
– Lo stato sleeping è lo stato nel quale un processo
attende l’arrivo di un segnale
• Appena ne arriva uno, viene risvegliato
25
Segnali (7)
• Cosa accade quando il kernel trova un segnale
pendente
– Esegue l’azione richiesta
• ignora, default o esegue sh definito dall’utente
– Se deve essere invocato un signal handler definito
dall’utente:
• Il kernel modifica la user stack inserendo un frame per il
signal handler e lo manda in esecuzione
• Quando il signal handler è terminato si riprende
l’esecuzione interrotta con il frame corretto
26
Segnali (8)
• Come si invia un segnale
– s = kill(pid,sig)
– invia un segnale di tipo sig al processo pid (se
ammesso)
– setta a 1 il corrispondente bit della signal bitmap
27
Segnali (9)
• Altre SC relative ai segnali
– s = pause()
• sospende il processo fino al prossimo segnale
– s = sigprocmask(how, &set, &oldset)
• permette di mascherare alcuni segnali
– resid=alarm(sec)
• dopo sec secondi invia una SIGALRM al processo
• resid tempo rimanente dal precedente settaggio di alarm
28
Stati dei processi in UNIX (2)
Fork
terminata
Idle
Runnable
Fork
iniziata
L’evento accade
scheduling
Sleeping
Running
Segnale
SIGSTOP
(CTRL Z)
Segnale
SIGCONT
Attesa di
un evento
exit
Stopped
waitpid
Zombified
29
Implementazione di processi (1)
• Contesto (context) di un processo
– tutte le informazioni necessarie per descrivere lo stato
di avanzamento di un processo ad un certo istante
• Cosa compone il contesto di un processo P
1. Spazio di indirizzamento utente: testo, dati, stack,
aree condivise (es. mmap)
2. Kernel stack : stack utilizzato durante le chiamate di
sistema relative a P
3. Variabili di ambiente
4. process table e user structure (u area)
30
Implementazione di processi (2)
• Variabili di ambiente :
– è un insieme di stringhe della forma
variabile = valore
– vengono ereditate dal padre, ci sono primitive per
leggerne il valore, modificarle etc …
– tipicamente sono memorizzate nella parte bassa dello
stack utente prima dell’attivazione del processo
31
Implementazione di processi (3)
• Process table : risiede sempre in RAM
– un elemento per ogni processo attivo
• Cosa contiene un elemento :
– parametri per lo scheduling (priorità)
– informazioni sull’area/e di memoria che contiene
testo, dati, stack e user area
– informazioni sui segnali pendenti (signal bitmap)
– stato
– PID, PID del padre
– user e group id (reali ed effettivi)
32
Implementazione di processi (4)
• User structure/area : risiede su disco se il
processo è swapped out
–
–
–
–
–
registri hw
tabella dei descrittori di file
stato della system call corrente
kernel stack
informazioni di accounting
• tempo CPU usato recentemente, etc.
– signal handler array
33
Il comando ls
Passi effettuati durante l’esecuzione del comando ls da
34
parte della shell
Le principali funzioni relative ai
Thread POSIX
• Alcune funzioni POSIX P1003.1c
• Possono essere implementate a livello user o kernel
35
Es. la creazione di un thread ...
err = pthread_create(&tid,
attr,
function,
arg)
– nella variabile tid si restituisce l’identificatore del
nuovo thread
– il nuovo thread inizia l’esecuzione a partire da
function con argomenti arg
– attr segnala gli attributi del nuovo thread (es la
priorità)
36
Implementazione di thread (1)
• Può essere user-level o kernel-level
• Problema : come mantenere la semantica
tradizionale di UNIX?
– fork : tutti i (kernel) thread del padre devono essere
creati nel figlio?
– I/O : cosa accade se due thread agiscono sullo stesso
file in modo incontrollato?
– segnali : devono essere diretti a un thread in
particolare o a tutto il processo?
37
Implementazione di thread (2)
• I thread di Linux
– kernel level
– SC per l’attivazione di un nuovo thread :
pid=clone(function, stack_ptr, sharing_flags, arg)
– function : funzione da cui iniziare l’esecuzione
– stack_ptr : puntatore alla pila privata del thread
– arg : argomenti con cui viene attivata function
– sharing_flags : bitmap di condivisione fra thread
padre e thread figlio
38
I flag per la clone()
• Significato dei bit nella bitmap sharing_flags
39
Scheduling in UNIX
Scheduling a due livelli :
• scheduler a basso livello (low-level): sceglie il
prossimo processo da mandare in esecuzione fra quelli
in RAM
• scheduler ad alto livello (high-level): sposta i processi
fra RAM e disco in modo da dare a tutti la possibilità
di ottenere l’accesso alla CPU
Nel seguito descriveremo lo scheduler a basso livello
40
Lo scheduler di UNIX (1)
Lo scheduling a basso livello è basato su una coda a più
livelli di priorità
41
Lo scheduler di UNIX (2)
• Si esegue il primo processo della prima coda non vuota
per massimo 1 quanto (tipicamente 100ms)
• Scheduling round robin fra processi con la stessa priorità
• Una volta al secondo tutte le priorità vengono
ricalcolate:
priorità = cpu _usage + nice + base
cpu _usage : numero di clock tick per secondo che il processo ha
avuto negli ultimi secondi
nice : valore intero nell’intervallo [-20, +20]
base : valore intero che dipende da cosa sta facendo il processo
• ha il valore della priorità precedente se il processo sta eseguendo
elaborazione normale in user mode
• ha un valore negativo molto basso se sta effettuando I/O da disco o da
terminale
42
Lo scheduler di UNIX (3)
Meccanismo di aging (invecchiamento o decadimento)
usato per il calcolo di cpu _usage :
• Fissiamo un intervallo di decadimento t
• I tick ricevuti mentre il processo P è in esecuzione
vengono accumulati in una variabile temporanea tick
• Ogni t
cpu _usage = cpu _usage / 2 + tick;
tick = 0;
• Il peso dei tick utilizzati descresce col tempo
• La penalizzazione dei processi che hanno utilizzato
molta CPU diminuisce nel tempo
43
Lo scheduler di Linux (1)
• Vengono schedulati i thread, non i processi
• Tre classi di thread : real-time FIFO, real-time Round
Robin, Timesharing
• Ogni thread ha
– una priorità nell’intervallo [0, +40], generalmente all’inizio la
priorità di default è 20
– un quanto (misurato in jiffy = 10ms, sono i tick del clock)
• Lo scheduler calcola la goodness (gdn, lett. bontà) di
ogni thread pronto come
if (class == real-time) gdn = 1000 + priority
if (class == timeshar && quantum > 0) gdn = quantum + priority
if (class == timeshar && quantum == 0) gdn = 0
44
Lo scheduler di Linux (2)
Algoritmo di scheduling :
• Ogni volta viene selezionato il thread con goodness
maggiore
• Ogni volta che arriva un tick il quanto del thread in
esecuzione viene decrementato
• Un thread viene de-schedulato se si verifica una delle
seguenti condizioni
– il quanto diventa 0
– il thread si blocca
– diventa ready un thread con una goodness maggiore
45
Lo scheduler di Linux (3)
Algoritmo di scheduling (contd.):
• Quando tutti i quanti dei thread ready sono andati a 0 , lo
scheduler ricalcola il quanto di ogni thread (anche se
blocked) come segue :
quantum = quantum / 2 + priority
46