Lesung 17: Parallelität

#### Software im 6.005

#### Ziele+ Message passing & Shared Memory+ Processes & Threads+ Time Slicing+ Race conditions## Parallelität*Parallelität* bedeutet, dass mehrere Berechnungen gleichzeitig durchgeführt werden. Parallelität ist überall in der modernen Programmierung, ob es uns gefällt oder nicht: + Mehrere Computer in einem Netzwerk+ Mehrere Anwendungen, die auf einem Computer ausgeführt werden+ Mehrere Prozessoren in einem Computer (heute oft mehrere Prozessorkerne auf einem einzigen Chip) In der Tat ist Parallelität in der modernen Programmierung unerlässlich: + Websites müssen mehrere gleichzeitige Benutzer verarbeiten.+ Mobile Apps müssen einen Teil ihrer Verarbeitung auf Servern (“in der Cloud”) durchführen.+ Grafische Benutzeroberflächen erfordern fast immer Hintergrundarbeiten, die den Benutzer nicht unterbrechen. Zum Beispiel kompiliert Eclipse Ihren Java-Code, während Sie ihn noch bearbeiten.In der Lage zu sein, mit Parallelität zu programmieren, wird auch in Zukunft wichtig sein. Die Prozessortaktgeschwindigkeiten steigen nicht mehr an. Stattdessen bekommen wir mit jeder neuen Chipgeneration mehr Kerne. Damit eine Berechnung in Zukunft schneller ausgeführt werden kann, müssen wir eine Berechnung in gleichzeitige Teile aufteilen.## Zwei Modelle für die gleichzeitige ProgrammierUnges gibt zwei gängige Modelle für die gleichzeitige Programmierung: * Shared Memory * und *Message Passing *.

**Gemeinsamer Speicher.** Im gemeinsam genutzten Speichermodell der Parallelität interagieren gleichzeitige Module durch Lesen und Schreiben gemeinsam genutzter Objekte im Speicher. Andere Beispiele für das Shared-Memory-Modell: + A und B können zwei Prozessoren (oder Prozessorkerne) im selben Computer sein, die sich denselben physischen Speicher teilen.+ A und B können zwei Programme sein, die auf demselben Computer ausgeführt werden und ein gemeinsames Dateisystem mit Dateien teilen, die sie lesen und schreiben können.+ A und B können zwei Threads im selben Java-Programm sein (wir erklären unten, was ein Thread ist), die dieselben Java-Objekte gemeinsam nutzen.

**Nachrichtenübermittlung.** Im Message-Passing-Modell interagieren gleichzeitige Module, indem sie Nachrichten über einen Kommunikationskanal aneinander senden. Module senden Nachrichten aus, und eingehende Nachrichten an jedes Modul werden zur Bearbeitung in die Warteschlange gestellt. Beispiele sind: + A und B können zwei Computer in einem Netzwerk sein, die über Netzwerkverbindungen kommunizieren.+ A und B können ein Webbrowser und ein Webserver sein – A öffnet eine Verbindung zu B, fragt nach einer Webseite und B sendet die Webseitendaten zurück an A.+ A und B können ein Instant Messaging-Client und -Server sein.+ A und B können zwei Programme sein, die auf demselben Computer ausgeführt werden, deren Eingabe und Ausgabe durch eine Pipe verbunden wurden, z. B. `ls | grep`, das in eine Eingabeaufforderung eingegeben wurde.## Prozesse, Threads, Time-slicingBei den Message-Passing- und Shared-Memory-Modellen geht es darum, wie gleichzeitige Module kommunizieren. Die gleichzeitigen Module selbst gibt es in zwei verschiedenen Arten: Prozesse und Threads.**Prozess**. Ein Prozess ist eine Instanz eines laufenden Programms, das von anderen Prozessen auf demselben Computer * isoliert * ist. Insbesondere verfügt es über einen eigenen privaten Bereich des Computerspeichers.Die Prozessabstraktion ist ein *virtueller Computer*. Das Programm fühlt sich an, als hätte es die gesamte Maschine für sich – als wäre ein neuer Computer mit frischem Speicher geschaffen worden, nur um dieses Programm auszuführen.Genau wie Computer, die über ein Netzwerk verbunden sind, teilen Prozesse normalerweise keinen Speicher zwischen ihnen. Ein Prozess kann überhaupt nicht auf den Speicher oder die Objekte eines anderen Prozesses zugreifen. Die gemeinsame Nutzung von Speicher zwischen Prozessen ist auf den meisten Betriebssystemen * möglich *, erfordert jedoch besonderen Aufwand. Im Gegensatz dazu ist ein neuer Prozess automatisch für die Nachrichtenübermittlung bereit, da er mit Standardeingabe & Ausgabeströmen erstellt wird, die das `System’ sind.out’ und `System.in ‘ streams, die Sie in Java verwendet haben.**Thread**. Ein Thread ist ein Kontrollort innerhalb eines laufenden Programms. Betrachten Sie es als einen Ort in dem Programm, das ausgeführt wird, plus den Stapel von Methodenaufrufen, die zu dem Ort geführt haben, an den es notwendig sein wird, zurückzukehren.So wie ein Prozess einen virtuellen Computer darstellt, repräsentiert die Thread-Abstraktion einen * virtuellen Prozessor *. Das Erstellen eines neuen Threads simuliert das Erstellen eines neuen Prozessors in dem durch den Prozess dargestellten virtuellen Computer. Dieser neue virtuelle Prozessor führt dasselbe Programm aus und teilt sich denselben Speicher wie andere Threads in Bearbeitung.Threads sind automatisch für den gemeinsam genutzten Speicher bereit, da Threads den gesamten Speicher im Prozess gemeinsam nutzen. Es bedarf besonderer Anstrengungen, um “thread-lokalen” Speicher zu erhalten, der für einen einzelnen Thread privat ist. Es ist auch erforderlich, die Nachrichtenübergabe explizit einzurichten, indem Warteschlangendatenstrukturen erstellt und verwendet werden. Wir werden in einer zukünftigen Lektüre darüber sprechen, wie das geht.

