Sommario
Un thread, o processo leggero, è un flusso di controllo sequenziale di un programma.
La coppia processo+threads realizza la separazione tra concorrenza e protezione.
Nei sistemi Linux, un thread:
Dal punto di vista di un programmatore, un thread può essere visto come una procedura che viene eseguita indipendentemente dal programma principale.
I processi contengono informazioni sulle risorse del programma e lo stato di esecuzione:
I thread possono essere schedulati ed eseguiti indipendente perché possiedono i loro:
Minor overhead per creazione/teminazione e context-switch.
Maggiore efficienza nella comunicazione tra thread.
Multithreading: non solo velocità di esecuzione, ma anche un preciso modello di programmazione.
Sono numerosi i casi di applicazioni che possono essere decomposte in attività che procedono “in parallelo”, condividendo dati e risorse comuni
Ad esempio, in un programma di elaborazioni testi possono essere individuate diverse attività:
… attività concorrenti che operano sugli stessi dati (il testo che viene prodotto).
Per separare un’applicazione in attività di foreground (ad es., risposta immediata agli input degli utenti) e background (ad es., processazione di operazioni complesse).
Per implementare funzioni asincrone con il normale flusso d’esecuzione del programma (ad es., funzioni che gestiscono eventi straordinari o periodici).
Per conferire maggiore modularità ai programmi.
Per aumentare la velocità di esecuzione.
Manager/Workers: un thread, il manager, riceve in input i comandi e assegna i lavori ad altri thread, i workers.
Pipeline: un task è suddiviso in una serie di operazioni più semplici, che possono essere eseguite in serie, e concorrentemente, da diversi thread.
Peer: simile al modello Manager/Workers, ma una volta che il thread principale assegna il lavoro agli altri thread, partecipa attivamente anch’esso nel lavoro.
I thread che eseguono in uno stesso processo condividono le risorse del processo, per cui:
Creazione
Terminazione e Join
Sincronizzazione
Non sono necessari meccanismi espliciti per creare segmenti di memoria condivisa!
Mapping uno ad uno tra ULT e KLT
Ciascun thread contiene:
Generalmente si usa il termine task anziché processo o thread.
La creazione di un thread avviene attraverso la chiamata del sistema clone()
.
clone()
anziché creare una copia del processo chiamante, crea un processo distinto che condivide lo spazio d’indirizzi del processo chiamante.
La fork()
è implementata attraverso la clone()
.
I thread ne linguaggio Java possono essere creati:
I thread nel linguaggio Java sono gestiti dalla macchina virtuale (JVM).
Tecniche per aumentare le prestazioni di un sistema di calcolo
Parallelismo:
Concorrenza: si sfruttano i tempi morti del processore:
Nelle architetture parallele, più thread possono eseguire su processori diversi, ognuno gestito in concorrenza.
Le tecniche di parallelismo e concorrenza sono introdotte al fine di ottenere una “velocizzazione” (speed-up) nell’esecuzione dei programmi.
Speed-up: S = TS / TP
dove:
Analogamente al multitasking, un primo fattore di speed-up è dovuto alla concorrenza nei tempi di attesa:
Nel caso in esempio, l’attesa di un thread non deve precludere l’esecuzione dell’atro thread (occorrono KLT, no ULT)
Speed-up: 2(Tr+Ts+Tg)/(2Tr+Ts+Tg) > 1
dove:
Tr tempo di richiesta, Ts tempo di servizio, Tg tempo di gestione
L’uso indiscriminato dei thread può aumentare l’overhead dovuto allo scheduling e al context-switch:
Inoltre, il tempo di esecuzione concorrente è compromesso dalla presenza di punti di sincronizzazione tra i thread (ad es., accesso in mutua esclusione a risorse condivise).
Quando è vantaggioso utilizzare il multithreading?
Nelle architetture monoprocessore si sfruttano il parallelismo implicito presente nelle istruzioni e i tempi morti del processore.
Il programmatore concepisce il programma come una sequenza di istruzioni, eseguite nell’ordine dalla CPU.
Non è tenuto a sapere come le istruzioni verranno manipolate nella CPU.
E se ciò non fosse abbastanza?
L’unica alternativa è ricorrere a sistemi multi-processore, nella speranza che almeno parte della soluzione del problema possa essere parallelizzata.
Parallelismo esplicito: il programmatore sa dell’esistenza di una architettura parallela, ed è suo compito scrivere una soluzione algoritmica in grado di sfruttare opportunamente questa architettura.
Molti problemi hanno una soluzione che è naturale ottenere con un insieme di programmi paralleli.
Tuttavia, (eccetto che in casi molto molto particolari) lo speed-up che si può ottenere è meno che lineare rispetto al numero di CPU disponibili:
C’è comunque sempre una parte di lavoro che non può essere svolta in parallelo a tutte le altre operazioni.
Consideriamo ad esempio il seguente comando:
gcc main.c function1.c function2.c –o output
Supponiamo che su una macchina monoprocessore ci vogliano:
3 secondi per compilare main.c
2 secondi per compilare function1.c
1 secondo per compilare function2.c
1 secondo per linkare gli oggetti
Se avessimo 3 CPU, i tre sorgenti potrebbero essere compilati in parallelo, e poi linkati assieme usando una delle tre CPU.
Ma l’operazione di linking può essere eseguita solo dopo che tutti e tre i file oggetto sono stati prodotti, ossia dopo 3 sec.
Il tempo necessario per generare output sarà quindi 3+1=4 secondi, per uno speed-up di 7/4 = 1.75, pur avendo usato il triplo dei processori.
Sia P un programma che gira in tempo T su un processore, con f = la frazione di T dovuta a codice sequenziale e (1-f) la frazione di T dovuta a codice parallelizzabile.
Allora, il tempo di esecuzione dovuto alla parte parallelizzabile, passa da (1-f)T a (1-f)T/n se sono disponibili n processori.
Lo speed-up che si ottiene è allora:
S = n solo se f = 0 => assenza di codice sequenziale!
Nella programmazione multithreaded, l’applicazione della legge di Amdahl richiederebbe di portare in conto anche il tempo di esecuzione in concorrenza.
Il parallelismo esplicito è limitato:
Questi costi dipendono ovviamente dal tipo di architettura adottata e dal numero di CPU coinvolte, ma in generale sono molto più elevati che in un sistema monoprocessore.
1. Introduzione ai Sistemi Operativi
5. Scheduling nei sistemi mono-processore
6. Threads, SMP
8. Scheduling Multiprocessore e Real-Time
9. Gestione dei processi nei sistemi operativi Unix/Linux e Window...
10. Introduzione alla Programmazione Concorrente
11. Sincronizzazione nel modello ad ambiente globale
12. Problemi di cooperazione nel modello ad ambiente globale
14. Sincronizzazione nel modello ad ambiente locale
15. Deadlock
16. Programmazione Multithread
18. Memoria Virtuale
20. Il File System
21. Primitive di sincronizzazione nel kernel Linux
22. Esercitazione: System call per la gestione dei processi
23. Esercitazione: Inteprocess Communication e Shared Memory
24. Esercitazione: System Call per la gestione dei semafori in Linu...
25. Esercitazione: Problema dei Produttori e dei Consumatori
26. Posix Threads
P. Ancilotti, M.Boari, A. Ciampolini, G. Lipari, “Sistemi Operativi”, Mc-Graw-Hill (par. 2.10)
W. Stallings, “Operating Systems : Internals and Design Principles (6th Edition)”, Prentice Hall (par. 4.1)