Kommunikation und Parallele Prozesse - Exam

Aufgabe 1)

Parallelität bedeutet die gleichzeitige Ausführung mehrerer Berechnungen, um die Effizienz zu steigern. Durch die Erhöhung der Rechenleistung und die Reduzierung der Ausführungszeit können komplexe Aufgaben schneller gelöst werden. Dies wird oft durch Multithreading und Mehrprozessorsysteme erreicht. Dabei sind jedoch Synchronisationsmechanismen notwendig, um Race Conditions zu vermeiden. Wichtige Modelle in der Parallelverarbeitung sind PRAM und CSP (Communicating Sequential Processes). Ebenso wichtig ist die Kommunikation zwischen parallelen Prozessen durch Nachrichtenpassing und gemeinsame Speicher.

a)

Aufgabe 1: Angenommen, Du hast ein Mehrprozessorsystem mit vier Kernen und eine Aufgabe, die mittels Multithreading parallelisiert werden soll. Die Aufgabe besteht darin, eine Liste von 10.000 numerischen Werten zu summieren. Beschreibe detailliert, wie Du diese Aufgabe parallelisieren würdest und welche Synchronisationsmechanismen Du verwenden würdest, um Race Conditions zu vermeiden.

Lösung:

Lösung der Aufgabe 1:

Um eine Liste von 10.000 numerischen Werten auf einem Mehrprozessorsystem mit vier Kernen zu summieren, und dabei Multithreading zu verwenden, gehe ich wie folgt vor:

• Schritt 1: Aufteilung der Liste Teile die Liste in vier gleichgroße Abschnitte auf, sodass jeder Kern einen Abschnitt der Liste verarbeitet. Da die Liste 10.000 Elemente enthält, würde jeder Abschnitt 2.500 Werte umfassen.
• Schritt 2: Erstellen der Threads Erstelle vier Threads, wobei jeder Thread für die Summierung eines Abschnitts der Liste verantwortlich ist. Jeder Thread berechnet die Teilsumme seines Abschnitts und speichert das Ergebnis in einer gemeinsamen Datenstruktur, z.B. einem Array oder einer Liste, in der jede Position die Teilsumme eines Threads enthält.
• Schritt 3: Synchronisation der Threads Damit keine Race Conditions auftreten, sind Synchronisationsmechanisamen nötig. Die einfachste Möglichkeit ist die Nutzung von mutexes (wechselseitiger Ausschluss - Mutual Exclusion). Jeder Thread erhält beim Zugriff auf die gemeinsame Datenstruktur einen Lock, um sicherzustellen, dass kein anderer Thread währenddessen auf dieselbe Struktur zugreift.
• Schritt 4: Verarbeiten der Teilsummen Nachdem alle Threads ihre Arbeit beendet haben, summiere die Teilsummen aus der gemeinsamen Datenstruktur zu einer Gesamtsumme. Diese Verarbeitung erfolgt thread-unabhängig und erfordert keine weiteren Synchronisationsmechanismen.
• Schritt 5: Implementierung in Code Hier ist ein Beispiel in Python:

import threading  from functools import reduce   # Beispiel Datensatz  data = list(range(10, 10010))   # Anzahl der Kerne  num_cores = 4  segment_length = len(data) // num_cores   # Ergebnisliste für Teilsummen  partial_sums = [0] * num_cores   # Synchronisationsmechanismus  lock = threading.Lock()   def sum_segment(start, end, index):  global partial_sums  segment_sum = sum(data[start:end])  with lock:  partial_sums[index] = segment_sum   threads = []  for i in range(num_cores):  start = i * segment_length  end = (i + 1) * segment_length  t = threading.Thread(target=sum_segment, args=(start, end, i))  threads.append(t)  t.start()   for t in threads:  t.join()   total_sum = reduce(lambda x, y: x + y, partial_sums)  print(total_sum) 

• Erläuterung:
  • Der Datensatz wird in Segmente aufgeteilt, die von den verschiedenen Threads parallel verarbeitet werden.
  • Jeder Thread berechnet die Teilsumme seines Segments und speichert diese in der gemeinsamen Struktur partial_sums ab.
  • Die Verwendung von with lock beim Zugriff auf partial_sums gewährleistet die Synchronisation, sodass keine Race Conditions auftreten.
  • Am Ende werden die Teilsummen zusammengeführt, um die endgültige Summe zu berechnen, die dann ausgegeben wird.

b)