Wie kann ich viele gleichzeitige Threads mit nur einem oder zwei Prozessoren in meinem Computer haben? Wenn mehr Threads als Prozessoren vorhanden sind, wird die Parallelität durch ** Time Slicing ** simuliert, was bedeutet, dass der Prozessor zwischen Threads wechselt. Die Abbildung rechts zeigt, wie drei Threads T1, T2 und T3 auf einem Computer mit nur zwei tatsächlichen Prozessoren zeitlich aufgeschnitten werden können. In der Abbildung verläuft die Zeit nach unten, sodass zuerst ein Prozessor Thread T1 und der andere Thread T2 ausführt und dann der zweite Prozessor zum Ausführen von Thread T3 wechselt. Thread T2 pausiert einfach bis zu seinem nächsten Zeitabschnitt auf demselben Prozessor oder einem anderen Prozessor.Auf den meisten Systemen erfolgt das Time Slicing unvorhersehbar und nicht deterministisch, was bedeutet, dass ein Thread jederzeit angehalten oder fortgesetzt werden kann.

mitx:c613ec53e92840a4a506f3062c994673 Processes & Threads## Beispiel für gemeinsam genutzten Speichersehen wir uns ein Beispiel für ein gemeinsam genutztes Speichersystem an. In diesem Beispiel soll gezeigt werden, dass die gleichzeitige Programmierung schwierig ist, da sie subtile Fehler aufweisen kann.

