Parallele und Funktionale Programmierung - Exam

Aufgabe 1)

Ein Softwareentwickler arbeitet an einem parallelen Verarbeitungsprogramm und möchte die Vorteile von Datenparallelität und Task-Parallelität verstehen. Der Entwickler möchte die verschiedenen Paradigmen in einem realen Szenario anwenden, um die Effizienz seines Programms zu maximieren. Angenommen, das Szenario umfasst einen Web-Server, der große Mengen an Bildern gleichzeitig verarbeiten und auf Kundenanfragen reagieren muss.

a)

Beschreibe, wie Du das Konzept der Datenparallelität auf die Bildverarbeitung auf dem Web-Server anwenden würdest. Erkläre Deine Vorgehensweise im Detail und welche Vorteile dies bringen würde.

Lösung:

Konzept der Datenparallelität auf einem Web-Server zur Bildverarbeitung:

• Schritt 1: Datenaufteilung Die erste Maßnahme besteht darin, die zu verarbeitenden Bilder in mehrere Blöcke oder Segmente zu unterteilen. Dies könnte durch einfache Teilung der Bilder in gleiche Teile erfolgen. Bei großen Bildmengen auf dem Web-Server wird jedes Bild in kleinere Chunks aufgeteilt, sodass diese Chunks parallel verarbeitet werden können.
• Schritt 2: Zuweisung an Prozesse oder Threads In einem Multi-Core-Prozessor-Umfeld oder einem verteilten System kann jedes Bildsegment an unterschiedliche Prozessoren oder Knoten im Netzwerk verteilt werden. Dies bedeutet, dass jeder Prozessor parallel an einem Segment des Bildes arbeiten kann. In der Regel würde man dabei mehrfädige Programmierung (Multithreading) oder Multi-Prozess-Programmieransätze, wie z.B. MapReduce verwenden.
• Schritt 3: Parallele Verarbeitung Jeder Thread oder Prozess führt die notwendigen Bildverarbeitungsoperationen (z.B. Filter, Transformationen, Kompression) auf seinem zugewiesenen Segment durch. Da die Verarbeitung unabhängig ist, können alle Prozesse parallel ohne Wartezeiten arbeiten. Dies reduziert die Gesamtlatenz erheblich.
• Schritt 4: Rekombination der Ergebnisse Nach Abschluss der parallelen Verarbeitung wird jeder verarbeitete Bildsegment wieder zusammengesetzt, um das vollständige Bild zu rekonstruieren. Dies kann durch einfache Zusammenfügung der Teilbilder geschehen. Auch das Aggregieren der Daten erfolgt parallel, um den Gesamtprozess weiter zu beschleunigen.
• Vorteile der Datenparallelität
  • Erhöhte Verarbeitungsgeschwindigkeit: Durch parallele Verarbeitung wird die Effizienz erheblich gesteigert, da mehrere Chunks von Bildern gleichzeitig bearbeitet werden können.
  • Optimale Ressourcennutzung: Die Nutzung von Multithreading und verteiltem Rechnen führt zu einer besseren Auslastung der verfügbaren Hardware-Ressourcen (Prozessoren/Knoten).
  • Skalierbarkeit: Da die Daten parallel bearbeitet werden, lässt sich das System einfach skalieren, indem mehr Prozessoren oder Server hinzugefügt werden, um die Verarbeitungskapazitäten zu erweitern.
  • Reduzierte Latenz: Da die Bearbeitung zeitgleich stattfindet, verkürzt sich die Latenz deutlich, wodurch Web-Server schneller auf Kundenanfragen reagieren können.

b)

Implementiere ein kleines Programm in Python, das die Datenparallelität nutzt, um eine Liste von Bildern gleichzeitig zu verarbeiten. Nutze dabei die Bibliothek 'multiprocessing' oder 'numpy'. Füge den Code hier ein:

'write your code actual here'

Lösung:

Hier ist ein Beispielprogramm in Python, das Datenparallelität nutzt, um eine Liste von Bildern gleichzeitig zu verarbeiten. In diesem Beispiel verwenden wir die Bibliothek 'multiprocessing', um die parallele Verarbeitung zu implementieren. Das Programm wendet eine einfache Bildtransformation (z.B. Graustufen) auf eine Liste von Bildern an.

import multiprocessing as mpimport cv2import os# Funktion zur Bildverarbeitung (z.B. Umwandlung in Graustufen)def process_image(image_path):    image = cv2.imread(image_path)    gray_image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)    output_path = f'{os.path.splitext(image_path)[0]}_gray.jpg'    cv2.imwrite(output_path, gray_image)    return output_path# Hauptfunktion zur parallelen Verarbeitung von Bilderndef main(image_paths):    with mp.Pool(processes=mp.cpu_count()) as pool:        results = pool.map(process_image, image_paths)    return resultsif __name__ == '__main__':    # Liste von Bildern, die verarbeitet werden sollen    image_paths = ['image1.jpg', 'image2.jpg', 'image3.jpg']    processed_images = main(image_paths)    print(f'Processed Images: {processed_images}')

