docs/pws2009/threads.pod

=encoding utf-8

=head1 Threads in dynamischen Sprachen und warum Perl-Pseudo-Threads sterben sollten

Wie man am Titel sieht, soll es im folgenden um zwei verwandte Themen
gehen. Einerseits möchte ich grundsätzliche Gedanken über Threads
liefern, einige Vorurteile ausräumen und erläutern, wie Threads in
dynamischen Sprachen implementiert werden und warum dies so ist.

Andererseits möchte ich erläutern, warum Perl keine Threads unterstützt
und weshalb Perls sogenannte Threads eher sterben sollten, da sie
mehr Schaden anrichten als sie helfen. Letzteres muss nicht einmal zu
Inkompatibilitäten führen: da Perl-Threads keine sind, lassen sie sich
effizient ohne emulieren.

=head2 Was ist ein Thread - Eine Begriffsbestimmung

Am einfachsten erklärt man Threads, in dem man sie Prozessen
gegenüberstellt:

Prozesse haben (üblicherweise) einen eigenen Adressraum, d.h. Variablen
existieren als Kopie in jedem Prozess und sind unabhängig
voneinander. Außerdem besitzt ein Prozess eine "Continuation", d.h. im
wesentlichen den aktuellen "Ort" der Programmausführung. Unter Unix
kommen dann noch andere Ressourcen wie File-Descriptoren hinzu, aber im
wesentlichen ist es das.

Ein Thread nun ist im wesentlichen ein abgespeckter Prozess (daher werden
sie auch oft "LWPs" - Light Weight Processes genannt), bei dem eine oder
mehrere dieser Ressourcen gemeinsam genutzt werden, insbesondere der
Adressraum. Daher kann man Threads auch als Untereinheit von Prozessen
ansehen: ein Prozess kann aus ein oder mehreren Threads bestehen, die sich
alle den gleichen Adressraum (die gleichen Variableninhalte) teilen.

Bei Threads gibt eine Menge verschiedene Variationen. Die wichtigsten sind:

=over 4

=item Kooperative Threads

Die "Urform" der Threads - diese Threads werden "kooperativ" genannt,
nicht, weil sie es sind, sondern, weil sie es sein müssen: Sobald
ein Thread ausgeführt wird, läuft dieser ohne Unterbrechung, bis er
freiwillig die CPU an einen anderen Thread abgibt. Tut ein Thread dies
nicht, läuft nichts anderes im System.

Manchmal werden Kooperative Threads auch Koroutinen, Fibers oder
Continuations genannt, was genau genommen falsch ist, aber im wesentlichen
bezeichnen diese Begriffe dasselbe.

Die Hauptvorteile von kooperativen Threads ist die vergleichsweise
einfache Programmierung (Race-conditions sind wesentlich einfacher zu
vermeiden) und ihre hohe Effizienz. Hauptnachteil ist, daß ein einzelner
wildgewordener Thread das gesamte System lahmlegen kann.

Windows 3.11, das Oberon-System oder das Coro-Modul von Perl sind
Beispiele für kooperatives Threading.

=item Preemptive Threads

Um das Problem der Monopolisierung des Rechners durch einen unkooperativen
(weil z.B. ferhlerhaften) Thread zu umgehen, wurden "preemptive" Threads
erfunden: Diese werden ohne ihr Zutun regelmäßig "unterbrochen" (z.B.
durch einen Timer) und dadurch von der CPU "verdrängt" (preempted).

Diese Art von Threads wird oft auch "time-slicing" (Zeitscheibenverfahren)
genannt, da hierbei ein Thread üblicherweise eine bestimmte Zahl von
Zeiteinheiten erhält und, wenn er in dieser Zeit die CPU nicht freigibt,
wird er automatisch verdrängt.

Hauptvorteil von preemptiven Systemen ist, daß man wildgewordene
Programme abbrechen kann, d.h. sie legen nicht das gesamte System
lahm. Hauptnachteil ist, daß ihre Benutzung sehr kompliziert ist: auch
Experten machen regelmäßig Fehler und erzeugen Race-Conditions.

Neuere Windows-Versionen, alle Unix-Versionen und insbesondere alle
Thread-Systeme dynamischer Sprachen (d.h. Ruby, Python usf.) benutzen
dieses Verfahren.

=item "Kernel-Threads" und "Userspace-Threads"

Ein weiterer wichtiger Unterschied zwischen Thread-Systemen ist, ob sie
vom Betriebssystem selbst implementiert werden oder innerhalb eines
Prozesses.

In letzterem Fall teilen sich alle Threads dieselbe Prozess-Continuation,
was nichts anderes bedeutet, als daß diese Threads niemals parallel
laufen können (z.B. auf einem SMP-System).

Der Begriff "Kernel-Thread" bezeichnet im Gegensatz dazu die Variante, bei
er die Threads tatsächlich parallel/gleichzeitig arbeiten können, obwohl
dies nicht zwangsweise im "Kernel" implementiert werden muss.