Aufgabe 2: CSP (Communicating Sequential Processes) ist ein Modell zur Beschreibung der Interaktionen zwischen parallelen Prozessen. Schreibe ein kurzes Programm (in einer Sprache Deiner Wahl), das zwei parallele Prozesse implementiert, die mittels Nachrichtenpassing kommunizieren. Der erste Prozess soll eine Nachricht an den zweiten Prozess senden, und der zweite Prozess soll die Nachricht empfangen und auf der Konsole ausgeben. Erkläre, welche Rolle Synchronisationsmechanismen in Deinem Programm spielen und wie sie implementiert sind.

Lösung:

Lösung der Aufgabe 2:

Das Modell CSP (Communicating Sequential Processes) nutzt Nachrichtenpassing zur Kommunikation zwischen parallelen Prozessen. Hier werde ich ein kurzes Programm in Python vorstellen, das zwei parallele Prozesse implementiert, die mittels Nachrichtenpassing kommunizieren.

Wir nutzen hierzu das multiprocessing-Modul von Python.

• Programmcode:

import multiprocessing   def sender(pipe):  '''Sender process sends a message'''  pipe.send('Hallo, dies ist eine Nachricht vom Sender-Prozess!')  pipe.close()   def receiver(pipe):  '''Receiver process receives a message'''  message = pipe.recv()  print('Empfangen Nachricht: ', message)  pipe.close()   if __name__ == '__main__':  # Erstellen eines unidirektionalen Pipes  sender_pipe, receiver_pipe = multiprocessing.Pipe()   # Erstellen und Starten der Prozesse  sender_process = multiprocessing.Process(target=sender, args=(sender_pipe,))  receiver_process = multiprocessing.Process(target=receiver, args=(receiver_pipe,))   sender_process.start()  receiver_process.start()   # Warten auf die Fertigstellung der Prozesse  sender_process.join()  receiver_process.join() 

• Erklärung:
  • Das Programm erstellt eine unidirektionale Pipe, die als Kommunikationskanal zwischen den Prozessen dient. Die Pipe hat zwei Enden, eines für den Sender und eines für den Empfänger.
  • Die Funktion sender() sendet eine Nachricht via pipe.send() durch die Pipe.
  • Die Funktion receiver() empfängt die Nachricht mittels pipe.recv() und gibt sie auf der Konsole aus.
  • Die beiden Prozesse sender_process und receiver_process werden erstellt und gestartet. Die Methode join() stellt sicher, dass das Hauptprogramm wartet, bis beide Prozesse beendet sind.

• Synchronisationsmechanismen:
  • Die Synchronisation zwischen den Prozessen wird durch das Nachrichtenpassing sichergestellt. Der Sender-Prozess sendet die Nachricht und wartet, bis der Empfänger-Prozess sie erhält. Dies vermeidet Race Conditions, da die Pipe sicherstellt, dass der Nachrichtenfluss in der vorgegebenen Reihenfolge erfolgt.
  • Mit der Methode join() stellt das Hauptprogramm sicher, dass beide Prozesse (Sender und Empfänger) ihre Arbeit vollständig abgeschlossen haben, bevor das Hauptprogramm selbst endet. Dies ermöglicht eine Synchronisation der Prozessenden.

Aufgabe 2)

Konzepte der Nebenläufigkeit und Synchronisation Du arbeitest in einem Softwareentwicklungsteam an einer multithreaded Anwendung und hast die Aufgabe, verschiedene Aspekte der Nebenläufigkeit und Synchronisation zu analysieren. Dabei spielen die Begriffe Race Conditions, Deadlocks, Semaphore und Monitore eine wichtige Rolle. Eine der zentralen Methoden, die in deinem Team verwendet werden, ist der Einsatz von Semaphoren zur Lösung von Race Conditions. Außerdem musst du Deadlocks vermeiden und hast beschlossen, Petersons Algorithmus zu untersuchen, um diese Problematik anzugehen. Basiert auf diesem Kontext, beantworte bitte die folgenden Fragen:

a)

Erkläre in Deinen eigenen Worten, was unter Race Conditions verstanden wird und wie Semaphoren verwendet werden können, um dieses Problem zu lösen. Veranschauliche deine Antwort mit einem kurzen Beispielcode in

Java

Lösung:

• Race Conditions:

Eine Race Condition tritt auf, wenn zwei oder mehr Threads gleichzeitig auf gemeinsame Ressourcen zugreifen und versuchen, diese zu ändern. Dies kann dazu führen, dass der endgültige Zustand der Ressource von der Reihenfolge der Zugriffe abhängt und somit unvorhersehbare oder inkorrekte Ergebnisse entstehen. Ein typisches Beispiel eines solchen Problems ist ein gemeinsames Zähler-Objekt, auf das mehrere Threads zugreifen und es inkrementieren.

