UNIVERSITÀ DI PARMA
DIPARTIMENTO DI SCIENZE MATEMATICHE, FISICHE E INFORMATICHE

Meccanismo a granularita' piu' fine per lo scheduling per le computazioni concorrenti. Il thread rappresenta l'unita' di base per l'utilizzo della CPU e consiste di un program counter un insieme di registri e di uno stack. I thread sono associati a gruppi. Ogni gruppo forma un task in cui i thread associati condividono lo spazio di memoria (codici e dati) e le risorse del sistema operativo (file aperti e segnali).

• Context switch veloce (non c’e scambio di pagetable)
• Comunicazioni facili e veloci (condivisione di memoria)

• Le routine di librerie in ambiente multithreading devono essere rientranti (thread-safe), ovvero non causano problemi di condivisione se 2 thread chiamano contemporaneamente la stessa funzione.

Esistono 2 diverse metodologie di implementazione dei thread:

- Lo scheduler non e' a conoscenza dei thread e vede solo processi - Tramite una libreria (a livello utente) viene realizzato uno "scheduler intraprocess" che suddivide il tempo di CPU assegnato al processo tra i vari thread che lo compongono. - Benefici: rende asincrone le chiamate a syscall bloccanti.

- Il sistema operativo mette a disposizione un insieme di syscall analoghe a quelle che si usano per la gestione dei processi. - In context switching e` piu` oneroso rispetto allo user level multithreading. - Benefici: permette l'esecuzione contemporanea di piu` thread dello stesso task.

Le ultime versioni del kernel forniscono la syscall clone() che viene utilizzata per implementare l'interfaccia utente a livello kernel. Il supporto dei thread a livello kernel rappresenta una delle principali differenze rispetto a Unix. Il thread e’ quindi l’unita’ di scheduling. Un processo tradizionale e’ quindi un thread che non condivide le risorse con altri thread.

La syscall clone() e’ specifica di Linux e quindi non e’ portabile.

 man clone

Per rendere piu’ standard e flessibile l’interfaccia ai Thread esistono diverse librerie. L'interfaccia piu' diffusa e' quella Posix (libreria pthread). Questa interfaccia e’ integrata nella libreria glibc:

rpm –ql glibc | grep thread
nm  /lib64/libpthread.so.0 | grep " pthread"

Principali funzioni delle librearia pthread:

• pthread_create(&thr_name, &thread_attrib,start_routine,arg) #Crea il thread precedentemente definito con pthread_t thr_name; Il secondo parametro contiene gli eventuali attributi (generalmente e’ NULL). Il terzo parametro e’ il nome della start_routine. L’ultimo e’ un puntatore ai dati da passare al thread.

• pthread_exit(&ret_val) # Termina l’esecuzione di un thread, passa un valore di ritorno (ret_val) che il

chiamante puo’ catturare con pthread_join()

• pthread_join(thr_name, &ret_val) # Attende il termine dell`esecuzione di thr_name

Legge (ret_val) il valore di ritorno del thread terminato. Se la funzione termina correttamente il valore di ritorno e` 0

Il mutex viene utilizzato per sincronizzare l’accesso (in mutua esculsione) ad una sezione critica da parte di piu’ thread: il thread prima di entrare nella sezione critica (ad esempio per modificare una struttura dati) fa il lock del mutex associato, dopo la modifica fa l’unlock.

• pthread_mutex_init(&mutex_name, mutex_attrib) # Crea il mutex preced. definito con pthread_mutex_t mutex_name;

Se si accettano gli attributi di default si utilizza NULL.

• pthread_mutex_lock(&mutex_name) #Blocca mutex_name. Se il mutex e’ gia in lock il thead viene sospeso in attesa dell’unloock.

• pthread_mutex_trylock(&mutex_name) # Prova a mettere in lock mutex_name senza bloccarsi. Ritorna 0 se e’ riuscito, altrimenti ritorna EBUSY

• pthread_mutex_unlock(&mutex_name) # Sblocca mutex_name

• pthread_mutex_destroy(&mutex_name) # Elimina mutex_name

La variabile condizione e’ uno strumento di sincronizzazione che consente ai thread di sospendere la propria esecuzione in attesa di un condizione logica. Ad ogni variabile condizione si associa una coda di attesa.

• pthread_cond_wait(cond_var, var_mutex) # Il thread viene sospeso nella coda “cond_var”, e “var_mutex” viene liberato. Al risveglio “var_mutex” verra’ messo nuovamente in lock

• pthread_cond_signal(cond_var) # Se ci sono thread sospesi nella coda “cond_var” viene risvegliato il primo, altrimenti non ha nessun effetto.

#define MAX 100    // numero massimo di utenti (thread) della risorsa
int N=0;           // numero corrente di utenti della risorsa
pthread_cond_t C;  // variabile condizione
pthread_mutex_t M; // mutex
process()
{
pthread_mutex_lock(&M);               // fase di entrata
If (N==MAX) pthread_cond_wait(&C,&M); // test and sleep
N++;                                  // aggiorna numero N
pthread_mutex_unlock(&M);
 
//Accesso alla risorsa
 
pthread_mutex_lock(&M);  // fase di uscita
N--;                     // aggiorna numero N
pthread_cond_signal(&C); // sveglia thr in coda
pthread_mutex_unlock(&M);
}

http://pubs.opengroup.org/onlinepubs/007908799/xsh/pthread.h.html

http://www.unix.org/version2/whatsnew/threadsref.html

https://computing.llnl.gov/tutorials/pthreads/

Test dei thread: threadtest.c

Programma sorgente: pi_thr.c

Script di sottomissione: thread.bash

Comando di sottomissione: qsub -q didattica -l nodes=1:ppn=8 thread.bash

Se T₁ è il tempo di esecuzione dell'algoritmo sequenziale e T_P è il tempo dell'algoritmo parallelo con P processi, misuriamo il rendimento della parallelizzazione come: Speedup= T₁/ T_P oppure Efficienza= T₁/ (T_P*P) = SpeedUp/P

Idealmente Speedup coincide con P, mentre l'Efficenza è pari a 1.

Questo andamento non e' realistico per 2 motivi:

1. T₁ non sempre è completamente parallelizzabile: T₁=T_par + T_nonpar. Se QP è la quota parallelizzabile (QP=T_par/T₁) e QNP quella Non Paralellizzabile (QNP=T_nonpar/T₁), la legge di Amdahl fissa un massimo allo Speedup: SpeedupMax = 1/(QNP+QP/P)
2. T_P dipende anche da altri tempi T_P=T_comp+T_comm+T_idle

• Tempo di Computazione
  • Se la replica della computazione e' contenuta T_comp tende a T₁/P
• Tempo di comunicazione
• Tempo di Idle
  • Idle per mancanza di computazione o mancanza di dati

Generare il plot dell'isoefficenza in funzione de numero di thread (da 1 a 16) del programma pi_thr.

Comandi utili:

 echo $EXE $ARGS  1>&2
 eval $EXE $ARGS |  grep -v "#"  | awk {'print $4'}