Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Domenico Cotroneo » 16.Programmazione Multithread


Dai processi ai thread

Sommario

  • Thread e processi
  • Modelli e primitive di programmazione MT
  • Concorrenza e parallelismo

Introduzione

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:

  • esiste all’interno di un processo e usa le sue risorse;
  • possiede il suo flusso di controllo indipendente (finché il processo padre esiste);
  • può condividere le risorse del processo con altri thread, che eseguono in maniera indipendente o dipendente;

Dal punto di vista di un programmatore, un thread può essere visto come una procedura che viene eseguita indipendentemente dal programma principale.

Processi e Thread

I processi contengono informazioni sulle risorse del programma e lo stato di esecuzione:

  • Process ID, process group ID, user ID, group ID;
  • Ambiente;
  • Directory corrente;
  • Registri (Program Counter, Stack Pointer, …);
  • Area codice del programma (text);
  • Area dati statici;
  • Area Stack;
  • Area Heap;
  • Descrittori dei file aperti;
  • Segnali;
  • IPC (code di messaggi, semafori, memoria condivisa).

Processi e Thread

I thread possono essere schedulati ed eseguiti indipendente perché possiedono i loro:

  • registri (Program Counter, Stack Pointer);
  • proprietà di scheduling;
  • segnali pendenti;
  • dati specifici;

Minor overhead per creazione/teminazione e context-switch.

Maggiore efficienza nella comunicazione tra thread.

Programmazione Multithreading

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à:

  • scrittura sul video;
  • lettura dei dati immessi;
  • la correzione ortografica e grammaticale;
  • il salvataggio periodico su disco.

… attività concorrenti che operano sugli stessi dati (il testo che viene prodotto).

Utilità dei thread

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.

Tipici Modelli di programmazione multithread

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.

Thread e condivisione

I thread che eseguono in uno stesso processo condividono le risorse del processo, per cui:

  • le modifiche fatte da un thread sulle risorse condivise (p. es: un thread chiude un file) saranno viste da tutti gli altri thread;
  • è possibile leggere/scrivere la stessa locazione di memoria (ad es., una variabile globale);
  • … per cui è richiesta una sincronizzazione esplicita tra i thread (attraverso semafori o monitor).

Thread e condivisione


Primitive per il multithreading

Creazione

  • Primitiva per effettuare il lancio (spawn) di un nuovo thread all’interno di un processo.
  • La primitiva accetta come parametro di input la routine che deve essere eseguita nel contesto del thread.

Terminazione e Join

  • Primitive per terminare l’esecuzione del thread e per ricongiungere il thread con il flusso principale di esecuzione.

Sincronizzazione

  • Semafori, monitor, barriere, …

Non sono necessari meccanismi espliciti per creare segmenti di memoria condivisa!

Thread nel sistema Win 2000

Mapping uno ad uno tra ULT e KLT
Ciascun thread contiene:

  • un identificatore di thread (ID);
  • un insieme di registri;
  • una pila d’utente e una pila del nucleo;
  • un’area di memoria privata.

Thread nel sistema Linux (2.6)

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().

Thread nel linguaggio Java

I thread ne linguaggio Java possono essere creati:

  • creando una nuova classe derivata dalla classe Thread;
  • sovrascrivendo il metodo run di quella classe.

I thread nel linguaggio Java sono gestiti dalla macchina virtuale (JVM).

Concorrenza e Parellelismo

Tecniche per aumentare le prestazioni di un sistema di calcolo
Parallelismo:

  • implicito: Istruction Level Parallelism (ILP), si sfrutta il parallelismo intrinseco delle istruzioni (architetture pipelined);
  • esplicito: si usano architetture parallele (sistemi multiprocessore, o n-core).

Concorrenza: si sfruttano i tempi morti del processore:

  • multitasking: capacità di eseguire più processi contemporaneamente;
  • multithreading: possibilità di avere più flussi di controllo (leggeri) nello stesso processo.

Nelle architetture parallele, più thread possono eseguire su processori diversi, ognuno gestito in concorrenza.

Speed-up

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:

  • TS: tempo di esecuzione sequenziale del processo;
  • TP: tempo di esecuzione parallela o concorrente.

Multithreading e speed-up in sistemi monoprocessore

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


Limiti del multithreading

L’uso indiscriminato dei thread può aumentare l’overhead dovuto allo scheduling e al context-switch:

  • più thread implicano più context-switch, lasciando quindi meno tempo utile all’elaborazione;

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?

  • Quando il tempo di esecuzione di ciascun thread è largamente superiore al tempo di context-switch tra i thread.
  • Quando l’esecuzione concorrente non è troppo vincolata dalla presenza di punti di sincronizzazione (codice non parallelizzabile).

Parallelismo esplicito

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.

Speed-up nelle architetture parallele

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:

  • analogamente ai thread, i programmi che girano in parallelo dovranno prima o poi sincronizzarsi per mettere in comune i dati elaborati da ciascuno;
  • sarà necessaria una fase comune di inizializzazione prima di far partire i vari programmi in parallelo.

C’è comunque sempre una parte di lavoro che non può essere svolta in parallelo a tutte le altre operazioni.

Speed-up nelle architetture parallele – esempio

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.

Legge di Amdahl

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=\frac{fT+(1-f)T}{fT+(1-f)T/n}=\frac 1 {f+1/n-f/n}=\frac n {1+(n-1)f}

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.

Limiti del parallelismo esplicito

Il parallelismo esplicito è limitato:

  • dalla quantità di parallelismo presente nei programmi, o almeno della parte che si è in grado di esplicitare e dunque sfruttare;
  • dagli elevati costi delle comunicazioni tra processori e memoria, che possono aumentare enormemente il costo di un cache miss o di una sincronizzazione tra processi che girano su CPU diverse.

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.

I materiali di supporto della lezione

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)

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion