STP059: Nebenläufigkeit

<p>Nachdem es in STP015 (Multitasking) bereits um die nacheinanderfolgende Verteilung von Resourcen an verschiedene Prozesse ging, kommt heute echtes "gleichzeitig Arbeiten" dran.</p><h2>Shownotes</h2><ul>
<li>
<p>Rückbezug und Abgrenzung zu STP015 (Multitasking in Betriebssystemen)</p>
<ul>
<li>Definition von <a href="de.wikipedia.org/w/index.php?title=Nebenl%C3%A…;: "in der Informatik die Eigenschaft eines Systems, mehrere Aufgaben, Berechnungen, Anweisungen oder Befehle gleichzeitig ausführen zu können"</li>
<li>Definition von <a href="de.wikipedia.org/w/index.php?title=Multitaskin…;: "die Fähigkeit eines Betriebssystems, mehrere Aufgaben [...] (quasi-)nebenläufig auszuführen"</li>
<li>eins definiert das andere \o/ -> wir schauen auf den Begriffsgebrauch in der Praxis</li>
<li>Multitasking: die funktionale Umsetzung einer Multiprozess-Architektur in Hardware und Software (auf Betriebssystem-Ebene)</li>
<li>Nebenläufigkeit: die Ertüchtigung von Userspace-Programmen zur Ausnutzung dieser Möglichkeiten unter Wahrung des korrekten Verhaltens</li>
</ul>
</li>
<li>
<p>Grundproblem: Wie vermeidet man Konflikte und Verwirrung beim Umgang mit geteilten Ressourcen?</p>
<ul>
<li>"Ressource" bedeutet vor allem: Speicherstellen, Dateisystem-Einträge (Dateien und Verzeichnisse), Geräte, (Aufmerksamkeit der Benutzerin)</li>
<li>explizit nicht Zeit; darum kümmert sich bereits die Multitasking-Unterstützung des Betriebssystems</li>
</ul>
</li>
<li>
<p><strong>Race</strong>: eine Situation, bei der das Ergebnis (und insbesondere die Korrektheit) mehrerer nebenläufiger Prozesse davon abhängt, in welcher Reihenfolge die einzelnen Rechenschritte verschiedener Prozesse zufälligerweise ausgeführt werden</p>
<ul>
<li>allgemein bekannt als <strong>Race Condition</strong> (<a href="de.wikipedia.org/w/index.php?title=Wettlaufsit…;) oder beim Speicherzugriff insbesondere <strong>Data Race</strong></li>
<li>Beispielsituation: im Arbeitsspeicher liegt ein Zähler mit aktuellem Wert 40; zwei Prozesse A und B wollen diesen Zähler gleichzeitig um 1 erhöhen -> erwarteter Endwert 42</li>
<li>Problem: "Zahl im Arbeitsspeicher verändern" ist nicht, wie Speicherzugriff in CPUs funktioniert (siehe STP007); tatsächlich sind jeweils drei Schritte erforderlich (Einlesen in CPU-Register, Erhöhen um 1, Zurückschreiben in den RAM)</li>
<li>möglicher Ausgang: beide Prozesse laufen auf verschiedenen CPUs, lesen gleichzeitig den Wert 40 in ihre CPU-Register, erhöhen gleichzeitig auf 41, schreiben dies zurück -> Ergebnis 41 statt 42</li>
<li>"auf verschiedenen CPUs" ist hier nicht erforderlich: z.B. A liest ein und erhöht, wird unterbrochen, B liest ein und erhöht, B schreibt zurück, wird unterbrochen, A schreibt zurück</li>
<li>"zwei Prozesse" ist auch nicht erforderlich: Prozesse können auch in <strong>Threads</strong> (parallele Ausführungsstränge) unterteilt sein, die nebenläufig Code ausführen, aber ansonsten fast alle Ressourcen (Speicherseiten, offene Dateien, etc.) teilen</li>
</ul>
</li>
<li>
<p>wir brauchen ein <a href="de.wikipedia.org/w/index.php?title=Mutex&o…;: einen Mechanismus zum wechselseitigen Ausschluss ("<strong>Mut</strong>ual <strong>Ex</strong>clusion")</p>
<ul>
<li>Problem: Wie implementiert man sowas?</li>
</ul>
</li>
<li>
<p>Idee: bevor wir den Zähler anfassen, fragen wir bei einem zentralen Prozess nach einer Sperre für diesen Zähler an; dieser Prozess vermerkt Sperr- und Entsperrvorgänge in seinem internen Speicher</p>
<ul>
<li>dieser Kontrollprozess könnte auch einfach ein Teil des Betriebssystems sein und der Sperr-/Entsperrvorgang ein Syscall (siehe STP019)</li>
<li>Vorteil: innerhalb dieses Kontrollprozesses keine Nebenläufigkeit und damit keine Gefahr eines Data Race</li>
<li>Nachteil: Interprozess-Kommunikation ist vergleichsweise grauenhaft langsam (Millisekunden vs. Mikrosekunden)</li>
</ul>
</li>
<li>
<p>Idee: in der <strong>kritischen Region</strong> (von Auslesen des Zählers bis Zurückschreiben) verbieten wir dem Betriebssystem, unseren Prozess zu unterbrechen</p>
<ul>
<li>Problem 1: hilft nur bei nebenläufigen Prozessen auf demselben CPU-Kern</li>
<li>Problem 2: immer noch ein teurer Syscall</li>
<li>Problem 3: böswillige Prozesse könnten einfach ihre gesamte Laufzeit als kritische Region markieren und die Rechenzeit blockieren</li>
</ul>
</li>
<li>
<p>praktische Umsetzung von Mutexen mittels <a href="de.wikipedia.org/w/index.php?title=Atomare_Ope…;: spezielle CPU-Instruktionen, die nicht unterbrochen werden können</p>
<ul>
<li>Beispiel für Mutex: "Fetch and Add" liest einen Wert aus dem Speicher aus, erhöht ihn um das Argument, und schreibt den erhöhten Wert zurück</li>
<li>schneller als ein Kontextwechsel zu einem Kontrollprozess oder ein Syscall</li>
<li>langsamer als ein normaler Speicherzugriff, da eventuell Caches ignoriert oder aktiv geleert werden müssen</li>
<li>in der Praxis evtl. Kombination mit Syscalls, um bei blockiertem Mutex den Prozess zu unterbrechen (z.B. unter Linux das <a href="de.wikipedia.org/w/index.php?title=Futex&o… Userspace Mutex" bzw. Futex</a>)</li>
</ul>
</li>
<li>
<p>andere Perspektive, hier zitiert aus der Programmiersprache Go: <a href="go.dev/doc/effective_go">"Do not communicate by sharing memory; instead, share memory by communicating."</a></p>
<ul>
<li>statt Zugriffssicherungen für geteilten Speicher dort eher Nutzung von "Kanälen" (<strong>Channels</strong>) zur Nachrichtenübermittlung zwischen Threads</li>
<li>Beispiel "Worker Pool": mehrere gleichartige und voneinander unabhängige Teilaufgaben sind abzuarbeiten (z.B. 100 Bilder in ein anderes Dateiformat umwandeln)</li>
<li>Idee: ein Worker (Arbeits-Prozess oder Arbeits-Thread) pro CPU-Kern; außerdem ein zentraler Prozess, der die Aufgaben verteilt; Zentrale stellt alle Dateinamen in einen Kanal, Arbeiter greifen nacheinander aus dem Kanal die Dateinamen heraus</li>
<li>unter der Haube nutzt der Kanal Atomics, um sich vor Data Races zu schützen</li>
<li>Rückbezug zu STP027: sobald man mehrere Threads untereinander koordinieren muss, hat man das ganze Problemfeld "Verteilte Systeme", was nach Xyrills Erfahrung nochmal wesentlich nerviger ist als Data Races</li>
</ul>
</li>
<li>
<p>Abendgedanken: <a href="de.wikipedia.org/w/index.php?title=Amdahlsches… Gesetz</a></p>
<ul>
<li>mehr CPU-Kerne machen nur Dinge schneller, die wahrhaft nebenläufig sind</li>
</ul>
</li>
</ul>