Stellen Sie sich vor, eine Bank verfügt über Geldautomaten, die ein Shared-Memory-Modell verwenden, sodass alle Geldautomaten dieselben Kontoobjekte im Speicher lesen und schreiben können.Um zu veranschaulichen, was schief gehen kann, vereinfachen wir die Bank auf ein einziges Konto, mit einem Dollarsaldo, der in der Variablen `balance` gespeichert ist, und zwei Operationen `deposit” und “withdraw”, die einfach einen Dollar hinzufügen oder entfernen: “`java// Angenommen, alle Geldautomaten teilen sich ein einziges Bankkontoprivate static int balance = 0;private static void deposit() { balance = balance + 1;}private static void withdraw() { balance = balance – 1;}”`Kunden verwenden die Geldautomaten, um Transaktionen wie diese durchzuführen:”`javadeposit(); // put ein Dollar in withdraw(); // take it back out`’In diesem einfachen Beispiel ist jede Transaktion nur eine Einzahlung von einem Dollar, gefolgt von einer Auszahlung von einem Dollar. Im Laufe des Tages verarbeitet jeder Geldautomat in unserem Netzwerk eine Abfolge von Ein- / Auszahlungstransaktionen.”‘java// Jeder Geldautomat führt eine Reihe von Transaktionen durch, die// das Guthaben ändern, aber danach unverändert lassenprivate static void cashMachine() { for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) { deposit(); // Setzen Sie einen Dollar in withdraw(); // take it back out }}”‘Also am Ende des Tages, unabhängig davon, wie viele Geldautomaten liefen oder wie viele Transaktionen wir verarbeitet haben, sollten wir erwarten, dass der Kontostand immer noch 0 ist.Aber wenn wir diesen Code ausführen, stellen wir häufig fest, dass der Saldo am Ende des Tages * nicht * 0 ist. Wenn mehr als ein `cashMachine ()`-Aufruf gleichzeitig ausgeführt wird – beispielsweise auf separaten Prozessoren auf demselben Computer -, ist `balance` am Ende des Tages möglicherweise nicht Null. Warum nicht?## InterleavingHier ist eine Sache, die passieren kann. Angenommen, zwei Geldautomaten, A und B, arbeiten beide gleichzeitig an einer Einzahlung. So gliedert sich der Schritt deposit() normalerweise in Prozessoranweisungen auf niedriger Ebene: `’get balance (balance= 0)add 1 write back the result (balance= 1“’Wenn A und B gleichzeitig ausgeführt werden, verschachteln sich diese Low-Level-Anweisungen miteinander (einige sind in gewissem Sinne sogar gleichzeitig, aber machen wir uns vorerst nur Gedanken über die Verschachtelung):`’A get balance (balance = 0) A add 1 A Schreiben Sie das Ergebnis zurück (balance = 1) B get balance (balance = 1) B add 1 B schreiben Sie das Ergebnis zurück (balance = 2)“Diese Verschachtelung ist in Ordnung – am Ende haben wir Balance 2, also haben sowohl A als auch B erfolgreich einen Dollar eingezahlt. Aber was wäre, wenn die Verschachtelung folgendermaßen aussehen würde: “A get balance (balance = 0) B get balance (balance = 0)A add 1 B add 1 A schreibe das Ergebnis zurück (balance = 1) B schreibe das Ergebnis zurück (balance = 1)“Das Gleichgewicht ist jetzt 1 – A’s Dollar war verloren! A und B lasen beide gleichzeitig den Kontostand, berechneten separate Endsalden und rannten dann los, um den neuen Kontostand zurückzuspeichern – was die Einzahlung des anderen nicht berücksichtigte.## Race ConditionDies ist ein Beispiel für eine **race condition**. Eine Wettlaufbedingung bedeutet, dass die Korrektheit des Programms (die Erfüllung von Nachbedingungen und Invarianten) vom relativen Zeitpunkt der Ereignisse in den gleichzeitigen Berechnungen A und B abhängt.”Einige Verschachtelungen von Ereignissen mögen in dem Sinne in Ordnung sein, dass sie mit dem übereinstimmen, was ein einzelner, nichtkonkurrenter Prozess erzeugen würde, aber andere Verschachtelungen erzeugen falsche Antworten – Verletzung von Nachbedingungen oder Invarianten.## Das Optimieren des Codes hilft nichtalle diese Versionen des Bankkontocodes weisen die gleiche Race-Bedingung auf:”‘java// version 1private static void deposit() { balance = balance + 1;}private static void withdraw() { balance = balance – 1;}”””java// version 2private static void deposit() { balance += 1;}private static void withdraw() { balance -= 1;}””” java // version 3private static void deposit() { ++balance;}private static void withdraw() { –balance;}“Sie können nicht nur anhand des Java-Codes erkennen, wie der Prozessor ihn ausführen wird. Sie können nicht sagen, was die unteilbaren Operationen – die atomaren Operationen – sein werden. Es ist nicht atomar, nur weil es eine Zeile Java ist. Es berührt Balance nicht nur einmal, nur weil die Balance-ID nur einmal in der Zeile vorkommt. Der Java-Compiler und in der Tat der Prozessor selbst machen keine Verpflichtungen darüber, welche Low-Level-Operationen er aus Ihrem Code generiert. Tatsächlich erzeugt ein typischer moderner Java-Compiler für alle drei Versionen genau den gleichen Code!Die wichtigste Lektion ist, dass man nicht anhand eines Ausdrucks erkennen kann, ob er vor Rennbedingungen sicher ist.