• Schritt 1: Importiere notwendige Bibliotheken Zuerst importieren wir die notwendigen Bibliotheken 'multiprocessing', 'cv2' und 'os'. 'cv2' wird für die Bildverarbeitung genutzt.
• Schritt 2: Definiere die Bildverarbeitungsfunktion Die Funktion 'process_image' liest ein Bild ein, wandelt es in Graustufen um und speichert das verarbeitete Bild ab.
• Schritt 3: Parallele Verarbeitung In der Funktion 'main' erstellen wir einen Pool von Prozessen basierend auf der Anzahl der verfügbaren CPU-Kerne und nutzen die Funktion 'pool.map', um die Bildverarbeitung parallel durchzuführen. Jeder Pfad in 'image_paths' wird an die Funktion 'process_image' übergeben.
• Schritt 4: Ausführung des Programms Im Hauptteil des Programms definieren wir eine Liste von Bildpfaden, die verarbeitet werden sollen, und rufen die 'main' Funktion auf, um die parallele Verarbeitung zu starten.

c)

Erkläre, wie Du das Konzept der Task-Parallelität auf die Verarbeitung von Kundenanfragen auf dem Web-Server anwenden würdest. Welche Methoden und Praktiken würdest Du einsetzen, um die Lastverteilung der Aufgaben effizient zu gestalten?

Lösung:

Konzept der Task-Parallelität auf einem Web-Server zur Verarbeitung von Kundenanfragen:

• Schritt 1: Aufgabenidentifikation Zuerst identifizieren wir die verschiedenen Aufgaben, die parallel ausgeführt werden können. Bei einem Web-Server, der Kundenanfragen bearbeitet, könnten dies Aufgaben wie die Bilderverarbeitung, die Datenbankabfragen, die Authentifizierung der Benutzer und das Laden von Inhalten sein. Jede dieser Aufgaben kann unabhängig voneinander ausgeführt werden.
• Schritt 2: Verwendung eines Task-Queue-Systems Ein Task-Queue-System, wie RabbitMQ oder Celery, hilft dabei, die Aufgaben zu verwalten und zu verteilen. Kundenanfragen werden in eine Warteschlange gestellt, und Worker-Prozesse holen sich die Aufgaben aus dieser Warteschlange zur Bearbeitung. Dies ermöglicht eine effiziente Lastverteilung und vermeidet Überlastungen.
• Schritt 3: Mehrfädigkeit und Prozessparallelität Die Web-Server-Software sollte in der Lage sein, mehrere Threads oder Prozesse zu erzeugen, um die eingehenden Anfragen parallel zu bearbeiten. In Python kann dies durch Bibliotheken wie 'threading' für Threads oder 'multiprocessing' für Prozesse erreicht werden. Beispielsweise könnte man für CPU-intensive Aufgaben 'multiprocessing' verwenden und für I/O-gebundene Aufgaben 'asyncio'.
• Schritt 4: Asynchrone Verarbeitung Die Verwendung von asynchroner Programmierung, etwa mit der Bibliothek 'asyncio' in Python, erlaubt es, viele I/O-gebundene Aufgaben gleichzeitig zu bearbeiten, ohne auf die Ergebnisse anderer Aufgaben warten zu müssen. Dies erhöht die Effizienz, besonders bei Aufgaben wie Datenbankabfragen oder Netzwerkkommunikation.
• Schritt 5: Lastverteilung und Skalierung Für eine effiziente Lastverteilung und Skalierung sollten LoadBalancer zum Einsatz kommen, die den Traffic auf mehrere Server oder Instanzen verteilen. Bekannte LoadBalancer sind HAProxy oder NGINX. Diese ermöglichen es, den Traffic gleichmäßig zu verteilen und Spitzenlasten abzufangen.
• Vorteile der Task-Parallelität
  • Effiziente Ressourcennutzung: Durch parallele Ausführung von Aufgaben werden die Ressourcen des Servers optimal genutzt.
  • Höhere Durchsatzrate: Mehrere Kundenanfragen können gleichzeitig bearbeitet werden, was die Durchsatzrate des Servers erhöht.
  • Verbesserte Skalierbarkeit: Das System kann leicht durch Hinzufügen zusätzlicher Worker oder Server skaliert werden, um steigende Lasten zu bewältigen.
  • Reduzierte Latenz: Da Aufgaben parallel verarbeitet werden, kann die Reaktionszeit des Web-Servers gesenkt werden, was zu einer besseren Benutzererfahrung führt.

d)

Diskutiere die potenziellen Herausforderungen und Nachteile der Verwendung von Datenparallelität und Task-Parallelität in Deinem Szenario. Erwähne dabei auch die Optimierungskriterien:

• Datenverteilung für Datenparallelität
• Lastverteilung für Task-Parallelität

Lösung:

Potenzielle Herausforderungen und Nachteile der Verwendung von Datenparallelität und Task-Parallelität:

• Datenverteilung für Datenparallelität:
  • Zuweisung und Synchronisation: Eine effiziente Zuweisung der Datenblöcke an verschiedene Prozessoren oder Knoten ist erforderlich, um die Vorteile der Datenparallelität zu nutzen. Dies kann kompliziert werden, wenn die Datenflüsse schwer vorhersehbar sind oder wenn unterschiedliche Chunks unterschiedliche Verarbeitungszeiten benötigen. Auch die Synchronisation der Threads oder Prozesse kann den Overhead erhöhen und die Effizienz verringern.
  • Datenabhängigkeiten: Falls es zwischen den verarbeiteten Datenblöcken Abhängigkeiten gibt, muss dies berücksichtigt werden. Synchronisation und Kommunikation zwischen den Threads können zu Engpässen führen und den Vorteil der Parallelität mindern.
  • Datenübertragung: In verteilten Systemen kann die Übertragung von Daten zwischen Knoten zeitaufwändig sein und zu einer erhöhten Latenz führen. Der Overhead der Datenübertragung kann den Geschwindigkeitsgewinn durch Parallelität aufheben.
  • Speicherressourcen: Die Verarbeitung großer Datenmengen kann erhebliche Speicherressourcen beanspruchen. Es ist wichtig zu optimieren, wie der verfügbare Speicher genutzt wird, um einen effizienten Zugriff und eine effiziente Verarbeitung zu gewährleisten.
• Lastverteilung für Task-Parallelität:
  • Effiziente Verteilung: Eine ungleiche Lastverteilung kann zu bestimmten Prozessoren oder Knoten führen, die unter- oder überlastet sind. Ein gutes Load-Balancing-Mechanismus ist notwendig, um sicherzustellen, dass die Server gleichmäßig ausgelastet sind und keine Ressourcen verschwendet werden. LoadBalancer müssen zudem intelligent genug sein, um unterschiedliche Arten von Anfragen effizient zu verteilen.
  • Skalierung: Beim Hinzufügen neuer Ressourcen (wie zusätzliche Server) müssen diese nahtlos in das bestehende System integriert werden. Dies kann zusätzliche Konfigurationsarbeit und möglicherweise Ausfallzeiten während des Integrationsprozesses erfordern.
  • Kommunikationsoverhead: In Systemen mit hoher Task-Parallelität kann der Overhead der Kommunikation zwischen den Aufgaben zu Leistungsproblemen führen, insbesondere wenn viele Task-Queue-Systeme wie RabbitMQ oder Celery verwendet werden. Die Verwaltung von Nachrichten und Synchronisationen kann komplex sein und zusätzliche Latenz einführen.
  • Fehlerbehandlung: Die Fehlererkennung und -behebung in einem System mit hoher Parallelität kann schwierig sein. Für eine robuste Fehlerbehandlung muss sichergestellt werden, dass Fehler isoliert und schnell behoben werden können, ohne das gesamte System zu beeinträchtigen.
• Optimierungskriterien:
  • Effiziente Datenaufteilung: Um die Datenparallelität zu optimieren, ist eine gleichmäßige und effiziente Aufteilung der Daten entscheidend. Algorithmen zur Lastverteilung und Datenpartitionierung können helfen, die Daten optimal zu segmentieren und den Overhead zu reduzieren.
  • Intelligentes Load Balancing: Für die Task-Parallelität ist die Implementierung eines intelligenten Load-Balancers unerlässlich. Dieser sollte in der Lage sein, die Last dynamisch und basierend auf den aktuellen Systemmetriken zu verteilen, um eine gleichmäßige Auslastung sicherzustellen.
  • Ressourcenmanagement: Eine optimale Nutzung der verfügbaren Ressourcen (z.B. CPU, Speicher) ist entscheidend für die Leistungsfähigkeit des Systems. Monitoring-Tools und Ressourcenmanagement-Lösungen können verwendet werden, um die Ressourcennutzung zu überwachen und bei Bedarf anzupassen.
  • Reduzierung des Overheads: Sowohl bei der Datenparallelität als auch bei der Task-Parallelität sollte darauf geachtet werden, den Overhead (Kommunikation, Synchronisation) zu minimieren. Effiziente Algorithmen und Protokolle helfen dabei, den Overhead zu reduzieren und die Leistung zu maximieren.

Aufgabe 2)

In einem parallelen System gibt es mehrere Threads, die auf eine gemeinsame Ressource zugreifen müssen. Um sicherzustellen, dass kein Konflikt durch gleichzeitigen Zugriff entsteht, sollen Synchronisationsmechanismen wie Mutex, Semaphore und Locks verwendet werden.

a)

Beschreibe die Funktionsweise eines Mutex und erläutere, wie Du ihn zur Synchronisation von zwei Threads verwenden würdest. Veranschauliche Deine Erklärung mit einem Beispielcode in C++.

Lösung:

Ein Mutex (von 'Mutual Exclusion abgeleitet) ist ein Synchronisationsmechanismus, der verwendet wird, um sicherzustellen, dass nur ein Thread gleichzeitig auf eine gemeinsame Ressource zugreifen kann. Der Grundgedanke besteht darin, dass der Mutex eine Art Sperre ist. Nur der Thread, der den Mutex erfolgreich gesperrt hat, darf die geschützte Ressource nutzen. Andere Threads, die denselben Mutex sperren wollen, müssen warten, bis der Mutex wieder freigegeben wird.

Wie funktioniert ein Mutex?

• Ein Thread, der auf eine gemeinsame Ressource zugreifen möchte, versucht zuerst einen Mutex zu sperren.
• Wenn der Mutex gesperrt ist, muss der Thread warten, bis der Mutex frei wird.
• Wenn der Mutex frei ist, kann der Thread ihn sperren und auf die Ressource zugreifen.
• Nach dem Zugriff auf die Ressource gibt der Thread den Mutex wieder frei, damit andere Threads darauf zugreifen können.

Um die Synchronisation von zwei Threads mit einem Mutex zu veranschaulichen, kannst Du folgendes Beispiel in C++ betrachten:

 #include <iostream> #include <thread> #include <mutex>  std::mutex mtx;  void printEven() {     for (int i = 0; i < 10; i += 2) {         std::lock_guard<std::mutex> lock(mtx);         std::cout << "Even: " << i << std::endl;         // Der Mutex wird automatisch freigegeben, wenn der lock_guard zerstört wird.     } }  void printOdd() {     for (int i = 1; i < 10; i += 2) {         std::lock_guard<std::mutex> lock(mtx);         std::cout << "Odd: " << i << std::endl;         // Der Mutex wird automatisch freigegeben, wenn der lock_guard zerstört wird.     } }  int main() {     std::thread t1(printEven);     std::thread t2(printOdd);      t1.join();     t2.join();      return 0; } 

• In diesem Beispiel gibt es zwei Funktionen: printEven und printOdd, die jeweils die geraden und ungeraden Zahlen von 0 bis 9 drucken.
• Beide Funktionen verwenden einen std::lock_guard<std::mutex>, um sicherzustellen, dass nur ein Thread gleichzeitig auf die Ressource (in diesem Fall die Konsole) zugreift.
• Der lock_guard sperrt den Mutex im Konstruktor und gibt ihn im Destruktor automatisch frei, sodass wir uns keine Sorgen über das manuelle Freigeben des Mutex machen müssen.

b)

Ein Semaphore ermöglicht mehrere gleichzeitige Zugriffe auf eine Ressource. Erkläre den Unterschied zwischen einem Binärsemaphore und einem Zählsemaphore. Implementiere einen Semaphore in C, der fünf gleichzeitige Zugriffe erlaubt.

Lösung:

Ein Semaphore ist ein Synchronisationsmechanismus, der verwendet wird, um den Zugriff auf eine gemeinsame Ressource in Multithreading-Umgebungen zu steuern. Der wesentliche Unterschied zu einem Mutex besteht darin, dass ein Semaphore mehr als einen gleichzeitigen Zugriff auf die Ressource erlauben kann.

Binärsemaphore:

• Ein Binärsemaphore funktioniert ähnlich wie ein Mutex.
• Er kann nur zwei Zustände haben: 0 (gesperrt) und 1 (frei).
• Er erlaubt nur einen gleichzeitigen Zugriff auf die Ressource.

Zählsemaphore:

• Ein Zählsemaphore kann beliebige nicht-negative Werte annehmen.
• Er kann mehr als einen gleichzeitigen Zugriff auf die Ressource erlauben.
• Der Zählerwert gibt die Anzahl der gleichzeitigen Zugriffe an, die erlaubt sind.

Hier ist eine Implementierung eines Semaphors in C, der fünf gleichzeitige Zugriffe erlaubt:

 #include <stdio.h> #include <stdlib.h> #include <pthread.h> #include <semaphore.h>  #define NUM_THREADS 10 #define NUM_RESOURCES 5  sem_t sem;  void* threadFunction(void* arg) {     int thread_num = *(int*)arg;      printf("Thread %d wartet auf Zugriff...", thread_num);     sem_wait(&sem);      printf("Thread %d hat Zugang", thread_num);     // Simuliere eine Ressourcennutzung     sleep(1);      printf("Thread %d gibt die Ressource frei", thread_num);     sem_post(&sem);      free(arg);     pthread_exit(NULL); }  int main() {     pthread_t threads[NUM_THREADS];      // Initialisiere den Semaphore mit der Anzahl der erlaubten Zugriffe     sem_init(&sem, 0, NUM_RESOURCES);      for (int i = 0; i < NUM_THREADS; i++) {         int* thread_num = malloc(sizeof(int));         *thread_num = i;         pthread_create(&threads[i], NULL, threadFunction, thread_num);     }      for (int i = 0; i < NUM_THREADS; i++) {         pthread_join(threads[i], NULL);     }      // Zerstöre den Semaphore     sem_destroy(&sem);      return 0; } 

• In diesem Beispiel wird ein sem_t Semaphore initialisiert, der bis zu fünf gleichzeitige Zugriffe ermöglicht.
• Die sem_wait Funktion wird verwendet, um auf den Semaphore zu warten. Wenn der Zähler des Semaphors größer als null ist, wird er dekrementiert und der Thread erhält Zugriff auf die Ressource. Andernfalls blockiert der Thread, bis der Zähler größer als null wird.
• Die sem_post Funktion wird verwendet, um den Semaphore freizugeben. Dadurch wird der Zähler des Semaphors um eins erhöht und ein wartender Thread (falls vorhanden) kann fortgesetzt werden.
• In der main Funktion werden zehn Threads erstellt, die alle auf eine simulierte Ressource zugreifen und jeweils eine Sekunde lang blockieren, bevor sie die Ressource freigeben.

c)

Was sind Reader-Writer-Locks und wie unterscheiden sie sich von einfachen Mutexes? Erkläre, wie sie dabei helfen können, die Performance zu verbessern, wenn eine Vielzahl von Leseoperationen und nur einige wenige Schreiboperationen durchgeführt werden sollen. Implementiere ein Reader-Writer-Lock in Python.

Lösung:

Ein Reader-Writer-Lock ist ein Synchronisationsmechanismus, der speziell dafür entwickelt wurde, um die Effizienz zu verbessern, wenn ein paralleles System hauptsächlich Leseoperationen und nur wenige Schreiboperationen durchführt. Im Gegensatz zu einem einfachen Mutex ermöglicht ein Reader-Writer-Lock mehreren Threads gleichzeitig Lesezugriff auf eine Ressource, blockiert jedoch alle Lese- und Schreiboperationen, wenn ein Thread Schreibzugriff benötigt.

Unterschiede:

• Ein einfacher Mutex erlaubt nur, dass entweder ein Lese- oder ein Schreibzugriff gleichzeitig auf eine Ressource erfolgen kann. Das bedeutet, dass ein Mutex alle Threads blockiert, egal ob sie lesen oder schreiben wollen.
• Ein Reader-Writer-Lock unterscheidet zwischen Lese- und Schreibzugriffen. Mehrere Threads können gleichzeitig lesen, solange keiner schreibt. Wenn ein Schreibzugriff benötigt wird, wird er alle laufenden Lesezugriffe warten lassen, bis der Schreibvorgang abgeschlossen ist.

Da Lesezugriffe normalerweise nicht die Daten verändern, können mehrere Lesezugriffe gleichzeitig erfolgen, ohne die Konsistenz der Daten zu gefährden. In Situationen, in denen Lesevorgänge häufiger auftreten als Schreibvorgänge, kann die Verwendung von Reader-Writer-Locks die Performance erheblich verbessern.

Hier ist eine Implementierung eines Reader-Writer-Locks in Python:

 import threading  class ReaderWriterLock:     def __init__(self):         self.readers = 0         self.writer = False         self.lock = threading.Lock()         self.read_cond = threading.Condition(self.lock)         self.write_cond = threading.Condition(self.lock)      def acquire_read_lock(self):         with self.lock:             while self.writer:                 self.read_cond.wait()             self.readers += 1      def release_read_lock(self):         with self.lock:             self.readers -= 1             if self.readers == 0:                 self.write_cond.notify_all()      def acquire_write_lock(self):         with self.lock:             while self.writer or self.readers > 0:                 self.write_cond.wait()             self.writer = True      def release_write_lock(self):         with self.lock:             self.writer = False             self.read_cond.notify_all()             self.write_cond.notify_all()  # Beispielanwendung: Leser und Schreiber import time  lock = ReaderWriterLock()  def reader(reader_id):     while True:         lock.acquire_read_lock()         print(f"Reader {reader_id} liest Daten...")         time.sleep(1)         lock.release_read_lock()         time.sleep(2)  def writer(writer_id):     while True:         lock.acquire_write_lock()         print(f"Writer {writer_id} schreibt Daten...")         time.sleep(2)         lock.release_write_lock()         time.sleep(3)  if __name__ == "__main__":     readers = [threading.Thread(target=reader, args=(i,)) for i in range(5)]     writers = [threading.Thread(target=writer, args=(i,)) for i in range(2)]      for r in readers:         r.start()     for w in writers:         w.start()      for r in readers:         r.join()     for w in writers:         w.join() 

• In dieser Implementierung sind die Methoden acquire_read_lock und release_read_lock für den Lesezugriff zuständig.
• Die Methoden acquire_write_lock und release_write_lock sind für den Schreibzugriff zuständig.
• Leser können gleichzeitig Zugriff erhalten, solange kein Schreiber zugreift.
• Ein Schreibzugriff blockiert alle anderen Zugriffe, bis er abgeschlossen ist.
• Die Beispielanwendung zeigt, wie fünf Lese-Threads und zwei Schreib-Threads parallel ausgeführt werden.

d)

Betrachte das folgende Szenario: Ein paralleles System führt Rechenschritte mit gemeinsamen Daten durch, wobei einige Berechnungen voneinander abhängen und nur fortgesetzt werden dürfen, wenn die vorigen Berechnungen abgeschlossen sind. Erläutere, wie Du dieses Problem mit einem Semaphore lösen würdest. Verwende mathematische Ausdrücke, um die Abhängigkeiten zu beschreiben.

Lösung:

Um das beschriebene Problem zu lösen, können wir Semaphoren als Synchronisationsmechanismus verwenden, um sicherzustellen, dass die Berechnungen in der richtigen Reihenfolge ausgeführt werden. Dabei kann ein Semaphore genutzt werden, um die Abhängigkeiten zwischen den Berechnungsschritten zu steuern.

Nehmen wir an, dass es drei Berechnungsschritte gibt: A, B und C. Die Berechnungen haben folgende Abhängigkeiten:

1. Berechnung B kann nur fortgesetzt werden, wenn A abgeschlossen ist.2. Berechnung C kann nur fortgesetzt werden, wenn B abgeschlossen ist.

Wir können dies mathematisch ausdrücken als:

• B = f(Bereich von B, Bereich von A(abgeschlossen))
• C = f(Bereich von C, Bereich von B(abgeschlossen))

Um diese Abhängigkeiten zu implementieren, können wir Semaphoren verwenden:

• Ein Semaphore 'sem_AB', um sicherzustellen, dass B erst fortgesetzt wird, wenn A abgeschlossen ist.
• Ein Semaphore 'sem_BC', um sicherzustellen, dass C erst fortgesetzt wird, wenn B abgeschlossen ist.

Hier eine Implementierung des Szenarios mit Python und threading sowie threading.Semaphore:

 import threading  sem_AB = threading.Semaphore(0) sem_BC = threading.Semaphore(0)  def berechnung_A():     print("Berechnung A beginnt...")     # Simuliere die Berechnung von A     threading.Timer(2, lambda: print("Berechnung A abgeschlossen")).start()     # Signalisiere, dass A abgeschlossen ist     sem_AB.release()  def berechnung_B():     # Warte darauf, dass A abgeschlossen ist     sem_AB.acquire()     print("Berechnung B beginnt...")     # Simuliere die Berechnung von B     threading.Timer(2, lambda: print("Berechnung B abgeschlossen")).start()     # Signalisiere, dass B abgeschlossen ist     sem_BC.release()  def berechnung_C():     # Warte darauf, dass B abgeschlossen ist     sem_BC.acquire()     print("Berechnung C beginnt...")     # Simuliere die Berechnung von C     threading.Timer(2, lambda: print("Berechnung C abgeschlossen")).start()  if __name__ == "__main__":     thread_A = threading.Thread(target=berechnung_A)     thread_B = threading.Thread(target=berechnung_B)     thread_C = threading.Thread(target=berechnung_C)      thread_A.start()     thread_B.start()     thread_C.start()      thread_A.join()     thread_B.join()     thread_C.join() 