• Verwendung von Semaphoren zur Lösung von Race Conditions:

Um Race Conditions zu verhindern, kann man Semaphoren verwenden. Eine Semaphore ist ein Synchronisationsmechanismus, der den Zugriff auf gemeinsame Ressourcen kontrolliert. Sie stellt sicher, dass immer nur eine bestimmte Anzahl von Threads gleichzeitig auf eine kritische Sektion zugreifen kann. In unserem Fall helfen uns binäre Semaphoren (auch Mutexe genannt) dabei, dass immer nur ein Thread in einem bestimmten Code-Bereich aktiv ist, wodurch wir die Race Condition vermeiden können.

• Beispielcode in Java:

 import java.util.concurrent.Semaphore;  public class RaceConditionExample {      private static int counter = 0;      private static final Semaphore semaphore = new Semaphore(1);      public static void main(String[] args) {          Thread t1 = new Thread(new IncrementTask());          Thread t2 = new Thread(new IncrementTask());          t1.start();          t2.start();      }      private static class IncrementTask implements Runnable {          public void run() {              try {                  semaphore.acquire();                  for (int i = 0; i < 1000; i++) {                      counter++;                  }              } catch (InterruptedException e) {                  e.printStackTrace();              } finally {                  semaphore.release();              }          }      }  }  

In diesem Beispiel verwenden wir eine binäre Semaphore, um den Zugriff auf die gemeinsame Ressource counter zu synchronisieren. Jeder Thread muss die Semaphore erwerben (erlaubt nur einem Thread den Zugriff gleichzeitig), bevor er den Zähler inkrementiert, und danach die Semaphore freigeben, wodurch Race Conditions vermieden werden.

b)

Ein Deadlock tritt auf, wenn sich zwei oder mehr Prozesse dauerhaft gegenseitig blockieren. Beschreibe ein Szenario, in dem ein Deadlock auftreten kann, und erläutere zumindest zwei Strategien zur Deadlock-Vermeidung oder -Erkennung. Du kannst mathematische Modelle nutzen, um die Erklärungen zu untermauern.

Lösung:

• Deadlock-Szenario:

Ein Deadlock tritt auf, wenn zwei oder mehr Prozesse jeweils auf eine Ressource warten, die von einem anderen Prozess gehalten wird, wodurch ein Zyklus der Abhängigkeiten entsteht. Ein klassisches Beispiel ist das Dining Philosophers Problem. Stell Dir vor, fünf Philosophen sitzen am Tisch, jeder Philosoph hat einen Teller Spaghetti vor sich und benötigt zwei Gabeln zum Essen. Es gibt jedoch nur fünf Gabeln, die zwischen den Philosophen liegen. Ein Deadlock kann auftreten, wenn jeder Philosoph eine Gabel aufnimmt und auf die zweite Gabel wartet, die von einem Nachbarn gehalten wird. Hier ist die Situation visualisiert:

• Philosoph 1 hält Gabel A und wartet auf Gabel B.
• Philosoph 2 hält Gabel B und wartet auf Gabel C.
• Philosoph 3 hält Gabel C und wartet auf Gabel D.
• Philosoph 4 hält Gabel D und wartet auf Gabel E.
• Philosoph 5 hält Gabel E und wartet auf Gabel A.

Da jeder auf eine Gabel wartet, die von einem anderen gehalten wird, kann keiner essen, und es entsteht ein Deadlock.

• Strategien zur Deadlock-Vermeidung oder -Erkennung:

1. Ressourcenzuweisungsgraf:

Ein Ressourcenzuweisungsgraf (Resource Allocation Graph) ist ein direkter Graph, der die Beziehung zwischen Prozessen und Ressourcen darstellt. Wenn ein Zyklus im Graphen existiert, ist ein Deadlock möglich. Durch das Überprüfen auf Zyklen kann ein Deadlock erkannt werden. Mathematisch lässt sich der direkte grafische Zyklus wie folgt darstellen:

 G = (P, R, E)  wobei:  P = {P1, P2, ..., Pn} die Menge von Prozessen ist,  R = {R1, R2, ..., Rm} die Menge von Ressourcen ist,  E eine Menge von Kanten ist, die Beziehungen zwischen Prozessen und Ressourcen zeigen. 

Repräsentiert ein Zyklus einen Deadlock im Graphen, müssen Maßnahmen ergriffen werden, um den Zyklus zu durchbrechen, z.B. durch Abbrechen oder Neuzuweisen von Ressourcen.

2. Bankiers-Algorithmus:

Der Bankiers-Algorithmus (Banker's Algorithm) ist ein Deadlock-Vermeidungsalgorithmus, der verwendet wird, um sicherzustellen, dass das System immer in einem sicheren Zustand bleibt. Mathematisch wird das Konzept des sicheren Zustands wie folgt dargestellt:

 Let:  Max(i) = maximale Anzahl von Ressourcen, die Prozess Pi benötigen kann,  Allocation(i) = Anzahl der Ressourcen, die Prozess Pi aktuell zugewiesen sind,  Need(i) = Max(i) - Allocation(i),  Available = Gesamtzahl der verfügbaren Ressourcen im System.  Dann: Der Zustand ist sicher, wenn es eine Sequenz {P1, P2, ..., Pn} der Prozesse gibt, so dass jeder Prozess Pi die benötigten Ressourcen erhält, falls sie angefordert werden. 

Der Bankiers-Algorithmus prüft jedes Mal, wenn eine Ressource angefordert wird, ob das Gewähren der Anforderung das System in einen unsicheren Zustand versetzen würde. Wenn ja, wird die Anforderung abgelehnt.

Durch die Implementierung solcher Techniken können Deadlocks effizient vermieden oder frühzeitig erkannt werden, um größere Probleme zu verhindern.

c)

Untersuche Petersons Algorithmus und erkläre, wie dieser genutzt werden kann, um eine wechselseitige Ausschließung zwischen zwei Prozessen zu garantieren. Die Erklärung sollte sowohl eine textuelle Beschreibung als auch die mathematische Darstellung der Schritte enthalten.

Lösung:

• Petersons Algorithmus:

Petersons Algorithmus ist ein einfacher und bekannter Algorithmus zur wechselseitigen Ausschließung (Mutual Exclusion) zwischen zwei Prozessen. Er löst das Problem der Race Conditions, indem er sicherstellt, dass immer nur ein Prozess gleichzeitig auf eine kritische Sektion zugreifen kann. Der Algorithmus setzt auf zwei Kontrollvariablen:

• flag: Diese Variable gibt an, ob ein Prozess bereit ist, in die kritische Sektion einzutreten. flag[0] gehört zu Prozess 0, flag[1] zu Prozess 1.
• turn: Diese Variable gibt an, welcher Prozess Vorrang hat, falls beide Prozesse gleichzeitig eintreten wollen.
• Mathematische Darstellung von Petersons Algorithmus:

 // Initialisierung  boolean[] flag = new boolean[2];  int turn;   // Prozess 0  flag[0] = true;  turn = 1;  while (flag[1] && turn == 1) {  // warten  }  // kritische Sektion  ...  flag[0] = false;   // Prozess 1  flag[1] = true;  turn = 0;  while (flag[0] && turn == 0) {  // warten  }  // kritische Sektion  ...  flag[1] = false;  

Angenommen, die Prozesse 0 und 1 verwenden Petersons Algorithmus, um wechselseitige Ausschließung für ihre kritischen Sektionen zu gewährleisten:

• Prozess 0: Setzt flag[0] auf true und wechselt die turn-Variable auf 1 (gibt Prozess 1 Vorrang). Prozess 0 tritt nur in die kritische Sektion ein, wenn entweder flag[1] auf false ist (Prozess 1 ist nicht bereit) oder turn nicht 1 ist (Prozess 0 hat Vorrang).
• Prozess 1: Setzt flag[1] auf true und wechselt die turn-Variable auf 0 (gibt Prozess 0 Vorrang). Prozess 1 tritt nur in die kritische Sektion ein, wenn entweder flag[0] auf false ist (Prozess 0 ist nicht bereit) oder turn nicht 0 ist (Prozess 1 hat Vorrang).

Dieser Mechanismus stellt sicher, dass immer nur ein Prozess in die kritische Sektion eintreten kann, selbst wenn beide Prozesse dies gleichzeitig versuchen. Petersons Algorithmus garantiert drei Eigenschaften:

• Wechselseitige Ausschließung (Mutual Exclusion): Immer nur ein Prozess darf sich in der kritischen Sektion befinden.
• Freundlichkeit (Progress): Wenn kein Prozess in der kritischen Sektion ist, darf jeder Prozess, der die kritische Sektion betreten möchte, dies tun.
• Begrenztes Warten (Bounded Waiting): Jeder Prozess darf die kritische Sektion in einer endlichen Anzahl von Schritten betreten, nachdem er dies gewünscht hat.

d)

Angenommen, Du hast eine Implementierung, die sowohl Monitore als auch Ereignisvariablen verwendet, um die Synchronisation zwischen Threads zu gewährleisten. Erkläre, wie Monitore und Ereignisvariablen zur Lösung von Synchronisationsproblemen eingesetzt werden und vergleiche sie mit Semaphoren hinsichtlich Effizienz und Anwendung. Verwende pseudocode zur Veranschaulichung.

Lösung:

• Monitore und Ereignisvariablen:

Monitore sind Abstraktionen, die als synchrone Zugriffsmechanismen für den Zugriff auf gemeinsam genutzte Ressourcen dienen. Sie stellen sicher, dass nur ein Thread gleichzeitig in den Monitor eintreten kann, wodurch die kritischen Abschnitte geschützt werden.

Ereignisvariablen (oder Bedingungsvariablen) unterstützen die Synchronisation, indem sie es Threads ermöglichen, auf bestimmte Bedingungen zu warten oder andere Threads zu benachrichtigen, wenn Bedingungen erfüllt sind.

• Nutzung von Monitoren und Ereignisvariablen zur Synchronisation:

Hier ist ein Beispiel für einen Monitor mit Ereignisvariablen in Pseudocode:

 monitor BeispielMonitor {    boolean Bedingung = false;    condition Bedingungserfüllt;        public void warteAufBedingung() {        while (!Bedingung) {            Bedingungserfüllt.wait();        }    }        public void bedingungErfüllen() {        Bedingung = true;        Bedingungserfüllt.notifyAll();        }  }  

• Effizienz:

Monitore sind im Allgemeinen in höhere Strukturen der Programmiersprache eingebettet und abstrahieren die Komplexität der Synchronisation, was die Programmierung vereinfacht und weniger fehleranfällig macht. Semaphoren erfordern mehr handwerkliche Steuerung durch den Programmierer, sind aber flexibler und können für eine breite Palette von Synchronisationsproblemen verwendet werden.

• Anwendung:
• Monitore bieten einen strukturierten Ansatz für die Synchronisation, der gut in Programmiersprachen wie Java integriert ist. Sie sind besonders nützlich, wenn eine klare und einfache Struktur benötigt wird, um den Zugriff auf Ressourcen zu sanieren.
• Semaphoren eignen sich besser für niedrig-levelige Synchronisation und können sowohl für binäre (Mutexe) als auch zählende Synchronisationen verwendet werden. Sie sind vielseitiger, aber auch anfälliger für Fehler wie Deadlocks, wenn nicht korrekt eingesetzt.

 // Beispiel-Pseudocode mit Semaphoren  Semaphore semaphore = new Semaphore(1);   void zugreifen() {    semaphore.acquire();    // kritische Sektion    semaphore.release();  }  

In diesem Beispiel erzeugen wir eine Semaphore mit einem einzigen verfügbaren Permissium. Bei jedem Aufruf von zugreifen() muss ein Thread die Semaphore erwerben (und wartet, falls sie nicht verfügbar ist), bevor er in die kritische Sektion eintritt. Nach dem Beenden der kritischen Sektion gibt der Thread die Semaphore wieder frei.

Monitore und Ereignisvariablen bieten eine strukturierte und integrierte Methode für die Synchronisation, die die Programmierung sicherer macht. Semaphoren hingegen bieten mehr Flexibilität und Vielseitigkeit, können aber komplexer und fehleranfälliger in der Anwendung sein. Die Wahl zwischen beiden hängt von den speziellen Anforderungen und der Komplexität der Anwendung ab.

Aufgabe 3)

Nachrichtenübermittlung vs. Shared MemoryNachrichtenübermittlung und Shared Memory sind Methoden zur Kommunikation und Synchronisation in parallelen Prozessen.

• Nachrichtenübermittlung: Daten werden explizit zwischen Prozessen gesendet und empfangen.
• Shared Memory: Prozesse greifen auf gemeinsame Speicherbereiche zu.
• Nachrichtenübermittlung: Gut für verteilte Systeme.
• Shared Memory: Effizient für eng gekoppeltes Multiprocessing.
• Nachrichtenübermittlung:

  send(), recv()

• Shared Memory:

  shmget(), shmat(), shmdt()

• Nachrichtenübermittlung: Synchronisation durch Kanal-/Queue-Operationen.
• Shared Memory: Synchronisation durch Sperren (Locks).

a)

Beschreibe den Hauptunterschied zwischen Nachrichtenübermittlung und Shared Memory. Welche Methode würdest Du bevorzugen, um parallele Prozesse auf einem verteilten System zu synchronisieren? Begründe Deine Antwort.

Lösung:

Hauptunterschied zwischen Nachrichtenübermittlung und Shared Memory:

Der Hauptunterschied zwischen Nachrichtenübermittlung und Shared Memory liegt in der Art und Weise, wie Daten zwischen parallelen Prozessen ausgetauscht und synchronisiert werden:

• Nachrichtenübermittlung: Bei der Nachrichtenübermittlung werden Daten explizit zwischen Prozessen gesendet und empfangen. Dies bedeutet, dass ein Prozess eine Nachricht sendet, die ein bestimmter anderer Prozess empfangen kann. Dieser Ansatz eignet sich besonders gut für verteilte Systeme, bei denen die Prozesse auf verschiedenen physikalischen Rechnern ausgeführt werden.
• Shared Memory: Beim Shared Memory greifen mehrere Prozesse auf denselben Speicherbereich zu, um Daten auszutauschen. Prozesse können direkt auf diese gemeinsam genutzten Speicherbereiche lesen und schreiben, was bei eng gekoppelten Multiprocessing-Systemen sehr effizient ist. Hier ist eine sorgfältige Synchronisation durch Sperren (Locks) notwendig, um Inkonsistenzen zu vermeiden.

Bevorzugte Methode für parallele Prozesse auf einem verteilten System:

Für die Synchronisation paralleler Prozesse auf einem verteilten System würde ich die Nachrichtenübermittlung bevorzugen. Die Gründe dafür sind:

• Isolation der Prozesse: Durch Nachrichtenübermittlung bleibt die Ausführung der Prozesse voneinander isoliert, was die Sicherheit und Fehlertoleranz erhöht.
• Netzwerkfreundlichkeit: Nachrichtenübermittlung ist für verteilte Systeme, die über ein Netzwerk kommunizieren, konzipiert. Sie bietet robuste Mechanismen zur Datenübertragung zwischen weit entfernten Knoten.
• Einfache Synchronisation: Die Nutzung von Kanälen oder Queues zur Nachrichtenübermittlung kann die Komplexität der Synchronisation reduzieren, da implizit eine Reihenfolge und Struktur durch das Nachrichtensystem vorgegeben wird.
• Skalierbarkeit: Nachrichtenübermittlung ermöglicht eine bessere Skalierbarkeit in verteilten Systemen, da Prozesse unabhängig voneinander laufen und nur über Nachrichten miteinander interagieren.

b)

Betrachte ein Szenario, bei dem fünf parallele Prozesse gleichzeitig auf einen geteilten Speicherbereich zugreifen müssen. Implementiere eine Synchronisationsmechanismus mit Sperren (Locks) in Python, um einen konkurrierenden Zugriff auf den Shared Memory zu verhindern. Nutze dafür die threading Bibliothek.

Lösung:

Implementierung eines Synchronisationsmechanismus mit Sperren (Locks) in Python:

In diesem Szenario müssen fünf parallele Prozesse synchronisiert werden, um auf denselben geteilten Speicherbereich zuzugreifen. Wir werden die threading Bibliothek verwenden und einen Lock verwenden, um den Zugriff zu kontrollieren.

Hier ist der Python-Code, der dies implementiert:

import threadingimport timeimport randomshared_memory = 0lock = threading.Lock()def process(id):    global shared_memory    for _ in range(5):        lock.acquire()        print(f'Process {id} is accessing the shared memory.')        temp = shared_memory        temp += 1        time.sleep(random.uniform(0.1, 0.5))        shared_memory = temp        print(f'Process {id} has updated the shared memory to {shared_memory}.')        lock.release()        time.sleep(random.uniform(0.1, 0.5))threads = []for i in range(5):    thread = threading.Thread(target=process, args=(i,))    threads.append(thread)    thread.start()for t in threads:    t.join()print(f'Final value of shared memory: {shared_memory}')

Erklärung des Codes:

• Wir importieren die threading Bibliothek und die time und random Module, um Verzögerungen zu simulieren.
• Wir initialisieren die Variable shared_memory und den lock, um die kritischen Abschnitte zu schützen.
• Die Funktion process simuliert einen Prozess, der fünfmal auf den geteilten Speicherbereich zugreift und ihn aktualisiert.
• Wir erstellen fünf Threads, die jeweils die process Funktion ausführen, und starten sie.
• Wir stellen sicher, dass alle Threads abgeschlossen sind, indem wir join auf den Threads aufrufen.
• Am Ende geben wir den finalen Wert des geteilten Speichers aus.

Aufgabe 4)

Der MPI (Message Passing Interface) Standard ermöglicht die parallele Programmierung verteilter Systeme durch Nachrichtenübermittlung. MPI unterstützt sowohl Punkt-zu-Punkt- als auch kollektive Kommunikation. Wichtige Implementierungen beinhalten MPICH und OpenMPI. Grundlegende Funktionen umfassen MPI_Send und MPI_Recv, deren Performance stark von der Nachrichtengröße und der Netzwerkarchitektur abhängt.