Userspace-Threads sind im allgemeinen um ein vielfaches schneller als
Kernel-Threads - die Userspace-Threading-Bibliothek, die von Coro benutzt
wird schaltet mehr als 100 mal schneller zwischen Threads um als der
Linux-Kernel. Selbst auf Perl-Ebene schalten die Userspace-Threads von
Coro mehr als 14 mal schneller als die Linux-Kernel-Threads.

Kernel-Threads verschärfen gegenüber Userspace-Threads die Problematik
der Programmierung nochmals. Ein gutes Beispiel ist MythTV, ein
C++-Programm, daß Threads benutzt: auf Single-Core-Systemen arbeitet
es meist korrekt, auf Multi-Core-Systemen sind crashes aber an der
Tagesordnung, da der Programmierer offenbar nicht damit rechnet,
daß Speicherzugriffe nicht mehr atomar sind bzw. die Gefahr einer
Race-Condition stark erhöht ist.

=back

=head2 Wozu wurden Threads erfunden, wozu eignen sie sich?

=head3 Single-Cores

Multi-Core und Multiprozessorsysteme sind erst seit kurzer Zeit
verbreitet. Die überwiegende Mehrheit der Rechner besitzt nach wie vor
nur einzelne CPUs.

Moderne CPUs besitzen im allgemeinen spezielle Hardware, um Prozesse zu
unterstützen, z.B. eine Memory-Management-Unit (MMU) um den Adressraum
zu verwalten und einen Translation-Lookaside-Buffer (TLB) um das ganze zu
beschleunigen.

Da jeder Prozess seinen eigenen Adressraum besitzt, muss die MMU bei jedem
Umschalten neu konfiguriert werden, Caches wie der TLB gehen häufig
verloren. Dies kann die Performance empfindlich beeinflussen, da die meisten
CPUs nur einen Zustand im Cache behalten können.

Die natürliche Lösung gegen zu viele Rekonfigurationen sind weniger
Rekonfigurationen bei Prozesswechseln. Wechselt man den Adressraum nicht,
so erhält man Threads auf natürliche Weise, da die CPU einfach den alten
Adressraum weiter benutzt.

Daher stammt der Name "Light Weight Processes" (leichtgewichtige
Prozesse): Threads werden hier als Prozesse mit weniger "Zustand" behandelt.

Dies beschleunigt das Prozessumschalten erheblich, vor allem auf älteren
Systemen.

=head3 Multiprozessor- oder Multi-Core-Systeme

Ein weit verbreiteter Irrtum ist es, daß Threads sich gut für die
Parallelisierung eignen, d.h. echte Parallelverarbeitung auf einem
Multiprozessorsystem.

Dies ist allerdings nicht der Fall: Das Problem, daß es nur eine Instanz
der Caches oder MMU gibt, existiert bei mehreren CPU-Kernen nicht, da
diese alle ihren eigenen Cache besitzen.

Im Gegenteil: Dadurch, daß Threads viele Ressourcen gemeinsam nutzen,
muss das Betriebssystem durch aufwändige (und langsame) Verwaltung
sicherstellen, daß auch alle CPUs im System den gleichen Zustand haben.

Wenn z.B. ein Prozess mit mehreren Threads auf einem Multi-Core-System
arbeitet und der eine Thread vom Betriebssystem Speicher anfordert,
so muss das Betriebssystem synchron alle anderen CPUs anhalten, ihnen
den neuen Zustand mitteilen, warten, bis alle den Zustand übernommen
haben und kann erst dann weiterarbeiten. Auf einem Dual-Core-System mag
dies noch akzeptabel sein, bei mehr Cores wird dies aber schnell sehr
aufwändig, auf Mehrfachprozessorsystemen, bei denen die Kommunikation
zwischen CPUs noch länger braucht, wird dies schnell inakzeptabel.

Aber auch der ganze normale Speicher-Cache wird nicht effizient
genutzt: Da Threads alle Variablen gemeinsam nutzen, liegen gemeinsam
genutzte Variablen nicht im lokalen Cache einer CPU, im Gegenteil, sie
wandern häufig zwischen den Caches hin- und her, d.h. die Kommunikation
läuft über den (vergleichsweise langsamen) Hauptspeicher ab.

Letzteres wird häufig dadurch verhindert, daß man unterschiedliche
Speicherbereiche in jedem Thread verwendet. Allerdings wird dies durhc
eine zusätzliche Indirektion bei jedem Zugriff bezahlt. Perls, die diese
Methode benutzten, werden dadurch zwischen 15 und ca. 200% langsamer als
Perls, die dies nicht tun (auch ohne Parallelbetrieb).

Ein Vorteil von Threads ist die vergleichsweise schnelle Kommunikation
über den Speicher, was bei Programmen, die viel Kommunikation betreiben,
einen großen Gewinn bedeutet, wenn die alternative z.B. Kommunikation über Sockets ist.

Moderne Betriebssysteme erlauben es aber ausnahmslos, einzelne
Speicherbereiche gemeinsam zu nutzen, so daß Prozesse mit selektiv
gemeinsam genutzten Speicher wesentlich effizienter auf Mehr-CPU-Systemen
arbeiten, als Threads.