• Im obigen Beispiel haben wir drei Semaphoren sem_AB und sem_BC verwendet, um die Abhängigkeiten zwischen den drei Berechnungsschritten A, B und C zu steuern.
• Der Thread für berechnung_B wartet darauf, dass der Thread für berechnung_A das Semaphore sem_AB freigibt, bevor es fortgesetzt wird.
• Der Thread für berechnung_C wartet darauf, dass der Thread für berechnung_B das Semaphore sem_BC freigibt, bevor es fortgesetzt wird.
• Durch die Verwendung von Semaphoren stellen wir sicher, dass die Berechnungsschritte in der richtigen Reihenfolge ausgeführt werden und keine Abhängigkeiten verletzt werden.

Aufgabe 3)

In einem parallelen Programm wird eine Logikkomponente für die Berechnung von Finanztransaktionen entwickelt. Die Logik beinhaltet mehrere Threads, die gleichzeitig auf gemeinsame Datenstrukturen zugreifen, um Transaktionen zu verarbeiten. Die Implementierung enthält Synchronisationsmechanismen, um Race Conditions und Deadlocks zu verhindern.

a)

Angenommen, Du hast den folgenden Pseudocode für die Transaktionsberechnung:

lock Alock BThread 1:   for each transaction t in transactions:    lock(t.sourceAccount)    lock(t.destinationAccount)    t.sourceAccount.balance -= t.amount    t.destinationAccount.balance += t.amount    unlock(t.destinationAccount)    unlock(t.sourceAccount)  nextunlock Aunlock B

• Erläutere, welche Art von Fehler bei der obigen Implementierung auftreten könnte und warum.
• Gib eine verbesserte Version der Implementierung, die Deadlocks vermeidet, an.

Lösung:

In einer parallelen Programmumgebung ist es wichtig, Synchronisationsmechanismen zu implementieren, um Race Conditions und Deadlocks zu verhindern. Betrachten wir zunächst die möglichen Fehler in der gegebenen Implementierung und bieten anschließend eine verbesserte Version an.

• Möglicher Fehler und Gründe:Ein Deadlock tritt auf, wenn zwei oder mehr Threads auf Ressourcen warten, die von den jeweils anderen Threads gehalten werden. Im gegebenen Pseudocode könnten Deadlocks entstehen, da die Reihenfolge, in der die Locks auf die Konten angewendet werden, nicht konsistent ist. Zum Beispiel könnte Thread 1 `t.sourceAccount` sperren und dann auf `t.destinationAccount` warten, während ein anderer Thread bereits `t.destinationAccount` gesperrt hat und auf `t.sourceAccount` wartet. Dies führt zu einer Situation, in der keiner der Threads fortfahren kann, und es entsteht ein Deadlock.
• Verbesserte Implementierung zur Vermeidung von Deadlocks:Um Deadlocks zu vermeiden, sollte eine konsistente Reihenfolge zum Sperren der Ressourcen festgelegt werden. Eine übliche Methode ist, die Objekte in einer festen Reihenfolge zu sperren, z.B. nach der Kontonummer. Hier ist eine verbesserte Version des Pseudocodes:

lock Alock BThread 1:   for each transaction t in transactions:    if t.sourceAccount.id < t.destinationAccount.id:        lock(t.sourceAccount)        lock(t.destinationAccount)    else:        lock(t.destinationAccount)        lock(t.sourceAccount)    t.sourceAccount.balance -= t.amount    t.destinationAccount.balance += t.amount    unlock(t.sourceAccount)    unlock(t.destinationAccount)  nextunlock Aunlock B

Durch die konsistente Sperrreihenfolge wird sichergestellt, dass Deadlocks vermieden werden, da immer zuerst die Ressource mit der kleineren ID gesperrt wird.

b)

Ein alternatives Szenario könnte die Verwendung eines anderen Synchronisationsmechanismus beinhalten:

lock LThread 1:   acquire(L)  for each transaction t in transactions:    wait until t.sourceAccount.lock and t.destinationAccount.lock are both available    lock(t.sourceAccount)    lock(t.destinationAccount)    t.sourceAccount.balance -= t.amount    t.destinationAccount.balance += t.amount    unlock(t.destinationAccount)    unlock(t.sourceAccount)    signal others waiting for t.sourceAccount.lock or t.destinationAccount.lock  next  release(L)

• Analysiere das Risiko von Race Conditions im obigen Pseudocode. Erkläre, wie sie behoben werden könnten.
• Erläutere die Nachteile dieser Implementierung gegenüber einem Deadlock-Präventionsansatz und diskutiere die Kompromisse.

Lösung:

In diesem alternativen Szenario wird ein anderer Synchronisationsmechanismus eingesetzt. Lassen uns die Risiken und Nachteile dieser Implementierung untersuchen sowie mögliche Lösungen vorschlagen.