a)

Erstelle ein einfaches MPI-Programm, das zwei Prozesse verwendet. Der erste Prozess sendet eine Nachricht an den zweiten Prozess, der die Nachricht empfängt und ausgibt. Das Programm sollte die Funktionen MPI_Send und MPI_Recv korrekt verwenden.

Lösung:

• Erstelle ein einfaches MPI-Programm:
• Du wirst ein einfaches C-Programm erstellen, welches das MPI-Framework nutzt, um eine Nachricht von einem Prozess zu einem anderen zu senden.
• Das Programm sollte MPI_Send und MPI_Recv korrekt verwenden.
• Hier ist der vollständige Code:

  #include <mpi.h>  #include <stdio.h>   int main(int argc, char** argv) {      MPI_Init(&argc, &argv);       int world_rank;      MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);       int world_size;      MPI_Comm_size(MPI_COMM_WORLD, &world_size);       if (world_size < 2) {          fprintf(stderr, "Benötigt mindestens zwei Prozesse");          MPI_Abort(MPI_COMM_WORLD, 1);      }       if (world_rank == 0) {          const char* message = "Hallo von Prozess 0";          MPI_Send(message, strlen(message) + 1, MPI_CHAR, 1, 0, MPI_COMM_WORLD);      } else if (world_rank == 1) {          char message[100];          MPI_Recv(message, 100, MPI_CHAR, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);          printf("Empfangene Nachricht vom Prozess 0: %s", message);      }       MPI_Finalize();      return 0;  }   

• Erläuterungen zum Code:
• Das Programm initialisiert MPI mit MPI_Init.
• Es erhält die aktuelle Prozessnummer mit MPI_Comm_rank und die Gesamtanzahl der Prozesse mit MPI_Comm_size.
• Der Prozess mit Rang 0 sendet eine Nachricht mit MPI_Send an den Prozess mit Rang 1.
• Der Prozess mit Rang 1 empfängt diese Nachricht mit MPI_Recv und gibt sie aus.
• Schließlich beendet MPI_Finalize die MPI-Umgebung.
• Überprüfe unbedingt, dass mindestens zwei Prozesse laufen, sonst gibt das Programm einen Fehler aus und bricht ab.

b)

Analysiere die Performance deines MPI-Programms bei verschiedenen Nachrichtengrößen. Führe das Programm mit unterschiedlichen Größen der gesendeten Nachricht (\textit{z.B.} 10 Bytes, 100 Bytes, 1000 Bytes) aus und dokumentiere die Sende- und Empfangszeiten. Welche Auswirkungen haben die Nachrichtengröße und die Netzwerkarchitektur auf die Performance?

Lösung:

• Analysiere die Performance deines MPI-Programms bei verschiedenen Nachrichtengrößen:
• Das MPI-Programm wird mit unterschiedlichen Nachrichtengrößen wie 10 Bytes, 100 Bytes und 1000 Bytes ausgeführt.
• Es wird die Zeit gemessen, die für das Senden und Empfangen der Nachrichten benötigt wird.
• Führe das Programm unter realistischen Netzwerkbedingungen aus, um die Auswirkungen der Netzwerkarchitektur auf die Performance zu bewerten.
• Hier ist der erweiterte Code mit Zeitmessungen:

#include <mpi.h>  #include <stdio.h>  #include <stdlib.h>  #include <string.h>  #include <time.h>   int main(int argc, char** argv) {      MPI_Init(&argc, &argv);       int world_rank;      MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);       int world_size;      MPI_Comm_size(MPI_COMM_WORLD, &world_size);       if (world_size < 2) {          fprintf(stderr, "Benötigt mindestens zwei Prozesse");          MPI_Abort(MPI_COMM_WORLD, 1);      }       int message_sizes[] = {10, 100, 1000};       for (int i = 0; i < 3; i++) {          int message_size = message_sizes[i];           char* message = (char*)malloc(message_size * sizeof(char));          memset(message, 'a', message_size);          message[message_size - 1] = '\0';           double start_time, end_time;           if (world_rank == 0) {              start_time = MPI_Wtime();              MPI_Send(message, message_size, MPI_CHAR, 1, 0, MPI_COMM_WORLD);              end_time = MPI_Wtime();              printf("Sendezeit für %d Bytes: %f Sekunden", message_size, end_time - start_time);          } else if (world_rank == 1) {              char* recv_message = (char*)malloc(message_size * sizeof(char));              start_time = MPI_Wtime();              MPI_Recv(recv_message, message_size, MPI_CHAR, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);              end_time = MPI_Wtime();              printf("Empfangszeit für %d Bytes: %f Sekunden", message_size, end_time - start_time);              free(recv_message);          }          free(message);      }       MPI_Finalize();      return 0;  }   