=head3 Ein Benchmark: Matrixmultiplikation

Am folgenden "Benchmark" wird dies deutlich. Das Benchmark-Programm
implementiert eine parallel Matrixmultiplikation, bei der einzelne
Zeilen und Spalten an vier "Arbeits-Threads" gesendet werden, die eine
Skalarmultiplikation durchführen und an einen Ergebnis-Thread senden.

Dabei kann es Perl-Pseudo-Threads (die parallel arbeiten) und Coro-Threads
benutzen.

Das Programm findet sich unter F<http://data.plan9.de/matmult>, ist aber
für die Diskussion nicht relevant.

=begin latex

 \begin{center}
 \includegraphics{mat2.eps}
 \end{center}

=end latex

=head4 Beschreibung

Das doppelt-logarithmische Diagramm stellt die Zahl der Anzahl der
Matrixmultiplikationen pro Sekunde der Matrixgröße gegenüber. Die
Größe der Matrix hat qualitativ wenig Einfluss, was zählt, ist der
relative Unterschied zwischen den Verfahren. Das Testsystem benutzt eine
relativ moderne Quad-Core-CPU.

Im Diagramm finden sich vier Kurven: die unterste (und langsamste)
entspricht den Perl-Pseudo-Threads, die auf allen Cores laufen dürfen und
dies auch weitestgehend tun (die CPU-Auslastung betrug ca. 80%). Darüber
befindet sich das gleich Programm, allerdings diesmal auf einen einzelnen
Core beschränkt (was im Prinzip Unsinn ist, da immer noch die gleiche
Anzahl Threads arbeitet).

Darüber befinden sich zwei Kurven, die Coro-Threads benutzen. Die obere,
langsamere wurde auf einen Perl mit Pseudo-Thread-Support erzeugt,
die darunterliegende auf einem Perl ohne, das Programm selbst war
identisch. Da Coro-Threads nicht parallel arbeiten, liefen beide auf einem
einzigen Core.

Was sofort auffällt, ist der starke Unterschied zwischen echter
Parallelverarbeitung und kooperativen Coro-Threads: Die Version mit echten
Threads ist am rechten Rand mehr als I<326> mal I<langsamer> als die
Version die nur eine CPU benutzt.

Weniger auffällig, aber umso interessanter ist es, daß das
Perl-Thread-Programm auf einer einzelnen CPU fast 20 mal schneller
arbeitet als auf 4 Cores, obwohl beide Pseudothread-Varianten identisch
sind.

Der Unterschied der Coro-Varianten ist in diesem Diagramm nicht sehr
deutlich, beträgt immerhin noch zwischen 25% und 35%, im Vergleich zu den
Pseudothread-Varianten verschwindend gering.

=head4 Diskussion

Der Benchmark wurde absichtlich so gewählt, daß die Kommunikation einen
entscheidenden Bestandteil bildet.

Die Pseudo-Threads von Perl sind hierbei doppelt im Nachteil: einerseits
besitzen sie keinen gemeinsamen Adressraum (d.h. Variablen müssen kopiert
werden), anderseits ist es durch Threads implementiert, und hat dadurch
einen erhöhten Aufwand bei der Verwaltung (doppelte Indirektion).

Dies allein kann den gewaltigen Unterschied von 31595% (!) erklären.

Der Unterschied zwischen den beiden Pseudothreaded-Kurven ist schwerer zu
erklären: Da die Programme identisch sind, muss der Unterschied durch
andere Effekte erklärt werden: Die Kommunikation läuft in einem Fall
weitestgehend über den CPU-Cache, während dieser bei mehrere Cores
nicht benutzt werden kann, hier also die Kommunikation über den L2-Cache
(ca. 10 mal langsamer) oder den Hauptspeicher (ca. 50 mal langsamer)
abläuft.

Hinzu kommt, daß während der Kommunikation gemeinsam genutzte Variablen
gegen Zugriffe anderer CPUs geschützt werden müssen. Versuchen
mehrere Threads gleichzeitig auf diese zuzugreifen, müssen sie sich
synchronisieren. Auch dies läuft über den Hauptspeicher ab und ist noch
dazu wesentlich aufwändiger.

Der Unterschied von ca. 30% bei den beiden Coro-Varianten erklärt
sich alleine dadurch, daß ein Pseudo-Threaded-Perl wesentlich mehr
Aufwand treiben muss, um die Adressräume der Threads künstlich
auseinanderzuhalten, mithin dupliziert es die Arbeit der MMU die in der
CPU eingebaut ist und, obwohl Perl effizienter ist, ist eine Software-MMU
natürlich immer noch langsamer als eine gut optimierte Hardwarelösung.


=head2 Die Herausforderung: Threads in dynamischen Sprachen

Thread-Programmierung ist komplex, vor allem, wenn die verwendeten Threads
preemptiv sind oder sogar echt parallel arbeiten. Ein gutes Beispiel ist
das "double-checked-locking"-Pattern, daß zehn Jahre in jedem Fachbuch
stand, bis man feststellte, daß es nicht stabil arbeitet.