• Analyse des Risikos von Race Conditions:Race Conditions treten auf, wenn mehrere Threads gleichzeitig auf gemeinsame Daten zugreifen und mindestens einer dieser Zugriffe ein Schreibvorgang ist, wodurch inkonsistente oder unerwartete Zustände entstehen können. Im gegebenen Pseudocode könnte eine Race Condition auftreten, wenn mehrere Threads versuchen, die gleichen Konten (sourceAccount und destinationAccount) zu sperren und zu bearbeiten. Obwohl das anfangs erfolgte acquire(L) und das letztendliche release(L) sicherstellen, dass nur ein Thread gleichzeitig die Transaktionen verarbeitet, gibt es ein Risiko während des Wartens und des Sperrens der einzelnen Accounts, wenn nicht alle Sperren ordnungsgemäß erworben werden.
• Vorschlag zur Behebung von Race Conditions:Um Race Conditions zu vermeiden, könnten die Kontensperren in einer festen Reihenfolge wie in der vorherigen Frage verwendet werden. Dabei sollte der globale Lock verwendet werden, um sicherzustellen, dass immer ein Thread zur gleichen Zeit die Sperren erwirbt und freigibt. Zum Beispiel:

lock LThread 1:   acquire(L)    for each transaction t in transactions:        if t.sourceAccount.id < t.destinationAccount.id:            lock(t.sourceAccount)            lock(t.destinationAccount)        else:            lock(t.destinationAccount)            lock(t.sourceAccount)        t.sourceAccount.balance -= t.amount        t.destinationAccount.balance += t.amount        unlock(t.sourceAccount)        unlock(t.destinationAccount)    next  release(L)

• Nachteile dieser Implementierung gegenüber einem Deadlock-Präventionsansatz:Diese Implementierung hat sowohl Vor- als auch Nachteile:
  • Vorteile:
    • Durch die globale Sperre (Lock L) wird verhindert, dass mehrere Threads gleichzeitig auf die Transaktionsliste zugreifen, wodurch Race Conditions vermieden werden.
  • Nachteile:
    • Die Verwendung einer globalen Sperre kann die Parallelität und damit die Effizienz des Programms erheblich verringern, da immer nur ein Thread Transaktionen verarbeiten kann.
    • Der Overhead durch Warten auf die globale Sperre kann in Systemen mit vielen Threads und Transaktionen signifikant sein, was zu einer verminderten Performance führt.
• Diskussion der Kompromisse:Der Einsatz einer globalen Sperre bietet eine einfache Möglichkeit, Race Conditions zu vermeiden, kann jedoch die Leistungsfähigkeit und Skalierbarkeit der Anwendung negativ beeinflussen. Eine Methodik zur Vermeidung von Deadlocks wie die konsistente Sperrreihenfolge bietet eine bessere Balance zwischen Sicherheit und Effizienz. Sie ermöglicht mehreren Threads die gleichzeitige Bearbeitung verschiedener Transaktionen, solange die festgelegten Regeln eingehalten werden. Allerdings kann die Implementierung und das Debugging solcher Ansätze komplexer sein.

Aufgabe 4)

Gegeben ist folgendes Szenario in Erlang:

Du sollst eine Funktion schreiben, die eine Liste von Zahlen erhält und für jede ungerade Zahl in der Liste einen neuen Prozess erstellt, um die Zahl zu verdoppeln. Das Ergebnis soll als Liste der verdoppelten Zahlen zurückgegeben werden. Beachte dabei, dass Variablen in Erlang unveränderlich sind und dass bei der Erstellung nebenläufiger Systeme die Syntax von spawn verwendet wird.

a)

Teil 1: Implementiere die Hauptfunktion process_odd_numbers(TL), welche eine rekursive Funktion ist und die ungeraden Zahlen aus der Liste extrahiert und verdoppelt. Die rekursive Funktion sollte die folgende Signatur haben:

process_odd_numbers([H|T]) -> {Ausdruck}

Wenn der Kopf der Liste H eine ungerade Zahl ist, soll die Funktion double_number/1 in einem neuen Prozess aufgerufen werden.

Lösung:

Um die Aufgabe zu lösen, musst Du eine rekursive Funktion in Erlang implementieren, die ungerade Zahlen aus einer Liste extrahiert und verdoppelt. Jede Verdopplung soll in einem neuen Prozess stattfinden. Unten findest Du eine Schritt-für-Schritt-Anleitung:

• Schritt 1: Definiere die rekursive Funktion process_odd_numbers/1.
• Schritt 2: Überprüfe in der Funktion, ob das Element ungerade ist.
• Schritt 3: Erstelle einen neuen Prozess mit spawn, der die Funktion double_number/1 aufruft, wenn das Element ungerade ist.
• Schritt 4: Setze die rekursive Verarbeitung der restlichen Liste fort.
• Schritt 5: Stelle sicher, dass das Ergebnis als Liste zurückgegeben wird.

Unten findest Du den entsprechenden Erlang-Code:

process_odd_numbers([]) -> [];process_odd_numbers([H|T]) ->  if    H rem 2 =:= 1 ->      Pid = spawn(fun() -> double_number(H) end),      [Pid ! get_result(Pid) | process_odd_numbers(T)];    true ->      process_odd_numbers(T)  end.double_number(N) ->  Result = 2 * N,  receive    {From, get_result} ->      From ! Result  end.get_result(Pid) ->  Pid ! {self(), get_result},  receive    Result -> Result  end.

