Multithreading - technisch beleuchtet
Vorwort
In diesem Artikel soll es mehr um den technischen Aspekt von Threads gehen, die
konkrete Implementierung ist nicht Teil dieses Artikels und wird hier nicht beschrieben. Als Syntax nutze ich zur Beschreibung der Algorithmen C Code, da dieser nativ ist und sich leicht auf andere Sprachen portieren lässt. Leider lässt es sich an manchen Stellen nicht vermeiden auch etwas tiefer in das System herein zu gehen und zum besseren Verständnis werde ich an der einen und an der anderen Stelle auch mal Assembler Code präsentieren. Bitte ignoriert einfach die vielen Rechtschreibfehler
, werde probieren die noch raus zu machen.
Warum dieses Thema
..., weil ich glaube das Software in Zukunft verstärkt multithreadingfähig sein muss um eine hohe Effiziens zu erreichen und man dies als Programmierer auch nutzen muss. Um dies aber auszunutzen muss man nicht nur wissen wie man Threads erstellt in einer Software, sondern auch was passiert und genau diesen Einblick möchte ich geben.
Einleitung
Um eine Einleitung zu geben, habe ich beschlossen kurz etwas zur Geschichte der Threads zu erzählen.
Zuerst konnte man auf einem Rechner immer nur genau ein Programm ausführen, das war zwar gut und schön, aber irgendwann dachte sich jemand das es doch noch toller wäre wenn man mehrere Programme zur selben Zeit ausführen könnte. Diese Idee bringt und direkt zum Multitasking. Jetzt konnten auf einem Rechner mehrere Prozesse/Programme laufen, nur ganz zufrieden mit dieser Lösung war man nicht. Wenn ein Prozess sich zum Beispiel um die Verwaltung des Spiels sich kümmert und der andere um die Graphik, ist zwischen diesen beiden Threads ein enormer Datenaustausch nötig. Beide Prozesse können so unter Umständen viel mehr an Speicher benötigen, unter Umständen sogar für die gleichen Dinge.
Man entwickelte daher das Multithreading, welches genau dieses Problem umging, da alle Threads den gleichen Adressraum hatten und nicht wie Prozesse einen eigenen. Der Vorteil lag darin, das der Datenaustausch jetzt viel einfacher war bzw. sogar wegfiel, da jeder Thread auf die gleiche Variable zugreifen kann. Wir werden später aber auch sehen das das uns aber auch eine Menge an Problemen und beschert.
Prozesse, Threads und andere Gemeinheiten
Bevor wir über Threads sprechen, müssen wir erstmal klären was Prozesse sind.
Prozesse sind streng genommen Einheiten die aus einem Adressraum und mindestens einem Thread bestehen. Man kann Prozesse auch etwas "lasch" als Programme bezeichnen, die gerade ausgeführt werden.
Ein Adressraum ist einfach nur ein Speicherbereich der durch die CPU ansprechbar ist. Jeder Prozess bekommt einen eigenen Adressraum und unser Betriebssystem achtet darauf, das wir nicht in den Adressraum eines anderen Prozesses "rutschen" und dort Unfug machen können.
Ein Thread, zu deutsch "Faden" wird auch häufig Aktivitätsträger genannt. Der Thread führt an sich unser Programm aus und wird vom Betriebssystem zur Verfügung gestellt.
Wozu Threads?
Der Hauptgrund für die Verwendung von (mehreren) Threads ist, das viele Anwendungen mehrere Aktivitäten auf einmal benötigen. Einige dieser Aktivitäten können auch blockieren (Eingaben, Timer etc.), in dieser Zeit können wir ohne Multithreading normalerweise nichts tun, und verschwenden so enorm viel Rechenpower.
Besonders in Spielen ist das wichtig, denn wenn wir z.B. Anno spielen und gerade unserem Mitspieler Tribut leisten wollen und den Betrag eingeben, möchten wir ja schon das andere Spieler noch was machen können und nicht das unser System ständig anhällt, nur weil Spieler X schon wieder Tribut errichten muss.
So ist es auch beliebt verschiedene Dinge in Spielen wie KI, Netzwerk, Eingaben und evtl. auch Ausgaben in eigenen Threads ablaufen zu lassen. In Zeiten von MultiCores bringt uns das unter Umständen sogar einen Geschwindigkeitsschub, aber auch viele Probleme und genau diese Probleme möchten wir uns gleich mal näher ansehen.
Betriebssysteme
Zunächst kommen wir aber zu ein paar Betriebssystemspeziefischen Dingen.
Unser Betriebssystem auf dem wir Multithreading betreiben möchten muss ja Threads umschalten können. Normalerweise werden die Threads aber nicht sagen "Hey, hier ich will die CPU abgeben", sondern eher das Gegenteil.
Deswegen brauch unser Betriebssystem einen Scheduler (ausgesprochen Skeduler) der genau das erledigt. Ein Scheduler sorgt dafür das die Threads mit einer hohen Priorität zuerst und vermehrt an die Reihe kommen, aber auch das kein Thread "verhungert", also jeder mal die CPU bekommt.
Bei einem Umschalt von Threads müssen verschiedene Dinge in dem sogenannten TCB (Thread Control Block) gespeichert oder wiederhergestellt werden. So zum Beispiel der Thread Zustand (wartend/blockierend, aktiv oder bereit), der Stack, Verweis auf den Adressraum, die Register und die oben genannten Scheduling Attribute (Priorität etc.), das übernimmt aber alles unser Betriebsystem.
Etwas Praxis....
Prozesse lassen sich in Windows Betriebssystemen mit
CreateProcess(...) und Threads mit
CreateThread(...) , welche Inhalt der WinAPI sind, erzeugen. In Unix funktioniert das ganze über den sogenannten
fork ("gabeln") Systemaufruf, der einfach eine identische Kopie erstellt und diese Kopie dann Code ausführen lässt.
Testfall
Wir wollen eine Software für eine große Bank entwerfen, diese Software soll auf irgendeinem Mainframe in Frankfurt laufen und alle Terminals sollen einen neuen Thread starten wenn sie Geld abbuchen wollen. Diesen Thread nennen wir abbuchen.
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
|
int Kontostand;
bool abbuchen(unsigned int Betrag)
{
if(Betrag <= Kontostand)
{
Kontostand = Kontostand - Betrag;
return true;
}
else return false;
}
|
Auf den ersten Blick sieht das doch ganz schnuckelig aus oder?
Ist es aber nicht, den hier stecken echt viele Tücken drin. Nehmen wir mal an zwei Benutzer wollen nahezu gleichzeitg von einem Konto Geld abbuchen. Zuerst ist Benutzer 1 an der Reihe und will 20 Euro abbuchen, Benutzer 2 40€. Der Kontostand beträgt nur 40 Euro.
(die gestrichelten Linien sollen Threadwechsel durch den Scheduler andeuten)
|
|
Quellcode
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
Benutzer 1 Benutzer 2
------------------------------------------------------------------------------------------
bool abbuchen(20)
{
if(20 <= 40) // true
{
------------------------------------------------------------------------------------------
bool abbuchen(40)
{
if(40 <= 40) // true
{
Kontostand = 40 - 40; // 0
------------------------------------------------------------------------------------------
Kontostand = 40 - 20; // 20
return true;
}
}
------------------------------------------------------------------------------------------
return true;
}
}
------------------------------------------------------------------------------------------
|
Zuerst kommt Benutzer 1 an die Reihe und führt abbuchen bis kurz vor der Zuweisung aus. Dann entscheidet der Scheduler zu wechseln und Thread2, also Benutzer 2 kommt an die Reihe. Der Thread schafft es 40€ abzubuchen. Die Variable Kontostand ist jetzt unter Benutzer 2 auf 0€. Davon weiss aber Thread1 nichts und Benutzer1 auch nichts, da er den alten Kontostand ja noch in seinen Registern hat (Register werden bei Thread Umschaltung gerettet). Demzufolge kann Benutzer1 die 20Euro abbuchen.
Wie wir sofort sehen, werden 20€ und 40€ erfolgreich abgebucht. Die Frage ist nun nur wie viel Geld noch auf dem Konto ist. Denken Sie am besten mal ein weilchen drüber nach bevor Sie die Lösung lesen. - Lösung mit Bildschirmlupe erkennbar.
[size=7]
Auf dem Konto sind jetzt 20€, da Benutzer 1 zuletzt Kontostand auf 20 setzt.
[/size]
So was nenn ich doch mal ne kundenfreundliche Bank!
So kann es aber auch passieren das zuerst Benutzer 1 die 20 Euro abbucht und Benutzer 2 gar nichts bekommt oder Benutzer 2 die 40 euro abbucht und Benutzer 1 nichts bekommt.
Wie funktionieren Critical Sections ?
Genau hierführ brauchen wir kritische Bereiche. Kritische Bereiche oder Abschnitte müssen verhindern das
[list]
(1) sich keine zwei oder mehr Threads dürfen sich zur selben Zeit im selben kritischen Abschnitt befinden.
(2) Jeder Thread der einen Kiritschen Abschnitt betreten möchte, muss ihn auch irgendwann verlassen und
(3) Es dürfen keine Annahmen über Anzahl, Reihenfolge oder Geschwindigkeiten der Threads gemacht werden.
[/list]
Probieren wir doch einfach mal ein paar Lösungsversuche um uns einen Kritischen Abschnitt zu definieren. Fangen wir mit der Frage doch mal an, wie Threads umgeschaltet werden, und unterbinden wir das doch einfach. Schnell wird man merken das das doch nur Zeitgesteuert (also wenn der Timer abgelaufen ist, sendet dieser einen Interrupt (Signal) an unser Betriebssystem, was daraufhin Threads umschaltet) ist und wenn wir das unterbinden, haben wir unseren Kritischen Abschnitt!
(die folgenden Codes bitte nicht nachmachen!)
Lösungsversuch 1
|
|
Quellcode
|
1
2
3
4
5
6
7
8
|
enter_criticalsection:
pushf // legt Prozessorflags auf den Keller
cli // löscht Interrupt Enable Flag in CPU Flags, es kommen keine Interrupts mehr durch
ret // return
leave_criticalsection:
popf // restauriert alte Prozessorflags
ret
|
Schnell wird uns klar, das dieser Ansatz reiner Unsinn ist. Wir sperren alle Interrupts (Ausnahmen, Signale), somit legen wir eigentlich unser System lahm. Es kommen keine Nachrichten von der Tastatur mehr durch etc. etc. . Wenn es ganz dumm läuft können wir mit diesem Code sogar unser System schroten (wir vergessen einfach irgendwo leave_criticalsection aufzurufen), den wenn wir den PC booten wollen bekommt der CPU bestimmte Interrupts, wenn die ausbleiben is nix da mit booten. Ausserdem würde diese Lösung nur für einen Kern funktionieren und nicht für Mehrkern-Prozessoren.
(Der Code funktioniert normalerweise aber nur im sogenannten Kern Modus der CPU, wo wir keinen Zugriff haben, denn cli wäre für den Benutzer oder einen Programmierer ausserhalb des Betriebssystem Kerns viel zu mächtig.)
Nachdem wir mit unserer letzen Lösung kläglich gescheitert sind, versuchen wir es jetzt mit einer reinen Software Lösung.
Lösungsversuch 2
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
unsigned Lock = 0;
// Lock == 0 -> frei
// Lock != 0 -> gesperrt
void entersection()
{
while(Lock != 0);
// busy waiting
Lock = 1;
}
void leavesection()
{
Lock = 0;
}
|
Sieht doch ganz einfach aus, funktioniert auch (für einen Prozessor), allerdings warten wir in der while Schleife immer nur und machen nichts. Trotzdem wollen wir uns vorerst mit dieser Lösung zufrieden geben. (Für Alternative Implementierungen siehe test_and_set (TAS), CAS und weitere).
Crital Sections sind normalerweise von jedem Betriebssystem implementiert und meist werden dort auch extrem ausgefeilte Algortithmen verwendet. Wie man Critical Sections benutzt siehe
hier.
Teil 2....
In Teil 2 wird es um Mutexe, Erzeuger Verbraucher Probleme und Botschaften zwischen Threads gehen.
Fehler, Fragen....
Bei Fehlern oder Fragen wär ich sehr dankbar wenn ich eine PM bekomme oder sie hier öffentlich diskutiert werden können.
Referenz
- Betriebssysteme Vorlesung
- Modern Operating Systems von Tanenbaum (engl. Version kaufen!)
Zitat
hab bisher nicht mit mehreren Treats zu tun gehabt aber wenn dann auch noch die Interaktion zwischen Treats vorgestellt wurde dann setz ich mich gleich an eigene Versuche
29.04.2024, 20:57
Zum Seitenanfang
