Embed Size (px)
Citation preview
Markus Klußmann, Amjad SaadehInstitut für Informatik
Pthreads
Pthreads
von Markus Klußmann und Amjad Saadeh
Pthreads, 19.12.2012 2
Inhalt
- Was sind Threads?- Prozess vs. Thread
- Kurzer Überblick POSIX- Threads im Betriebssystem- Erzeugung und Verwaltung von Threads- Koordination von Threads
- Datenverwaltung- Mutex- und Conditions-Variablen
- Thread-Scheduling- Prioritäten- Prioritätsinversion
- Programmiermodelle mit Threads- Anwendungsbeispiele
Pthreads, 19.12.2012 3
Was sind Threads?
- Übersetzung: Ausführungsfaden- teilen sich den gleichen Adressraum / Speicher- nur Ausführungsstapel privat- gehören immer zu einem Prozess- können parallel zueinander laufen- viele Implementierungen dieses Modells:
- Java-Threads- Python-Threads- Pthreads
Pthreads, 19.12.2012 4
Prozess vs. Threads
Prozess- eigener Adressraum- => privater Speicher- Daten müssen „aufwendig“ übermittelt
werden- werden immer vom Betriebssystem
verwaltet werden
Thread- gemeinsamer Adressraum- => gemeinsamer Speicher / Heap- Verwaltung übernimmt
Threadbibliothek- können aber vom Betriebssystem
unterstützt / verwaltet werden
Pthreads, 19.12.2012 5
Kurzer Überblick POSIX
- „Portable Operation System Interface“- erste Version 1988 verabschiedet (IEE Std 1003.1-1988)- aktuelle Version IEEE Std 1003.1-2008- Pthreads ab 1995- definiert u.a.:
- C-Systemaufrufe und C-Header- einige Hilfsprogramme- grundlegende I/O-Schnittstellen
- (teilweise) kompatible Betriebssysteme:- Linux (Distributionsabhängig)- Mac OS X- Windows (mit entsprechenden Erweiterungen)- Solaris
Pthreads, 19.12.2012 6
Threads im Betriebssystem
Wie werden Threads verwaltet?
Pthreads, 19.12.2012 7
Keine Unterstützung durch OS
Pthreads, 19.12.2012 8
1:1 Abbildung
Pthreads, 19.12.2012 9
m:n Abbildung
Pthreads, 19.12.2012 10
Beispiel: Solaris
Pthreads, 19.12.2012 11
Erzeugung und Verwaltung von Threads
- erzeugen durch:int pthread_create(
pthread_t *thread,const pthread_attr_t *attr,void *(*start_routine)(void *),void *arg)
- warten bis Thread beendet ist:int pthread_join(pthread_t thread, void **valuep)
- falls kein join für Thread vorliegt:int pthread_detach(pthread_t thread)
- Thread von außen abbrechen:int pthread_cancel(pthread_t thread)
Pthreads, 19.12.2012 12
Erzeugung und Verwaltung von Threads
Beispiel: Matrix-Multiplikation
Pthreads, 19.12.2012 13
Erzeugung und Verwaltung von Threads
Pthreads, 19.12.2012 14
Koordination von Threads
Wie kommunizieren Threads?
Wie vermeide ich Konsistenzkonflikte?
Wie beende ich den Trhead?
Wie vermeide ich Deadlocks?
Pthreads, 19.12.2012 15
Datenverwaltung- globale Variablen
- liegen im gemeinsamen Speicher- können Pointer auf Heap sein => gemeinsamer Speicher
int i;
void add() { i++; }
int main(int argc, char* argv[]) {
int num;
scanf(„%i“, argv[1], &num);
pthread_t threads[num];
int j;
for (j=0; j < num; j++) pthread_create(*(threads[j]));
for (j=0; j < num; j++) pthread_join(*(threads[j]));
printf(„%i\n“, i);
return;
}
Pthreads, 19.12.2012 16
DatenverwaltungSchlüssel- Schlüssel als globale Variable- jeder Thread hat eigenen Datensatz der an Schlüssel gebunden ist- sofern keine Daten von Thread gesetzt: NULL
pthread_key_t key;
void print_test() {
int* num = pthread_getspecific(key);
printf(„%i“, *num);
}
void test() {
int num = random_number;
pthread_setspecific(key, &num);
print_test();
}
int main(int argc, char* argv[]) {pthread_key_create(key);
pthread_t threads[4];int i;for (i=0; i<4; i++) pthread_create(*(threads[i]));for (i=0; i<4; i++) pthread_join(*(threads[i]));
return;
}
Pthreads, 19.12.2012 17
Mutex- und Conditionvariablen
- Synchronisation an manchen Stellen notwendig bzw. ratsam- z.B.: zwei Threads sollen die gleiche Variable manipulieren- => ein Thread sollte warten bis der andere fertig ist- Lösungen:
- Busy-Waiting- wartenden Thread blockieren
- Mutexvariablen für gegenseitigen Ausschluss- Conditionvariablen zum realisieren von Signalmechanismen
Pthreads, 19.12.2012 18
Mutex- und Conditionvariablen
Mutex:phtread_mutex_lock(&randomly_chosen_mutex);
// kritische Manipulation
pthread_mutex_unlock(&randomly_chosen_mutex);
Condition:
phtread_mutex_lock(&condition_mutex);
while (!condition) {
pthread_cond_wait(&condition_var, contition_mutex);
}
pthread_mutex_unlock(&condition_mutex);
Pthreads, 19.12.2012 19
Beispiel: Read-Write-Lock
typedef struct {
int reader;
bool writer;
pthread_mutex_t mutex;
pthread_cond_t cond;
} rw_lock;
void rw_lock_init(rw_lock *rwl) {
rwl>reader = 0;
rwl>writer = false;
pthread_cond_init(&(rwl>mutex), NULL);
pthread_mutex_init(&(rwl>cond), NULL);
}
Pthreads, 19.12.2012 20
Beispiel: Read-Write-Lock
void read_lock(rw_lock *rwl) {
pthread_mutex_lock(&(rwl>mutex));
while (rwl>writer)
pthread_cond_wait(&(rwl>cond), &(rwl>mutex));
rwl>reader++;
pthread_mutex_unlock(&(rwl>mutex));
}
void read_unlock(rw_lock *rwl) {
pthread_mutex_lock(&(rwl>mutex));
rwl>reader;
if (rwl>reader == 0)
pthread_cond_signal(&(rwl>cond));
pthread_mutex_unlock(&(rwl>mutex));
}
Pthreads, 19.12.2012 21
Beispiel: Read-Write-Lock
void write_lock(rw_lock *rwl) {
pthread_mutex_lock(&(rwl>mutex));
while ((rwl>reader > 0) || rwl>writer)
pthread_cond_wait(&(rwl>cond), &(rwl>mutex));
rwl>writer = true;
pthread_mutex_unlock($(rwl>mutex));
}
void write_unlock(rw_lock *rwl) {
pthread_mutex_unlock(&(rwl>mutex));
rwl>writer = false;
pthread_cond_broadcast($(rwl>cond));
pthread_mutex_unlock(&(rwl>mutex));
}
Pthreads, 19.12.2012 22
Thread Scheduling
Wie kann der Programmierer das Thread-Scheduling beeinflussen?
Pthreads, 19.12.2012 23
Thread Scheduling
- nur möglich, wenn POSIXTHREAD_PRIORITY_SCHEDULING Macro definiert ist
- kann zur Laufzeit festgestellt werden
- für Scheduling muss eine Datenstruktur vom Typ struct shed_param existieren
- int shed_priority (zwingend benötigt)
- Veränderung zur Laufzeit möglich
Pthreads, 19.12.2012 24
Priorität
- wie bevorzugt wird dieser Thread vom Bibliotheks-Scheduler behandelt- es gibt eine maximale Priorität (von Bibliothek vorgegeben)- es gibt eine minimale Priorität (von Bibliothek vorgegeben)
Pthreads, 19.12.2012 25
Scheduling Methoden
- SHED_FIFO (First In First Out)
- SHED_RR (Round Robbin)
- SHED_OTHER (Bibliotheksabhängig)
- kann zur Laufzeit geändert werden
Pthreads, 19.12.2012 26
SHED_FIFO (First In First Out)
- eine Warteschlange für jede Priorität
- immer der erste Thread aus Schlange höchster Priorität
- wird neuer Thread mit höherer Priorität als der aktuelle eingefügt:
→ aktuellen Thread unterbrechen und wichtigeren ausführen
Pthreads, 19.12.2012 27
SHED_RR (Round Robbin)
- CPU Zeit wird in Zeitscheiben aufgeteilt- Länge der Zeitscheiben ist von der Bibliothek vordefiniert- es wird nur die höchste Prioritätsebene betrachtet- die Prozesse in der höchsten ebene sind nacheinander an der Reiche und
können so lange rechnen wie die Zeitscheibe ist.
Pthreads, 19.12.2012 28
SHED_OTHER (Bibliotheksabhängig)
- nicht zwingend implementiert- vorhanden um sich an das Betriebssystem anpassen zu können- meist Prioritätsanpassung an I/O-Verhalten
- interaktive Threads bevorzugt- rechenintensive Threads benachteiligt
Pthreads, 19.12.2012 29
Scheduling Bereich
- gibt an welche anderen Threads beim Scheduling beachtet werden
- PTHREAD_SCOPE_PROCESS
- prozesslokales Scheduling- führt meist zu besseren Ergebnissen
- PTHREAD_SCOPE_SYSTEM
- globales Scheduling
- Kann mit pthread_attr_setscope(pthread_attr_t *attr, int scope) gesetzt werden
- Kann mit pthread_attr_getscope(pthread_attr_t *attr, int *scope) gelesen werden
Pthreads, 19.12.2012 30
SCS
Pthreads, 19.12.2012 31
PCS
Pthreads, 19.12.2012 32
Prioritätsinversion
- Probleme mit Mutexvariablen verhindern durch Anpassung der Priorität
Pthreads, 19.12.2012 33
Prioritätsinversion
- Mechanismen zur Umgehung
- Prioritäts-Obergrenze (PTHREAD_PRIO_PROTECT)
- Prioritätsvererbung (PTHREAD_PRIO_INHERIT)
- nichts (PTHREAD_PRIO_NONE)
Pthreads, 19.12.2012 34
Prioritäts-Obergrenze
- Konstante POSIX_THREAD_PRIO_PROTECT muss definiert sein
- Priorität der Obergrenze muss definiert werden- Thread der Mutexvariable sperrt bekommt die vordefiniert Priorität- zur Vermeidung von Prioritätsinversion muss diese Priorität gleich der höchsten
Priorität sein- niedriger Laufzeitaufwand- nicht fair (besonders wenn variable lange gesperrt wird)
Pthreads, 19.12.2012 35
Prioritätsvererbung
- Priorität eines Mutexinhabers wird angehoben sobald ein Thread höherer Priorität zugreifen möchte
- nach Freigabe erhält er seine ursprüngliche Priorität zurück- hoher Laufzeitaufwand- fairer, weil Priorität gleich bleibt
Pthreads, 19.12.2012 36
Programmiermodelle mit Threads
Pthreads, 19.12.2012 37
Master-Slave-Modell
- Master-Thread weist Slave-Threads Aufgaben zu
- Slave-Threads arbeiten diese ab und warten dann wieder auf Anweisungen des Master-Threads
Aufgabenverteilung
Pthreads, 19.12.2012 38
Worker-Modell
- arbeiten Aufgaben weitgehend unabhängig ab
- Worker können neue Aufgaben anlegen
- gut mit globalem Taskpool zu implementieren
Pthreads, 19.12.2012 39
Pipeline-Modell
- Aufgabe wird Stufe für Stufe abgearbeitet
- Zwischenergebnisse werden von Thread zu Thread weitergereicht
Input
Output
Stufe 1
Stufe 3
Stufe 4
Stufe 2
Pthreads, 19.12.2012 40
Client-Server-Modell
- Client-Thread stellt Anfrage an Server-Thread
- Server-Thread übergibt Ergebnis an Client zurück
- Bsp.:- GUI läuft als Client-Thread- eigentliche Berechnung
übernimmt Server-Thread
Client Server
Pthreads, 19.12.2012 41
Anwendungsbeispiele
- Server- Spiele- Video-/Bildbearbeitung- Datenkompression (pbzip)- Alle Anwendungen die größtenteils unabhängige Teilaufgaben durchführen- Livedemo: Primzahlfilter (Quellcode: http://goo.gl/kXamB)
Pthreads, 19.12.2012 42
Quellen:
http://de.wikipedia.org/wiki/Prioriätsinversion
http://pubs.opengroup.org/onlinepubs/009604599/functions/pthread_mutexattr_getprotocol.htmlhttp://pubs.opengroup.org/onlinepubs/9699919799/
Thomas Rauber, Gudula Rünger: Parallele Programmierung, Springer 2012
Margarita Esponda: OS_V8_Scheduling_Teil_2.key.pdf