Hier sind die wichtigsten Punkte der Implementierung:

• Die Funktion process_odd_numbers/1 nimmt eine Liste entgegen und prüft, ob das erste Element ungerade ist.
• Falls ungerade, erstellt sie einen neuen Prozess mit spawn, der die Funktion double_number/1 aufruft.
• Die Funktion double_number/1 verdoppelt die Zahl und sendet das Ergebnis zurück.
• Die Resultate werden in einer neuen Liste gesammelt.

So wird eine Liste von verdoppelten ungeraden Zahlen zurückgegeben.

b)

Teil 2: Implementiere die Funktion double_number/1, welche die gegebene Zahl verdoppelt und das Ergebnis zurückgibt. Diese Funktion sollte rein funktional sein und keine Nebenwirkungen haben. Verwende diese Signatur:

double_number(X) -> {Ausdruck}

Wo X die Eingabezahl ist.

Lösung:

Um die Funktion double_number/1 zu implementieren, die eine gegebene Zahl verdoppelt und das Ergebnis zurückgibt, folge diesen Schritten:

• Die Funktion sollte eine einfache Multiplikation durchführen.
• Die Funktion sollte rein funktional sein und keine Nebenwirkungen haben.
• Die Funktion wird die Eingabezahl X als Argument nehmen und das doppelte von X zurückgeben.

Im Folgenden findest du den entsprechenden Erlang-Code:

 double_number(X) -> 2 * X. 

Hier sind die wichtigsten Punkte der Implementierung:

• Die Funktion double_number/1 nimmt eine Zahl X entgegen.
• Sie verdoppelt die Zahl, indem sie X mit 2 multipliziert.
• Das Ergebnis wird zurückgegeben.

Diese Implementierung erfüllt die Anforderung, dass die Funktion keine Nebenwirkungen haben und rein funktional sein muss. Die Funktion ist einfach und führt die gewünschte Berechnung durch.

c)

Teil 3: Erläutere anhand eines Beispiels, wie Pattern Matching in deiner Implementierung verwendet wird, um die ungeraden Zahlen aus der Liste zu extrahieren. Nutze eine Beispiel-Liste [1, 2, 3, 4, 5] und zeige den Schritt-für-Schritt Prozess deiner Funktion anhand dieser Liste. Welche besondere Rolle spielt Rekursion und wie wird sichergestellt, dass die Funktion korrekt terminiert?

Lösung:

Um zu erläutern, wie Pattern Matching in der Implementierung verwendet wird, um die ungeraden Zahlen aus einer Liste zu extrahieren und zu verdoppeln, schauen wir uns die folgende Beispiel-Liste [1, 2, 3, 4, 5] an und demonstrieren den Schritt-für-Schritt-Prozess der Funktion.

• Schritt 1: Die Funktion process_odd_numbers/1 nimmt die Liste [1, 2, 3, 4, 5] als Argument entgegen.
• Schritt 2: Durch Pattern Matching wird das erste Element 1 als Kopf der Liste H und die Liste [2, 3, 4, 5] als Schwanz der Liste T extrahiert.
• Schritt 3: Da 1 ungerade ist, wird ein neuer Prozess mit spawn erstellt, der die Funktion double_number/1 aufruft, um 1 zu verdoppeln. Das Ergebnis 2 wird gesammelt.
• Schritt 4: Die Funktion ruft sich rekursiv mit der restlichen Liste [2, 3, 4, 5] auf.
• Schritt 5: Dieses Mal ist das erste Element 2 und die Liste [3, 4, 5]. Da 2 gerade ist, wird es übersprungen und die Funktion ruft sich rekursiv mit der restlichen Liste [3, 4, 5] auf.
• Schritt 6: Das neue Element ist 3 und die Liste [4, 5]. Da 3 ungerade ist, wird ein neuer Prozess erstellt, um 3 zu verdoppeln. Das Ergebnis 6 wird gesammelt.
• Schritt 7: Die Funktion ruft sich rekursiv mit der restlichen Liste [4, 5] auf.
• Schritt 8: Dieses Mal ist das erste Element 4 und die Liste [5]. Da 4 gerade ist, wird es übersprungen und die Funktion ruft sich rekursiv mit der restlichen Liste [5] auf.
• Schritt 9: Das neue Element ist 5 und die Liste ist leer. Da 5 ungerade ist, wird ein neuer Prozess erstellt, um 5 zu verdoppeln. Das Ergebnis 10 wird gesammelt.
• Schritt 10: Die Funktion ruft sich rekursiv mit der leeren Liste [] auf.
• Schritt 11: Da die Liste jetzt leer ist, terminiert die Funktion und gibt die gesammelten Ergebnisse [2, 6, 10] zurück.

Hier ist der vollständige Code der Funktion:

 process_odd_numbers([]) -> [];process_odd_numbers([H|T]) ->  if    H rem 2 =:= 1 ->      Pid = spawn(fun() -> double_number(H) end),      [Pid ! get_result(Pid) | process_odd_numbers(T)];    true ->      process_odd_numbers(T)  end.double_number(X) -> 2 * X.get_result(Pid) ->  Pid ! {self(), get_result},  receive {Result} -> Result. end. 

Besondere Rolle der Rekursion: Die Rekursion ermöglicht es der Funktion, durch die Liste zu iterieren und sicherzustellen, dass jeder Punkt abgearbeitet wird, bis die Liste leer ist. Dies stellt sicher, dass die Funktion korrekt terminiert.