## NeuordnungEs ist sogar noch schlimmer als das. Die Wettlaufbedingung auf dem Bankkontostand kann durch unterschiedliche Verschachtelungen sequentieller Operationen auf verschiedenen Prozessoren erklärt werden. Wenn Sie jedoch mehrere Variablen und mehrere Prozessoren verwenden, können Sie nicht einmal damit rechnen, dass Änderungen an diesen Variablen in derselben Reihenfolge angezeigt werden.Hier ist ein Beispiel`”‘javaprivate boolean ready = false;private int answer = 0;// computeAnswer läuft in einem threadprivate void computeAnswer() { answer = 42; ready = true;}// useAnswer läuft in einem anderen threadprivate void useAnswer() { while (!bereit) { Thread.yield(); } if (answer == 0) throw new RuntimeException(“Antwort war nicht bereit!”);}”‘Wir haben zwei Methoden, die in verschiedenen Threads ausgeführt werden. ‘computeAnswer’ führt eine lange Berechnung durch und liefert schließlich die Antwort 42, die es in die Antwortvariable einfügt. Dann setzt es die Variable ‘ready` auf true, um der Methode, die im anderen Thread `useAnswer’ ausgeführt wird, zu signalisieren, dass die Antwort zur Verwendung bereit ist. Wenn also `useAnswer’ `ready` als wahr ansieht, scheint es vernünftig, dass davon ausgegangen werden kann, dass die `Antwort` 42 ist, oder? Nicht so.Das Problem ist, dass moderne Compiler und Prozessoren eine Menge Dinge tun, um den Code schnell zu machen. Eines dieser Dinge besteht darin, temporäre Kopien von Variablen wie answer und ready in einem schnelleren Speicher (Register oder Caches auf einem Prozessor) zu erstellen und vorübergehend mit ihnen zu arbeiten, bevor sie schließlich wieder an ihrem offiziellen Speicherort gespeichert werden. Der Storeback kann in einer anderen Reihenfolge erfolgen, als die Variablen in Ihrem Code manipuliert wurden. Hier ist, was unter der Decke vor sich gehen könnte (aber in Java-Syntax ausgedrückt, um es klar zu machen). Der Prozessor erstellt effektiv zwei temporäre Variablen, `tmpr` und `tmpa`, um die Felder ready und answer zu bearbeiten:`’javaprivate void useanswer() { boolean tmpr = ready; int tmpa = answer; tmpa = 42; tmpr = true; ready = tmpr; // <– was passiert, wenn sich useAnswer() hier verschachtelt? // ready ist gesetzt, aber answer ist es nicht. answer = tmpa;}”‘mitx:2bf4beb7ffd5437bbbb9c782bb99b54e Race Conditions## Message Passing Example