• Dokumentation von Sende- und Empfangszeiten:
• Führe das Programm für verschiedene Nachrichtengrößen (10 Bytes, 100 Bytes, 1000 Bytes) aus und notiere die gemessenen Zeiten.
• Vergleiche die Zeiten und dokumentiere die Ergebnisse.
• Analyse der Ergebnisse:
• Die Sende- und Empfangszeiten werden mit zunehmender Nachrichtengröße länger, da mehr Daten übertragen werden müssen.
• Die Netzwerkarchitektur beeinflusst die Performance erheblich. Bei schnelleren Netzwerken (z.B. Infiniband) sind die Zeiten kürzer im Vergleich zu langsameren Netzwerken (z.B. Ethernet).
• Bei sehr großen Nachrichten kann es zu Netzwerkengpässen kommen, was die Übertragungszeiten weiter erhöht.

c)

Erweitere das MPI-Programm aus dem ersten Teil zu einem Programm, das kollektive Kommunikation verwendet. Schreibe das Programm so um, dass nun alle Prozesse (mindestens vier) teilnehmen und eine Broadcast-Operation durchgeführt wird. Benutze die Funktion MPI_Bcast und erkläre, wie sich die Programmstruktur und die Performance ändern.

Lösung:

• Erweiterung des MPI-Programms für kollektive Kommunikation:
• Das vorhandene MPI-Programm wird geändert, damit alle Prozesse an einer Broadcast-Operation teilnehmen können.
• Statt der Punkt-zu-Punkt-Kommunikation zwischen zwei Prozessen wird die Funktion MPI_Bcast verwendet.
• In diesem Beispiel wird vorausgesetzt, dass mindestens vier Prozesse verwendet werden.
• Hier ist der erweiterte Code mit kollektiver Kommunikation:

#include <mpi.h>  #include <stdio.h>  #include <stdlib.h>  #include <string.h>   int main(int argc, char** argv) {      MPI_Init(&argc, &argv);       int world_rank;      MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);       int world_size;      MPI_Comm_size(MPI_COMM_WORLD, &world_size);       if (world_size < 4) {          fprintf(stderr, "Benötigt mindestens vier Prozesse");          MPI_Abort(MPI_COMM_WORLD, 1);      }       int message_size = 100;      char* message = (char*)malloc(message_size * sizeof(char));       if (world_rank == 0) {          memset(message, 'a', message_size);          message[message_size - 1] = '\0';          printf("Prozess 0: Sende Nachricht: %s", message);      }       MPI_Bcast(message, message_size, MPI_CHAR, 0, MPI_COMM_WORLD);       printf("Prozess %d: Empfangene Nachricht: %s", world_rank, message);       free(message);       MPI_Finalize();      return 0;  }  

• Erläuterungen zum Code:
• Das Programm initialisiert MPI mit MPI_Init.
• Es erhält die aktuelle Prozessnummer mit MPI_Comm_rank und die Gesamtanzahl der Prozesse mit MPI_Comm_size.
• Der Prozess mit Rang 0 erstellt eine Nachricht und initialisiert sie mit 100 Zeichen 'a'.
• Die Funktion MPI_Bcast wird verwendet, um die Nachricht von Prozess 0 an alle anderen Prozesse zu senden.
• Jeder Prozess gibt nach dem Empfang der Nachricht den Inhalt der Nachricht aus.
• Schließlich wird MPI_Finalize aufgerufen, um die MPI-Umgebung zu beenden.
• Änderungen an der Programmstruktur:
• Statt nur zwei Prozesse zu verwenden, können nun beliebig viele Prozesse (mindestens vier) teilnehmen.
• Die Funktion MPI_Bcast ermöglicht es, die Nachricht gleichzeitig an alle Prozesse zu senden, anstatt immer nur eine Punkt-zu-Punkt-Kommunikation durchzuführen.
• Das Programm strukturiert sich neu, um kollektive Operationen zu unterstützen.
• Auswirkungen auf die Performance:
• Die Broadcast-Operation kann effizienter sein als mehrfache Punkt-zu-Punkt-Sendungen, insbesondere bei größeren Prozesszahlen oder großen Nachrichten.
• Das Netzwerk spielt nach wie vor eine wichtige Rolle, da die Nachricht gleichzeitig an mehrere Prozesse gesendet wird.
• Die Gesamtzeit für die Kommunikation kann reduziert werden, jedoch hängt dies von der Netzwerkarchitektur und der Nachrichtengröße ab.