Für "hardwarenahe" Sprachen ist es sehr viel einfacher, mit Threads
umzugehen: viele Datentypen (z.B.  C<int> in C) erlauben atomare Zugriffe,
Locking ist explizit, der Zugriff selbst (nur lesend oder verändernd) ist
genau festgelegt und so weiter. Und wenn's Crasht dann Crasht's eben - in
C ist das nichts ungewöhnliches.

Für Sprachen wie Perl oder Python stellt sich das ganze anders
dar: Selbst "einfache" Integer-Variablen sind auf C-Ebene durch viele
Variablen repräsentiert. Dadurch gibt es keine atomaren Zugriffe, d.h.
auch lesend zugreifen kann man nur indem man ein Lock benutzt. Hinzu
kommt, daß viele Zugriffe, die man als Programmierer als "Lesezugriff"
ansieht, intern tatsächlich Schreibzugriffe auslöst. Ein Beispiel:

   $a .= $b;

Ganz klar, C<$a> wird verändert. Nicht so offensichtlich ist, daß auch
C<$b> verändert werden kann, z.B. wenn C<$b> noch nicht als String
vorliegt.

Da dies interne Details des Interpreters betrifft, ist es für einen Perl-
(Python-, Ruby- ...) Programmierer nicht ersichtlich, wann man ein Lock/Mutex
benutzen muss und wann nicht.

Hinzu kommt, daß Programmierer von dynamischen Sprachen einen gewissen
Schutz erwarten: Eine Exception zur Laufzeit ist akzeptabel, ein Crash
oder gar Memory-Corruption ist es nicht.

=head3 Lösungen: Perl

Threads wurden zum ersten (und letzten) Mal in Perl 5.005 eingeführt. Das
5.005-Modell implementierte echte Threads, die, sofern die Platform
Kernel-Threads unterstützte, auch parallel liefen.

Crashes in diesem Modell waren die Tagesordnung. Offenbar war es
Perl-Programmierern nicht zu vermitteln, daß man in zwei Threads nicht
gleichzeitig (auch nicht lesend) auf dieselbe Variable zugreifen darf.

Dies führte dazu, daß dieses Modell in Verruf geriet, obwohl
es eigentlich nur das lieferte, was Threads bedeuten: schwierige
Programmierung, Crashes und so weiter.

Tatsächlich zeigt dies ein generelles Problem bei Threads auf: Sie lassen
sich nicht abstrahieren: Stabile Programme erhält man unter anderem
durch Abstraktion und Schichtung: einzelne Aufgaben werden in Komponenten
abstrahiert (z.B. Module), die die Details regeln, während der Benutzer
dieser Komponenten sich nicht um die Details kümmern braucht.

Bei Sicherheit funktioniert dies nicht gut: TLS z.B. ist sehr sicher,
dennoch darf man (wie Microsoft schon häufig bewiesen hat) nicht naiv
davon ausgehen, daß eine Verbindung abhörsicher oder privat wäre, nur,
weil man TLS benutzt.

Ähnlich ist es mit Threads: sicherlich kann man Queues und ähnliches
abstrahieren, aber in vielen Fällen muss man dennoch wissen, wie diese
Komponenten implementiert sind, um z.B. Deadlocks zu vermeiden. Und wenn
man Daten an andere Threads sendet, muss man sowieso immer selbst den
Zugriff regeln, oder selbst Kopien herstellen.

Dies ist grundsätzlich unvereinbar mit dem Anspruch, Threads in
Hochsprachen sicher gestalten zu können, es sei denn, man belegt alles
mit einem Lock. In der Praxis wird die Implementation dadurch aber sehr
viel langsamer, was den Vorteil durch Parallelverarbeitung mehr als
aufwiegt.

Das 5.005-Modell verschwand also wieder in der Versenkung, dennoch wollte
man irgendwelche "Threads" anbieten.

=head4 Windows - Wurzel allen Übels

Und die "Rettung" war Windows. Genaugenommen die Ineffizienz von Windows.