Schauen wir uns nun den Message-Passing-Ansatz für unser Bankkonto-Beispiel an.Jetzt sind nicht nur die Geldautomatenmodule, sondern auch die Konten Module. Module interagieren, indem sie Nachrichten aneinander senden. Eingehende Anfragen werden in eine Warteschlange gestellt, um einzeln bearbeitet zu werden. Der Absender hört nicht auf zu arbeiten, während er auf eine Antwort auf seine Anfrage wartet. Es verarbeitet mehr Anforderungen aus seiner eigenen Warteschlange. Die Antwort auf seine Anfrage kommt schließlich als weitere Nachricht zurück.Leider schließt die Weitergabe von Nachrichten die Möglichkeit von Race Conditions nicht aus. Angenommen, jedes Konto unterstützt die Vorgänge `Get-balance` und `withdraw’ mit entsprechenden Meldungen. Zwei Benutzer am Geldautomaten A und B versuchen beide, einen Dollar vom selben Konto abzuheben. Sie überprüfen zuerst den Kontostand, um sicherzustellen, dass sie niemals mehr abheben, als das Konto hält, da Überziehungen große Bankstrafen auslösen:“get-balanceif balance >= 1 then withdraw 1“Das Problem ist wieder die Verschachtelung, aber diesmal die Verschachtelung der * Nachrichten *, die an das Bankkonto gesendet werden, und nicht die * Anweisungen *, die von A und B ausgeführt werden. Wenn das Konto mit einem Dollar beginnt, welche Verschachtelung von Nachrichten täuscht dann A und B zu der Annahme, dass sie beide einen Dollar abheben und dadurch das Konto überziehen können?Eine Lektion hier ist, dass Sie die Operationen eines Message-Passing-Modells sorgfältig auswählen müssen. ‘abheben-wenn-ausreichend-Mittel’ wäre eine bessere Operation als nur `abheben`.## Parallelität ist schwer zu testen und zu debuggenwenn wir Sie nicht davon überzeugt haben, dass Parallelität schwierig ist, finden Sie hier das Schlimmste. Es ist sehr schwierig, die Rennbedingungen mithilfe von Tests zu ermitteln. Und selbst wenn ein Test einen Fehler gefunden hat, kann es sehr schwierig sein, ihn auf den Teil des Programms zu lokalisieren, der ihn verursacht.Parallelitätsfehler weisen eine sehr schlechte Reproduzierbarkeit auf. Es ist schwer, sie zweimal auf die gleiche Weise passieren zu lassen. Die Verschachtelung von Anweisungen oder Nachrichten hängt vom relativen Zeitpunkt von Ereignissen ab, die stark von der Umgebung beeinflusst werden. Verzögerungen können durch andere laufende Programme, anderen Netzwerkverkehr, Entscheidungen zur Betriebssystemplanung, Variationen der Prozessortaktgeschwindigkeit usw. verursacht werden. Jedes Mal, wenn Sie ein Programm ausführen, das eine Race-Bedingung enthält, erhalten Sie möglicherweise ein anderes Verhalten. Diese Arten von Fehlern sind ** Heisenbugs **, die nicht deterministisch und schwer zu reproduzieren sind, im Gegensatz zu einem “Bohrbug”, der immer wieder auftaucht, wenn man ihn ansieht. Fast alle Fehler in der sequentiellen Programmierung sind Bohrbugs.Ein Heisenbug kann sogar verschwinden, wenn Sie versuchen, ihn mit `println` oder `debugger` zu betrachten! Der Grund dafür ist, dass Drucken und Debuggen so viel langsamer sind als andere Vorgänge, oft 100-1000x langsamer, dass sie das Timing von Vorgängen und das Interleaving dramatisch verändern. Also eine einfache print-Anweisung in die cashMachine einfügen():`’javaprivate static void cashMachine() { for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) { deposit(); // einen Dollar in withdraw(); // take it back out System.aus.println(balance); // lässt den Fehler verschwinden! }}“`…und plötzlich ist das Gleichgewicht immer 0, wie gewünscht, und der Fehler scheint zu verschwinden. Aber es ist nur maskiert, nicht wirklich fixiert. Eine Änderung des Timings an einer anderen Stelle im Programm kann dazu führen, dass der Fehler plötzlich zurückkehrt.Parallelität ist schwer richtig zu machen. Ein Teil des Ziels dieser Lektüre ist es, Sie ein wenig zu erschrecken. In den nächsten Lesungen werden wir prinzipielle Möglichkeiten sehen, gleichzeitige Programme so zu entwerfen, dass sie vor solchen Fehlern sicherer sind.mitx: 704b9c4db3c6487c9f1549956af8bfc8 Parallelität testen ## Zusammenfassung + Parallelität: mehrere gleichzeitig laufende Berechnungen + Shared-Memory & Message-Passing-Paradigmen+ Prozesse & Threads + Prozess ist wie ein virtueller Computer; Thread ist wie ein virtueller Prozessor+ Race Conditions + Wenn die Korrektheit des Ergebnisses (Nachbedingungen und Invarianten) vom relativen Zeitpunkt der Ereignisse abhängtdiese Ideen verbinden sich meist auf schlechte Weise mit unseren drei Schlüsseleigenschaften guter Software. Parallelität ist notwendig, verursacht aber ernsthafte Probleme für die Korrektheit. Wir werden daran arbeiten, diese Probleme in den nächsten Lesungen zu beheben.+ ** Sicher vor Fehlern.** Parallelitätsfehler gehören zu den am schwierigsten zu findenden und zu behebenden Fehlern und erfordern ein sorgfältiges Design, um sie zu vermeiden.+ ** Leicht zu verstehen.** Die Vorhersage, wie sich gleichzeitiger Code mit anderem gleichzeitigen Code verschachteln könnte, ist für Programmierer sehr schwierig. Es ist am besten, so zu entwerfen, dass Programmierer nicht darüber nachdenken müssen. + ** Bereit für den Wandel.** Hier nicht besonders relevant.