Threads
Lernziele
Unterschied zwischen Prozessen und Threads kennen lernen
Thread-API in C nutzen kĂśnnen
Was sind Threads
Wiederholung
Bisher gelernt
Virtualisierung einer CPU â also mit ÂťSchedulingÂŤ den Anschein erwecken, als gäbe es viele CPUs
Virtualisierung von Speicher â also mittels ÂťAdressräumenÂŤ den Anschein erwecken, als hätte jedes Programm seinen ganz eigenen Speicher
Dabei galt implizit immer die Annahme, dass ein Prozess aus einem einzigen AusfĂźhrungsstrang besteht
Was sind Threads?
Anstelle nur eines Ausfßhrungsstrangs besitzen multi-threaded Programme mehrere Ausfßhrungsstränge
Jeder dieser Ausfßhrungsstränge (engl. thread) kann grundsätzlich wie ein Prozess verstanden werden
Ein wichtiger Unterschied: Während jeder Prozess seinen ganz eigenen Adressraum besitzt, teilen sich Threads einen Adressraum und kÜnnen auf dieselben Daten zugreifen
Eigenschaften von Threads
Threads werden grundsätzlich wie Prozesse behandelt
BenÜtigen einen Programm Counter (PC) fßr die nächste Instruktion
Haben eigene Register
Laufen zwei Threads auf einer CPU, muss ein Context-Switch stattfinden
FĂźr den Context Switch wird ein Thread Control Block (TCB) analog zum Process Control Block (PCB) benĂśtigt
Wichtiger Unterschied: Der Adressraum bleibt beim Context-Switch von Threads der gleiche
Multi-Thread-Adressräume
Threads laufen unabhängig, rufen eigene Routinen mit eigenen lokalen Variablen und Rßcksprungadressen auf und benÜtigen daher dedizierte Stacks (engl. thread-local storage)
Offensichtlich: Parallelisierung, sobald mehrere CPUs bereitstehen, kĂśnnen Aufgaben gleichzeitig durchgefĂźhrt werden
Etwas subtiler: WĂźrde ein Prozess aufgrund einer I/O-Operation geblockt werden, kĂśnnte ein weitere Thread im Prozess weiterlaufen und somit das blockieren des Prozesses vermeiden
Vorteil: Threads greifen auf dieselben Daten innerhalb eines Prozesses zu.
Threads und Determinismus
Threads laufen nicht deterministisch, da Routinen im Thread unabhängig vom Aufrufer laufen
Was dann tatsächlich läuft wird durch den Scheduler gesteuert
Problem verschärft sich noch, da Threads auf dieselben Daten zugreifen
Konsequenz: Nicht-deterministische Programmläufe und Ergebnisse
OSTEP Kapitel 26.2 zum Erzeugen von Threads (in C)
Scheduling Beispiel
Hier: ErhĂśhen eines Counters um 1
Variable fĂźr Counter liegt bei Adresse 0x8049a1c
Wert der Variable wird in Register eax geladen (Zeile 1)
Wert wird um 1 erhĂśht (Zeile 2)
Neuer Wert wird aus Register zurĂźck an Andresse 0x8049a1c geschrieben
Annahme: Es gbit twei Threads, T1 und T2
T1 fĂźhrt den Code aus und erhĂśht den Wert (z.B. 50) um 1
In Register eax steht nun 51
Jetzt: Timer Interrupt, Betriebssystem speichert T1
Programm Counter
Register einschlieĂlich eax
Nun wird T2 ausgefĂźhrt
T2 lädt den Wert von 0x8049a1c
In eax steht nun 50 (Jeder Thread hat seine eigenen virtualisierten Register!!!1)
eax wird erhĂśht und zurĂźckgeschrieben
Jetzt findet nochmal ein Context-Switch statt und T1 wird wieder ausgefĂźhrt
Alle Register werden geladen
In eax steht nun 51
T1 fĂźhrt nun noch Zeile 3 aus und schreibt 51 an 0x8049a1c
Was sollte aber eigentlich in unserer Variable stehen?
⥠OSTEP Kapitel 26.3 fßr detaillierten Trace des Ablaufs
Race Conditions
Ergebnis abhängig vom Timing bei der Ausfßhrung von Code: Race Condition
FĂźhrt zu einem nicht-deterministischen Programmfehler, der in der Regel schwer zu finden ist (Ergebnis heiĂt auf engl. indeterminate)
Code, der die Race Condition auslĂśsen kann wird kritischer Abschnitt (engl. critical section) genannt
Greift auf eine gemeinsame Variable (engl. shared variable) bzw. gemeinsame Ressource (engl. shared resource).
Durch wechselseitigen Ausschluss (engl. mutual exclusion) wird erreicht, dass wenn sich ein Thread in einem kritischen Abschnitt befindet, kein anderer Thread auf diesen Code zugreifen kannâŚ
Aber wie?
Thread API
Fragestellung: Welche Schnittstellen muss das Betriebssystem bereitstellen, um Threads zu erstellen und zu kontrollieren?
Am Beispiel von POSIX (Portable Operating System Interface) Systemen:
Ein Thread erzeugen
Auf einen Thread warten
Locks = Ausschluss aus kritischem Abschnitt
Condition Variable (dt. Monitor = Synchronisationsmechanismus)
4 Argumente erforderlich: thread
, attr
, start routine
, arg
thread
Pointer auf Struktur vom Typ
pthread_t
, wird genutzt um mit dem Thread zu interagieren
attr
Spezifiziert die Attribute des Threads (GrĂśĂe d. Stacks, Scheduling Priorität etc.)
start_routine
Function Pointer auf Routine, die vom Thread ausgefĂźhrt werden soll
arg
Argument, das an den Anfang des Threads Ăźbergeben wird
Auf einen Thread warten
pthread_t
Spezifiziert den Thread, auf den gestartet wird
value_ptr
Zeiger auf den RĂźckgabewert der Routine
Einen Thread mittels
pthread_create
zu erzeugen und direkt danach mittelspthread_join
auf dessen Beendigung zu warten ist natĂźrlich nicht sonderlich sinnvollIn diesem Fall ist ein einfacher Prozeduraufruf einfacher.
Wenn der Thread jedoch gestartet wird, und erst im späteren Verlauf des Programms auf seine Beendigung gewartet wird, macht es wieder Sinn
Locks
Funktionen fĂźr den gegenseitigen Ausschluss
Mutex: Mutual Exclusion Object
Wie funktioniert ein Mutex?
Kritischer Abschnitt kann nur betreten werden, wenn man (der Code) in Besitz des Mutex ist
Beispiel hier:
pthread_mutex_loc
setzt das Mutex, und kein anderer Thread (mit dem gleichen Code) kann diesen Code-Abschnitt betreten, bevorpthread_mutex_unlock
aufgerufen wurdeWie wird das erreicht?
Ist der Lock gesetzt, kehrt die Routine
pthread_mutex_lock
erst zurĂźck, nachdem das Mutex freigegeben wurde
Condition Variables
Verständigung zwischen Threads
z.B. ein Thread wartet auf etwas von einem anderen Thread
pthread_cond_wait
lässt den Thread warten, bis er das entsprechende Signal bekommt, dass er weitermachen kann
Zusammenfassung
Durch das Aufrufen einer
lock
-Routine wird versucht Zugriff auf ein ein Lock, also eine Art Token zu erhalten, die das alleinige AusfĂźhrungsrecht eines kritischen Abschnitts sicherstelltRuft jemand anderes nun
lock
auf, kehrt diese Methode solange nicht zurĂźck, wie das Lock nicht freigegeben wurdeErst wenn der ursprĂźngliche Aufrufer durch
unlock
das Lock wieder frei gibt, kehrt eine der bisher aufgerufenelock
-Routinen zurßck und lässt die Ausfßhrung des kritischen Abschnitts zu
Anforderungen an ein Lock
Mutual Exclusion: Locks mĂźssen gegenseitigen Ausschluss ermĂśglichen
Fairness: Hat jeder Thread eine faire Chance das Lock zu erhalten, sobald es wieder freigegeben wird? Anders ausgedrĂźckt: Es muss vermieden werden, dass ein Thread verhungert (engl. starve), wenn er âewigâ auf das Lock wartet
Overhead: Hält sich der Aufwand fßr einen einzelnen Thread in Grenzen, um das Lock zu erhalten und wieder freizugeben? Wie verhält es sich mit der Performance, wenn es viele Threads und ggf. mehrere CPUs gibt?
Ansatz 1: Interrupts deaktivieren
Durch Ausschalten der Interrupts, wird Code in einem kritischen Abschnitt nicht mehr unterbrochen
Pro und Contra deaktivierte Interrupts
Vorteil:
Einfach
Nachteil(e):
Privilegierte Operation kĂśnnte ggf. missbraucht werden, indem am Anfang vom ganzen Programm
lock und erst am Ende `` unlock
aufgerufen wirdFunktioniert nicht auf Multi-CPU-Systemen
Wird, wenn Ăźberhaupt, nur vom Betriebssystem intern genutzt, um auf eigene Datenstrukturen zuzugreifen oder um ungĂźnstige Interrupt-Situationen vorzubeugen
Ansatz 2: Einfache Variable
Weshalb kann die Verwendung einer einfachen Variablen als Lock nicht genĂźgen?
Zur Erinnerung: Im POSIX-System verwenden wir auch eine Variable in Kombination mit lock
- und unlock
-Routinen. Wie funktioniert das?
Grundidee:
Einfache Variable (ein Flag) als Lock nutzen
Aufruf von
lock
testet ob Flag == 1 ist, falls nicht wird dieses auf 1 gesetzt und Thread hat jetzt das LockRuft nun ein zweiter Thread
lock
auf, wartet er solange bis das Flag wieder 0 ist
Probleme
Problem 1 (Korrektheit): Durch ungĂźnstige Context-Switches schaffen es beide Threads nun zu laufen, da beide Threads das Flag auf 1 setzen konnten
Problem 2 (Performance): Während ein Thread auf das Lock wartet, prßft er ständig die Variable und verschwendet Rechenzeit des anderen Prozesses z.B. durch Context-Switch, Speicherzugriff, etc. (eng. spin-waiting)
Ansatz 3: Spin Locks mit Test-and-Set
Hardware-UnterstĂźtzung bereits in den 1960ern, die heute noch zum Einsatz kommt
Test-and-Set bzw. Atomic Exchange
Liefert den ÂťaltenÂŤ Wert an der Adresse von
old_ptr
Setzt gleichzeitig den Wert an
*old_ptr
auf den Inhalt von newWichtig: Diese Operationen werden atomar aufgerufen!
Es funktioniert weil...
Szenario 1
Annahme, Thread ruft
lock
auf und kein anderer Thread hält das Lock (flag==0)TestAndSet
liefert 0, also wird der aufrufende Thread nicht weite prĂźfen (spinning)Das Flag wird auĂerdem auf 1 gesetzt (atomar!), d.h. kein anderer Thread kann das Lock erhalten
Ist der Thread fertig, ruft er
unlock
auf und das Flag wird wieder auf 0 gesetzt
Szenario 2
Annahme, Ein anderer Thread hält das Lock (flag==1)
TestAndSet
liefert 1, also wird der aufrufende Thread nicht weite prĂźfen (spinning)Das Flag wird auĂerdem auf 1 gesetzt (atomar!), das ist aber nicht schlimm
Solange der andere Thread das Lock besitzt, liefert
TestAndSet
immer 1
Spinning Lock
Wir haben das erste funktionierende Lock gebaut
Spin Lock: Einfachste Variante, dreht sich (engl. to spin) solang unter der Verwendung von CPU Cycles bis das Lock verfĂźgbar wird
BenĂśtigt einen Preemtive Scheduler (Sie erinnern sich!?), der Threads via Timer unterbricht, damit ein anderer Thread laufen kann ď ohne Preemtive Scheduling machen Spin Locks auf Systemen mit nur einer CPU keinen Sinn, da der Thread sonst nie die CPU freigeben wĂźrde
In x86 z.B. via
xchg
realisiert (x86 Instruction Set Reference1): â... This instruction is useful for implementing semaphores or similar data structures for process synchronization.â
Spin Locks: Kurze Betrachtung
Korrektheit
Wenn, wie zuvor umgesetzt, stellen Spin Locks sicher, dass nur ein einziger Thread einen kritischen Abschnitt ausfĂźhren kann
Fairness
Nope, es kann sein, dass der wartende Thread niemals in den kritischen Abschnitt kommt, und kĂśnnen somit zum âverhungernâ eines anderen Threads fĂźhren
Performanz
Jeder wartende Thread nutzt eine Zeitscheibe zum PrĂźfen, daher auf 1-CPU-Systemen nicht sonderlich performant, auf Multi-CPU Systemen ganz OK, solange Anzahl der Threads ~ Anzahl der CPUs
Ansatz 4: Compare-and-Swap
Wird ebenfalls in gängigen Systemen (x86 via cmpxchg
) eingesetzt2
PrĂźft, ob der Wert an Adresse von
ptr
dem Wert vonexpected
entsprichtFalls ja, wird der Wert von
new
gesetztDann wird der (unveränderte) Wert von
original
zurĂźck geleifertNutzung analog zu Test-and-Swap
Yield
Anstelle zu warten, kann ein Thread sich selbst mittels
yield
ÂťentschedulenÂŤ, d.h. ein anderer Thread wird anstelle dessen geplantFunktioniert gut bei zwei Threads
Was aber, wenn viele Threads um das Lock konkurrieren?
Dann werden sehr viele Context Switches ausgefĂźhrt, und wie wir wissen, lohnen sich diese erst ab einer gewissen Laufzeit
Bisher wird alles mehr oder weniger dem Zufall Ăźberlassen.
Der Scheduler entscheidet darßber, welcher Thread als nächstes ausgefßhrt wird
Je nachdem welcher Thread ausgewählt wird, wartet dieser auf das Lock oder entschedult (mittels
yield
) sich, während ein anderer Thread hätte ausgefßhrt werden kÜnnenIn beiden Fällen ist dies reine Verschwendung von Rechenkapazität
Wie kann diese Situation verbessert werden? Hier hilft uns das Betriebssystem!
Referenzen
Last updated