Revision:	1.3
Committed:	Sat Jan 17 05:42:02 2009 UTC (17 years, 9 months ago) by root
Branch:	MAIN
Changes since 1.2:	+125 -7 lines
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	=encoding utf-8
2
3			=head1 Threads in dynamischen Sprachen und warum Perl-Pseudo-Threads sterben sollten
4
5			Wie man am Titel sieht, soll es im folgenden um zwei verwandte Themen
6			gehen. Einerseits möchte ich grundsätzliche Gedanken über Threads
7			liefern, einige Vorurteile ausräumen und erläutern, wie Threads in
8			dynamischen Sprachen implementiert werden und warum dies so ist.
9
10			Andererseits möchte ich erläutern, warum Perl keine Threads unterstützt
11			und weshalb Perls sogenannte Threads eher sterben sollten, da sie
12			mehr Schaden anrichten als sie helfen. Letzteres muss nicht einmal zu
13			Inkompatibilitäten führen: da Perl-Threads keine sind, lassen sie sich
14			effizient ohne emulieren.
15
16			=head2 Was ist ein Thread - Eine Begriffsbestimmung
17
18			Am einfachsten erklärt man Threads, in dem man sie Prozessen
19			gegenüberstellt:
20
21			Prozesse haben (üblicherweise) einen eigenen Adressraum, d.h. Variablen
22			existieren als Kopie in jedem Prozess und sind unabhängig
23			voneinander. Außerdem besitzt ein Prozess eine "Continuation", d.h. im
24			wesentlichen den aktuellen "Ort" der Programmausführung. Unter Unix
25			kommen dann noch andere Ressourcen wie File-Descriptoren hinzu, aber im
26			wesentlichen ist es das.
27
28			Ein Thread nun ist im wesentlichen ein abgespeckter Prozess (daher werden
29			sie auch oft "LWPs" - Light Weight Processes genannt), bei dem eine oder
30			mehrere dieser Ressourcen gemeinsam genutzt werden, insbesondere der
31			Adressraum. Daher kann man Threads auch als Untereinheit von Prozessen
32			ansehen: ein Prozess kann aus ein oder mehreren Threads bestehen, die sich
33			alle den gleichen Adressraum (die gleichen Variableninhalte) teilen.
34
35			Bei Threads gibt eine Menge verschiedene Variationen. Die wichtigsten sind:
36
37			=over 4
38
39			=item Kooperative Threads
40
41			Die "Urform" der Threads - diese Threads werden "kooperativ" genannt,
42			nicht, weil sie es sind, sondern, weil sie es sein müssen: Sobald
43			ein Thread ausgeführt wird, läuft dieser ohne Unterbrechung, bis er
44			freiwillig die CPU an einen anderen Thread abgibt. Tut ein Thread dies
45			nicht, läuft nichts anderes im System.
46
47			Manchmal werden Kooperative Threads auch Koroutinen, Fibers oder
48			Continuations genannt, was genau genommen falsch ist, aber im wesentlichen
49			bezeichnen diese Begriffe dasselbe.
50
51	root	1.2	Die Hauptvorteile von kooperativen Threads ist die vergleichsweise
52			einfache Programmierung (Race-conditions sind wesentlich einfacher zu
53			vermeiden) und ihre hohe Effizienz. Hauptnachteil ist, daß ein einzelner
54			wildgewordener Thread das gesamte System lahmlegen kann.
55
56	root	1.1	Windows 3.11, das Oberon-System oder das Coro-Modul von Perl sind
57			Beispiele für kooperatives Threading.
58
59			=item Preemptive Threads
60
61			Um das Problem der Monopolisierung des Rechners durch einen unkooperativen
62			(weil z.B. ferhlerhaften) Thread zu umgehen, wurden "preemptive" Threads
63			erfunden: Diese werden ohne ihr Zutun regelmäßig "unterbrochen" (z.B.
64			durch einen Timer) und dadurch von der CPU "verdrängt" (preempted).
65
66			Diese Art von Threads wird oft auch "time-slicing" (Zeitscheibenverfahren)
67			genannt, da hierbei ein Thread üblicherweise eine bestimmte Zahl von
68			Zeiteinheiten erhält und, wenn er in dieser Zeit die CPU nicht freigibt,
69			wird er automatisch verdrängt.
70
71	root	1.2	Hauptvorteil von preemptiven Systemen ist, daß man wildgewordene
72			Programme abbrechen kann, d.h. sie legen nicht das gesamte System
73			lahm. Hauptnachteil ist, daß ihre Benutzung sehr kompliziert ist: auch
74			Experten machen regelmäßig Fehler und erzeugen Race-Conditions.
75
76	root	1.1	Neuere Windows-Versionen, alle Unix-Versionen und insbesondere alle
77			Thread-Systeme dynamischer Sprachen (d.h. Ruby, Python usf.) benutzen
78			dieses Verfahren.
79
80			=item "Kernel-Threads" und "Userspace-Threads"
81
82			Ein weiterer wichtiger Unterschied zwischen Thread-Systemen ist, ob sie
83			vom Betriebssystem selbst implementiert werden oder innerhalb eines
84			Prozesses.
85
86			In letzterem Fall teilen sich alle Threads dieselbe Prozess-Continuation,
87			was nichts anderes bedeutet, als daß diese Threads niemals parallel
88			laufen können (z.B. auf einem SMP-System).
89
90			Der Begriff "Kernel-Thread" bezeichnet im Gegensatz dazu die Variante, bei
91			er die Threads tatsächlich parallel/gleichzeitig arbeiten können, obwohl
92			dies nicht zwangsweise im "Kernel" implementiert werden muss.
93
94			Userspace-Threads sind im allgemeinen um ein vielfaches schneller als
95			Kernel-Threads - die Userspace-Threading-Bibliothek, die von Coro benutzt
96			wird schaltet mehr als 100 mal schneller zwischen Threads um als der
97			Linux-Kernel. Selbst auf Perl-Ebene schalten die Userspace-Threads von
98			Coro mehr als 14 mal schneller als die Linux-Kernel-Threads.
99
100	root	1.2	Kernel-Threads verschärfen gegenüber Userspace-Threads die Problematik
101			der Programmierung nochmals. Ein gutes Beispiel ist MythTV, ein
102			C++-Programm, daß Threads benutzt: auf Single-Core-Systemen arbeitet
103			es meist korrekt, auf Multi-Core-Systemen sind crashes aber an der
104			Tagesordnung, da der Programmierer offenbar nicht damit rechnet,
105			daß Speicherzugriffe nicht mehr atomar sind bzw. die Gefahr einer
106			Race-Condition stark erhöht ist.
107
108	root	1.1	=back
109
110			=head2 Wozu wurden Threads erfunden, wozu eignen sie sich?
111
112			=head3 Single-Cores
113
114			Multi-Core und Multiprozessorsysteme sind erst seit kurzer Zeit
115			verbreitet. Die überwiegende Mehrheit der Rechner besitzt nach wie vor
116			nur einzelne CPUs.
117
118			Moderne CPUs besitzen im allgemeinen spezielle Hardware, um Prozesse zu
119			unterstützen, z.B. eine Memory-Management-Unit (MMU) um den Adressraum
120			zu verwalten und einen Translation-Lookaside-Buffer (TLB) um das ganze zu
121			beschleunigen.
122
123			Da jeder Prozess seinen eigenen Adressraum besitzt, muss die MMU bei jedem
124			Umschalten neu konfiguriert werden, Caches wie der TLB gehen häufig
125			verloren. Dies kann die Performance empfindlich beeinflussen, da die meisten
126			CPUs nur einen Zustand im Cache behalten können.
127
128			Die natürliche Lösung gegen zu viele Rekonfigurationen sind weniger
129			Rekonfigurationen bei Prozesswechseln. Wechselt man den Adressraum nicht,
130			so erhält man Threads auf natürliche Weise, da die CPU einfach den alten
131			Adressraum weiter benutzt.
132
133			Daher stammt der Name "Light Weight Processes" (leichtgewichtige
134			Prozesse): Threads werden hier als Prozesse mit weniger "Zustand" behandelt.
135
136			Dies beschleunigt das Prozessumschalten erheblich, vor allem auf älteren
137			Systemen.
138
139			=head3 Multiprozessor- oder Multi-Core-Systeme
140
141			Ein weit verbreiteter Irrtum ist es, daß Threads sich gut für die
142			Parallelisierung eignen, d.h. echte Parallelverarbeitung auf einem
143			Multiprozessorsystem.
144
145			Dies ist allerdings nicht der Fall: Das Problem, daß es nur eine Instanz
146			der Caches oder MMU gibt, existiert bei mehreren CPU-Kernen nicht, da
147			diese alle ihren eigenen Cache besitzen.
148
149			Im Gegenteil: Dadurch, daß Threads viele Ressourcen gemeinsam nutzen,
150			muss das Betriebssystem durch aufwändige (und langsame) Verwaltung
151			sicherstellen, daß auch alle CPUs im System den gleichen Zustand haben.
152
153			Wenn z.B. ein Prozess mit mehreren Threads auf einem Multi-Core-System
154	root	1.2	arbeitet und der eine Thread vom Betriebssystem Speicher anfordert,
155			so muss das Betriebssystem synchron alle anderen CPUs anhalten, ihnen
156			den neuen Zustand mitteilen, warten, bis alle den Zustand übernommen
157			haben und kann erst dann weiterarbeiten. Auf einem Dual-Core-System mag
158			dies noch akzeptabel sein, bei mehr Cores wird dies aber schnell sehr
159			aufwändig, auf Mehrfachprozessorsystemen, bei denen die Kommunikation
160			zwischen CPUs noch länger braucht, wird dies schnell inakzeptabel.
161
162			Aber auch der ganze normale Speicher-Cache wird nicht effizient
163			genutzt: Da Threads alle Variablen gemeinsam nutzen, liegen gemeinsam
164			genutzte Variablen nicht im lokalen Cache einer CPU, im Gegenteil, sie
165			wandern häufig zwischen den Caches hin- und her, d.h. die Kommunikation
166			läuft über den (vergleichsweise langsamen) Hauptspeicher ab.
167
168			Letzteres wird häufig dadurch verhindert, daß man unterschiedliche
169			Speicherbereiche in jedem Thread verwendet. Allerdings wird dies durhc
170			eine zusätzliche Indirektion bei jedem Zugriff bezahlt. Perls, die diese
171			Methode benutzten, werden dadurch zwischen 15 und ca. 200% langsamer als
172			Perls, die dies nicht tun (auch ohne Parallelbetrieb).
173
174			Ein Vorteil von Threads ist die vergleichsweise schnelle Kommunikation
175			über den Speicher, was bei Programmen, die viel Kommunikation betreiben,
176			einen großen Gewinn bedeutet, wenn die alternative z.B. Kommunikation über Sockets ist.
177
178			Moderne Betriebssysteme erlauben es aber ausnahmslos, einzelne
179			Speicherbereiche gemeinsam zu nutzen, so daß Prozesse mit selektiv
180			gemeinsam genutzten Speicher wesentlich effizienter auf Mehr-CPU-Systemen
181			arbeiten, als Threads.
182
183	root	1.3	=head3 Ein Benchmark: Matrixmultiplikation
184
185	root	1.2	Am folgenden "Benchmark" wird dies deutlich. Das Benchmark-Programm
186			implementiert eine parallel Matrixmultiplikation, bei der einzelne
187			Zeilen und Spalten an vier "Arbeits-Threads" gesendet werden, die eine
188			Skalarmultiplikation durchführen und an einen Ergebnis-Thread senden.
189
190			Dabei kann es Perl-Pseudo-Threads (die parallel arbeiten) und Coro-Threads
191			benutzen.
192	root	1.1
193	root	1.2	Das Programm findet sich unter F<http://data.plan9.de/matmult>, ist aber
194			für die Diskussion nicht relevant.
195	root	1.1
196			=begin latex
197
198			\begin{center}
199			\includegraphics{mat2.eps}
200			\end{center}
201
202			=end latex
203
204	root	1.3	=head4 Beschreibung
205
206	root	1.2	Das doppelt-logarithmische Diagramm stellt die Zahl der Anzahl der
207			Matrixmultiplikationen pro Sekunde der Matrixgröße gegenüber. Die
208			Größe der Matrix hat qualitativ wenig Einfluss, was zählt, ist der
209			relative Unterschied zwischen den Verfahren. Das Testsystem benutzt eine
210			relativ moderne Quad-Core-CPU.
211
212			Im Diagramm finden sich vier Kurven: die unterste (und langsamste)
213			entspricht den Perl-Pseudo-Threads, die auf allen Cores laufen dürfen und
214			dies auch weitestgehend tun (die CPU-Auslastung betrug ca. 80%). Darüber
215			befindet sich das gleich Programm, allerdings diesmal auf einen einzelnen
216			Core beschränkt (was im Prinzip Unsinn ist, da immer noch die gleiche
217			Anzahl Threads arbeitet).
218
219			Darüber befinden sich zwei Kurven, die Coro-Threads benutzen. Die obere,
220			langsamere wurde auf einen Perl mit Pseudo-Thread-Support erzeugt,
221			die darunterliegende auf einem Perl ohne, das Programm selbst war
222			identisch. Da Coro-Threads nicht parallel arbeiten, liefen beide auf einem
223			einzigen Core.
224
225			Was sofort auffällt, ist der starke Unterschied zwischen echter
226	root	1.3	Parallelverarbeitung und kooperativen Coro-Threads: Die Version mit echten
227			Threads ist am rechten Rand mehr als I<326> mal I<langsamer> als die
228			Version die nur eine CPU benutzt.
229
230			Weniger auffällig, aber umso interessanter ist es, daß das
231			Perl-Thread-Programm auf einer einzelnen CPU fast 20 mal schneller
232			arbeitet als auf 4 Cores, obwohl beide Pseudothread-Varianten identisch
233			sind.
234
235			Der Unterschied der Coro-Varianten ist in diesem Diagramm nicht sehr
236			deutlich, beträgt immerhin noch zwischen 25% und 35%, im Vergleich zu den
237			Pseudothread-Varianten verschwindend gering.
238
239			=head4 Diskussion
240
241			Der Benchmark wurde absichtlich so gewählt, daß die Kommunikation einen
242			entscheidenden Bestandteil bildet.
243
244			Die Pseudo-Threads von Perl sind hierbei doppelt im Nachteil: einerseits
245			besitzen sie keinen gemeinsamen Adressraum (d.h. Variablen müssen kopiert
246			werden), anderseits ist es durch Threads implementiert, und hat dadurch
247			einen erhöhten Aufwand bei der Verwaltung (doppelte Indirektion).
248
249			Dies allein kann den gewaltigen Unterschied von 31595% (!) erklären.
250
251			Der Unterschied zwischen den beiden Pseudothreaded-Kurven ist schwerer zu
252			erklären: Da die Programme identisch sind, muss der Unterschied durch
253			andere Effekte erklärt werden: Die Kommunikation läuft in einem Fall
254			weitestgehend über den CPU-Cache, während dieser bei mehrere Cores
255			nicht benutzt werden kann, hier also die Kommunikation über den L2-Cache
256			(ca. 10 mal langsamer) oder den Hauptspeicher (ca. 50 mal langsamer)
257			abläuft.
258
259			Hinzu kommt, daß während der Kommunikation gemeinsam genutzte Variablen
260			gegen Zugriffe anderer CPUs geschützt werden müssen. Versuchen
261			mehrere Threads gleichzeitig auf diese zuzugreifen, müssen sie sich
262			synchronisieren. Auch dies läuft über den Hauptspeicher ab und ist noch
263			dazu wesentlich aufwändiger.
264
265			Der Unterschied von ca. 30% bei den beiden Coro-Varianten erklärt
266			sich alleine dadurch, daß ein Pseudo-Threaded-Perl wesentlich mehr
267			Aufwand treiben muss, um die Adressräume der Threads künstlich
268			auseinanderzuhalten, mithin dupliziert es die Arbeit der MMU die in der
269			CPU eingebaut ist und, obwohl Perl effizienter ist, ist eine Software-MMU
270			natürlich immer noch langsamer als eine gut optimierte Hardwarelösung.
271
272
273			=head2 Die Herausforderung: Threads in dynamischen Sprachen
274
275			Thread-Programmierung ist komplex, vor allem, wenn die verwendeten Threads
276			preemptiv sind oder sogar echt parallel arbeiten. Ein gutes Beispiel ist
277			das "double-checked-locking"-Pattern, daß zehn Jahre in jedem Fachbuch
278			stand, bis man feststellte, daß es nicht stabil arbeitet.
279
280			Für "hardwarenahe" Sprachen ist es sehr viel einfacher, mit Threads
281			umzugehen: viele Datentypen (z.B. C<int> in C) erlauben atomare Zugriffe,
282			Locking ist explizit, der Zugriff selbst (nur lesend oder verändernd) ist
283			genau festgelegt und so weiter. Und wenn's Crasht dann Crasht's eben - in
284			C ist das nichts ungewöhnliches.
285
286			Für Sprachen wie Perl oder Python stellt sich das ganze anders
287			dar: Selbst "einfache" Integer-Variablen sind auf C-Ebene durch viele
288			Variablen repräsentiert. Dadurch gibt es keine atomaren Zugriffe, d.h.
289			auch lesend zugreifen kann man nur indem man ein Lock benutzt. Hinzu
290			kommt, daß viele Zugriffe, die man als Programmierer als "Lesezugriff"
291			ansieht, intern tatsächlich Schreibzugriffe auslöst. Ein Beispiel:
292
293			$a .= $b;
294
295			Ganz klar, C<$a> wird verändert. Nicht so offensichtlich ist, daß auch
296			C<$b> verändert werden kann, z.B. wenn C<$b> noch nicht als String
297			vorliegt.
298
299			Da dies interne Details des Interpreters betrifft, ist es für einen Perl-
300			(Python-, Ruby- ...) Programmierer nicht ersichtlich, wann man ein Lock/Mutex
301			benutzen muss und wann nicht.
302
303			Hinzu kommt, daß Programmierer von dynamischen Sprachen einen gewissen
304			Schutz erwarten: Eine Exception zur Laufzeit ist akzeptabel, ein Crash
305			oder gar Memory-Corruption ist es nicht.
306
307			=head3 Lösungen: Perl
308
309			Threads wurden zum ersten (und letzten) Mal in Perl 5.005 eingeführt. Das
310			5.005-Modell implementierte echte Threads, die, sofern die Platform
311			Kernel-Threads unterstützte, auch parallel liefen.
312
313			Crashes in diesem Modell waren die Tagesordnung. Offenbar war es
314			Perl-Programmierern nicht zu vermitteln, daß man in zwei Threads nicht
315			gleichzeitig (auch nicht lesend) auf dieselbe Variable zugreifen darf.
316
317			Dies führte dazu, daß dieses Modell in Verruf geriet, obwohl
318			es eigentlich nur das lieferte, was Threads bedeuten: schwierige
319			Programmierung, Crashes und so weiter.
320
321			Tatsächlich zeigt dies ein generelles Problem bei Threads auf: Sie lassen
322			sich nicht abstrahieren: Stabile Programme erhält man unter anderem
323			durch Abstraktion und Schichtung: einzelne Aufgaben werden in Komponenten
324			abstrahiert (z.B. Module), die die Details regeln, während der Benutzer
325			dieser Komponenten sich nicht um die Details kümmern braucht.
326
327			Bei Sicherheit funktioniert dies nicht gut: TLS z.B. ist sehr sicher,
328			dennoch darf man (wie Microsoft schon häufig bewiesen hat) nicht naiv
329			davon ausgehen, daß eine Verbindung abhörsicher oder privat wäre, nur,
330			weil man TLS benutzt.
331
332			Ähnlich ist es mit Threads: sicherlich kann man Queues und ähnliches
333			abstrahieren, aber in vielen Fällen muss man dennoch wissen, wie diese
334			Komponenten implementiert sind, um z.B. Deadlocks zu vermeiden. Und wenn
335			man Daten an andere Threads sendet, muss man sowieso immer selbst den
336			Zugriff regeln, oder selbst Kopien herstellen.
337
338			Dies ist grundsätzlich unvereinbar mit dem Anspruch, Threads in
339			Hochsprachen sicher gestalten zu können, es sei denn, man belegt alles
340			mit einem Lock. In der Praxis wird die Implementation dadurch aber sehr
341			viel langsamer, was den Vorteil durch Parallelverarbeitung mehr als
342			aufwiegt.
343	root	1.2
344	root	1.3	Das 5.005-Modell verschwand also wieder in der Versenkung, dennoch wollte
345			man irgendwelche "Threads" anbieten.
346	root	1.2
347	root	1.3	=head4 Windows - Wurzel allen Übels
348	root	1.2
349	root	1.3	Und die "Rettung" war Windows. Genaugenommen die Ineffizienz von Windows.
350	root	1.2
351