659172fc-d6da-46b7-9417-cd687279279d_Unbenannt.pdf

Klausurvorbereitung 2024-10-09 10:00-12:00, Nebenläufige, parallele und verteilte Prog Frage Antwort Thema Hier sind kurze Erklärungen der...

Klausurvorbereitung 2024-10-09 10:00-12:00, Nebenläufige, parallele und verteilte Prog Frage Antwort Thema Hier sind kurze Erklärungen der Begriffe im Kontext von Threads: Deadlock: Ein Deadlock tritt auf, wenn zwei oder mehr Threads sich gegenseitig blockieren, weil jeder auf eine Ressource wartet, die von einem anderen Thread gesperrt ist. Keiner der Threads kann weitermachen, weil sie in einem Zyklus von Abhängigkeiten feststecken. Race Condition: Eine Race Condition entsteht, wenn zwei oder mehr Threads gleichzeitig auf gemeinsame Daten zugreifen und die Reihenfolge des Zugriffs unvorhersehbar ist. Dies kann zu inkorrekten Ergebnissen führen, da der Ablauf der Threads nicht deterministisch ist. Verhungern (Starvation): Verhungern tritt auf, wenn ein Thread über lange Zeit oder dauerhaft keinen Zugriff auf den kritischen Abschnitt bekommt, weil andere Threads bevorzugt oder ständig vor ihm Unbenannt 1  Frage Antwort Thema ausgeführt werden. Der Thread wartet also unendlich, ohne jemals fortfahren zu können. Threads sind leichtgewichtige Was sind Threads Prozesse, die innerhalb desselben Alp4_Threads Programms parallel ausgeführt werden. Nebenläufig/concurrent: Gemeinsamer Speicher: Mehrere Ausführungen teilen sich denselben Speicher, oft auf einer CPU. Parallel: Welche Arten von Gemeinsamer oder verteilter Speicher: nichtsequentieller Mehrere Ausführungen laufen Alp_Allgemein Programmierung gibt gleichzeitig, oft auf mehreren CPUs. es? Verteilt: Kein gemeinsamer Speicher und keine gemeinsame CPU: Die Ausführungen sind auf verschiedenen Systemen verteilt, die über ein Netzwerk kommunizieren. Es soll: - die funktionalen Anforderungen erfüllen Welche zwei (das tun, was wir erwarten) Anforderungen stellen - di Alp_Allgemein wir an ein Programm? e nichtfunktionalen Anforderungen erfüllen (Performance, Benutzbarkeit, Sicherheit,...) Welche Modelle Modell der Systemzustandsänderung: Alp_Allgemein nutzen wir für die Menge von Erstellung von Operationen, dargestellt durch Befehle Programmen und einer Programmiersprache. wodurch wird die Korrektheit des Programmiermodell: Programms Auswahl und Reihenfolge von sichergestellt? Operationen. Ausführungsmodell: Unbenannt 2  Frage Antwort Thema Auswahl und Reihenfolge von Befehlen. Maschinenausführungsmodell: Übertragung des Ausführungsmodell in Maschinencode. Korrektheit: Ein Programm gilt als korrekt, wenn die Modelle fehlerfrei in das jeweils nächste Modell übertragen werden. Determinismus: Ein deterministischer Algorithmus ist determiniert und durchläuft immer die gleichen Operationen in der Was bedeuten gleichen Reihenfolge. Determinismus und Alp_Allgemein Determiniertheit: Ein determinierter Determiniertheit? Algorithmus erzeugt zu jeder bestimmten Eingabe immer die gleiche Ausgabe Wann ist ein Programm Korrekt, wenn das Programm korrekt im deterministisch ist. Erreicht durch Sinne der Vorlesung Alp_Allgemein und wie wird dies korrekte Übertragung der Modelle in erreicht? das nächste Modell. Warum sind die Weil externe Einflüsse (z.B. I/O) die meisten Programme deterministische Ausführung Alp_Allgemein nichtdeterministisch? verhindern können. Wie kann trotz Programm in sinnvolle Module nichtdeterministischer aufteilen, die aus deterministischen Ausführung die Abläufen bestelen, aber in ihrer Alp_Allgemein Korrektheit des Gesamtheit keine deterministische Programms Ausführung benötigen. sichergestellt werden? Was sind atomare und Atomare Operationen sind nicht in Alp_Allgemein nicht-atomare kleinere Operationen aufteilbar und Operationen? könnend daruch nicht durch einen Interrupt unterbrochen werden Nicht- atomare Operationen bestehen aus Unbenannt 3  Frage Antwort Thema mehreren Maschineninstruktionen und können durch einen Interrupt unterbrochen werden die Anforderungen an ein System, um Nebenläufigkeit (gleichzeitige Ausführung mehrerer Prozesse) zu ermöglichen 1. Trennung der Speicherbereiche durch Adressräume 2. Möglichkeit der Prozessgenerierung: Das System muss in der Lage sein, neue Prozesse oder Threads zu erstellen. Dies geschieht durch Welche Anforderungen Systemaufrufe wie fork() in Unix- stellt Nebenläufigkeit basierten Systemen oder durch Alp4_Nebenläufigkeit an das System? Thread-APIs wie pthread_create() in der POSIX-Thread-Bibliothek. Prozesse oder Threads sind notwendig, um verschiedene Aufgaben gleichzeitig zu bearbeiten. 3. Möglichkeit, zwischen Prozessen zu wechseln (Prozesswechsel oder Kontextwechsel): Das System muss fähig sein, zwischen verschiedenen Prozessen oder Threads zu wechseln. Dies wird als Kontextwechsel (Context Switch) bezeichnet. Kontextwechsel Ein Kontextwechsel (auch (Context Switch) Prozesswechsel genannt) bezeichnet in der Informatik den Vorgang, bei dem das Betriebssystem von einem Prozess oder Thread zu einem anderen wechselt. Dabei wird der aktuelle Ausführungszustand (Kontext) des laufenden Prozesses gesichert und der Kontext des neuen Prozesses geladen. Der Kontext umfasst alle relevanten Informationen des Prozesses, wie: Unbenannt 4  Frage Antwort Thema Den Befehlszähler (welche Anweisung als Nächstes ausgeführt werden soll) Die CPU-Register (Werte, die gerade von der CPU verwendet werden) Den Speicherzustand (Informationen über den zugewiesenen Speicher) Dieser Wechsel ist notwendig, um mehrere Prozesse oder Threads auf einer CPU laufen zu lassen, da nur ein Prozess/Thread zur gleichen Zeit aktiv auf der CPU ausgeführt werden kann. Overhead: Kontextwechsel verursachen einen gewissen Overhead, da das Speichern und Laden des Prozesses Zeit kostet und Ressourcen verbraucht, ohne dabei produktive Arbeit zu leisten. Welchen Einfluss hat Prozesswechsel: Alp4_Nebenläufigkeit Nebenläufigkeit auf die Prozesswechsel erzeugen einen Performance? Overhead Häufige Wechsel zwischen Prozessen erzeugen Overhead, der die Leistung verringert. Wenn mehrere Prozesse oder Threads nebeneinander laufen, müssen oft die Prozessorressourcen zwischen ihnen gewechselt werden. Dieser Wechsel wird als Prozesswechsel (oder Kontextwechsel) bezeichnet. Jeder Kontextwechsel erfordert Zeit, um den aktuellen Zustand eines Prozesses zu speichern und den Zustand eines anderen zu laden. Dies verursacht einen Overhead, der die Gesamtleistung beeinträchtigen kann, da diese Zeit nicht für die eigentliche Verarbeitung genutzt wird. Reduzierung CPU-Leerlauf: Unbenannt 5  Frage Antwort Thema Nebenläufigkeit reduziert den Leerlauf der CPU, indem sie es ermöglicht, in Wartezeiten andere Aufgaben zu bearbeiten. Overhead bezeichnet in der Informatik den zusätzlichen Ressourcenaufwand (z.B. Zeit, Speicher), der erforderlich ist, um eine Aufgabe auszuführen, aber nicht direkt zur eigentlichen Verarbeitung beiträgt. Ein Beispiel ist der Kontextwechsel zwischen Prozessen, bei dem Zeit für das Speichern und Laden von Zuständen benötigt wird, ohne dass dabei nützliche Arbeit erledigt wird. Wie agieren Threads in Alle Threads nutzen einen Alp4_Threads Bezug auf das gemeinsamen Adressraum, aber Maschinenmodell? jeweils einen eigenen Stack. Gemeinsamer Adressraum: Alle Threads eines Prozesses nutzen denselben virtuellen Adressraum. Das bedeutet, sie haben Zugriff auf die gleichen globalen Variablen, den gleichen Heap-Speicher und statische Daten. Dadurch können Threads Daten effizient austauschen, da sie auf denselben Speicher zugreifen können. Eigener Stack: Jeder Thread besitzt jedoch seinen eigenen Stack. Der Stack enthält lokale Variablen, Funktionsaufrufe und Rücksprungadressen, die nur für diesen Thread relevant sind. Dies ist notwendig, damit Threads unabhängig voneinander Funktionen aufrufen und abarbeiten können, ohne sich gegenseitig zu beeinflussen. Unbenannt 6  Frage Antwort Thema Zusammengefasst: Threads teilen sich den Speicher (Adressraum) und können auf dieselben Daten zugreifen, sind aber durch eigene Stacks voneinander getrennt, um unabhängig agieren zu können. Bei klassischer Nebenläufigkeit mit Prozessen wird der gesamte Speicher eines Prozesses (inklusive Adressraum) für jeden neuen Prozess kopiert. Dies führt zu einem höheren Speicherbedarf. Threads hingegen teilen sich den gleichen Adressraum innerhalb eines Welchen Vorteil haben Prozesses, wodurch kein vollständiges Threads in Bezug auf Kopieren des Speichers notwendig ist. Speichernutzung Sie sparen dadurch Speicher, da sie Alp4_Threads gegenüber auf denselben globalen Speicher und Nebenläufigkeit? Heap zugreifen können, während jeder Thread nur seinen eigenen Stack benötigt. Zusammengefasst: Threads haben einen geringeren Speicheraufwand, weil sie den Speicher eines Prozesses teilen, anstatt ihn für jeden neuen Prozess zu duplizieren. Welches Das Hauptproblem bei der Alp4_Threads Hauptproblem erzeugt Programmierung mit mehreren Threads die Programmierung ist die fehlende Deterministik der mit mehreren Threads Ausführung. Da die Threads parallel und wie nennt man auf den gemeinsamen Adressraum Bereiche, in denen zugreifen, kann es zu dieses auftritt? Dateninkonsistenzen kommen, wenn mehrere Threads gleichzeitig dieselben Daten ändern. Dies kann unerwartete oder falsche Ergebnisse verursachen. Solche Bereiche, in denen mehrere Threads gleichzeitig auf gemeinsam Unbenannt 7  Frage Antwort Thema genutzte Ressourcen zugreifen und es zu Konflikten kommen kann, nennt man kritische Abschnitte. Um diese zu schützen, müssen Mechanismen wie Sperren (Locks) oder Semaphore eingesetzt werden, um den gleichzeitigen Zugriff zu koordinieren. Operationen der einzelnen Threads werden nicht mehr deterministisch ausgeführt und können dadurch aufgrund des gemeinsamen Adressraums ein falsches Ergebnis erzeugen. Solche Bereiche werden Kritische Abschnitte genannt. Funktionale Anforderungen: - Sicherung des kritischen Abschnitts - Höhere Programmiersprache Welche Anforderungen - Kein Deadlo stellen wir an eine ck Alp4_Threads Lösung zur Sicherung Gegenseitiger eines kritischen Nichtfunktionale Anforderu Ausschluss Abschnitts? ngen: - Minimaler Overhead (kein übermäßiges warten) - Fairer Zugriff auf kritischen Abschnitt - Einfaches Lock Welche Arten von - Twofold Lock Gegenseitiger Locks ohne OS- - Twofold Lock with Primary Protection Ausschluss Unterstützung gibt es? - Twofold Lock with Mutual Precedence Woran erkenne ich ein Gegenseitiger Nur eine Lock-Variable Ausschluss einfaches Lock? Welche funktionalen Locken ist ein ungeschützter Anforderungen erfüllt Gegenseitiger kritischer Abschnitt ein einfaches Lock Ausschluss nicht? Unbenannt 8  Frage Antwort Thema Sei n die Anzahl der Threads. - Array von n Lock-Variablen - Locken passiert nach der Warteschleife Ein Twofold Lock (oder auch Dekker’s Algorithmus/Algorithmus mit zwei Sperren) erkennt man an folgenden Merkmalen: 1. Array von n Lock-Variablen: - Es gibt ein Array mit n Lock- Variablen, wobei jede Variable einem Thread zugeordnet ist. Diese Lock- Variablen zeigen an, ob ein bestimmter Thread in einen kritischen Abschnitt eintreten möchte oder nicht. 2. Warteschleife (Busy Waiting): - Bevor ein Thread in den kritischen Woran erkenne ich ein Abschnitt eintritt, überprüft er in einer Gegenseitiger Warteschleife (Busy Waiting), ob die Ausschluss Twofold Lock? Lock-Variablen der anderen Threads gesetzt sind. Der Thread muss warten, wenn ein anderer Thread bereits eintritt oder den Eintritt beabsichtigt. 3. Locken nach der Warteschleife: - Nachdem ein Thread erfolgreich festgestellt hat, dass kein anderer Thread den kritischen Abschnitt betreten möchte, setzt er seine eigene Lock-Variable und betritt den kritischen Abschnitt. Dadurch signalisiert er den anderen Threads, dass er den Abschnitt nutzt. Das Twofold Lock stellt sicher, dass nur ein Thread den kritischen Abschnitt betreten kann, indem es zwei Schritte nutzt: Erst die Überprüfung der Lock- Variablen und dann das Setzen des eigenen Locks. Unbenannt 9  Frage Antwort Thema Locken ist ein ungeschützter kritischer Abschnitt - Freigebender Thread könnte Zugriff anfordern, obwohl er zuvor Unlockt hat. Ein Twofold Lock erfüllt die folgenden funktionalen Anforderungen nicht vollständig: 1. Ungeschützter kritischer Abschnitt beim Locken: ◦ Das Setzen des Locks (Locken) selbst findet in einem ungeschützten Bereich statt. Dies bedeutet, dass mehrere Threads gleichzeitig versuchen könnten, die Lock-Variable zu setzen, was zu Race Conditions führen kann, bei denen unvorhersehbare Zustände Welche funktionalen entstehen. Anforderungen erfüllt 2. Gegenseitiger ein Twofold Lock Freigabeprobleme (Unlocken): Ausschluss nicht? ◦ Ein Thread, der gerade den kritischen Abschnitt verlässt und seine Lock- Variable freigibt, könnte gleichzeitig wieder den kritischen Abschnitt anfordern. Da das Locken nicht atomar erfolgt, besteht die Möglichkeit, dass der freigebende Thread sich selbst erneut sperrt, bevor ein anderer Thread die Chance hat, den kritischen Abschnitt zu betreten. Das führt zu unfairen Bedingungen oder ineffizientem Verhalten, da andere Threads blockiert bleiben könnten. Zusammengefasst: Das Twofold Lock hat Schwächen in der Synchronisation des Lockens und Unlockens, da diese Operationen nicht sicher vor Race Conditions sind und nicht garantieren, dass der Zugriff auf den kritischen Abschnitt stets korrekt erfolgt. Unbenannt 10  Frage Antwort Thema Sei n die Anzahl der Threads. - Array von n Lock-Variablen - Locken passiert vor der Warteschleife. Ein Twofold Lock with Primary Protection lässt sich an folgenden Merkmalen erkennen: 1. Array von n Lock-Variablen: Es gibt ein Array mit n Lock-Variablen, wobei jede Variable einem bestimmten Thread zugeordnet ist. Jede dieser Variablen zeigt an, ob ein Thread den kritischen Abschnitt betreten möchte. 2. Locken vor der Warteschleife: Woran erkenne ich ein Im Gegensatz zum einfachen Twofold Gegenseitiger Twofold Lock with Lock wird hier das Locken vor der Ausschluss Primary Protection? Warteschleife durchgeführt. Das bedeutet, dass ein Thread zuerst seine eigene Lock-Variable setzt, bevor er in die Warteschleife eintritt, um zu überprüfen, ob andere Threads gerade den kritischen Abschnitt betreten. Zusammengefasst: Bei einem Twofold Lock with Primary Protection erfolgt das Locken direkt vor der Warteschleife, was einen besseren Schutz vor gleichzeitigen Zugriffsversuchen durch mehrere Threads bietet. Welche funktionalen Es kann ein Deadlock enstehen. Gegenseitiger Anforderungen erfüllt Ein Ausschluss ein Twofold Lock with Twofold Lock with Primary Protection Primary Protection erfüllt die folgenden funktionalen nicht? Anforderungen nicht vollständig: 1. Deadlock-Gefahr: ◦ Da jeder Thread seine eigene Lock- Variable vor dem Eintritt in die Warteschleife setzt, kann es passieren, Unbenannt 11  Frage Antwort Thema dass zwei oder mehr Threads gleichzeitig ihre Lock-Variablen setzen und dann aufeinander warten. Dies führt zu einem Deadlock, bei dem kein Thread den kritischen Abschnitt betreten kann, weil sie sich gegenseitig blockieren. Sei n die Anzahl der Threads. - Array von n Lock-Variablen - Locken passiert vor der Warteschleife - In der Warteschleife wird das eigene Lock Woran erkenne ich ein wiederholt für 1 Sekunde unlockt. Das Gegenseitiger Twofold Lock with wiederholte Unlocken stellt sicher, Ausschluss Mutual Precedence? dass andere Threads eine Chance bekommen, in den kritischen Abschnitt zu gelangen, und verringert die Wahrscheinlichkeit von Verhungern (Starvation). Warum erfüllt ein - Kritischer Abschnitt wird zuverlässig Twofold Lock with geschützt. - Ist in höherer Gegenseitiger Mutual Precedence die Programmiersprache umsetzbar - Ausschluss funktionalen Deadlocks werden durch Unlocken in Anforderungen? Warteschleife aufgelöst. Welche Lösung zur Sicherung des kritischen Abschnitts Ein Twofold Lock with Mutual Gegenseitiger ohne OS- Precedence Ausschluss Unterstützung erfüllt alle funktionalen Anforderungen? Welche Lösung zur Sicherung des kritischen Abschnitts ohne OS- Ein Twofold Lock with Mutual Access Gegenseitiger Unterstützung erfüllt by Peterson Ausschluss alle funktionalen und nichtfunktionalen Anforderungen? Unbenannt 12  Frage Antwort Thema Welche Gründe sprechen für eine OS- - Overhead wird durch Hardware- Gegenseitiger basierte Lösung zur Optimierungen reduziert - Locken und Ausschluss Sicherung des Unlocken sind atomare Operationen kritischen Abschnitts? - Threadwechsel erzeugen einen Welchen Einfluss Overhead - Ein Gegenseitiger haben Threads auf die Geschwindigkeitszuwachs entsteht, Ausschluss Performance? wenn das Programm sinnvoll in parallele Abschnitte aufgeteilt wird Entstehung Wenn der anfordernde Wann entsteht ein Thread das Lock nicht innerhalb der Gegenseitiger Livelock und was ist Sleep-Zeit des anderen Threads Ausschluss die Folge? erlangen kann Folge Verhungern Unterschied zum Deadlock: Deadlock: Die Threads sind vollständig blockiert und warten gegenseitig auf Ressourcen, sodass keiner mehr weitermachen kann. Sie bleiben in einem Zustand vollständiger Blockierung. Gegenseitiger Livelock Vs. Deadlock Livelock: Die Threads sind nicht Ausschluss blockiert, sondern ändern ständig ihren Zustand (z.B. freigeben und anfordern), kommen aber ebenfalls nicht weiter. Tür beispiel, aus höflichkeit immer zurücktreten In beiden Fällen entsteht eine Blockade, aber beim Livelock sind die Threads aktiv, beim Deadlock sind sie blockiert. 1. Ressourcen werden exklusiv genutzt 2. Threads oder Prozessen ist eine Wie lauten die vier Ressource zugewiesen und sie Bedingungen für eine versuchen, sich eine andere Verklemmung Verklemmung? zuzuweisen 3. Es gibt keine Preemption 4. Es gibt einen Kreis im Wartegraphen Unbenannt 13  Frage Antwort Thema 1. Thread 1 hat Objekt 1 im Speicher gesperrt (zugewiesen). 2. Thread 2 hat Objekt 2 im Speicher gesperrt (zugewiesen). 3. Thread 1 versucht nun, auf Objekt 2 Kann es beim zuzugreifen, das aber von Thread 2 Hauptspeicher als gesperrt ist. Ressource zu einer 3. Gleichzeitig versucht Thread 2, auf Verklemmung Verklemmung Objekt 1 zuzugreifen, das von Thread 1 kommen? gesperrt ist. In diesem Fall entsteht ein Deadlock, da beide Threads aufeinander warten und keiner weiterkommen kann, weil sie die jeweils vom anderen gesperrten Ressourcen benötigen. Kann es bei der CPU Ja, zum Beispiel bei mehreren Verklemmung als Ressource zu einer Threads, deren kritischer Abschnitt Verklemmung mit einem Lock ohne Mutual kommen? Precedence gesichert ist. Beispiel: Mehrere Threads verwenden einen kritischen Abschnitt, der mit einem Lock gesichert ist, aber dieses Lock hat keine Mutual Precedence (gegenseitige Vorzugsregel). Thread 1 hat das Lock erworben und führt Berechnungen aus, während Thread 2 wartet. Wenn Thread 1 nun eine weitere Ressource benötigt, die von Thread 2 blockiert ist (oder umgekehrt), entsteht eine Zyklusabhängigkeit. Grund: Ohne Mutual Precedence oder eine ähnliche Fairness-Regel kann es passieren, dass Threads sich gegenseitig in einem Wartezustand festhalten, Unbenannt 14  Frage Antwort Thema insbesondere wenn sie auf verschiedene Ressourcen zugreifen oder eine unkoordinierte Sperrmechanik verwenden. Zusammengefasst: Deadlock Prevention (Verklemmungsvermeidung): Deadlocks verhindern, bevor sie entstehen. Deadlock Avoidance Welche vier Methoden (Verklemmungsumgehung): gibt es für den Ressourcenvergabe so steuern, dass Verklemmung Umgang mit Deadlocks vermieden werden. Verklemmungen? Deadlock Detection (Verklemmungserkennung): Aktiv nach Deadlocks suchen und sie erkennen. Deadlock Resolution(Verklemmungsauflösung): Maßnahmen ergreifen, um erkannte Deadlocks aufzulösen. G = B + R v = f + B[+] Wie lauten die (Spaltensummen) Nach jeder Gleichungen für den Verklemmung Terminierung eines Threads t: f := f Bankier-Algorithmus? + B[Zeile t] Mutex: Verhindert gleichzeitigen Zugriff auf einen kritischen Abschnitt. Welche Lösungen zur Semaphore: Steuert den Zugriff auf Sicherung des eine Anzahl von Ressourcen und Gegenseitiger kritischen Abschnitts ermöglicht mehr Flexibilität. Ausschluss mit OS-Unterstützung gibt es? Monitor: Kapselt kritische Abschnitte und bietet eine einfache Schnittstelle für den Zugriff und die Verwaltung von Bedingungsvariablen. Eine Lösung für gegenseitigen Gegenseitiger Was ist ein Mutex? Ausschluss Ausschluss Unbenannt 15  Frage Antwort Thema Erweiterung der Lock-Variable (um die Möglichkeit, mehrere Threads gleichzeitig den Zugriff auf den kritischen abschnitt zu erlauben Was ist eine Semaphore und wie Unterschied zum Lock: Es können Gegenseitiger unterscheidet sie sich mehrere Threads in den kritischen Ausschluss von einem Lock und Abschnitt eintreten einem Monitor? Unterscheid zum Monitor: Semaphore, Lock und Unlock sind explizit (von dem Programmierer gesetzt. Monitor ist implizit, es passiert also automatisch Zähler, der anzeigt, wie viele Threads in den kritischen Abschnitt eintreten dürfen Eintreten ist erst möglich, wenn der Wie funktioniert eine Gegenseitiger Zähler > 0 ist Semaphore? Ausschluss Beim Eintreten wird der Zähler dekrementiert (-1) Beim Austreten wird der Zähler inkrementiert (+1) Was ist ein Monitor Ein Objekt, - das Funktionen und Daten Gegenseitiger und wie unterscheidet enthält - sicherstellt, dass immer nur Ausschluss er sich von einem Lock ein Thread gleichzeitig darauf zugreift. und einer Semaphore? Unterschiede zu Lock und Semaphore: 1. Monitor vs. Lock: ◦ Lock: Ein Lock ist einfach, die explizit vom Programmierer verwendet wird, um einen kritischen Abschnitt zu sperren und wieder freizugeben. Es stellt sicher, dass nur ein Thread in den kritischen Abschnitt eintreten kann, aber der Programmierer muss das Sperren und Freigeben manuell steuern. ◦ Monitor: Im Gegensatz dazu kümmert Unbenannt 16  Frage Antwort Thema sich der Monitor automatisch um das Sperren und Freigeben. Der Programmierer arbeitet nur mit den Funktionen und muss nicht explizit locken oder unlocken. 2. Monitor vs. Semaphore: ◦ Semaphore: Eine Semaphore kann mehrere Threads gleichzeitig in den kritischen Abschnitt lassen, je nachdem, wie der Zähler der Semaphore eingestellt ist. Der Programmierer muss explizit festlegen, wann ein Thread eintreten darf ( sem_wait ) und wann er den Abschnitt verlassen soll ( sem_post ). ◦ Monitor: Im Gegensatz dazu erlaubt der Monitor standardmäßig nur einem Thread den Zugriff auf den kritischen Abschnitt. Die Synchronisation wird automatisch verwaltet, ohne dass der Programmierer lock oder unlock Befehle verwenden muss. - Zeigen an, ob ein Thread innerhalb Was sind Condition des Monitors freigegeben werden kann Gegenseitiger Variables bei oder warten muss. Ausschluss Monitoren? wait,signal,broadcast Wann ist ein Teil eines Wenn es eine Folge von Transitionen Petri Netzes gibt, durch die Tokens den Teil Petri Netze erreichbar? erreichen können Schwach lebendig: Wenn es eine Transition gibt, die feuern kann und Wann ist ein Petri-Netz dieses Feuern das Feuern einer stark lebendig und anderen Transition ermöglicht. Petri Netze schwach lebendig? Stark lebendig: Wenn alle Transitionen schwach lebendig sind. Was sind farbige Petri- - Erweiterung von Petri-Netzen - Token Petri Netze Netze und wann sind werden farblich oder mit Nummern Unbenannt 17  Frage Antwort Thema sie sinnvoll? gekennzeichnet - Sinnvoll bei komplexen Petri-Netzen Welche Probleme - Speisende Philosophen, - wurden in der Produzenten und Konsumenten, - Petri Netze Vorlesung mit Petri- (Accouting) Netzen modelliert? 1. Partitionierung: Aufteilen des Problems in minimale unabhängige Aufgaben Welche vier Schritte 2. Communication: Beziehungen beinhaltet das zwischen Aufgaben rausfinden Fostersche 3. Agglomeration: Aufgaben zu Foster Vorgehensmodell zur Gruppen zusammenfassen, die je Entwicklung paralleler zusammen auf einem Prozessor laufen Programme? sollen 4. Mapping: Die Gruppen den konkreten Prozessoren zuordnen Welche zwei Arten von Partionierung gibt es im Fosterschen Vorgehensmodell? Domain and Data Decomposition: Welche zwei Arten von Zerlegt das Problem auf Basis der Partionierung gibt es Daten, die voneinander unabhängig Foster im Fosterschen verarbeitet werden können. Vorgehensmodell? Functional Decomposition: Zerlegt das Problem auf Basis der Funktionen oder Aufgaben, die unabhängig voneinander ausgeführt werden können. Welches Problem tritt Komplette Aufteilung ist nicht möglich. Foster bei Partitionierung auf? Aufteilung ist immer ein Kompromiss zwischen Größe der Aufgaben und Kommunikationskosten. Zu kleine Partitionen: ◦ Viele kleine Aufgaben können zu einer Effizienzsteigerung in der Lastverteilung führen, aber die Unbenannt 18  Frage Antwort Thema notwendige Kommunikation und Synchronisation zwischen den Prozessen oder Threads kann mehr Zeit in Anspruch nehmen als die eigentliche Berechnung. Zu große Partitionen: ◦ Große Aufgaben minimieren die Kommunikationskosten, aber sie können zu ungleichmäßiger Lastverteilung führen, bei der einige Prozessoren überlastet sind, während andere untätig bleiben Mehr Aufgaben als Prozessoren Wenige redundante Berechnungen Wann ist eine und Daten Foster Partitionierung gut? Aufgaben sind alle gleich groß Anzahl der Aufgaben proportional zur Problemgröße - Gleichmäßige Lastverteilung des Kommunikationsaufwands zwischen allen aufgaben - Minimale Interaktion zwischen Aufgaben (wenig kommunikation unter Wann ist ein den aufgaben selbst) Kommunikationsmodell - Nebenläufige Ausführung von Foster gut? Kommunikation und Berechnungen (Das bedeutet, dass die Aufgaben während der Kommunikation weiterhin Berechnungen durchführen können, ohne auf den Abschluss der Kommunikation warten zu müssen) Wann ist ein - Reduziert insgesamt Agglomerationsmodell Kommunikationsaufwand - Foster gut? Änderungsfreundlichkeit Wann ist ein - Volle Auslastung aller Prozessoren Foster Mappingmodell gut? Was besagt Amdahls - Geschwindigkeitszuwachs bei Foster Gesetz? parallelen Programmen wird durch sequentiellen Anteil beschränkt - Je Unbenannt 19  Frage Antwort Thema höher der sequentielle Anteil, desto niedriger der Geschwindigkeitszuwachs Sockets sind Endpunkte für die Netzwerkkommunikation, die den Datenaustausch zwischen einem Client und einem Server ermöglichen. Was sind Sockets & Sockets Ports? Ports sind numerische Kennungen, die verschiedene Netzwerkdienste oder Anwendungen auf einem Computer identifizieren und ermöglichen es mehreren Anwendungen, gleichzeitig zu kommunizieren. RMI ist eine Java Technologie, die den Aufruf von Methoden auf entfernten Systemen erlaubt. Es wird verwendet, um verteilte Anwendungen zu Was ist Java RMI? RMI erstellen, bei denen Komponenten auf verschiedenen Rechnern miteinander kommunizieren und zusammenarbeiten können. Was passiert (bezogen 1. Client verbindet sich zum Server: RMI auf RMI), wenn eine Der Client sucht das entfernte Objekt in Methode eines der RMI-Registry und verbindet sich entfernten Objekts mit dem Server, auf dem das Remote- aufgerufen wird? Objekt registriert ist. 2. Client serialisiert Aufrufdaten: Der Methodenaufruf und die übergebenen Parameter werden serialisiert (in eine übertragbare Form umgewandelt). 3. Server akzeptiert die Verbindung: Der Server empfängt die Anfrage des Clients und stellt sicher, dass die Verbindung hergestellt ist. 4. Server leitet den Aufruf an das Unbenannt 20  Frage Antwort Thema Remote-Objekt weiter: Auf der Serverseite wird der Methodenaufruf durch den Skeleton (oder direkt durch das Framework) an das entfernte Objekt weitergeleitet, und die Methode wird ausgeführt. 5. Server serialisiert die Ausgabe des Aufrufs: Die Rückgabewerte oder Ausgaben der entfernten Methode werden serialisiert, um sie über das Netzwerk zurück an den Client zu senden. 6. Client empfängt und deserialisiert die Antwort: Der Client empfängt die Antwort, deserialisiert sie und gibt sie an den Aufrufer (den Client-Teil der Anwendung) zurück. Was passiert (bezogen auf RMI), wenn eine Methode eines Es wird eine RemoteException, entfernten Objekts mit genauer eine NotSerializableException einem Parameter, das geworfen, weil die Argumente einer RMI nicht das Serializable- Remote Method serialisierbar sein Interface müssen. implementiert, aufgerufen wird? Welche Java RMI- Interfaces werden -Remote -Serializable RMI benötigt? Server erstellt Stub des Remote- Objekts Was muss passieren, Server bindet Stub in der Registry damit ein Client ein Client holt sich Registry vom Server RMI Vertreter-Objekt Client holt sich Stub des Remote- erhält? Objekts aus der Registry Der Stub ist das Vertreter- Objekt. Was ist MPI MPI (Message Passing Interface) ist MPI ein standardisiertes Unbenannt 21  Frage Antwort Thema Kommunikationsprotokoll, das für paralleles Rechnen auf verteilten Systemen verwendet wird. Es ermöglicht den Austausch von Nachrichten zwischen Prozessen, die auf verschiedenen Rechnern oder in verschiedenen Adressräumen laufen. Wie lauten die Hier ist die Zusammenfassung der MPI Signaturen der wichtigsten MPI-Befehle: wichtigsten MPI- Befehle? MPI_Init(int *argc, char *argv) Initialisiert die MPI-Laufzeitumgebung. MPI_Finalize() Beendet die MPI-Laufzeitumgebung und gibt alle Ressourcen frei. *MPI_Comm_rank(MPI_Comm comm, int rank) Gibt den Rang (die ID) des aktuellen Prozesses zurück. *MPI_Comm_size(MPI_Comm comm, int size) Gibt die Anzahl der Prozesse in der MPI-Gruppe zurück. *MPI_Send(const void buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm) Sendet Daten synchron an einen anderen Prozess (blockiert bis Buffer freigegeben). **MPI_Isend(const void buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Request request) Asynchrone Version von MPI_Send (blockiert nicht). **MPI_Recv(void buf, int count, Unbenannt 22  Frage Antwort Thema MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status status) Empfängt synchron Daten von einem anderen Prozess. **MPI_IRecv(void buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Request request) Asynchrone Version von MPI_Recv. **MPI_Test(MPI_Request *request, int flag, MPI_Status status) Überprüft, ob eine asynchrone Operation abgeschlossen ist. **MPI_Wait(MPI_Request request, MPI_Status status) Wartet auf den Abschluss einer asynchronen Operation. OpenMP ist ideal für multithreading auf Shared-Memory-Systemen (z.B. Desktop- oder Server-Systeme). OpenMP VS MPI MPI ist optimal für verteiltes Rechnen auf Distributed-Memory-Systemen (z.B. Cluster oder Supercomputer). Wann ist bei einer Statisches Scheduling OpenMP parallelen For-Schleife Wann sinnvoll? statisches, wann dynamisches Wenn alle Iterationen der Schleife Scheduling sinnvoll ähnliche oder gleiche Kosten haben. und was ist ein Da die Arbeitslast gleichmäßig verteilt Nachteil des werden kann, führt dies zu einer dynamischen effizienten Auslastung der Threads. Scheduling? Dynamisches Scheduling Wann sinnvoll? Wenn die Iterationen unterschiedliche Unbenannt 23  Frage Antwort Thema Kosten oder Laufzeiten aufweisen (z. B. wenn einige Berechnungen aufwendiger sind als andere). Erlaubt eine flexible Verteilung der Iterationen an Threads, basierend auf deren Verfügbarkeit. Nachteil: Höherer Overhead im Vergleich zum statischen Scheduling, da zusätzliche Ressourcen benötigt werden, um die Iterationen dynamisch zu verwalten und Threads bei der Arbeit zu koordinieren. Dies kann die Gesamteffizienz der Parallelisierung beeinträchtigen, insbesondere bei kurzen Schleifen oder wenn die Kostenunterschiede zwischen den Iterationen gering sind. Weitere Klausurfragen 1. In der Klausur kam auch die Frage: Wie sieht der Pseudocode einesTwofold Locks with Mutual Precedence aus? (Globals, lock(), unlock()) 2. Was sind die wichtigsten POSIX- Methoden für Semaphoren? sem_init: Semaphore initialisieren - sem_t *sem: Zeiger auf Semaphore - int pshared: Max. gleichzeitige Threads - int value: Initialer Zähler sem_wait: Warten auf Eintritt Unbenannt 24  - sem_t *sem: Zeiger auf Semaphore sem_post: Austritt - sem_t *sem: Zeiger auf Semaphore 3. Info zu: OS-basierte Lösung zur Sicherung des kritischen Abschnitts Hier sind die Hauptgründe, die für eine OS-basierte Lösung zur Sicherung des kritischen Abschnitts sprechen: 1. Hardware-Unterstützung für atomare Operationen: Das Betriebssystem nutzt spezielle Hardware-Instruktionen, wie Test-and-Set, Compare-and-Swap, oder Fetch-and-Add, um Locken und Unlocken als atomare Operationen durchzuführen. Dies garantiert, dass diese Operationen ununterbrochen und ohne Race Conditions ausgeführt werden. 2. Reduzierter Overhead durch Optimierungen: Betriebssysteme verwenden optimierte Scheduling-Algorithmen und Hardware-Synchronisationsmechanismen (z.B. Spinlocks, Mutexe), um den Overhead für Kontextwechsel und Synchronisation zu minimieren. Hardware-basierte Lösungen sind dabei oft schneller und effizienter als softwarebasierte Implementierungen. 3. Vermeidung von Deadlocks und Starvation: Das Betriebssystem implementiert erweiterte Mechanismen, um Deadlocks zu vermeiden oder zu lösen, und stellt sicher, dass Threads nicht verhungern (Fairness). Diese Mechanismen sind in Softwarelösungen schwieriger zu implementieren. 4. Skalierbarkeit: OS-basierte Lösungen sind auf Multithreading und Multiprozessorsysteme optimiert, wodurch sie besser skalieren und effizient mit einer großen Anzahl von Threads und Prozessen umgehen können. Zusammengefasst bieten OS-basierte Lösungen durch Hardware- Unterstützung, Effizienz, Atomizität und erweiterte Mechanismen zur Unbenannt 25  Vermeidung von Problemen wie Deadlocks und Starvation eine sicherere und leistungsfähigere Methode zur Synchronisation von Threads Locks Unbenannt 26 Unbenannt 27 Unbenannt 28 Unbenannt 29 Unbenannt 30  Parallele Programmierung: Foster Modell + 2 Beispiele Beispiel Matrizenmultiplikation Unbenannt 31  Partitionierung: - Berechnung der Felder in der Zielmatrix Communication: - Vor Berechnung: Zeile der Eingabematrix A und Spalte der Eingabematrix B vom Root Task zum jeweiligen Untertask - Nach Berechnung: Ergebnisse der Untertasks zum Root Task Agglomeration: - Gruppiere Tasks, die die gleichen Zeilen und Spalten der Eingabematrizen nutzen Mapping: - Keine Kommunikation zwischen Untertasks Unbenannt 32  - Root Task so zuordnen, dass die Kommunikationskosten zu den Untertasks reduziert wird Beispiel Quicksort: Partitionierung: - Functional decomposition nicht sinnvoll, denn Berechnungen sind voneinander abhängig - Data decomposition nicht sinnvoll, denn Array-Bereiche sind während Laufzeit von Pivot- Element abhängig - Also eine Kombination: Tasks sind die Unterlisten jeder Rekursionsstufe - Bei jedem Merge muss synchronisiert werden Communication: Unbenannt 33  - Unterlisten bei jeder Rekursion vom Aufrufer zur Unteraufgabe - Nach jeder Berechnung von der Unteraufgabe zum Aufrufer Agglomeration: - Tasks gruppieren, die auf der gleichen Unterliste rechnen Mapping: - Untertasks sollten möglichst nah an ihrem Ersteller liegen Client-Server-Socket-Kommunikation Ist der zeitliche Ablauf für eine Client- Server-Socket- Kommunikation korrekt? Server | ServerSocket s = new ServerSocket(port); Server | s.accept(); Client | Socket s = new Socket(serverURL, serverPort); Client | InputStream in = s.getInputStream(); Client | OutputStream out = s.getOutputStream(); Server | InputStream in = s.getInputStream(); Server | OutputStream out = s.getOutputStream(); Client Server ServerSocket s = new ServerSocket(port); s.accept(); Socket s = new Socket(serverURL, serverPort); InputStream in = s.getInputStream(); OutputStream out = s.getOutputStream(); InputStream in = s.getInputStream(); OutputStream out = s.getOutputStream(); Unbenannt 34  Ablauf in der Reihenfolge: Server erstellt ServerSocket. Server wartet (blockiert) auf eine Client-Verbindung. Client stellt eine Verbindung zum Server her. Client erhält Input- und Output-Streams. Server erhält Input- und Output-Streams. Sockets: Pseudocode für einen Echo-Server mit Sockets aus (Client und Server)? Wie sieht der Pseudocode für einen Echo-Server mit Sockets aus (Client und Server)? Server: ServerSocket s = new ServerSocket(port); s.accept(); InputStream in = s.getInputStream(); BufferedReader reader = new BufferedReader( new InputStreamReader(in) ); OutputStream out = s.getOutputStream(); while(true) { String line = reader.readLine(); if(line.equals(”bye\n”)) { s.close(); break; } out.write() } Client: Socket s = new Socket(serverURL, serverPort); InputStream in = s.getInputStream(); OutputStream out = s.getOutputStream(); Unbenannt 35  ….. ich glaube es ist so noch nicht vollständig RMI: Wie sieht der Code für einen Fernaufruf einer Methode auf dem Client aus? Unbenannt 36  OpenMP Code Unbenannt 37  MPI Code MPI VS OpenMP Unbenannt 38 Unbenannt 39  Pragmas und Clauses von OpenMP: Unbenannt 40 Unbenannt 41