Kommunikation und Parallele Prozesse - Exam

Aufgabe 1)

Prozesskommunikation ist ein essentieller Bestandteil der parallelen und verteilten Systeme. Die Interaktionen zwischen Prozessen beinhalten die Synchronisation und den Datenaustausch. Die wichtigsten Konzepte hierbei sind Nachrichtenübermittlung und gemeinsamer Speicher. Bei der Nachrichtenübermittlung kann zwischen synchroner und asynchroner Kommunikation sowie blockierenden und nicht-blockierenden Operationen unterschieden werden. Middleware wie CORBA, MPI und JMS bieten eine abstrahierte Schnittstelle für die Prozesskommunikation. Die Synchronisation kann durch Mechanismen wie Mutex, Monitore und Barrieren erreicht werden, um Probleme wie Deadlocks und Race Conditions zu verhindern.

a)

Angenommen, Du hast zwei Prozesse, die gleichzeitig auf eine gemeinsame Ressource zugreifen. Beschreibe detailliert, wie Du dieses Szenario mithilfe von Mutexen und Monitoren so synchronisieren würdest, dass es keine Race Conditions gibt. Erläutere auch, welche zusätzlichen Maßnahmen notwendig sind, um Deadlocks zu verhindern.

Lösung:

Um zwei Prozesse, die gleichzeitig auf eine gemeinsame Ressource zugreifen, zu synchronisieren und Race Conditions zu vermeiden, können Mutexe und Monitore verwendet werden. Lade bitte dazu ausführliche Erklärungen mit etwas Code und mathematischen Formeln, die das Konzept verdeutlichen.

• Verwendung von Mutexen:

  Ein Mutex (Mutual Exclusion) dient dazu, einen exklusiven Zugriff auf gemeinsame Ressourcen sicherzustellen. Dabei wird ein Mutex-Objekt verwendet, um den Zugang zu einer kritischen Sektion zu regulieren.

   // Pseudocode für Prozess 1 Mutex lock; // Mutex initialisieren lock.acquire(); // Kritische Sektion // ... Zugriff auf gemeinsame Ressource lock.release(); 

   // Pseudocode für Prozess 2 Mutex lock; // Mutex initialisieren lock.acquire(); // Kritische Sektion // ... Zugriff auf gemeinsame Ressource lock.release(); 

  Hier sorgt das Mutex dafür, dass immer nur ein Prozess gleichzeitig Zugriff auf die gemeinsame Ressource hat. Wenn ein Prozess die Ressource verwenden möchte, muss er zuerst den Mutex sperren (lock.acquire()) und nach der Nutzung wieder freigeben (lock.release()).

• Verwendung von Monitoren:

  Ein Monitor ist eine spezielle Synchronisationsstruktur, die sowohl den Mutex als auch die Bedingungsvariablen kombiniert, um den Zugriff auf gemeinsame Ressourcen zu verwalten.

   // Pseudocode für Prozess 1 monitor.enter(); // Kritische Sektion // ... Zugriff auf gemeinsame Ressource monitor.exit(); 

   // Pseudocode für Prozess 2 monitor.enter(); // Kritische Sektion // ... Zugriff auf gemeinsame Ressource monitor.exit(); 

  Der Monitor stellt sicher, dass nur ein Prozess gleichzeitig in der kritischen Sektion agieren kann. Die Methode monitor.enter() sperrt den Zugriff, während monitor.exit() ihn wieder freigibt.

• Zusätzliche Maßnahmen zur Vermeidung von Deadlocks:
  • Verwendung der Reihenfolge:

    Sicherstellen, dass alle Prozesse in derselben Reihenfolge mehrere Ressourcen anfordern, um zyklische Abhängigkeiten zu vermeiden.

  • Timeouts:

    Timeout-Mechanismen können eingeführt werden, die verhindern, dass Prozesse unendlich lange warten. Wenn ein Prozess eine Ressource nicht innerhalb einer bestimmten Zeitspanne erhält, gibt er alle gewonnenen Ressourcen frei.

  • Deadlock-Erkennung:

    Algorithmen zur Erkennung von Deadlocks können implementiert werden, um die Existenz von Deadlocks im System zu überprüfen und entsprechend zu handeln (z. B. Abbruch oder Neustart betroffener Prozesse).

b)

Betrachte ein System, das für die Nachrichtenübermittlung MPI verwendet. Beschreibe den Unterschied zwischen synchroner und asynchroner Kommunikation sowie zwischen blockierenden und nicht-blockierenden Operationen. Implementiere ein einfaches Beispiel in C, bei dem ein Prozess eine Nachricht an einen anderen sendet und gleichzeitig auf eine Antwort wartet. Achte darauf, beide Kommunikationsarten (synchron und asynchron) und beide Arten von Operationen (blockierend und nicht-blockierend) zu demonstrieren.

Lösung:

Die Prozesskommunikation unter Verwendung von MPI kann auf verschiedene Arten erfolgen. Es ist wichtig, die Unterschiede zwischen den Kommunikationsarten und Operationen zu verstehen, um das richtige Vorgehen für das jeweilige Problem zu wählen.

• Synchrone vs. Asynchrone Kommunikation:
  • Synchrone Kommunikation: Bei der synchronen Kommunikation warten Sender und Empfänger darauf, dass der Nachrichtenaustausch vollständig abgeschlossen ist, bevor sie fortfahren.
  • Asynchrone Kommunikation: Bei der asynchronen Kommunikation können Sender und Empfänger unabhängig voneinander fortfahren, ohne darauf zu warten, dass der Nachrichtenaustausch vollständig abgeschlossen ist.
• Blockierende vs. Nicht-blockierende Operationen:
  • Blockierende Operationen: Der Prozess wird angehalten, bis die Operation abgeschlossen ist. Bei einer sendenden Operation beispielsweise wird der Kontrollfluss erst fortgesetzt, wenn die Nachricht erfolgreich gesendet wurde.
  • Nicht-blockierende Operationen: Der Prozess wird nicht angehalten. Die Operation wird im Hintergrund ausgeführt, und der Prozess kann parallel dazu fortgesetzt werden.

Hier ist ein einfaches Beispiel in C, das beide Kommunikationsarten (synchron und asynchron) und beide Arten von Operationen (blockierend und nicht-blockierend) demonstriert:

 #include <mpi.h> #include <stdio.h> #include <string.h> #define TAG 100 int main(int argc, char **argv) { MPI_Init(&argc, &argv); int rank, size; MPI_Comm_rank(MPI_COMM_WORLD, &rank); MPI_Comm_size(MPI_COMM_WORLD, &size); char message[20]; MPI_Status status; if (rank == 0) { // Blockierende synchrone Sendung strcpy(message, "Hello from Rank 0"); MPI_Ssend(message, strlen(message) + 1, MPI_CHAR, 1, TAG, MPI_COMM_WORLD); // Blockierender Empfang MPI_Recv(message, 20, MPI_CHAR, 1, TAG, MPI_COMM_WORLD, &status); printf("Rank 0 received: %s", message); } else if (rank == 1) { // Blockierender Empfang MPI_Recv(message, 20, MPI_CHAR, 0, TAG, MPI_COMM_WORLD, &status); printf("Rank 1 received: %s", message); // Nicht-blockierende asynchrone Sendung strcpy(message, "Hello from Rank 1"); MPI_Request request; MPI_Isend(message, strlen(message) + 1, MPI_CHAR, 0, TAG, MPI_COMM_WORLD, &request); // Nicht-blockierende Sendung überprüfen MPI_Wait(&request, &status); } MPI_Finalize(); return 0; } 

In diesem Beispiel:

• Prozess 0 sendet eine Nachricht an Prozess 1 mit einer blockierenden synchronen Sendung (MPI_Ssend) und wartet anschließend auf eine Antwort mit einem blockierenden Empfang (MPI_Recv).
• Prozess 1 empfängt die Nachricht mit einem blockierenden Empfang (MPI_Recv) und sendet anschließend eine Antwort mit einer nicht-blockierenden asynchronen Sendung (MPI_Isend). Der Abschluss dieser nicht-blockierenden Sendung wird mit MPI_Wait überprüft.

Aufgabe 2)

Parallelität und ConcurrencyParallelität bedeutet die gleichzeitige Ausführung mehrerer Aufgaben, während Concurrency die Strukturierung von Aufgaben beschreibt, die scheinbar gleichzeitig ablaufen.Betrachte dabei folgende Aspekte:

• Kontextwechsel (\textit{context switch}) bei Concurrency
• \textit{Thread}- und \textit{Prozess}-Parallelität
• Ressourcenkonflikte und Synchronisation
• Nutzung von Mehrkernprozessoren, um die Effizienz zu steigern
• Wichtigkeit für Systemleistung und -verfügbarkeit

a)

a) Eine Applikation muss in einer Umgebung ausgeführt werden, in der mehrere Threads parallel arbeiten müssen. Erläutere den Ablauf eines Kontextwechsels, wenn der Scheduler der Applikation von einem Thread auf einen anderen wechselt. Gehe auf die einzelnen Schritte und deren Auswirkungen auf die Systemleistung ein. Nutze dabei Begriffe wie \textit{Prozesskontrollblock}, \textit{Registersicherung} und \textit{Speicherabbilder}. Vergleiche außerdem den Kontextwechsel zwischen Threads und Prozessen.

Lösung:

Parallelität und ConcurrencyParallelität bedeutet die gleichzeitige Ausführung mehrerer Aufgaben, während Concurrency die Strukturierung von Aufgaben beschreibt, die scheinbar gleichzeitig ablaufen.Betrachte dabei folgende Aspekte:

• Kontextwechsel (context switch) bei Concurrency
• Thread- und Prozess-Parallelität
• Ressourcenkonflikte und Synchronisation
• Nutzung von Mehrkernprozessoren, um die Effizienz zu steigern
• Wichtigkeit für Systemleistung und -verfügbarkeit

a) Eine Applikation muss in einer Umgebung ausgeführt werden, in der mehrere Threads parallel arbeiten müssen. Erläutere den Ablauf eines Kontextwechsels, wenn der Scheduler der Applikation von einem Thread auf einen anderen wechselt. Gehe auf die einzelnen Schritte und deren Auswirkungen auf die Systemleistung ein. Nutze dabei Begriffe wie Prozesskontrollblock, Registersicherung und Speicherabbilder. Vergleiche außerdem den Kontextwechsel zwischen Threads und Prozessen.Kontextwechsel bei Threads:

• Speichern des aktuellen Zustands: Der Zustand des aktuellen Threads wird gespeichert, einschließlich der Werte der CPU-Register (Registersicherung), des Program Counters und des Stack Pointers. Dieser Zustand wird im Prozesskontrollblock (PCB) des Threads gespeichert.
• Schedulerauswahl: Der Scheduler wählt den nächsten Thread zur Ausführung aus. Dies erfolgt auf Basis von Prioritäten, Zeitanteilen oder anderen Scheduling-Algorithmen.
• Wiederherstellen des neuen Zustands: Der Zustand des neu gewählten Threads wird aus seinem PCB geladen. Dies umfasst das Laden der gesicherten Registerwerte, des Program Counters und des Stack Pointers.
• Fortsetzung der Ausführung: Die Ausführung des neu gewählten Threads wird an dem Punkt fortgesetzt, an dem er zuvor unterbrochen wurde.

Auswirkungen auf die Systemleistung:

• Der Kontextwechsel zwischen Threads ist relativ teuer, da er Zeit in Anspruch nimmt, um den Zustand des aktuellen Threads zu speichern und den Zustand des neuen Threads wiederherzustellen.
• Häufige Kontextwechsel können die Systemleistung negativ beeinflussen, da weniger Zeit für die tatsächliche Ausführung von Anweisungen bleibt.
• Die Effizienz von Kontextwechseln kann durch Hardwareunterstützung und optimierte Scheduleralgorithmen verbessert werden.

Vergleich zwischen Kontextwechsel bei Threads und Prozessen:

• Ähnlichkeiten:
  • In beiden Fällen müssen der CPU-Zustand gespeichert und wiederhergestellt werden.
  • Beide erfordern einen Scheduler, der den nächsten ausführbaren Thread oder Prozess auswählt.
• Unterschiede:
  • Beim Wechsel zwischen Prozessen muss zusätzlich der gesamte Adressraum gewechselt werden, während bei Threads oft derselbe Adressraum benutzt wird. Dies macht Threads effizienter als Prozesse.
  • Prozesse haben separate Speicherräume und Ressourcen, während Threads den gleichen Speicherraum und Ressourcen innerhalb eines Prozesses teilen.
  • Kontextwechsel bei Prozessen sind in der Regel kostspieliger, da mehr Information gespeichert und wiederhergestellt werden muss (z. B. Speicherabbilder).

b)

b) Betrachte eine Mehrkernprozessor-Architektur. Angenommen, Du hast ein Rechenproblem, das mithilfe von Threads parallelisiert werden soll. Erkläre, wie Du die Threads auf die verschiedenen Kerne verteilen würdest, um die beste Leistung zu erzielen. Welche Mechanismen müssen implementiert werden, um Ressourcenkonflikte und Synchronisationsprobleme zu vermeiden? Diskutiere dabei auch Konzepte wie \textit{Mutexes}, \textit{Semaphore} und \textit{Spinlocks}.

Lösung:

Parallelität und ConcurrencyParallelität bedeutet die gleichzeitige Ausführung mehrerer Aufgaben, während Concurrency die Strukturierung von Aufgaben beschreibt, die scheinbar gleichzeitig ablaufen.Betrachte dabei folgende Aspekte:

• Kontextwechsel (context switch) bei Concurrency
• Thread- und Prozess-Parallelität
• Ressourcenkonflikte und Synchronisation
• Nutzung von Mehrkernprozessoren, um die Effizienz zu steigern
• Wichtigkeit für Systemleistung und -verfügbarkeit

b) Betrachte eine Mehrkernprozessor-Architektur. Angenommen, Du hast ein Rechenproblem, das mithilfe von Threads parallelisiert werden soll. Erkläre, wie Du die Threads auf die verschiedenen Kerne verteilen würdest, um die beste Leistung zu erzielen. Welche Mechanismen müssen implementiert werden, um Ressourcenkonflikte und Synchronisationsprobleme zu vermeiden? Diskutiere dabei auch Konzepte wie Mutexes, Semaphore und Spinlocks.Verteilung der Threads auf die Kerne:

• Load Balancing: Eine effektive Lastverteilung ist entscheidend. Dies kann durch statische Verteilung oder durch dynamisches Load Balancing erfolgen. Bei der statischen Verteilung wird eine bestimmte Anzahl an Threads jedem Kern fest zugewiesen, während beim dynamischen Load Balancing die Threads je nach aktueller Auslastung der Kerne zugewiesen werden.
• Affinity: Thread-Affinität bedeutet, dass Threads bevorzugt auf den gleichen Kernen wieder ausgeführt werden, auf denen sie vorher liefen. Dies kann Cache-Kohärenz erhöhen und den Overhead verringern.
• Parallel Execution: Die Threads sollten so parallel wie möglich ausgeführt werden, um die Vorteile der Mehrkernprozessor-Architektur zu nutzen.

Mechanismen zur Vermeidung von Ressourcenkonflikten und Synchronisationsproblemen:

• Mutexes: Mutexes (Mutual Exclusions) werden verwendet, um den Zugriff zu kritischen Abschnitten zu synchronisieren. Ein Thread muss den Mutex sperren, bevor er einen kritischen Abschnitt betritt, und ihn freigeben, wenn er ihn verlässt. Dies verhindert, dass mehrere Threads gleichzeitig auf dieselbe Ressource zugreifen.

   pthread_mutex_t mutex;pthread_mutex_lock(&mutex);/* kritischer Abschnitt */pthread_mutex_unlock(&mutex);

• Semaphore: Semaphore sind Zähler, die mehrere Threads beschränken können, um gleichzeitig auf eine bestimmte Anzahl von Ressourcen zuzugreifen. Semaphoren können für komplexere Synchronisationsprobleme genutzt werden, bei denen mehr als ein Thread zugelassen werden kann.

   sem_t semaphore;sem_init(&semaphore, 0, 1);sem_wait(&semaphore);/* kritischer Abschnitt */sem_post(&semaphore);

• Spinlocks: Spinlocks sind eine Art von Sperre, bei der ein Thread in einer Schleife (Spin) auf das Freigeben einer Sperre wartet. Sie sind besonders nützlich bei kurzen Sperrzeiten, da sie den Overhead von Kontextwechseln vermeiden.

   spinlock_t lock;spin_lock(&lock);/* kritischer Abschnitt */spin_unlock(&lock);

