UNIVERSITÀ DEGLI STUDI DI PARMA
Dipartimento di Matematica e Informatica
Corso di Laurea in Informatica
Un caso di studio
sulla Thread Safety:
la Parma Polyhedra Library
Candidato: Maxim Gaina
Relatore: Prof. Enea Zaffanella
Anno Accademico 2013/2014
Indice
Introduzione
3
1 Thread Safety
1.1 Codice Thread Unsafe . . . . . . . . . . . . . . .
1.1.1 Tabella dei simboli . . . . . . . . . . . . .
1.2 Strategie per scrivere codice Thread Safe . . . . .
1.2.1 Programmazione funzionale . . . . . . . .
1.2.2 Conservazione stato nel thread chiamante
1.2.3 Thread Local Storage . . . . . . . . . . . .
1.2.4 Mantenere istanze diverse di una libreria .
1.2.5 Stati Condivisi . . . . . . . . . . . . . . .
1.2.6 Strategie adottate nel caso della PPL . . .
2 L’ambiente di sviluppo
2.1 Piattaforma . . . . . . . . . . . .
2.1.1 Configurazione elaboratore
2.2 Configurazione dell’ambiente . . .
2.3 Debug . . . . . . . . . . . . . . .
2.4 Altri strumenti . . . . . . . . . .
2.4.1 GNU nm . . . . . . . . . .
2.4.2 GNU grep . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 PPL e Thread Local Storage
3.1 Conditional Thread Safety . . . . . . . . . . . . . . . . .
3.1.1 Standard Template Library C++ e variabili const
3.1.2 PPL e variabili const . . . . . . . . . . . . . . . .
3.2 Thread Local Storage . . . . . . . . . . . . . . . . . . . .
3.2.1 Alternative allo standard C++: TLS in GCC . .
3.2.2 TLS in C++11 . . . . . . . . . . . . . . . . . . .
3.3 Ricerca di codice thread-unsafe . . . . . . . . . . . . . .
3.3.1 Ricerca testuale . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6
6
8
10
10
11
11
12
13
13
.
.
.
.
.
.
.
15
15
16
16
17
18
18
19
.
.
.
.
.
.
.
.
20
20
20
21
22
22
23
25
26
INDICE
3.4
3.5
3.6
3.7
2
3.3.2 Ricerca sulla tabella dei simboli
Modifiche TLS . . . . . . . . . . . . .
3.4.1 Dichiarazioni PPL_TLS . . . .
Inizializzazione . . . . . . . . . . . . .
Funzione wrapper . . . . . . . . . . . .
Interfaccia C . . . . . . . . . . . . . . .
3.7.1 Inizializzazione . . . . . . . . .
4 Testing
4.1 ppl_lcdd . . . . . . . . . . . .
4.1.1 Modifiche a ppl_lcdd .
4.1.2 Prova pratica . . . . .
4.2 ppl_lpsol . . . . . . . . . . .
4.2.1 Modifiche a ppl_lpsol
4.2.2 Prova pratica . . . . .
Bibliografia
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
27
28
28
30
31
33
34
.
.
.
.
.
.
36
36
37
40
42
43
45
50
Introduzione
Un thread di esecuzione è un singolo flusso di controllo in un programma, a
partire dall’invocazione iniziale di una funzione e includendo ricorsivamente
ogni funzione successivamente invocata. In un processo, che è il programma
in esecuzione, ogni thread può accedere ad un oggetto o funzione ad esso
appartenente. L’esecuzione di un programma consiste nell’esecuzione di tutti
i suoi thread.
Per single threading si intende l’esecuzione di un processo formato da un
unico thread, per cui in ogni momento è in esecuzione una sola istruzione del
programma.
Per multi threading si intende un metodo di programmazione ed esecuzione che permette l’esistenza di più thread nello stesso contesto, che riguardano
un processo. In altre parole è l’esecuzione concorrente di diversi thread, dove questi ultimi condividono risorse come la memoria, il codice eseguibile, i
descrittori dei file e le periferiche in uso.
L’insieme degli elementi appena elencati formano lo stato del processo.
Parma Polyhedra Library
La Parma Polyhedra Library (PPL, [1]) fornisce astrazioni numeriche indirizzate soprattutto alle applicazioni nel campo dell’analisi e verifica di sistemi
complessi. Queste astrazioni includono:
• poliedri convessi, definiti come l’intersezione di un numero finito di
semispazi (aperti o chiusi), ciascuno descritto da una disuguaglianza
lineare (stretta o non stretta) con coefficienti razionali;
• alcune classi speciali di poliedri che hanno lo scopo di offrire un compromesso tra complessità e precisione;
• grid (griglie) che rappresentano punti regolarmente distanziati che soddisfano una serie di relazioni di congruenza lineari.
Introduzione
4
La libreria supporta anche sottoinsiemi finiti di poliedri e prodotti cartesiani tra poliedri (di qualsiasi tipo) e grid, un risolutore di problemi di programmazione lineare a interi misti tramite una versione ad aritmetica esatta
dell’algoritmo del simplesso, un risolutore per la programmazione lineare parametrica, e primitive per l’analisi di terminazione via sintesi automatica di
funzioni lineari di ranking.
PPL e Multithreading
Per iniziare è bene distinguere due diversi obiettivi: quello di scrivere librerie multi-thread e quello di scrivere librerie che possono essere chiamate da
programmi multi-thread, garantendo la correttezza.
È possibile creare una libreria che è multi-thread internamente, cioè alla
ricezione di una chiamata essa suddivide il lavoro su diversi thread per ottenere un miglioramento prestazionale (vedere Figura 1). Alternativamente,
Figura 1: Libreria che genera internamente dei thread
si può volere una libreria che si comporta in maniera corretta se chiamata
da un programma multithread. Quando una libreria possiede questa seconda
proprietà, si dice che essa è Thread Safe (vedere Figura 2). Altrimenti, si
dirà che la libreria è Thread Unsafe.
Introduzione
5
Figura 2: Libreria thread-safe
Inizialmente la PPL non aveva nessuna delle proprietà sopra elencate: era
una libreria single-thread e thread-unsafe. Infatti, lo scopo di questo lavoro è
rendere la PPL thread-safe e non verrà presa in considerazione la possibilità
(seppure interessante) di aumentare le prestazioni della libreria facendole
generare thread internamente. Ci si concentra appunto sulla sua correttezza
e robustezza nel caso l’utente volesse utilizzarla in un applicativo a thread
multipli. Una libreria, ovviamente, può contemporaneamente essere threadsafe e generare thread internamente.
Capitolo 1
Thread Safety
Come già accennato, ogni thread viene eseguito indipendentemente dagli altri
e ognuno esegue diverse sequenze di istruzioni. In ogni caso tutti i thread
condividono lo stesso spazio degli indirizzi, e possono accedere alle stesse
istanze di certe categorie di dati. Infatti nella programmazione multi-thread
le variabili globali rimangono tali, puntatori e riferimenti ad oggetti possono
essere condivisi fra thread.
In questo capitolo si parlerà degli elementi più sensibili dal punto di vista
della thread-safety, di come individiarli e delle possibili soluzioni.
1.1
Codice Thread Unsafe
Verranno mostrati in maniera preliminare le tipologie di variabili che rendono
thread-unsafe una porzione di codice. Come è stato già detto i thread condividono le risorse del proecesso, quindi bisogna vedere come è strutturato
quest’ultimo per individuarne i punti critici. Trattandosi di una libreria dedicata a calcoli matematici è possibile escludere ragionamenti su risorse che
non siano la memoria di un processo: sarà l’utente a preoccuparsi di eventuali condivisione degli stessi file descriptor, socket e così via. Sarà invece
fondamentale la gestione della memoria. Nell’architettura di un processo 1.1,
la memoria assegnatagli è generalmente composta dalle seguenti aree:
• stack ;
• heap;
• area per allocazione statica dei dati, cioè segmento dei dati;
• segmento del codice del programma;
1.1 Codice Thread Unsafe
7
Stack L’area dello stack non presenta momenti critici in relazione all’obiettivo posto, dal momento che ogni thread ne possiede uno ed è destinato
a contenere le variabili locali, che contano esclusivamente nello stack frame
in cui si trovano. Questa sicurezza però potrebbe essere compromessa se si
prende l’indirizzo di un oggetto sullo stack e lo si passa ad un altro thread:
tali situazioni vanno gestite con cura, possono essere causati dei data race e
puntatori ad aree deallocate (se il thread a cui apparteneva tale stack non
c’è più).
Heap L’heap è l’area assegnata al processo per rispondere alle esigenze
di allocazione dinamica della memoria. Essa è condivisa da tutti i thread
presenti nel processo e a prima vista potrebbe essere un problema per la
thread-safety. Lo standard C++11 (come anche quello precedente) offre le
new expression [8, New, Sezione 5.3.4]. Esempio di new expression:
1 Object * object = new Object ( args ...) ;
2
3 int * array1 = new int [5] {1 , 2 , 3 , 4 , 5};
Una volta chiamata, una new expression ottiene spazio per l’oggetto chiamando l’operator new, se il tipo da allocare è un array invoca l’operator
new[] [8, Dynamic memory management, Sezione 18.6]. Dopo di che la new
expression invoca il costruttore del relativo oggetto inizializzandolo nella locazione appena ottenuta. Gli elementi sui cui porre attenzione ora sono due:
operator new e costruttori. Per quanto riguarda l’operator new, lo standard promette che, in caso di chiamate concorrenti, esso allocherà una porzione di memoria alla volta, senza quindi creare problemi [8, Data races,
Sezione 18.6.1.4]. La new expression potrebbe invocare più costruttori: quello dell’oggetto per il quale è stata chiamata, costruttori di sue classi base
e costruttori di suoi membri. Tutti loro devono essere thread-safe per far sì
che lo sia l’intera new expression. Il ragionamento è analogo per le delete
expression [8, Delete, Sezione 5.3.5] e relativi operator delete, operator
delete[] e distruttori coinvolti. Anche qui c’è il rischio che un thread che
ha ottenuto un indirizzo tramite la new expression lo renda disponibile ad
altri thread; quindi è necessario evitare data race e puntatori non validi.
Allocazione statica dei dati Il segmento dei dati è usato per contenere
le variabili globali e static inizializzate già a tempo di compilazione. Il
segmento può essere ulteriormente suddiviso in area per sola lettura o per
lettura e scrittura. Mentre le variabili di sola lettura non presentano alcun
pericolo, le altre fanno parte dello stato condiviso del processo modificabile.
1.1 Codice Thread Unsafe
1
2
3
4
5
6
7
8
9
10
11 }
8
// Costante globale ( nessun pericolo )
const int a = 1;
// Variabile globale in area dati
char b = ’B ’;
void foo () {
// Variabile static in area dati
static int c = 2;
return ;
L’area .bss che solitamente fa parte del segmento dati, contiene le variabili
non inizializzate. Essa contiene tutte le variabili static e globali che sono
state inizializzate a valore nullo o non hanno nessuna inizializzazione esplicita
nel codice sorgente.
1
2
3
4
5
6
7
8
9
10
11
12
13
// Variabile globale costante ( nessun pericolo )
const int a ;
// Variabili globali in area . bss
extern char b ;
double c = 0;
void foo () {
// Variabile static in area . bss
static int d ;
return ;
}
Quindi si è visto che gli oggetti critici per la thread-safety sono costruttori
e distruttori, variabili allocate staticamente e le variabili allocate su stack e
heap soggette a condvisione. La responsabilità per la condivisione di variabili
allocate su stack e heap è nelle mani dell’utente. Nel capitolo a venire tutti
gli aspetti critici verranno trattati separatamente fornendo delle soluzioni
adeguate.
1.1.1
Tabella dei simboli
La tabella dei simboli è una struttura dati usata da compilatori e interpreti,
dove ogni identificatore nel codice sorgente viene associato alle informazioni
1.1 Codice Thread Unsafe
9
Figura 1.1: Esempio di astrazione dell’architettura di Processo e Thread
relative a dove è stato dichiarato e dove appare, il suo tipo e la porzione del
programma in cui tale identificatore è valido. Attraverso l’uso della tabella dei
simboli è possibile, infatti, risolvere correttamente tutti i riferimenti ai nomi
introdotti dal programmatore, risalendo così all’opportuno oggetto denotato.
Senza cominciare ad analizzare le scelte fatte da ogni singolo compilatore, in
genere ogni linguaggio che supporta scope statico, uso di funzioni, procedure
e diversi tipi di passaggio dei parametri, fa generare una tabella dei simboli
che deve fornire:
• per ogni nome la categoria, cioè variabile, parametro, funzione o procedura;
1.2 Strategie per scrivere codice Thread Safe
10
• per ogni variabile il suo tipo, l’offset nel Record di Attivazione del blocco
in cui è definita;
• per ogni parametro il suo tipo, la modalità di passaggio e l’offset;
• per ogni funzione o procedura l’indirizzo della locazione di memoria
nella zona codice alla quale inizia la sua traduzione.
In presenza di riferimenti a nomi non appartenenti all’ambiente locale di
un blocco, sarà necessario cercare il nome nell’ambiente locale dei blocchi in
cui il blocco attivo in un determinato momento risulta annidato. Al fine di
implementare correttamente lo scope statico e dinamico è necessario, quindi,
conoscere quanti livelli di annidamento ci sono tra il blocco attivo e quello
che definisce il nome utilizzato. Questa informazione può essere calcolata staticamente (e quindi opportunamente memorizzata nella tabella dei simboli)
in regime di scope statico.
La tabella dei simboli risulterà particolarmente importante e la si vedrà
nella Sezione 3.3.2.
1.2
Strategie per scrivere codice Thread Safe
Prima di tutto è bene conoscere alcuni approcci da seguire per arrivare ad
avere una libreria thread-safe. Si vedrà di seguito quali di questi approcci si
riveleranno utili per la PPL.
1.2.1
Programmazione funzionale
Si tratta di un paradigma di programmazione in cui il flusso di esecuzione del
programma assume la forma di una serie di valutazioni di funzioni. Il punto
di forza principale di questo paradigma è la mancanza di effetti collaterali
delle funzioni, il che comporta una più facile verifica della correttezza e della
mancanza di bug del programma e la possibilità di una maggiore ottimizzazione dello stesso. Un uso particolare del paradigma, per l’ottimizzazione dei
programmi, è quello di trasformare gli stessi per utilizzarli nella programmazione parallela. I problemi che sorgono quando si costruisce una libreria
thread-safe generalmente derivano dall’uso di stati condivisi tra le chiamate.
Una scelta è quella di eliminare semplicemente qualsiasi stato memorizzato,
utilizzando uno stile di programmazione funzionale.
Tuttavia la programmazione funzionale è una scelta opportuna se si scrive
una libreria da zero, e non è il caso della PPL. Quest’ultima contiene codice
scritto anche non recentemente, e in funzione soprattutto dell’efficienza: sono
1.2 Strategie per scrivere codice Thread Safe
11
presenti un numero non trascurabile di variabili globali (e anche variabili
locali allocate staticamente).
1.2.2
Conservazione stato nel thread chiamante
In questo modello, lo stato delle variabili viene mantenuto dal chiamante.
L’API (Application Programming Interface) deve fornire un modo alla libreria per accedere allo stato, in genere utilizzando un puntatore passato ad
ogni chiamata alla libreria. Così facendo ogni chiamante mantiene uno stato
completamente isolato da altri thread ed è un approccio comodo quando si
prevedono scambi di flussi di controllo fra diversi thread (Figura 1.2).
Figura 1.2: Conservazione stato nel chiamante
Il principale svantaggio è che l’API in questione va modificata, richiedendo modifiche alle applicazioni. Prendere questa strada significa complicare
parecchio la situazione, nel caso della PPL.
1.2.3
Thread Local Storage
Gli stati delle variabili si possono salvare nell’ambiente locale dei thread.
Da qui nascono le variabili Thread Local, esse permettono di avere istanze
separate dello stesso oggetto per ogni thread del programma. Il punto di
1.2 Strategie per scrivere codice Thread Safe
12
forza di questo approccio è che non richiede la modifica dell’interfaccia della
libreria (Figura 1.3).
Figura 1.3: Thread Local Storage
Si potrebbe obiettare che il metodo Thread Local Storage (TLS), in alcuni
casi, trasformi in difetto il suo più grande pregio: quello di isolare completamente i thread gli uni dagli altri. Questo può essere un problema quando
un applicativo prevede di passare flussi di esecuzione fra thread. Si vedrà
comunque che tale problema è aggirabile e, siccome il meccanismo TLS sembra interessante e complica di meno l’obiettivo posto, verrà scelto e discusso
meglio più in avanti (si veda nella Sezione 3.2).
1.2.4
Mantenere istanze diverse di una libreria
Durante l’esecuzione, è possibile caricare in memoria copie separate della
stessa libreria che può essere Thread Unsafe, quindi con un’istanza unica
per ogni thread chiamante. Il vantaggio di questa scelta sta nel fatto che il
programmatore può caricare in memoria tante copie della stessa libreria (non
thread-safe) quanti sono i thread di cui ha bisogno, senza per questo dover
conoscere la sua implementazione (Figura 1.4). Non lo si può fare facilmente
su tutti i sistemi operativi, dato che alcuni di loro seguono la politica delle
librerie condivise, ed è senza dubbio una soluzione esigente dal punto di vista
delle risorse.
1.2 Strategie per scrivere codice Thread Safe
13
Figura 1.4: Istanze diverse di una Libreria Thread Unsafe
È inoportuno pensare a una strada del genere, dato che si sposa poco con
l’obiettivo di rilasciare una versione thread-safe della PPL, semplificando il
lavoro degli utenti.
1.2.5
Stati Condivisi
Si vedrà più in avanti che, in un processo, non sempre si ha la necessità
di isolare una variabile a livello di thread. Talvolta questi ultimi devono
condividere lo stato di un oggetto, sarà compito della libreria mantenerlo in
uno stato ben definito e sincronizzare le letture e gli accessi, se ce ne fosse
bisogno (Figura 1.5).
1.2.6
Strategie adottate nel caso della PPL
Si noti che è possibile mescolare più di una tra le metodologie discusse. In
questo caso particolare, l’attenzione cadrà sulle variabili TLS e sugli stati
delle variabili condivisi. Il meccanismo TLS verrà ampiamente discusso nella
Sezione 3.2. Non è possibile sfruttare i principi della programmazione funzionale in quanto la PPL va modificata e non scritta da zero. La PPL è stata già
implementata secondo principi che non rispettano i criteri della programmazione funzionale. Non è nemmeno possibile la conservazione dello stato nel
1.2 Strategie per scrivere codice Thread Safe
14
Figura 1.5: Stati Condivisi
thread chiamante, dato che andrebbe modificata l’interfaccia della libreria. A
sua volta questo implicherebbe dover modificare tutti i programmi già scritti
che usano la PPL. Anche mantenere istanze diverse della libreria può essere
utile in alcuni casi ma non fa al caso della PPL.
Capitolo 2
L’ambiente di sviluppo
Prima di apporofondire il lavoro svolto, in questo capitolo si vedrà la descrizione degli strumenti più rilevanti che sono stati usati. Tutti i dettagli
degli strumenti usati verranno presentati qui; il come sono stati impiegati in
funzione dell’obiettivo posto lo si vedrà in un secondo momento.
2.1
Piattaforma
La PPL è scritta in C++ standard, con l’intento di essere portabile. Sono presenti interfacce in altri linguaggi di programmazione quali C, Java, OCaml e
Prolog.
Per apportare modifiche interne alla PPL è necessario un supporto alla programmazione multi-thread che non comprometta la portabilità della libreria.
A tale scopo lo sviluppo punterà sullo standard C++11, talvolta indicato con
C++0x. Esso infatti è il primo a introdurre il supporto per la programmazione
multi-thread, e, fra gli altri, aggiunge i seguenti elementi:
• libreria per il supporto di thread di esecuzione multipli, e per l’interazione fra loro;
• miglioramento per il modello di accesso sequenziale alla memoria, che
permette la coesistenza di più thread;
• oggetti e operazioni atomiche;
• Thread Local Storage (TLS).
Il meccanismo TLS si rivelerà particolarmente importante, è stato introdotto
nella sezione 1.2.3 e verranno approfonditi i suoi aspetti nella sezione 3.2.
Ci si potrebbe chiedere per esempio quali fra le implementazioni pthread e
2.2 Configurazione dell’ambiente
16
std::thread sia più efficiente. Tuttavia, come già discusso precedentemente,
le modifiche sulla libreria non prevedono l’utilizzo interno di thread attivi,
e, per questo motivo, questo lavoro non ha interesse nello stabilire quale
supporto alla programmazione multi-thread sia più efficiente: sarà l’utente a
seguire le sue preferenze a riguardo, nelle proprie applicazioni.
Verranno analizzate brevemente le alternative all’uso del supporto al multithreading fornito dallo standard C++11. L’utilizzo della libreria Boost [2]
avrebbe comportato alla dipendenza da terzi. L’uso diretto dello standard
POSIX [3] per l’utilizzo dei thread avrebbe portato la necessità di considerare
il modello TLS implementato da GNU Compiler Collection (GCC, [4]), che
porta delle limitazioni. Esso verrà visto nella sezione 3.2.1.
Allo stato attuale esiste già lo standard C++14 che è un’estensione di C++11,
ed esiste già il nome informale C++17 per indicare il prossimo rilascio. Tuttavia C++11 è l’ultima versione completamente supportata da un numero più
ampio di compilatori [10] quali GCC, Clang++ [5] e Intel C++ [6].
2.1.1
Configurazione elaboratore
Hardware Il lavoro è stato svolto su una macchina che supporta 8 thread, resi
possibili da 4 core fisici e altrettanti core logici. È assente qualsiasi
supporto al calcolo parallelo tramite scheda grafica, cioè il così detto
General Purpose Graphic Processing Unit (GPGPU), oggi ampiamente usato. Quindi nel lavoro svolto è stato impiegato esclusivamente il
processore centrale.
SO e Kernel Il sistema operativo alla base è la distribuzione Linux Fedora 21, 64
bit. La versione del kernel è 3.18.7-200.fc21.x86_64.
gcc Versione del compilatore gcc 4.9.2 20150212 (Red Hat 4.9.2-6)
clang Versione del compilatore clang 3.5.0 x86_64-redhat-linux-gnu,
Thread model: posix
2.2
Configurazione dell’ambiente
Facendo uso della nota piattaforma di versionamento dei sorgenti git [11],
è stato creato un branch separato da quello ufficiale della libreria PPL. Tramite alcune passaggi meccanici sono stati scaricati i file sorgenti della PPL. Lo
script di configurazione è stato modificato per aggiungere l’opzione
–enable-thread-safe, mediante il quale si può abilitare il supporto alla
thread-safety. È stato usato il comando autoreconf per aggiornare gli script
2.3 Debug
17
di configurazione. In una directory diversa da quella delle sorgenti, sono state
create due cartelle dedicate alla generazione di eseguibili e ausiliari tramite
il comando make. La prima directory, build, viene usata per compilare la
libreria PPL in modalità produzione. Nel caso della cartella debug, la PPL viene compilata in funzione della ricerca di anomalie e bug. In questa modalità
però, la libreria stessa e i programmi demo presenti nella PPL (per esempio
ppl_lcdd), effettuano numerosi calcoli non necessari per controllare le consistenza interna della libreria e quindi possono risultare estremamente lenti
rispetto alla versione ottimizzata. Ci si sposta in build e si lancia il seguente
comando:
/ppl/configure --enable-interfaces=c,c++ --enable-thread-safe
Dopo di che tocca alla directory debug:
/ppl/configure --enable-interfaces=c,c++ --enable-thread-safe
--disable-optimization --enable-assertions
Il comando configure ha diverse opzioni. Tramite –enable-interfaces
si comunica quali interfacce verso altri linguaggi abilitare. Oltre all’interfaccia c e c++ abilitata sopra, si può abilitare l’interfaccia della PPL verso java,
ocaml e prolog. Nel caso della directory debug è stata disabilitata l’ottimizzazione e sono state abilitate le asserzioni. L’opzione –enable-thread-safe
è stata aggiunta in seguito a questo stesso lavoro per far scegliere all’utente se
vuole usufruire della PPL in modalità di programmazione parallela. Se questa
opzione è assente, verrà compilata la versione della PPL thread-unsafe, ovvero
quella iniziale. Si vedrà più avanti come è stato realizzato tale meccanismo,
nella Sezione 3.4.
2.3
Debug
Durante la fase di stesura di codice aggiuntivo o della modifica di quello
esistente si sono anche verificati casi in cui il codice non funzionava come
desiderato, portando a fallimenti a tempo di esecuzione o risultati inattesi.
Per analizzare le situazioni anomale e risalire alla loro causa sono stati usati,
in questo lavoro di tirocinio, diversi tool per il debugging del codice. In particolare è stato utilizzato il debugger gdb ed i checker messi a disposizione da
valgrind (helgrind, memcheck e drd). Per utilizzare questi strumenti in fase di sviluppo del codice della PPL è necessario invocarli attraverso libtool,
nel modo seguente:
1. libtool --mode=execute gdb --args
./<prog_name> <prog_options>
2.4 Altri strumenti
18
2. libtool --mode=execute valgrind --tool=helgrind
./<prog_name> <prog_options>
3. libtool --mode=execute valgrind --tool=drd
./<prog_name> <prog_options>
4. libtool --mode=execute valgrind --tool=memcheck
./<prog_name> <prog_options>
Nella PPL i comandi precedenti vanno eseguiti nella directory debug. gdb
permette di vedere cosa sta succedendo all’interno di un programma mentre viene eseguito. Esso permette di far partire il programma da analizzare
specificando dei comportamenti che deve assumere; fermare l’esecuzione in
un punto a piacere ed esaminare l’accaduto; apportare dei cambiamenti al
programma in modo da sperimentarne i comportamenti. valgrind offre un
insieme di strumenti che aiutano a rendere il programma più veloce e corretto. helgrind è particolarmente utile in quanto è specializzato nell’identificare
errori di sincronizzazione in ambienti di programmazione parallela. È stato
usato particolarmente per la sua abilità di invidividuare accessi a memoria
senza un’adeguata gestione degli stessi. Uno strumento utile da affiancare
a helgrind è drd, che svolge funzioni simili. memcheck invece è utile per
individuare accessi a porzioni di memoria già rilasciate, individuare l’uso di
valori non ancora inizializzati, memory leak e altro. Quest’ultimo tool si è
rivelato particolarmente utile.
2.4
2.4.1
Altri strumenti
GNU nm
Sui sistemi operativi Unix like, GNU nm è un comando usato per esaminare file
binari quali librerie, codice oggetto o eseguibili. La tabella dei simboli 1.1.1
viene costruita a tempo di compilazione, una parte delle sue informazioni
sono salvate nell’object file per consentire il collegamento. Le informazioni a
disposizione sono più precise se, compilando con gcc, si attiva l’opzione -g.
Esso permette di visualizzare i contenuti di questi file e le meta-informazioni
contenute al loro interno, specialmente quella parte della tabella dei simboli
contenuta nell’object file. Per ogni simbolo viene visualizzato suo valore e
tipo, che può appartenere alle seguenti categorie (lettera minuscola se si tratta
di simboli locali, maiuscola se di tipo extern):
• B b, indica che il simbolo si trova nell’area .bss;
2.4 Altri strumenti
19
• D d, indica che il simbolo si trova nel segmento dati;
• R r, indica che il simbolo è read only.
Per un elenco completo delle categorie di simboli previsti da nm, si rimanda il
lettore alla documentazione ufficiale completa [9]. L’impiego di questo strumento ai fini dello studio della PPL verrà descritto più avanti, nella Sezione
3.3.2.
2.4.2
GNU grep
GNU grep è un programma che prende in input uno o più nomi di file e cerca,
al loro interno, le righe che soddisfano determinati pattern di ricerca. Una
volta individuate, le righe sono copiate su standard output, e questo output
può essere formattato a seconda di opzioni aggiuntive che grep offre. Questi
strumenti torneranno utili per la ricerca testuale di variabili nella Sezione
3.3.1.
Capitolo 3
PPL e Thread Local Storage
3.1
Conditional Thread Safety
La thread-safety si suddivide in tre livelli, partendo dal più debole per finire
con il più forte:
1. Thread Unsafe, quando al codice sorgente non deve accedere più di un
thread alla volta (la situazione iniziale della PPL), nel caso si abbiano
accessi da parte di più thread, l’esito è imprevedibile;
2. Conditionally Thread Safe, quando al codice sorgente vi possono accedere più thread contemporaneamente, ma a condizione che essi non
operino sullo stesso oggetto, nemmeno in lettura. Come nel caso precedente, l’accesso contemporaneo da parte di più thread allo stesso
oggetto, se non protetto da opportuni meccanismi di sincronizzazione
(la cui predisposizione è a carico dell’utente), potrebbe incorrere in un
data race e dare quindi luogo ad comportamento imprevedibile;
3. Thread Safe, se più thread accedono in sola lettura allo stesso oggetto
allora l’utente fa a meno di usare meccanismi di sincronizzazione; se almeno un thread accede in scrittura, vanno implementati degli adeguati
meccanismi di sincronizzazione;
Questi tre termini sono spesso usati dai produttori di software per specificare
con esatteza le proprietà dei loro prodotti.
3.1.1
Standard Template Library C++ e variabili const
Citando lo standard C++11, due valutazioni di espressione vanno in conflitto
se una di loro modifica una locazione di memoria mentre l’altra cerca di accedervi o cercare di modificare la stessa locazione [8, Multi-threaded executions
3.1 Conditional Thread Safety
21
and data races, Sezione 1.10/4]. L’esecuzione di un programma contiene una
data race se contiene due azioni che vanno in conflitto in thread differenti,
una delle quali non è atomica e accade che una non venga eseguita prima
dell’altra [8, Multi-threaded executions and data races, Sezione 1.10/21], in
casi del genere si ottiene undefined behavior.
Lo standard offre anche dei requisiti che ogni implementazione di funzione
appartenente alla Standard Template Library (STL) deve rispettare, affinché
non accadano fenomeni di data race [8, Data race avoidance, Sezione 17.6.5.9].
Una implementazione della STL non deve modificare direttamente o indirettamente oggetti accessibili da thread che non siano quello corrente, a meno
che agli oggetti stessi sia stato fatto accesso, direttamente o indirettamente,
usando gli argomenti non-const della funzione data, this incluso data race
[8, Data race avoidance, Sezione 17.6.5.9/3].
In altre parole questo significa che qualsiasi operazione sugli oggetti di
tipo const è thread-safe, e che quindi la STL è thread-safe. Nella prossima
sezione si vedrà che la PPL, invece, non garantisce questa proprietà.
3.1.2
PPL e variabili const
Verrà spiegato ora, mediante un esempio astratto, il motivo per il quale la PPL
non può essere facilmente resa thread safe. Queste difficoltà ci indirizzeranno verso l’obiettivo della conditional-thread-safety. Si vedrà ora un esempio
astratto.
Siano in un processo due thread t1 e t2 . Supponiamo che entrambi operino sullo stesso numero razionale r che in un determinato momento vale 48 .
Consideriamo anche il caso apparentemente più innocuo, siano i metodi m1
e m2 che prendono in input il razionale r e promettono di non modificarne il
valore (ce ne sono diversi di questo tipo nella PPL). t1 invoca m1 passandogli
r, e contemporaneamente t2 invoca m2 passandogli r. Come è stato detto,
m1 e m2 non modificano r, ma potrebbero avere delle preferenze diverse sulla rappresentazione interna di r, assumiamo che t1 decida all’interno di m1
di trasformare la rappresentazione 84 in 12 , semplificandolo. Esso comincia a
modificare il numeratore e gli assegna 1, ma in questo momento t2 (tramite
m2 ) decide di leggere r e ottiene 18 anziché 48 .
Per ovviare a questo problema, nei metodi di una libreria dovrebbero
essere inserite delle operazioni atomiche o la gestione delle risorse tramite
semafori. La PPL non può permettersi il "lusso" di implementare tali meccanismi: questo implicherebbe un sostanziale peggioramento dell’efficienza,
che, stando ai vincoli imposti dagli sviluppatori, è una caratteristica cruciale
di questa libreria. La scelta è quella di lasciare che la PPL rimanga a livello
3.2 Thread Local Storage
22
conditional-thread-safe, dove la condizione per gli utilizzatori è quella di non
avere più thread diversi che operano sullo stesso oggetto.
D’ora in poi verrà detto per semplicità che la PPL vorrà essere thread-safe,
ma di fatto questo significherà conditional-thread-safe.
3.2
Thread Local Storage
Qui verrà affrontato in maniera più dettagliata il metodo di programmazione Thread Local Storage (TLS). Esso usa aree di memoria statica o globale
localmente per un thread. Si ricorre a ciò perché diversi thread possono riferirsi alla stessa area di memoria e non sempre lo si vuole. In altre parole,
le variabile global e static vengono allocate normalmente nella stessa area
di memoria, quando ci si riferisce a loro da diversi thread. Le variabili nello
stack delle chiamate sono comunque locali ai thread, perché ognuno ha uno
stack proprio.
3.2.1
Alternative allo standard C++: TLS in GCC
Il metodo di programmazione TLS era supportato dal compilatore GCC ancora
prima dello standard C++11, con una propria implementazione. Consultando
la documentazione [4], si evince che essa richiede un supporto significativo
da parte del linker ld, linker dinamico ld.so e le librerie di sistema libc.so
e libpthread.so, che non sono disponibili ovunque. Il qualificatore di una
variabile thread-local è __thread e può essere usato singolarmente o con le
parole chiave extern e static, che vanno messe prima di __thread.
1
2
3
4
5
6
7
8
// Variabile thread - local
__thread int i ;
// Variabile thread - local definita altrove
extern __thread struct state s ;
// Variabile thread - local statica
static __thread char * p ;
Inoltre, se è presente lo specificatore __thread non sono ammesse altre
parole chiave oltre alle due già citate. Esso può essere applicato a:
• variabili globali;
• variabili static nello scope di un file;
3.2 Thread Local Storage
23
• variabili static a scope di funzione;
• dati membro static di una classe.
Il qualificatore __thread non può essere usato su variabili non statiche
nello scope di un blocco o su dati membro non static di una classe.
Quando l’operatore address-of (&) viene applicato ad una variabile threadlocal, l’indirizzo viene valutato a tempo di esecuzione e ritorna l’indirizzo
che ha tale variabile nell’istanza del thread corrente. L’indirizzo ottenuto
può essere usato poi anche da altri thread, e una volta che il thread originario "muore", qualsiasi puntatore a sue variabili thread-local diventa non
valido. Nessuna inizializzazione statica può riferirsi all’indirizzo di una variabile __thread. In C++, se c’è un inizializzatore per una variabile threadlocal, deve essere una constant expression così come definita nello standard
ANSI/ISO C++ 5.19.2. Come si può vedere appena sotto, quindi, una variabile thread-local deve essere inizializzata con una espressione nota a tempo
di compilazione e non a run time.
1
2
3
4
5
6
7
// Errato
int a = 1;
static __thread int b = a ;
// Corretto
const int c = 2;
static __thread int d = c ;
3.2.2
TLS in C++11
In C++11, si qualifica una variabile come thread-local tramite la parola chiave thread_local. Seguendo lo standard [8, Storage Class Specifiers, Sezione 7.1.1] tale specificatore fa parte della categoria degli storage-class-specifier
che comprendono:
• register;
• static;
• thread_local;
• extern;
• mutable.
3.2 Thread Local Storage
24
Al massimo uno di questi può comparire nella dichiarazione di una variabile, eccetto thread_local che può essere accompagnato dagli specificatori
extern e static. Se lo specificatore thread_local compare nella dichiarazione di una variabile, lo stesso deve essere presente in ogni sua altra
dichiarazione. Possono essere dichiarate thread-local:
• le variabili nello scope di un namespace;
• i dati membro static di una classe;
• le variabili locali.
Infatti, secondo lo standard [8, Class Members, Sezione 9.2], il membro di
una classe non può essere dichiarato thread_local se non è static. Se un
membro static è dichiarato thread_local c’è esattamente una copia di
tale membro per ogni thread, altrimenti, c’è una copia condivisa da tutti gli
oggetti di tale classe [8, Static Data Members, Sezione 9.4.2].
1
2
3
4
5
6
7
8
9
10
11
12
// Variabile thread - local a scope di namespace
thread_local int x ;
class tls {
// Membro static e thread - local di una classe
static thread_local std :: string s ;
};
void foo () {
// Variabile thread - local locale
thread_local std :: vector < int > v ;
}
La storage duration, ovvero la durata di "conservazione", è la proprietà
di un oggetto che definisce il tempo di vita di un contenitore di informazione.
thread_local indica che l’oggetto ha la durata di vita del thread, ed è detta
thread storage duration [8, Thread Storage Duration, Sezione 3.7.2].
Inizializzazione e Distruzione
L’inizializzazione di una generica variabile con la proprietà thread-storageduration deve avvenire prima del suo primo utilizzo, e, se costruita, deve
essere distrutta prima della terminazione del thread. Se il thread t2 vuole
inizializzare una variabile mentre lo sta già facendo t1 , t2 dovrà aspettare
finché l’inizializzazione non avverrà per mano di t1 . La distruzione di una
3.3 Ricerca di codice thread-unsafe
25
variabile thread-local locale avverrà solo se è stata in precedenza inizializzata
[8, Declaration Statement, Sezione 6.7].
L’inizializzazione di una variabile locale (block scoped ) con la proprietà
thread-storage-duration, avviene la prima volta che un flusso di controllo ci
passa all’interno. Se l’inizializzazione lancia un’eccezione, essa è incompleta, e
l’inizializzazione verrà ritentata al prossimo flusso di controllo che incontrerà
tale dichiarazione.
L’inizializzazione di variabili thread_local a visibilità di namespace e
membri di classi è implementation defined. Esse sono costruite prima del loro
utilizzo proveniente dalla stessa unità di traduzione, ma senza specificare
quanto prima. Alcune implementazioni possono inizializzarle appena prima
dell’utilizzo; appena il thread è stato creato, oppure in istanti ancora diversi.
Se nessuna delle variabili thread-local nella stessa unità di traduzione viene
usata, non c’è nessuna garanzia che esse siano mai state costruite.
Per il resto, le variabili thread_local condividono le altre proprietà con
quelle static: sono zero-inizializzate prima ancora che avvenga ogni altro
tipo di inizializzazione (come quella dinamica). I distruttori delle variabili
thread-local vengono invocati in ordine inverso alla loro costruzione, se un
thread è ancora in esecuzione quando il thread padre è già uscito, i distruttori
delle sue variabili non vengono invocati. Bisogna tenere conto che l’ordine di
inizializzazione non è specificato, ed evitare interdipendenze fra distruttori.
Come è stato già detto, le variabili thread-local hanno diversi indirizzi
per ogni thread. È possibile ottenere il puntatore di una di loro e accedere a
tale locazione a partire da diversi flussi di esecuzione, ma il relativo accesso
è undefined behaviour se il thread d’origine è già terminato, e la sue relative
variabili thread-local sono state già distrutte.
3.3
Ricerca di codice thread-unsafe
Per cercare entità thread-unsafe è stata analizzata la directory delle sorgenti della PPL e la directory che contiene le interfacce per i diversi linguaggi
previsti:
1. src/;
2. interfaces/<lang>/.
Dove lang è uno dei linguaggi tra C, Java, OCaml e Prolog. In questo lavoro
di tirocinio è stata modificata soltanto l’interfaccia C.
La directory src contiene prevalentemente classi, suddivise per file come
segue:
3.3 Ricerca di codice thread-unsafe
26
• file di implementazione;
• *_defs.hh file header contenente la definizione della classe;
• *_inlines.hh file header contenente le sue funzioni di tipo inline;
• *_types.hh file header contenente contenente le dichiarazioni "pure"
della classe (le cosiddette forward declaration).
Ci sono alcuni file e altre classi che non rispettano questo schema.
Essendo il codice sorgente da analizzare molto ampio, sia in termini di
numero di file sorgenti che, in alcuni casi, di dimensioni dei file stessi, non è
proponibile pensare ad una ricerca manuale delle porzioni di codice threadunsafe; inoltre, l’approccio sarebbe troppo sensibile ad errori e sviste.
3.3.1
Ricerca testuale
Per prima cosa ci si è concentrati sulle variabili di tipo extern. Se una variabile è dichiarata con il qualificatore extern questo implica che è soggetta ad
allocazione statica, è può essere stata dichiarata e/o definita altrove. È stato
usato lo strumento grep 2.4.2 per la ricerca di tale parola chiave. Sia quindi
il seguente insieme di righe generate dal comando
grep -w -n "extern" <dir>/ppl/src/*.
Si usa -w per estrarre solo le righe in cui extern forma una parola intera e
-n per mostrare il numero della riga nel file, in modo da facilitare la ricerca.
In C++, non è detto che la parola chiave extern indichi per forza che si
tratti di una variabile. Infatti, oltre a un tipo di durata dello storage extern
viene usata per linkare moduli scritti in linguaggi diversi e viene usata anche
insieme ai template, per evitare l’istanziazione implicita (a partire da C++11).
Per ogni riga quindi, c’è la necessità di verificare manualmente di cosa si
tratta: se non è una variabile, la riga viene eliminata dall’insieme. Sia ora
var una variabile appartenente a tale insieme, per ogni var è stato verificato
se essa è stata definita o dichiarata altrove ripetendo il comando precedente
grep -w -n "<var>" <dir>/ppl/src/*.
Il risultato di questa serie di ricerche su ogni var viene unito con quello del
comando precedente, eliminando i duplicati, in questo modo si è riusciti a
risalire ad una parte delle variabili globali della PPL e loro dichiarazioni.
Le variabili static si possono individuare nella stessa maniera, tramite
il comando
3.3 Ricerca di codice thread-unsafe
27
grep -w -n "static" <dir>/ppl/src/*.
Oltre che variabili, di tipo static possono essere anche funzioni membro di
una classe. Anche in questo caso si è andati a verificare manualmente e, se si
trattava di una funzione, essa veniva eliminata dalla lista ottenuta lasciando
solo le variabili.
3.3.2
Ricerca sulla tabella dei simboli
Il comando nm (visto nella Sezione 2.4.1) è stato usato sulle varie librerie prodotte da linker nella directory di compilazione build (Sezione 2.3).
Spostandosi nella seguente directory
cd build/src/.libs/
è possibile trovare le librerie statiche con estensione .a e quelle dinamiche,
con estensione .so. Sono state analizzate le librerie statiche con la seguente
sequenza di comandi:
nm -A -C *.a | egrep ’ [A-Z] ’ | egrep -v ’ [UTWRV] ’,
dove -A fa visualizzare il nome del file da dove viene un dato simbolo, e grazie
a -C è possibile leggere facilmente i namespace ed il nome della variabile.
Tramite egrep ’ [A-Z] ’ si filtrano i simboli globali. Tramite egrep -v ’
[UTWRV] ’ vengono rimossi i simboli indefiniti; i simboli nell’area del codice;
i così detti weak objects; i simboli che rappresentano variabili read only ed i
così detti weak symbol. Nella ricerca era possibile includere anche i simboli
marcati tramite la u minuscola che aiutano a risalire alle variabili locali di
tipo static, ma ciò è superfluo dato che per esse è stata usata la ricerca
testuale.
Lo svantaggio di questo metodo è che il procedimento va ripetuto per
ogni tipo di configurazione di una directory di compilazione. Per esempio,
in modalità -enable-assertions, a causa di eventuali direttive condizionali
del preprocessore, potrebbe essere dichiarato un numero diverso di variabili
globali. Un altro punto a sfavore è che è necessario studiare il comportamento
di nm in base al compilatore usato. Ad ogni modo, esistono altri modi più
eleganti per cercare in maniera sistematica le variabili globali: si può per
esempio scrivere un visitor per il parser clang, approccio che comunque non
è stato preferito per via della sua complessità.
3.4 Modifiche TLS
3.4
28
Modifiche TLS
Una volta individuato l’insieme delle variabili thread-unsafe esse vanno convertite in variabili thread-local. A prescindere dalle varie implementazioni
esistenti, il costo dell’utilizzo di variabili thread-local è di norma relativamente basso, tanto da non far percepire all’utente alcuna differenza. Tuttavia, se
alle variabili thread-local si accede troppo frequentemente il costo aumenta a
sua volta. C’è anche l’eventualità che l’utente non abbia intenzione di usare
la PPL in ambiente multithread, quindi il costo del meccanismo TLS è del
tutto superfluo in ogni caso. È stato creato il file header thread_safe.hh in
cui viene definita la macro PPL_TLS:
1
2
3
4
5
# ifdef PPL_THREAD_SAFE
# define PPL_TLS thread_local
# else
# define PPL_TLS
# endif
Alle variabili trovate nella sezione precedente è stato aggiunto come qualificatore la macro PPL_TLS. Per errori di mancanza di dichiarazione di PPL_TLS,
l’header thread_safe.hh è stato incluso nei seguenti file:
1. global_defs.hh
2. Init_defs.hh
3. Temp_defs.hh
4. Threshold_Watcher_defs.hh
5. Variable_defs.hh
Lo standard C++11 afferma che se lo storage class specifier thread_local
compare in una qualsiasi dichiarazione di una variabile, lo stesso specificatore
deve essere inserito in tutte le sue dichiarazioni [8, Storage Class Specifiers,
Sezione 7.1.1/2]. Quando ciò non accadeva, tramite gli errori stessi del compilatore GCC è stato possibile risalire a un numero maggiore di dichiarazioni
di variabili.
3.4.1
Dichiarazioni PPL_TLS
Verrano ora proposti degli esempi di variabili che hanno ottenuto il qualificatore PPL_TLS, nella directory /src. Gli esempi verranno raggruppati in
base al tipo di variabile. Si cercherà anche di quantificare le variabili per ogni
3.4 Modifiche TLS
29
categoria; per le variabili di tipo static i valori possono non essere esatti
datto che la categorizzazione è stata fatta manualmente.
Variabili extern
Lo specificatore PPL_TLS è stato inserito per 12 variabili di tipo extern. Si
può vedere un esempio di variabili PPL_TLS di tipo extern nel file header
Coefficient_inlines.hh:
extern PPL_TLS const Coefficient* Coefficient_zero_p;
extern PPL_TLS const Coefficient* Coefficient_one_p;
Variabili static locali
Due delle circa 10 variabili locali static che hanno ottenuto il qualificatore
PPL_TLS sono le seguenti:
PPL_TLS
N(-2,
N(-1,
N( 0,
N( 1,
N( 2,
};
PPL_TLS
static N stop_points[] = {
ROUND_UP),
ROUND_UP),
ROUND_UP),
ROUND_UP),
ROUND_UP)
static Coefficient zero(0);
stop_points si trova nel file Octagonal_Shape_inlines.hh mentre la seconda la si trova nel file Coefficient_inlines.hh.
Dati membro static
Hanno ottenuto lo specificatore PPL_TLS circa 32 dati membro di tipo static.
Un esempio si può tovare nel file header Congruence_defs.hh:
static const Congruence* zero_dim_false_p;
static const Congruence* zero_dim_integrality_p;
Variabili static con visibilità di file
Esistono circa 30 variabili static con visibilità di file che hanno ottenuto lo
specificatore PPL_TLS:
3.5 Inizializzazione
30
PPL_TLS static Parma_Polyhedra_Library::Thread_Init
Parma_Polyhedra_Thread_initializer;
PPL_TLS static Parma_Polyhedra_Library::Thread_Init*
Parma_Polyhedra_Thread_initializer_p = 0;
Come già specificato in precedenza, lo standard C++11 esige che se la
parola chiave thread_local (che nel nostro caso equivale a PPL_TLS) come
pare in una dichiarazione di una variabile essa deve comparire in tutte le
altre dichiarazioni e definizioni. Anche a causa di questa direttiva, alla fine,
lo specificatore PPL_TLS è stato inserito come qualificatore per 135 variabili.
Una volta concluso l’inserimento dello specificatore PPL_TLS, ci sono stati problemi nei programmi di prova (che verranno approfonditi nella Sezione
4.1): la libreria non veniva più inizializzata automaticamente. Per questo,
all’interno del programma, è comparsa la necessità di inizializzare esplicitamente la PPL prima di ogni utilizzo della stessa.
3.5
Inizializzazione
Nella PPL, la classe Init è una classe di inizializzazione: essa contiene funzioni
di inizializzazione di tutte le altre classi necessarie, e quindi anche variabili.
Tutte quante le funzioni vengono eseguite prima di usare la libreria. Dopo
l’inserimento del meccanismo TLS descritto nella sezione precedente, ci si
aspetta avere di più thread di esecuzione e, per ognuno di questi, va eseguita
l’inizializzazione in quanto hanno tutti una propria versione degli stati delle
variabili. Tuttavia, le funzioni di inizializzazione da invocare, alcune delle
quali inizializzano variabili globali, possono essere ulteriormente classificate
nel seguente modo:
• Inizializzazione a livello di libreria, cioè funzioni che inizializzano
variabili inizializzabili una sola volta prima di usare la PPL, dove il
numero dei thread possibili e il loro ordine di esecuzione non influiscono
sul loro stato;
• Inizializzazione a livello di thread, cioè funzioni che inizializzano
variabili inizializzabili ogni volta che diventa operativo un nuovo thread,
in quanto quelle variabili hanno un’istanza diversa in base al thread.
Se tutte le funzioni di inizializzazione fossero a livello di thread, la classe
Init non avrebbe dovuto subire modifiche, ma non è così. Infatti, come
afferma la documentazione GMP [12], la funzione
ppl_set_GMP_memory_allocation_functions();
3.6 Funzione wrapper
31
fa uso di variabili globali per memorizzare le funzioni di allocazione di memoria impostate. Non essendo una libreria su cui si possa mettere mano ai
fini della tesi, la funzione mp_set_memory_functions non è thread-safe. Non
potrebbe far parte dell’inizializzazione a livello di thread. Infine, è stato pensato che anche modifiche future della PPL possano introdurre variabili globali
a livello di libreria, e che quindi una differenziazione torni ancora utile.
La classe Init verrà suddivisa nelle classi Library_Init e Thread_Init.
È stato fatto in modo che nella PPL i restanti oggetti globali siano di proprietà
esclusiva di un thread; di conseguenza tutti loro verranno inizializzati a livello
di thread, quindi nella classe Thread_Init. Va ricordato ancora che, l’utente
non deve condividere oggetti PPL fra thread diversi.
3.6
Funzione wrapper
A questo punto in ogni programma è necessario, prima di ogni altra operazione con la PPL, inizializzarla a livello di libreria:
PPL::Library_Init library_init;
In C++11, per iniziare l’esecuzione di un thread è necessario passare al suo
costruttore un diverso thread già creato, oppure un oggetto chiamabile (funzione, oggetto funzione...) da eseguire nel nuovo thread, seguito dagli argomenti che servono per invocare l’oggetto chiamabile. All’inizio di ognuno di
questi oggetti chiamabili l’utente deve inizializzare la PPL a livello di thread:
PPL::Thread_Init thread_init;
Si supponga che per qualche ragione l’utente non voglia o non possa modificare un oggetto chiamabile già esistente, in cui si usa la PPL. Una soluzione è
quella di implementare una funzione wrapper, ovvero una funzione che riveste
l’oggetto chiamabile originario, e prima di eseguirlo inizializza la PPL a livello
di thread.
1 template < typename Fun >
2 class Threadable_Fun {
3
private :
4
Fun fun ;
5
6
public :
7
explicit Threadable_Fun ( Fun f ) : fun ( f ) {}
8
9
template < typename ... Args >
3.6 Funzione wrapper
10
11
32
auto operator () ( Args &&... args ) const
-> decltype ( fun ( std :: forward < Args >( args ) ...) )
{
Thread_Init thread_init ;
12
13
14
return fun ( std :: forward < Args >( args ) ...) ;
15
}
16 };
17
18 template < typename Fun >
19 Threadable_Fun < Fun > make_PPL_Threadable ( Fun fun )
{
20
return Threadable_Fun < Fun >( fun ) ;
21 };
Tale implementazione permette di creare un nuovo thread che prende
come oggetto chiamabile la funzione wrapper che prende come parametro
l’oggetto chiamabile, seguita dagli argomenti necessari all’oggetto chiamabile:
std::thread t(PPL::make_PPL_Threadable(oggetto_chiamabile),
arg_1,
...,
arg_n);
Nel caso in cui l’utente facesse uso di thread-pool (verrà visto nella Sezione
4.1.1), il seguente è un altro esempio di utilizzo della funzione wrapper:
std::function<void()> func = std::bind(oggetto_chiamabile,
arg1_,
...,
arg_n);
thread_pool.submit(PPL::make_PPL_Threadable(func));
Dove si suppone che il thread-pool sia una classe con il metodo submit che
aggiunge un altro compito da svolgere. In questo caso, tramite std::bind si
crea un oggetto funzione che viene passato alla funzione wrapper.
La funzione templatica make_PPL_Threadable prende come parametro
formale un oggetto fun di tipo Fun, e crea un oggetto della classe templatica
Threadable_Fun. Il costruttore della classe Threadable_Fun prende in input fun. L’overloading dell’operatore () della classe Threadable_Fun ha lo
stesso tipo di ritorno di fun, interrogandolo nella dichiarazione (decltype).
L’operatore () prende in input gli argomenti necessari a fun. A questo punto
3.7 Interfaccia C
33
viene inizializzata la libreria a livello di thread e, dopo l’esecuzione di fun,
viene ritornato il suo stesso tipo di ritorno.
Si ricorda che alla fine di un blocco vengono invocati i distruttori di
tutti gli oggetti create in tale blocco. Non è quindi necessario finalizzare
esplicitamente la PPL, sia a livello di thread che di libreria. L’operazione
di finalizzazione viene eseguita dai distruttori invocati su library_init e
thread_init.
3.7
Interfaccia C
Tra tutte le interfacce presenti nella PPL, è stato affrontata la thread-safety
dell’interfaccia C. Per farlo si è subito pensato di usare lo standard C11, ma il
supporto per il multithreading secondo questo standard è ancora incompleto
e quindi si è deciso di usare le estensioni di GCC. Nel file ppl_c_header è
stata definita la macro PPL_C_TLS nel seguente modo:
1
2
3
4
5
# ifdef PPL_THREAD_SAFE
# define PPL_C_TLS __thread
# else
# define PPL_C_TLS
# endif
Come nel caso della macro PPL_TLS, PPL_C_TLS verrà usata come qualificatore delle variabili che necessitano di essere TLS, se richiesto. Analogamente a
quanto fatto con il codice sorgente della PPL, sono stati combinati i risultati
delle seguenti ricerche testuali:
grep -w -n "extern" /ppl/interfaces/C/*
grep -w -n "static" /ppl/interfaces/C/*
Dopo di che è stata fatta un ricerca per informazioni della tabella dei simboli
nei seguenti file:
nm -A -C *.a | egrep ’ [A-Z] ’ | egrep -v ’ [UTWRV] ’
Nell’interfaccia C della PPL ci sono relativamente pochi file sorgenti, quindi è stata possibile anche una breve ricerca visiva. Le variabili allocabili
staticamente che necessitano di essere TLS sono le seguenti:
error_handler_type user_error_handler = 0;
static char buffer[20];
ppl_io_variable_output_function_type* c_variable_output_function;
Variable::output_function_type* saved_cxx_Variable_output_function;
3.7 Interfaccia C
34
Parma_Polyhedra_Library::Watchdog* p_timeout_object = 0;
Weightwatch* p_deterministic_timeout_object = 0;
static timeout_exception e;
static timeout_exception e;
extern error_handler_type user_error_handler;
Le variabili elencate si trovano tutte nel file ppl_c_implementation_common.cc
ad eccezione dell’ultima, che è una dichiarazione e nel file
ppl_c_implementation_common_defs.cc.
3.7.1
Inizializzazione
L’header initializer.hh che si trova nella directory delle sorgenti della PPL,
fornisce le seguenti funzioni:
inline
inline
inline
inline
void
void
void
void
library_initialize();
library_finalize();
thread_initialize();
thread_finalize();
Le funzioni library_initalize() e thread_initalize() allocano rispettivamente gli oggetti Library_Init e Thread_Init. Le funzioni library_finalize()
e
thread_finalize() invece, li deallocano. Tali funzioni sono chiamabili da
interfacce dei vari linguaggi per inizializzare e finalizzare la PPL. Per quanto
riguarda l’interfaccia C, per inizializzare e finalizzare la PPL c’erano i metodi
int ppl_initialize(void);
int ppl_finalize(void);
Queste sono state sostituite con le seguenti:
1. int ppl_library_initialize(void) inizializza a livello di libreria,
chiamando il metodo library_initalize() e inizializza le variabili
allocabili staticamente che non necessitano di essere TLS, nell’interfaccia
C;
2. int ppl_thread_initialize(void) inizializza a livello di thread, chiamando il metodo thread_initalize() e inizializza un sottoinsieme
delle variabili allocabili staticamente che necessitano di essere TLS,
nell’interfaccia C;
3. ppl_library_finalize(void) finalizza a livello di libreria, chiamando
il metodo library_finalize() e impostando la funzione di output di
default;
3.7 Interfaccia C
35
4. ppl_thread_finalize(void) finalizza a livello di thread, chiamando
il metodo thread_finalize() e impostando la funzione di output di
default.
Capitolo 4
Testing
In questo capitolo si descriveranno le modifiche effettuate ad alcuni programmi demo che utilizzano la PPL, inizialmente sviluppati in versione singlethread, al fine di testare la correttezza e l’efficienza della versione thread-safe
della PPL.
4.1
ppl_lcdd
ppl_lcdd è un programma demo allegato alla libreria PPL ed è basato su
quest’ultima. Ci sono più modi per rappresentare un poliedro, tramite una
H-rappresentazione o una V-rappresentazione. ppl_lcdd prende in input un
poliedro in V-rappresentazione e produce una H-rappresentazione (o viceversa) dello stesso poliedro. All’interno della PPL, ppl_lcdd fa uso di alcune
cache globali alle quali si accede senza alcun controllo di sincronizzazione.
Come discusso nei capitoli precedenti, nel caso di thread multipli questo causerebbe dei data race e comportamenti indefiniti, per cui tali cache sono state
dichiarate thread_local. Per questo motivo, il programma ppl_lcdd costituisce un test significativo per la versione thread-safe della libreria. Il programma è stato modificato per renderlo in grado di operare su più poliedri
contemporaneamente producendo risultati corretti per ognuno dei poliedri in
input. Inizialmente ppl_lcdd supportava le seguenti opzioni:
• -CSECS, –max-cpu=SECS, limita il tempo di utilizzo della CPU;
• -RMB, –max-memory=MB, limita l’utilizzo di della memoria a MB megabyte;
• -h, –help, stampa il testo dell’help su standard output;
• -oPATH, –output=PATH, appendi l’output a PATH;
4.1 ppl_lcdd
37
• -t, –timings, stampa i tempi su stderr;
• -v, –verbose, produce più output durante l’esecuzione;
• -V, –version, stampa su standard output la versione del programma;
• -cPATH, –check=PATH, controlla se il poliedro ottenuto è uguale a
quello che c’è in PATH.
Si vedrà come ognuna di queste opzioni finirà nella versione modificata
4.1.1
Modifiche a ppl_lcdd
Verranno elencate le più rilevanti modifiche apportate a ppl_lcdd. Per la
programmazione parallela è stata usata la classe std::thread.
Come prima cosa, a inizio del main è stata introdotta l’inizializzazione a
livello di libreria, cioè creando un oggetto della classe Library_Init.
Il corpo del main si occupa della conversione tra i due tipi di rappresentazione del poliedro. Siccome ora i poliedri in input saranno più di uno, il
codice che si occupa della conversione è stato spostato nel corpo di una nuova
funzione:
void convert(char* input_file_name);
Ogni thread potrà far partire l’esecuzione della funzione convert, ognuno con
un nome del file di input diverso. All’inizio della funzione convert è possibile inserire l’inizializzazione a livello di thread, ma avendo a disposizione la
funzione wrapper (Sezione 3.6) ciò non è necessario.
ppl_lcdd possiede la funzione
void process_options(int argc, char* argv[]);
che viene chiamata dal main per processare le opzioni ed i file in ingresso.
Sono state fatte delle modifiche a process_options in modo che, oltre a cambiare il comportamento di ppl_lcdd in base alle opzioni, sia capace di rilevare
nomi di file multipli in ingresso. Questi file rappresentano i poliedri rappresentati in una certa forma. Per ogni poliedro in ingresso process_options
lancia un nuovo thread. Il thread cambia la rappresentazione del poliedro e
lo salva in una directory specificata tramite l’opzione -o.
A questo punto dello sviluppo è comparso un problema: cosa succede se il
numero dei poliedri in ingresso supera il numero dei thread supportati dalla
macchina? Tale numero, ovviamente, è limitato.
4.1 ppl_lcdd
38
Thread Pool
Il thread-pool indica un gestore software di thread, viene utilizzato per semplificare ed ottimizzare l’utilizzo dei thread all’interno di un programma.
C’è una moltitudine di tipi di thread-pool e più numerose sono le possibili
implementazioni.
Nel caso di ppl_lcdd è bastato un thread-pool relativamente semplice.
Non è necessario badare a un valore di ritorno dei thread dato che, una volta
iniziata la conversione della rappresentazione del poliedro, per tutta la sua
durata e alla fine, il master -thread non deve più interagire con il worker thread. Una ulteriore semplificazione è data dal fatto che tutti i thread sono
indipendenti fra loro. Nel frame 4.1.1 viene rappresentata l’interfaccia del
thread-pool inserito nella directory del programma demo ppl_lcdd.
1 class Thread_Pool
2 {
3
private :
4
std :: atomic_bool done ;
5
Threadsafe_Queue < std :: function < void () > >
6
work_queue ;
7
std :: vector < std :: thread > threads ;
8
Join_Threads joiner ;
9
10
void worker_thread () ;
11
12
public :
13
Thread_Pool () ;
14
15
template < typename FunctionType >
16
void submit ( FunctionType f ) ;
17
void free () ;
18
19
~ Thread_Pool () ;
20 };
Nel seguito si fornirà una breve spiegazione del funzionamento di questo
thread-pool, senza scendere troppo nei dettagli implementativi. Al riguardo,
il lettore interessato può consultare il libro [13], dal quale si è preso spunto per l’implementazione del thread-pool. Una volta creato l’oggetto di tipo
Thread_Pool, il suo costruttore (riga 13) interroga la macchina hardware su
quanti
thread
riesca
a
supportare,
tramite
la
funzione
std::thread::hardware_concurrency(). A volte hardware_concurrency()
4.1 ppl_lcdd
39
può ritornare il valore 0: se questo accade il thread-pool assume che la macchina sia in grado di supportare 4 thread. Questi thread appena creati vengono
salvati nel vettore threads (riga 7). A tutti i thread viene fatta eseguire la
stessa funzione membro worker_thread (riga 10). worker_thread non fa altro che verificare se sulla work_queue (riga 6) ci siano oggetti chiamabili da
eseguire, che sono di fatto i task che l’utente impone di eseguire al threadpool, tramite la funzione membro templatica void submit(FunctionType
f). submit infatti aggiunge generici oggetti chiamabili alla work_queue. In
altre parole, l’utente assegna al thread-pool dei lavori in coda da far fare
ai thread, che sono tanti quanti la macchina riesce a supportare senza creare overhead. Quando un thread finisce un task cerca di prelevarne un’altra
dalla coda. Quando l’utente è sicuro che tutte i task le abbia assegnate al
thread-pool, può invocare il metodo void free() per comunicarlo, e tale
informazione verrà salvata in std::atomic_bool done.
Se il blocco in cui è stato creato l’oggetto della classe Thread_Pool giunge
alla sua fine, viene invocato il suo distruttore che potrebbe mettere fine al
lavoro dei thread anche se questi non hanno ancora finito la conversione della
rappresentazione dei poliedri. Ma ciò non accade perché Thread_Pool()
tenterà di distruggere i membri dati in ordine inverso alla loro dichiarazione,
ed il primo è l’oggetto joiner (riga 8) della classe Join_Threads 4.1.1.
1 class Join_Threads
2 {
3
private :
4
std :: vector < std :: thread >& threads ;
5
6
public :
7
explicit
8
Join_Threads ( std :: vector < std :: thread >&
9
threads_ ) ;
10
11
~ Join_Threads () ;
12 };
L’oggetto joiner viene costruito prendendo in input l’insieme dei thread
creati dal thread-pool. Il distruttore invocato su joiner prima di uscire invoca la funzione std::thread::join su ogni thread all’interno del thread-pool.
std::thread::join non fa altro che fermare il flusso di esecuzione finché il
thread in questione non ha finito. In questo modo il distruttore invocato
sull’oggetto joiner farà aspettare anche il distruttore invocato sull’oggetto
della classe Thread_Pool, impedendo la sua distruzione prima che il lavoro
in corso venga finito.
4.1 ppl_lcdd
40
L’oggetto work_queue è della classe implementata Threadsafe_Queue,
che si comporta come una generica struttura dati di tipo queue, con le stesse
operazioni, ma è anche thread-safe.
Opzioni ppl_lcdd_mt
La versione multi-thread di ppl_lcdd verrà d’ora in poi chiamata ppl_lcdd_mt.
Le opzioni eventualmente modificate che sono supportate da ppl_lcdd_mt
sono le seguenti:
• -CSECS, –max-cpu=SECS, che limita il tempo di utilizzo della CPU del
processo, causando la morte di tutti i threads;
• -RMB, –max-memory=MB, che limita l’utilizzo di della memoria a MB
megabyte, a livello di processo;
• -h, –help, stampa i tempi su stderr;
• -oPATH, –output=PATH, tutti gli output vengono salvati come file nella
directory PATH, i nuovi file avranno lo stessi nome (assieme alla vecchia
estensione) dei file in input, ma con l’aggiunta della stringa .out alla
fine;
• -V, –version, stampa su standard output la versione del programma.
In ppl_lcdd_mt è stata lasciata anche l’opzione –verbose, ma non è stata
adeguatamente testata dal momento che ogni thread potrebbe impegnare
lo standard output senza sincronizzazione. È stata tolta del tutto l’opzione
–check=PATH.
4.1.2
Prova pratica
La correttezza di ppl_lcdd_mt è stata testata facendolo partire ogni volta con
un numero arbitrario di poliedri (a partire da 12 fino a 15) su cui operare. Così
è stato fatto per più gruppi di poliedri. Ogni volta che finiva la conversione
di un gruppo di poliedri, i risultati venivano confrontati con i risultati di
ppl_lcdd sugli stessi poliedri. Non sono mai state riscontrate differenze: nei
test effettuati ppl_lcdd_mt e ppl_lcdd si sono comportati nello stesso modo
per ogni singolo poliedro.
4.1 ppl_lcdd
41
ppl_lcdd_mt con la PPL thread-unsafe
Come verifica ulteriore, sono stati anche effettuati alcuni test con il programma ppl_lcdd_mt al quale, però, era stata collegata la versione thread-unsafe
della PPL. Come prevedibile, in questo caso l’esecuzione mostra i classici sintomi dell’undefined behavior, causando errori a tempo di esecuzione e/o la
produzione di output non corretto. Tali errori sono facilmente riscontrabili,
ma avendo natura non deterministica non possono essere riprodotti con esattezza e rientrano quindi nella categoria di errori estremamente difficile da
correggere. Le variabili staticamente allocabili all’interno della PPL non sono
TLS, e quindi ogni thread cerca di scrivere e di leggere sulle stesse variabili,
che hanno un’unica istanza, senza alcuna sincronizzazione. Il contenuto dei
file in output è imprevedibile.
ppl_lcdd e ppl_lcdd_mt su singolo poliedro
Si vogliono confrontare le prestazioni di ppl_lcdd (sulla PPL thread-unsafe)
e ppl_lcdd_mt (sulla PPL thread-safe) su singoli poliedri, con l’intento di
riuscire a vedere eventuali inefficenze introdotte dal meccanismo TLS e dalla
maggiore complessità di ppl_lcdd_mt. Nella tabella appena sotto è possibile
vedere un confronto dei tempi (espresso in secondi) di esecuzione di ogni
singolo file elencato. Ogni valore è una media di più prove eseguite. Si nota che
ppl_lcdd ppl_lcdd_mt
Secondi
cyclic17_8.ine
0.03
0.045
dcube12.ext
0.06
0.08
0.1
0.13
kkd38_6.ext
in7.ine
0.77
1.04
mit31-20.ine
2.46
2.95
sampleh8.ine
8.05
10.51
16.05
18.2
mit41-16.ine
l’esecuzione di ppl_lcdd_mt richiede più tempo man mano che la complessità
dei calcoli aumenta.
ppl_lcdd_mt con più poliedri
Si prenda come esempio il gruppo dei poliedri nella tabella sotto. I tempi di
esecuzione sono di ppl_lcdd abbinato alla PPL thread-unsafe. Far convertire
a ppl_lcdd tutti questi file in sequenza impiegherebbe almeno 43 secondi,
nella condizione ideale in cui tra un comando e l’altro i tempi sono nulli.
ppl_lcdd_mt invece, prendendo in input tutti i file elencati alla volta, richiede
4.2 ppl_lpsol
42
Nome file
ppl_lcdd
ccc6.ine
0.03
dcube12.ext
0.06
kkd38_6.ext
0.1
in7.ine
0.77
2.46
mit31-20
cyclic25_13.ext
15.49
8.05
sampleh8.ine
mit41-16.ine
16.05
20,9 secondi. Il tempo richiesto per convertire il poliedro più impegnativo
(mit41-16.ine) è di 18.2 secondi, ciò significa che ppl_lcdd_mt converte
tutti i file in un tempo che supera di poco il file più impegnativo.
4.2
ppl_lpsol
ppl_lpsol, un altro programma demo basato sulla PPL, è un risolutore di
problemi nella programmazione lineare intera e mista scritto in C, anche allo
scopo di testare la funzionalità dell’interfaccia della PPL verso tale linguaggio. Lo useremo quindi, in modo analogo a quanto fatto precedentemente per
ppl_lcdd, per testare la correttezza della versione thread-safe dell’interfaccia
C. ppl_lpsol legge un file nel formato .mps e cerca di trovare la soluzione
usando degli algoritmi di ottimizzazione forniti dalla PPL. ppl_lpsol usa
strumenti della PPL che fanno uso della classe MIP_solver. Per facilitare il
lavoro, le opzioni di ppl_lpsol sono state classificate in due categorie: le
opzioni che impongono dei vincoli sul problema da risolvere e le opzioni che
condizionano il comportamento del programma, da un punto di vista tecnico.
Alla seconda categoria appartengono le seguenti opzioni:
• -c, –check[=THRESHOLD], verifica il risultato ottenuto usadndo GLPK
(GNU Linear Programming Kit [14]);
• -CSECS, –max-cpu=SECS, limita il tempo di utilizzo della CPU a SECS
secondi;
• -RMB, –max-memory=MB, limita l’utilizzo di della memoria a MB megabyte;
• -h, –help, stampa il testo dell’help su standard output;
• -oPATH, –output=PATH, appendi l’output a PATH;
4.2 ppl_lpsol
43
• -t, –timings, stampa i tempi su stderr;
• -v, –verbosity=LEVEL, produce più output durante l’esecuzione;
• -V, –version, stampa su standard output la versione del programma.
Mentre le opzioni che esprimono vincoli per la risoluzione del problema sono
le seguenti:
• -i, –incremental, risolvere il problema in maniera incrementale;
• -m, –min, minimizza la funzione oggetto;
• -M, –max, massimizza la funzione oggetto;
• -n, –no-optimization, verificare soltanto la soddisfacibilità;
• -r, –no-mip, considerare variabili intere come reali;
• -e, –enumerate, usare il costoso metodo dell’enumerazione;
• -pM, –pricing=M, da usare insieme al metodo del simplesso, sceglie di
usare lo pricing method M;
• -s, –simplex, usare il metodo del simplesso.
Le opzioni di vincolo sulla risoluzione del problema non verranno modificate
in alcun modo.
4.2.1
Modifiche a ppl_lpsol
Per la programmazione parallela è stata usata a libreria POSIX Threads
Programming [3]. Verrano descritte le principali modifiche in maniera sintetica. Non è stato implementato un thread-pool: i thread da eseguire possono
essere al massimo 8. Se ppl_lpsol_mt riceve in input più di 8 file, ne leggerà
i primi 8, gli altri file verranno ignorati.
È stata introdotta l’inizializzazione a livello di libreria fornita dall’interfaccia C
if (ppl_library_initialize() < 0)
fatal("cannot initialize the Parma Polyhedra Library");
La funzione
static void process_options(int argc, char* argv[]);
4.2 ppl_lpsol
44
è stata modificato in modo che sia capace di fare il parsing di più file in input,
che rappresentano i problemi da risolvere. ppl_lpsol fa uso della libreria
glpk che, dopo alcuni tentativi di parallelizzare il programma, ha causato
problemi dimostrando di non essere thread-safe. A causa di questo problema
il procedimento della risoluzione del problema è stato diviso in due funzioni.
Dato un problema in input infatti, c’è una prima fase di preparazione del
problema. In questa prima fase si legge il problema e se ne crea l’ambiente
per tale problema. Questa prima fase è rappresentata dalla funzione
static pthread_t solve(char* file_name);
Alla fine, la funzione solve crea un thread worker al quale passa il costrutto di tipo thread_args_t specificamente preparato per il problema da
affrontare:
1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct {
ppl_Constraint_System_t ppl_cs ;
ppl_Linear_Expression_t ppl_objective_le ;
ppl_dimension_type * integer_variables ;
ppl_dimension_type num_integer_variables ;
mpz_t den_lcm ;
char * input_file_name ;
FILE * output_file ;
int dimension ;
# ifdef PPL_LPSOL_SUPPORTS_TIMINGS
struct timeval saved_ru_utime ;
# endif
} thread_args_t ;
solve inizializza i campi nella maniera dovuta. Tale costrutto servirà al futuro thread di tipo p_thread per usare i metodi forniti dalla PPL. Il nuovo
thread rappresenta la seconda fase della risoluzione del problema ed esso
eseguirà la funzione
static void* thread_solve(void* vp);
Qui si andrà a operare con gli strumenti forniti dalla PPL. Prima di tutto,
all’interno di thread_solve la PPL va inizializzata a livello di thread:
if (ppl_thread_initialize() < 0)
fatal("cannot thread-initialize the Parma Polyhedra Library");
Nella fase finale di thread_solve vengono finalizzate tutte le componenti del
costrutto di tipo thread_args_t. A differenza di ppl_lcdd_mt, la libreria va
4.2 ppl_lpsol
45
finalizzata esplicitamente dato che non si dispone in C del meccanismo dei
distruttori di un oggetto:
(void) ppl_thread_finalize();
Per riassumere, la funzione solve viene chiamata per ogni problema in input
e ogni chiamata viene risolta in sequenza. Ogni chiamata di solve genera
un nuovo thread che continua con la risoluzione del problema usando però
la PPL. In altre parole la risoluzione di un problema in ppl_lpsol è stata
parallelizzata a metà.
Sia ora il programma ppl_lpsol_mt il programma ppl_lpsol parallelizzato come descritto sopra. Le opzioni che sono state lasciate ed eventualmente
modificate in ppl_lpsol_mt sono le seguenti:
• -CSECS, –max-cpu=SECS, limita il tempo di utilizzo della CPU a SECS
secondi, a livello di processo;
• -RMB, –max-memory=MB, limita l’utilizzo di della memoria a MB megabyte, a livello di processo;
• -h, –help, stampa il testo dell’help su standard output;
• -oPATH, –output=PATH, tutti gli output vengono salvati come file nella
directory PATH, i nuovi file avranno lo stessi nome (assieme alla vecchia
estensione) dei file in input, ma con l’aggiunta della stringa .out alla
fine;
• -V, –version, stampa su standard output la versione del programma.
Come per ppl_lcdd_lpsol, è stata lasciata anche l’opzione –verbose, ma
non è stata adeguatamente testata dal momento che ogni thread potrebbe
impegnare lo standard output senza sincronizzazione. È stata tolta del tutto
l’opzione -c.
4.2.2
Prova pratica
ppl_lpsol_mt con la PPL thread-unsafe
Presi in input più di un problema da risolvere, ppl_lpsol_mt che fa uso della
PPL thread-unsafe è semplicemente undefined behavior. Le variabili staticamente allocabili della PPL non sono TLS. Come nel caso di ppl_lcdd_mt,
l’esito degli output è imprevedibile.
4.2 ppl_lpsol
46
ppl_lpsol e ppl_lpsol_mt su singolo problema
Si vogliono confrontare le prestazioni di ppl_lpsol e ppl_lpsol_mt su singoli problemi, con l’intento di riuscire a vedere eventuali inefficienze introdotte dal meccanismo TLS. ppl_lpsol userà la PPL thread-unsafe, mentre
ppl_lpsol_mt userà la versione thread-safe. Nella tabella appena sotto è
possibile vedere un confronto dei tempi (espresso in secondi) di esecuzione di
ogni singolo file elencato. Ogni valore è una media di più prove eseguite.
markashare2.mps
kb2.mps
mas76.mps
blend.mps
mas74.mps
boeing1.mps
lseu.mps
opt1217.mps
ppl_lpsol ppl_lpsol_mt
0.16
0.16
0.27
0.27
2.48
2.54
3.56
7.49
5.01
5.22
5.85
6.71
21.66
23.02
62.85
67.19
ppl_lpsol_mt con più problemi
Per risolvere più problemi alla volta, ppl_lpsol_mt necessita che questi problemi siano risolvibili tutti quanti con gli stessi vincoli. Si intende che tutti
i problemi devono essere risolvibili con l’unica configurazione di opzioni che
l’utente dà al programma. Il test verrà fatto sul seguente insieme di file:
ppl_lpsol
markashare2.mps
0.16
0.27
kb2.mps
mas76.mps
2.48
blend.mps
3.56
mas74.mps
5.01
boeing1.mps
5.85
lseu.mps
21.66
opt1217.mps
62.85
Il tempo richiesto per eseguirli tutti quanti in sequenza sarebbe di almeno
102 secondi, con ppl_lpsol. Con ppl_lpsol_mt sono il tempo richiesto è di
67.8 secondi, per eseguirli tutti quanti. Si noti anche che ppl_lpsol_mt, per
eseguire tutti i file, ha richiesto tanti secondi quanti ne richiede il problema
opt1217.mps, che è il più complesso da risolvere.
Conclusioni
In questo lavoro di tesi si è partiti da una panoramica generale sugli approcci
da assumere per scrivere una generica libreria thread-safe. In particolare ci si
è concentrati sulle tecniche per rendere thread-safe una libreria esistente (originariamente sviluppata per thread singoli e quindi thread-unsafe). In seguito
è stato selezionato l’approccio che meglio si adatta al caso della PPL. Sono
state fornite le caratteristiche dell’ambiente di sviluppo e si sono discusse le
linee guida da usare nella scelta fra le varie alternative.
Sono stati discussi i vari livelli della thread-safety di una libreria, arrivando alla conclusione che l’opzione migliore per la PPL è il livello conditionallythread-safe.
Sono state approfondite alcune implementazioni del meccanismo Thread
Local Storage. In seguito ad una serie di valutazioni si è arrivati a optare per
la specifica fornita dallo standard C++11, specifica che è stata studiata per
esteso per conoscerne al meglio le caratteristiche. Si è quindi passati alla fase
di implementazione che ha richiesto, fra le altre cose, la ricerca sistematica
delle occorrenze di variabili staticamente allocate.
La fase di inizializzazione della PPL è stata spezzata in due: inizializzazione
a livello di libreria e a livello di thread. Tale cambiamento nel processo di
inizializzazione, non più implicita, comporta un intervento diretto da parte
dell’utente, che deve ricordarsi di inizializzare la PPL ogni volta che crea un
nuovo thread. Per aiutare l’utente è stata introdotta una funzione wrapper
che inizializza automaticamente la PPL a livello di thread. In seguito il lavoro
è stato esteso per rendere thread-safe anche l’interfaccia verso il linguaggio
C della PPL.
Per verificare la correttezza della soluzione adottata sono stati fatti dei
test tramite programmi demo della PPL, modificati a loro volta in modo
che lavorassero in ambiente multithread. Si è verificato che la PPL produce
risultati corretti per ppl_lcdd_mt e ppl_lpsol_mt. Sia con ppl_lcdd_mt
che con ppl_lpsol_mt si è verificato che in un processo a singolo thread la
versione thread-safe della PPL risulta leggermente più lenta. Si è verificato che
in ambienti a thread multipli il vantaggio in termini di velocità di esecuzione
4.2 ppl_lpsol
48
è sostanziale.
Il lavoro svolto ha permesso di garantire la thread-safety di una vasta
porzione della PPL, e costituisce un primo e sostanziale passo per ottenere una
versione della PPL thread-safe. Possibili estensioni future potranno riguardare
questi punti:
• estendere la thread-safety alle interfacce Java, Prolog e OCaml;
• adattare la documentazione della PPL spiegando l’implementazione adottata per la thread-safety, fornendo esempi su cosa non si può fare;
• testare la portabilità della soluzione adottata, utilizzando compilatori
che non siano GCC e Clang;
• trovare una soluzione per rendere thread-safe la classe Watchdog, che
implementa dei meccanismi di timeout per la PPL.
Ringraziamenti
Vorrei ringraziare in particolar modo i miei genitori Tamara e Valentin, i
quali mi hanno dato l’opportunità di intraprendere questo cammino e mi
hanno supportato sia durante i momenti di successo che nei momenti più
difficili. Ringrazio il mio relatore Enea Zaffanella, professore dal quale non
ho mai smesso di imparare; che mi ha offerto la possibilità di arricchire la
mia esperienza con argomenti che mi appassionano più degli altri nel vasto
mondo dell’informatica; e professore che ogni ateneo vorrebbe avere. Un altro
ringraziamento importante per la mia formazione va a Gianfranco Rossi,
Roberto Bagnara, Alessandro Zaccagnini, Grazia Lotti, Federico Bergenti e
Alessandro Dal Palù. Ringrazio i miei compagni e le compagne di studio
che hanno reso questo percorso più vario e divertente: Francesco Trombi,
Daniela Pedroni, Sebastian Davrieux, Jacopo Fagio Freddi, Paolo Grossi,
Alessio Bortolotti, Victoria Nica, Luca Cirani, Eleonora Fontanesi, Federico
Bertoli e tutti coloro che rendevano le pause più interessanti davanti alla
macchinetta del caffè.
Ringrazio la mia costante voglia di migliorare
Bibliografia
[1] BUGSENG s.r.l.
PPL: Parma Polyhedra Library
http://bugseng.com/products/ppl/
[2] Boost Developers
Boost: C++ Libraries
http://www.boost.org/
[3] Austin Group
POSIX Thread Programming
https://computing.llnl.gov/tutorials/pthreads/
[4] GCC Team
GCC: GNU Compiler Collection
https://gcc.gnu.org/
[5] LLVM Team
clang: a C language family frontend for LLVM
http://clang.llvm.org/
[6] Intel Compilers
Intel C++ Compiler
https://software.intel.com/en-us/c-compilers
[7] Steve Lewin-Berlin (Intel)
Hot and Safe: a Beginner’s Guide to Multithreaded Libraries
[8] ISO
C++ International Standard: Final Draft International Standard
ISO/IEC JTC1 SC22 WG21 N 3290, 11 Aprile 2011
BIBLIOGRAFIA
[9] Free Software Foundation
GNU Development Tools, nm
http://linux.die.net/man/1/nm
[10] C++ Enthusiasts
C++ compiler support
http://en.cppreference.com/w/cpp/compiler_support
[11] Junio Hamano
git
http://git-scm.com/doc
[12] Free Software Foundation
The GNU Multiple Precision Arithmetic Library
https://gmplib.org/manual/Reentrancy.html
[13] Anthony Williams
C++ Concurrency In Action: Practical Multithreading
Manning Publications Co., 2012.
[14] Free Software Foundation
The GNU Linear Programming Kit
https://www.gnu.org/software/glpk
51