Diese Synchronisationsmechanismen helfen, Ressourcenkonflikte zu minimieren und sicherzustellen, dass Threads sicher und effizient zusammenarbeiten können.Zusammenfassend:

• Die Verteilung der Threads auf die Kerne sollte effizient und dynamisch erfolgen, um die Rechenleistung der Mehrkernprozessor-Architektur optimal zu nutzen.
• Synchronisationsmechanismen wie Mutexes, Semaphore und Spinlocks sind entscheidend, um Ressourcenkonflikte und Synchronisationsprobleme zu vermeiden.
• Eine gute Balance zwischen Parallelität und Synchronisation steigert die Systemleistung und -verfügbarkeit erheblich.

Aufgabe 3)

Stellen Sie sich vor, Sie arbeiten an einem verteilten System, das sowohl synchrone als auch asynchrone Kommunikationsmechanismen verwenden kann. Sie müssen entscheiden, welcher Kommunikationsmechanismus in verschiedenen Szenarien verwendet werden soll, und Ihre Entscheidungen anhand der Vor- und Nachteile der beiden Kommunikationsformen rechtfertigen.

a)

Erläutern Sie die Vor- und Nachteile der synchronen Kommunikation in verteilten Systemen. Geben Sie ein konkretes Beispiel, bei dem synchrone Kommunikation bevorzugt wird, und erklären Sie, warum dies der Fall ist.

Lösung:

Vor- und Nachteile der synchronen Kommunikation in verteilten Systemen

• Vorteile:
  • Konsistenz: Bei synchroner Kommunikation warten beide Kommunikationsparteien aufeinander, bis die Nachricht gesendet und empfangen wurde. Dies gewährleistet eine hohe Konsistenz der übertragenen Daten.
  • Einfachheit der Implementierung: Da die Kommunikation in einer festgelegten Reihenfolge abläuft, ist die Implementierung oft einfacher und weniger fehleranfällig.
  • Sofortige Rückmeldung: Die Kommunikationspartner erhalten sofort eine Rückmeldung, ob die Nachricht erfolgreich übertragen wurde oder nicht.
• Nachteile:
  • Wartezeiten: Da der Sender auf eine Bestätigung vom Empfänger wartet, kann es zu Verzögerungen und Wartezeiten kommen, besonders wenn das System stark ausgelastet oder der Empfänger langsam ist.
  • Ressourcenbindung: Während der Wartezeit bleiben die Ressourcen des sendenden Systems belegt, was zu Ineffizienzen führen kann.
  • Fehlende Skalierbarkeit: In großen verteilten Systemen kann synchrone Kommunikation zu einem Flaschenhals werden und die Skalierbarkeit einschränken.

Beispiel für synchrone Kommunikation

Ein konkretes Beispiel, bei dem synchrone Kommunikation bevorzugt wird, ist das Online-Banking. Wenn ein Benutzer eine Überweisung tätigt, muss das System sofort verifizieren, ob alle notwendigen Daten korrekt sind und ob das Konto über ausreichend Deckung verfügt.

• Warum synchrone Kommunikation? In diesem Szenario sind sofortige Rückmeldungen und hohe Datenkonsistenz entscheidend:
  • Der Benutzer erwartet eine Bestätigung der erfolgreichen Transaktion in Echtzeit.
  • Es muss sichergestellt werden, dass der Betrag sofort vom Konto des Senders abgezogen wird und beim Empfänger gutgeschrieben wird, um Doppelbuchungen oder Inkonsistenzen zu vermeiden.
  • Jede Verzögerung oder Unsicherheit kann zu Vertrauensverlust der Benutzer führen.
  • Durch die synchrone Kommunikation wird gewährleistet, dass die Transaktion vollständig abgeschlossen ist, bevor der Benutzer fortfahren kann.

b)

Diskutieren Sie die Vor- und Nachteile der asynchronen Kommunikation in verteilten Systemen. Nennen Sie ein konkretes Beispiel, bei dem asynchrone Kommunikation besser geeignet ist, und erklären Sie den Grund.

Lösung:

Vor- und Nachteile der asynchronen Kommunikation in verteilten Systemen

• Vorteile:
  • Höhere Effizienz: Da der Sender nicht auf eine Antwort vom Empfänger warten muss, kann er sofort weiterarbeiten. Dies führt zu einer besseren Ressourcen-Nutzung und erhöhter Effizienz.
  • Bessere Skalierbarkeit: Asynchrone Kommunikation eignet sich besser für große, verteilte Systeme, weil sie unabhängig von den Antwortzeiten des Empfängers funktioniert und daher keine Engpässe durch Wartezeiten entstehen.
  • Entkopplung der Komponenten: Die Kommunikationspartner sind weniger stark miteinander verzahnt, was das System flexibler und robuster gegenüber Ausfällen oder Verzögerungen einzelner Komponenten macht.
• Nachteile:
  • Konsistenzprobleme: Die Datenkonsistenz kann schwieriger zu gewährleisten sein, da keine sofortige Rückmeldung erfolgt, ob die Nachricht erfolgreich empfangen und verarbeitet wurde.
  • Komplexität der Fehlerbehandlung: Da Fehler erst verzögert erkannt werden, ist die Fehlerverfolgung und -korrektur komplexer im Vergleich zu synchroner Kommunikation.
  • Kompensationslogik erforderlich: Es muss zusätzliche Logik zur Kompensation und zum Handling von zwischenzeitlichen Datenänderungen oder Konflikten implementiert werden.

Beispiel für asynchrone Kommunikation

Ein konkretes Beispiel, bei dem asynchrone Kommunikation besser geeignet ist, ist das Bestellen und Verarbeiten von Hintergrund-Jobs in einer Webanwendung.

• Warum asynchrone Kommunikation? In diesem Szenario sind Flexibilität und Effizienz entscheidend:
  • Beim Einreichen eines Hintergrund-Jobs (z.B. das Generieren eines Berichts) muss der Benutzer nicht auf die Fertigstellung warten. Die Aufgabe kann im Hintergrund laufen, während der Benutzer die Anwendung weiterhin verwenden kann.
  • Die Anwendung kann eine einfache Empfangsbestätigung an den Benutzer senden und ihn benachrichtigen, wenn der Job abgeschlossen ist. Die Verarbeitung kann unabhängig vom Frontend erfolgen, was zu einer besseren Benutzererfahrung führt.
  • Die asynchrone Kommunikation entlastet das System und erlaubt es, umfangreiche oder zeitintensive Aufgaben auf mehrere Knoten zu verteilen, ohne die Reaktionszeiten des Frontends zu beeinträchtigen.
  • Skalierbarkeit wird verbessert, da das System mehrere Jobs effizient parallel verarbeiten kann, ohne durch synchrone Wartezeiten gebremst zu werden.

c)

Betrachten Sie ein Szenario, bei dem ein Client eine Anfrage an einen Server sendet und auf eine Antwort wartet. Skizzieren und analysieren Sie die Performance-Unterschiede zwischen der Verwendung einer synchronen und einer asynchronen Kommunikation. Gehen Sie dabei auch auf die möglichen Warte- und Blockierungszeiten ein.

Lösung:

Performance-Unterschiede zwischen synchroner und asynchroner Kommunikation

Betrachten wir ein Szenario, bei dem ein Client eine Anfrage an einen Server sendet und auf eine Antwort wartet. Im Folgenden werden die Performance-Unterschiede zwischen synchroner und asynchroner Kommunikation skizziert und analysiert.

Synchrone Kommunikation

• Ablauf: Der Client sendet eine Anfrage an den Server und wartet, bis der Server die Antwort zurücksendet. Während dieser Wartezeit kann der Client keine anderen Aufgaben ausführen.
• Warte- und Blockierungszeiten: Der Client ist während der gesamten Zeit blockiert, bis eine Antwort vom Server empfangen wird. Dies kann zu folgenden Performance-Einschränkungen führen:
  • Wenn der Server überlastet ist oder zusätzliche Zeit zur Verarbeitung benötigt, wartet der Client entsprechend länger.
  • Ressourcen wie Netzwerkverbindungen und Threads bleiben während der Wartezeit belegt.
• Performance-Analyse: Wegen der Blockierung des Clients und der Ressourcenbindung kann es zu einer ineffizienten Nutzung der Systemressourcen kommen, insbesondere in Szenarien mit hoher Latenzzeit oder langsamen Servern. Die Wartezeiten können die Antwortzeiten des Systems insgesamt erhöhen.

Asynchrone Kommunikation

• Ablauf: Der Client sendet eine Anfrage an den Server und erhält sofort eine Empfangsbestätigung. Der Client kann dann andere Aufgaben ausführen, ohne auf die Antwort des Servers zu warten. Sobald die Antwort verfügbar ist, wird der Client benachrichtigt oder kann die Antwort abrufen.
• Warte- und Blockierungszeiten: Hier sind die Wartezeiten für den Client minimiert, da er nicht blockiert wird. Mögliche Szenarien:
  • Der Client kann während der Verarbeitung der Server-Anfrage andere Operationen ausführen.
  • Nachrichten, die über Queues oder andere Mechanismen empfangen werden, können asynchron verarbeitet werden.
• Performance-Analyse: Die asynchrone Kommunikation führt zu einer effizienteren Nutzung der Systemressourcen, da der Client und Server unabhängig voneinander arbeiten können. Dies kann die Gesamtlatenzzeit reduzieren und die Systemleistung verbessern, insbesondere in verteilten Systemen mit potenziell hohen Netzwerkverzögerungen.

Zusammenfassende Analyse

Die Wahl zwischen synchroner und asynchroner Kommunikation hängt von den spezifischen Anforderungen und Bedingungen des Szenarios ab:

• Synchrone Kommunikation: Geeignet für Szenarien, in denen sofortige Rückmeldungen und hohe Konsistenz erforderlich sind, aber auf Kosten von Warte- und Blockierungszeiten.
• Asynchrone Kommunikation: Besser geeignet für Szenarien, in denen Effizienz und Skalierbarkeit entscheidend sind und der Client andere Aufgaben parallel ausführen kann, ohne auf die Antwort des Servers warten zu müssen.

Insgesamt bietet die asynchrone Kommunikation oft bessere Performance-Vorteile in verteilten Systemen, da sie die Systemressourcen optimal nutzt und die Blockierungszeiten reduziert.

d)

Stellen Sie sich vor, Sie entwerfen ein Messaging-System, das Nachrichten zwischen verschiedenen Komponenten eines verteilten Systems austauschen muss. Beschreiben Sie, wie Sie sowohl synchrone als auch asynchrone Kommunikation in Ihrem Design integrieren würden. Erläutern Sie, welche Kommunikationsform für welche Art von Nachrichten und Operationen geeignet ist.

Lösung:

Design eines Messaging-Systems mit synchroner und asynchroner Kommunikation

Beim Entwerfen eines Messaging-Systems, das Nachrichten zwischen verschiedenen Komponenten eines verteilten Systems austauschen muss, ist es wichtig, beide Kommunikationsmechanismen zu berücksichtigen. Im Folgenden wird beschrieben, wie sowohl synchrone als auch asynchrone Kommunikation integriert werden kann und welche Kommunikationsform für welche Art von Nachrichten und Operationen geeignet ist.

Integration synchroner Kommunikation

• Geeignete Nachrichten und Operationen:
  • Transaktionsbasierte Operationen: Situationen, in denen Konsistenz und sofortige Rückmeldung entscheidend sind, wie z.B. Zahlungstransaktionen oder Datenbankaktualisierungen.
  • Echtzeit-Kommunikation: Anwendungen, die eine sofortige Antwort erfordern, wie z.B. Chat-Anwendungen oder Remote Procedure Calls (RPC).
• Implementierung:
  • Schnittstelle: Verwende eine synchrone Schnittstelle (z.B. HTTP) für Operationen, bei denen der Client auf eine Antwort wartet, bevor er fortfährt.
  • Fehlerbehandlung: Implementiere Mechanismen zur sofortigen Fehlererkennung und -behandlung, damit der Client auf etwaige Probleme zeitnah reagieren kann.
  • Beispiele:
    • Ein Client sendet eine Anfrage an einen Authentifizierungsserver, um Benutzerdaten zu validieren. Der Client wartet auf eine sofortige Antwort, um den Benutzer entweder einzuloggen oder eine Fehlermeldung anzuzeigen.
    • Ein Finanzdienstleister sendet eine Überweisungsanforderung an die Bank-API und wartet auf eine Bestätigung, bevor der Überweisungsvorgang abgeschlossen ist.

Integration asynchroner Kommunikation

• Geeignete Nachrichten und Operationen:
  • Hintergrundverarbeitung: Aufgaben, die im Hintergrund ausgeführt werden können, wie z.B. Datenverarbeitung, Batch-Jobs oder E-Mail-Versand.
  • Entkopplung von Komponenten: Szenarien, in denen die Kommunikationspartner asynchron Nachrichten austauschen, wie z.B. Event-Driven Architecture und Message Queues.
• Implementierung:
  • Schnittstelle: Verwende Messaging-Queues oder Event-Broker (z.B. RabbitMQ, Kafka) für asynchrone Nachrichtenübermittlung.
  • Skalierbarkeit: Implementiere eine skalierbare Infrastruktur, bei der Nachrichten in Warteschlangen zwischengespeichert und von mehreren Konsumenten verarbeitet werden können.
  • Fehlerbehandlung: Implementiere Retry-Mechanismen und Dead-Letter-Queues zur robusten Fehlerbehandlung.
  • Beispiele:
    • Ein Webshop verarbeitet Bestellungen asynchron: Der Client erhält sofort eine Bestellbestätigung, während die eigentliche Auftragsverarbeitung und der Versand im Hintergrund erfolgen.
    • Ein Analysesystem sammelt Log-Daten in Echtzeit und verarbeitet die Daten asynchron, um Berichte und Alarme zu generieren.

Zusammenführung beider Kommunikationsformen

• Hybridansatz: In vielen Systemen kann eine Kombination aus synchroner und asynchroner Kommunikation verwendet werden, um die Vorteile beider Ansätze zu nutzen.
  • Beispiel: Ein Benutzer sendet eine Anfrage, um einen Bericht zu generieren (synchrone Kommunikation für die Bestätigung, dass die Anfrage empfangen wurde) und der Bericht wird später per E-Mail gesendet (asynchrone Verarbeitung des Berichts).
• Entwurfsmuster: Verwende Entwurfsmuster wie Command Query Responsibility Segregation (CQRS) und Event Sourcing, um die Systeme zu entkoppeln und die Kommunikationsformen zu optimieren.

Durch die gezielte Integration sowohl synchroner als auch asynchroner Kommunikation kann das Messaging-System optimal gestaltet werden, um die spezifischen Anforderungen und Anwendungsfälle zu erfüllen.

Aufgabe 4)

Betrachte ein verteiltes System, bestehend aus fünf Prozessen (P1, P2, P3, P4 und P5) und fünf unterschiedlichen Arten von Ressourcen (R1, R2, R3, R4 und R5). Jeder Prozess kann mehrere Ressourcentypen gleichzeitig anfordern und halten. In diesem Kontext sollst Du verschiedene Techniken zur Vermeidung und Auflösung von Deadlocks anwenden und analysieren.

a)

a) Erkläre die vier notwendigen Bedingungen (Klauseln) für das Auftreten eines Deadlocks (Verklemmung). Illustriere jede Bedingung anhand eines Beispiels in Bezug auf das verteilte System mit den Prozessen P1 bis P5 und den Ressourcen R1 bis R5.

Lösung:

Notwendige Bedingungen für das Auftreten eines Deadlocks (Verklemmung)

Ein Deadlock (Verklemmung) entsteht in einem verteilten System, wenn die folgenden vier Bedingungen gleichzeitig erfüllt sind:

• Wechselseitiger Ausschluss (Mutual Exclusion)Diese Bedingung besagt, dass jede Ressource entweder exklusiv von einem Prozess gehalten wird oder, wenn sie von einem anderen Prozess angefordert wird, als nicht verfügbar betrachtet wird.
• Beispiel: In unserem System hält P1 die Ressource R1, und kein anderer Prozess kann R1 verwenden, solange sie von P1 gehalten wird.
• Behalten und Warten (Hold and Wait)Prozesse, die bereits Ressourcen halten, können zusätzliche Ressourcen anfordern und darauf warten, ohne die bereits gehaltenen Ressourcen freizugeben.
• Beispiel: P1 hält R1 und fordert zusätzlich R2 an, die momentan von P2 gehalten wird. Gleichzeitig hält P2 R2 und fordert R3 an.
• Keine Vorenthaltung (No Preemption)Ressourcen können nur freiwillig durch den Prozess, der sie hält, freigegeben werden. Ein anderer Prozess oder das System kann sie nicht einfach wegnehmen.
• Beispiel: P1 hält R1 und kann R1 nicht durch P2 oder ein anderes System selektiv entzogen werden. P1 muss sich entscheiden, R1 freiwillig freizugeben.
• Zirkuläres Warten (Circular Wait)Es gibt eine geschlossene Kette von Prozessen, bei der jeder Prozess in der Kette eine Ressource hält, auf die der nächste Prozess in der Kette wartet.
• Beispiel: P1 hält R1 und fordert R2 an, die von P2 gehalten wird. P2 hält R2 und fordert R3 an, die von P3 gehalten wird. P3 hält R3 und fordert R4 an, die von P4 gehalten wird. P4 hält R4 und fordert R5 an, die von P5 gehalten wird. P5 hält R5 und fordert R1 an, die von P1 gehalten wird. Dies erzeugt eine zirkuläre Wartebedingung.

b)

b) Angenommen, die Prozesse P1 bis P5 beanspruchen Ressourcen gemäß folgender Tabelle:

Prozess	Beanspruchte Ressourcen	Verbleibende Ressourcen
P1	R1, R2	R3
P2	R2	R4
P3	R4	R5
P4	R5	R1
P5	R3	R2

Erstelle einen Ressourcenzugriffsgraphen. Analysiere, ob ein Deadlock in diesem System existiert. Falls ja, identifiziere die betroffenen Prozesse.

Lösung:

Ressourcenzugriffsgraph und Deadlock-Analyse

Ein Ressourcenzugriffsgraph stellt die Beziehungen zwischen Prozessen und Ressourcen in einem verteilten System grafisch dar. Knoten im Graphen repräsentieren entweder Prozesse oder Ressourcen, und gerichtete Kanten zeigen, welche Prozesse welche Ressourcen anfordern oder welche Ressourcen von welchen Prozessen gehalten werden.

Basierend auf der gegebenen Tabelle:

• P1 hält R1, R2 und fordert R3 an
• P2 hält R2 und fordert R4 an
• P3 hält R4 und fordert R5 an
• P4 hält R5 und fordert R1 an
• P5 hält R3 und fordert R2 an

Der Ressourcenzugriffsgraph sieht wie folgt aus:

Ressourcenzugriffsgraph

• P1 -> R3 (P1 fordert R3 an)
• R1 -> P1 (P1 hält R1)
• R2 -> P1 (P1 hält R2)
• P2 -> R4 (P2 fordert R4 an)
• R2 -> P2 (P2 hält R2)
• P3 -> R5 (P3 fordert R5 an)
• R4 -> P3 (P3 hält R4)
• P4 -> R1 (P4 fordert R1 an)
• R5 -> P4 (P4 hält R5)
• P5 -> R2 (P5 fordert R2 an)
• R3 -> P5 (P5 hält R3)

In diesem Graphen können wir den folgenden Zyklus entdecken:

• P1 -> R3 -> P5 -> R2 -> P2 -> R4 -> P3 -> R5 -> P4 -> R1 -> P1

Da ein Zyklus existiert, liegt ein Deadlock vor.

Betroffene Prozesse:

• P1 ist in den Deadlock verwickelt, da es R3 anfordert, das von P5 gehalten wird.
• P2 ist in den Deadlock verwickelt, da es R4 anfordert, das von P3 gehalten wird.
• P3 ist in den Deadlock verwickelt, da es R5 anfordert, das von P4 gehalten wird.
• P4 ist in den Deadlock verwickelt, da es R1 anfordert, das von P1 gehalten wird.
• P5 ist in den Deadlock verwickelt, da es R2 anfordert, das von P2 gehalten wird.

Alle fünf Prozesse (P1, P2, P3, P4 und P5) sind von dem Deadlock betroffen.

c)

c) Beschreibe detailliert den Bankier-Algorithmus zur Vermeidung von Deadlocks. Verwende die obigen Prozesse und Ressourcen, um ein Beispiel zu konstruieren, bei dem dieser Algorithmus einen Deadlock verhindern kann. Zeige die Berechnungen und Entscheidungen Schritt für Schritt.

Lösung:

Der Bankier-Algorithmus zur Vermeidung von Deadlocks

Der Bankier-Algorithmus, entwickelt von Edsger Dijkstra, ist eine Methode zur Vermeidung von Deadlocks in Systemen, die mehrere Prozesse und Ressourcen verwalten. Der Algorithmus bestimmt anhand von Sicherheitsprüfungen, ob eine bestimmte Ressourcenanforderung erfüllt werden kann, ohne dass das System in einen unsicheren Zustand gerät.

Schlüsselkonzepte des Bankier-Algorithmus:

• Maximalanspruch (Maximum Claim): Die maximale Anzahl von Ressourcen, die ein Prozess in seinem Laufzeitzyklus anfordern kann.
• Allokation (Allocation): Die Anzahl von Ressourcen, die einem Prozess derzeit zugeteilt sind.
• Anforderung (Request): Die Anzahl von Ressourcen, die ein Prozess aktuell anfordert.
• Verfügbarkeit (Available): Die Anzahl von verfügbaren Ressourcen, die dem System nicht zugeteilt sind.

Der Bankier-Algorithmus verwendet diese Informationen, um zu entscheiden, ob eine Ressourcenzuteilung sicher ist:

• Füge die aktuelle Anforderung zu den Ressourcen hinzu, die der Prozess bereits besitzt.
• Denk dir die Ressourcenzahl, die dem Prozess noch fehlen, um seinen Maximalanspruch zu erfüllen.
• Berechne, ob die verbleibenden verfügbaren Ressourcen alle Maximalansprüche der verbleibenden Prozesse decken können.

Schritt-für-Schritt Beispiel mit P1 bis P5 und R1 bis R5

Nehmen wir die von den Prozessen gewünschte Ressourcenverteilung aus der Tabelle an:

Prozess	Maximalanspruch (Maximum)	Allokation	Anforderung (Request)
P1	R1, R2, R3	R1, R2	R3
P2	R2, R4	R2	R4
P3	R4, R5	R4	R5
P4	R1, R5	R5	R1
P5	R2, R3	R3	R2

Zunächst berechnen wir die verfügbaren Ressourcen. Wenn in diesem Beispiel alle fünf Ressourcenarten jeweils 1-mal vorhanden sind, haben wir:

• Available = Total - Allocation = (1, 1, 1, 1, 1) - (R1, R2, R2, R3, R4, R5) = (0, -1, -1, -1, -1)

Angenommen, die Anfrage von P1 für R3 kommt:

• 1. Prüfen, ob Request (R3) ≦ Available (Hier könnte R3 = 0 sein)
• Es sollte umgesetzt werden.

Berechnen und aktualisieren von Verfügbarkeit und Allokation:

• Request update:
• Available = (1, 1, 1, 1, 1) - (0, 0, 1, 0, 0) => 0
• Safe-State-Prüfung:
• Max - Allocation
• Es wäre sicher, wenn verfügbar ist. (Nicht ausfallend)

Durch die überwachte Bewilligung verhindert der Bankier-Algorithmus Deadlock der Prozesse. Bei Veränderung von Ressourcenanforderung und Allokation können weitere Prozesse sicher behandelt werden.

d)

d) Diskutiere zwei Methoden zur Auflösung eines Deadlocks: den Prozessabbruch und den Ressourcenentzug. Welche Vor- und Nachteile haben diese Methoden? Vorschlage, welche der beiden Methoden in dem gegebenen verteilten System am effektivsten wäre und begründe Deine Antwort.

Lösung:

Methoden zur Auflösung eines Deadlocks

Um Deadlocks zu lösen, können zwei Hauptmethoden verwendet werden: der Prozessabbruch und der Ressourcenentzug. Beide Methoden haben ihre eigenen Vor- und Nachteile.

1. Prozessabbruch

Beim Prozessabbruch wird mindestens ein Prozess, der in den Deadlock verwickelt ist, beendet. Es gibt zwei Varianten:

• Abbruch aller betroffenen Prozesse: Alle Prozesse, die an dem Deadlock beteiligt sind, werden abgebrochen. Dies garantiert die Auflösung des Deadlocks, setzt jedoch alle betroffenen Prozesse zurück, was zu großem Ressourcenausfall führt.
• Selektiver Abbruch: Nur ein oder mehrere Prozesse, die als weniger wichtig oder weniger kritisch angesehen werden, werden abgebrochen. Dies minimiert den Ressourcenausfall, erfordert jedoch eine sorgfältige Auswahl der abzubrechenden Prozesse.

Vorteile:

• Einfache Umsetzung.
• Schnelle Deadlock-Auflösung.

Nachteile:

• Verlust von Fortschritt und Daten, wenn Prozesse beendet werden.
• Kann Ressourcenverschwendung verursachen, wenn alle betroffenen Prozesse abgebrochen werden.

2. Ressourcenentzug

Beim Ressourcenentzug werden Ressourcen, die von Prozessen im Deadlock gehalten werden, zwangsweise entzogen und anderen Prozessen zugewiesen. Dies kann auf zwei Arten erfolgen:

• Selektiver Ressourcenentzug: Ressourcen werden gezielt von weniger kritischen Prozessen entzogen und an Prozesse im Deadlock verteilt.
• Roll-Back und Neuvergabe: Prozesse werden in einen früheren sicheren Zustand zurückversetzt, und die Ressourcen werden neu verteilt, um eine Deadlock-freie Konfiguration zu erreichen.

Vorteile:

• Beibehaltung des Prozessfortschritts, indem Ressourcen dynamisch umgeschichtet werden.
• Vermeidung von vollständigem Prozessabbruch.

Nachteile:

• Komplexere Implementation.
• Kann zu inkonsistenten Zuständen führen, wenn nicht sorgfältig durchgeführt.

Empfehlung für das verteilte System

In dem gegebenen verteilten System mit fünf Prozessen und fünf Ressourcentypen wäre der Ressourcenentzug vermutlich die effektivere Methode zur Deadlock-Auflösung. Dies liegt an folgenden Gründen:

• Vermeidung des kompletten Abbruchs kritischer Prozesse: Da alle Prozesse (P1 bis P5) an unterschiedlichen Ressourcen arbeiten, könnte der Abbruch eines wichtigen Prozesses zu erheblichen Verzögerungen und Datenverlust führen.
• Effiziente Ressourcennutzung: Durch dynamisches Umschichten der Ressourcen kann das System seine Leistungsfähigkeit beibehalten und Deadlocks auf intelligente Weise vermeiden.
• Sicherung von Prozesszuständen: Durch Roll-Back und Neuvergabe können Prozesse in sichere Zustände zurückversetzt werden, wodurch der Systemfortschritt aufrechterhalten wird.

Zwar ist die Implementierung von Ressourcenentzug komplexer, jedoch überwiegen die Vorteile in einem komplexen, verteilten System, wie es hier der Fall ist.