alp4-lernkarten-sose.pdf

lOMoARcPSD|6917782 Alp4-Lernkarten - SoSe Nichtsequentielle und verteilte Programmierung (Freie Universität Berlin) Scanne, um auf Studocu zu öffnen Studocu wird von keiner Unive...

lOMoARcPSD|6917782 Alp4-Lernkarten - SoSe Nichtsequentielle und verteilte Programmierung (Freie Universität Berlin) Scanne, um auf Studocu zu öffnen Studocu wird von keiner Universität gesponsert oder unterstützt. Heruntergeladen durch Dilek Shener ([email protected])  lOMoARcPSD|6917782 Alp4-Lernkarten Frage Antwort Tags Nebenläufig - Gemeinsamer Welche Arten von Speicher - Eine CPU Parallel - nichtsequentieller Gemeinsamer oder verteilter Alp4_Allgemein Programmierung gibt Speicher - Mehr als eine CPU es? Verteilt - Weder gemeinsamer Speicher - Noch gemeinsame CPU Es soll: - die funktionalen Anforderungen erfüllen (das tun, Welche zwei was wir erwarten) - die Anforderungen stellen Alp4_Allgemein nichtfunktionalen Anforderungen wir an ein Programm? erfüllen (Performance, Benutzbarkeit, Sicherheit, …) Modell der Systemzustandsänderung: Menge von Operationen, dargestellt durch Welche Modelle Befehle einer Programmiersprache. nutzen wir für die Programmiermodell: Auswahl und Erstellung von Reihenfolge von Operationen. Programmen und Ausführungsmodell: Auswahl und Alp4_Allgemein wodurch wird die Reihenfolge von Befehlen. Korrektheit des Maschinenausführungsmodell: Programms Übertragung des sichergestellt? Ausführungsmodell in Maschinencode. Korrektheit: Jedes Modell muss fehlerfrei in das jeweils nächste übertragen werden. Determinismus: Ein deterministischer Algorithmus ist determiniert und durchläuft immer Was bedeuten die gleichen Operationen in der Determinismus und gleichen Reihenfolge. Alp4_Allgemein Determiniertheit? Determiniertheit: Ein determinierter Algorithmus erzeugt zu jeder bestimmten Eingabe immer die gleiche Ausgabe Alp4-Lernkarten 1 Heruntergeladen durch Dilek Shener ([email protected])  lOMoARcPSD|6917782 Frage Antwort Tags Wann ist ein Korrekt, wenn das Programm Programm korrekt im deterministisch ist. Erreicht durch Sinne der Vorlesung Alp4_Allgemein korrekte Übertragung der Modelle in und wie wird dies das nächste Modell. erreicht? Warum sind die Weil externe Einflüsse (z.B. I/O) die meisten Programme deterministische Ausführung Alp4_Allgemein nichtdeterministisch? verhindern können. Wie kann trotz Programm in sinnvolle Module nichtdeterministischer aufteilen, die aus deterministischen Ausführung die Abläufen bestelen, aber in ihrer Alp4_Allgemein Korrektheit des Gesamtheit keine deterministische Programms Ausführung benötigen. sichergestellt werden? - Trennung Speicherbereichen Welche Anforderungen durch Adressräume - Möglichkeit stellt Nebenläufigkeit der Prozessgenerierung - Alp4_Nebenläufigkeit an das System? Möglichkeit, zwischen Prozessen zu wechseln Atomare Operationen sind nicht in kleinere Operationen aufteilbar und könnend daruch nicht durch einen Was sind atomare und Interrupt unterbrochen werden nicht-atomare Nicht-atomare Operationen Alp4_Allgemein Operationen? bestehen aus mehreren Maschineninstruktionen und können durch einen Interrupt unterbrochen werden Welchen Einfluss hat - Prozesswechsel erzeugen einen Nebenläufigkeit auf die Overhead - Nebenläufigkeit Alp4_Nebenläufigkeit Performance? reduziert Leerlauf der CPU Wie agieren Threads in Alle Threads nutzen einen Bezug auf das gemeinsamen Adressraum, aber Alp4_Threads Maschinenmodell? jeweils einen eigenen Stack. Welchen Vorteil haben Bei Nebenläufigkeit wird der Threads in Bezug auf Speicher komplett kopiert. Threads Speichernutzung haben einen geringeren Alp4_Threads gegenüber Speicheraufwand, weil sie einen Nebenläufigkeit? gemeinsamen Adressraum nutzen. Alp4-Lernkarten 2 Heruntergeladen durch Dilek Shener ([email protected])  lOMoARcPSD|6917782 Frage Antwort Tags Welches Operationen der einzelnen Threads Hauptproblem erzeugt werden nicht mehr deterministisch die Programmierung ausgeführt und können dadurch mit mehreren Threads aufgrund des gemeinsamen Alp4_Threads und wie nennt man Adressraums ein falsches Ergebnis Bereiche, in denen erzeugen. Solche Bereiche werden dieses auftritt? Kritische Abschnitte genannt. Funktionale Anforderungen: - Welche Anforderungen Sicherung des kritischen Abschnitts stellen wir an eine - Höhere Programmiersprache - Alp4_Threads Lösung zur Sicherung Kein Deadlock Nichtfunktionale eines kritischen Anforderungen: - Minimaler Gegenseitiger Ausschluss Abschnitts? Overhead - Fairer Zugriff auf kritischen Abschnitt - Einfaches Lock - Twofold Lock - Welche Arten von Twofold Lock with Primary Locks ohne OS- Gegenseitiger Ausschluss Protection - Twofold Lock with Unterstützung gibt es? Mutual Precedence Woran erkenne ich ein - Nur eine Lock-Variable Gegenseitiger Ausschluss einfaches Lock? Welche funktionalen Anforderungen erfüllt Locken ist ein ungeschützter ein einfaches Lock kritischer Abschnitt nicht? Sei n die Anzahl der Threads. - Woran erkenne ich ein Array von n Lock-Variablen - Locken Gegenseitiger Ausschluss Twofold Lock? passiert nach der Warteschleife Welche funktionalen - Locken ist ein ungeschützter Anforderungen erfüllt kritischer Abschnitt - Freigebender ein Twofold Lock Thread könnte Zugriff anfordern, nicht? obwohl er zuvor Unlockt hat. Woran erkenne ich ein Sei n die Anzahl der Threads. - Twofold Lock with Array von n Lock-Variablen - Locken Gegenseitiger Ausschluss Primary Protection? passiert vor der Warteschleife Welche funktionalen Anforderungen erfüllt ein Twofold Lock with - Es kann ein Deadlock enstehen. Gegenseitiger Ausschluss Primary Protection nicht? Alp4-Lernkarten 3 Heruntergeladen durch Dilek Shener ([email protected])  lOMoARcPSD|6917782 Frage Antwort Tags Sei n die Anzahl der Threads. - Array von n Lock-Variablen - Locken Woran erkenne ich ein passiert vor der Warteschleife - In Twofold Lock with Gegenseitiger Ausschluss der Warteschleife wird das eigene Mutual Precedence? Lock wiederholt für 1 Sekunde unlockt. - Kritischer Abschnitt wird Warum erfüllt ein zuverlässig geschützt. - Ist in Twofold Lock with höherer Programmiersprache Mutual Precedence die Gegenseitiger Ausschluss umsetzbar - Deadlocks werden funktionalen durch Unlocken in Warteschleife Anforderungen? aufgelöst. Welche Lösung zur Sicherung des kritischen Abschnitts Ein Twofold Lock with Mutual ohne OS- Gegenseitiger Ausschluss Precedence Unterstützung erfüllt alle funktionalen Anforderungen? Wie sieht der #include … int threads; char Pseudocode eines lock; int lock(long tid) { lock[tid] = Twofold Locks with 1; while(lock[_NUM_THREADS - 1 - Gegenseitiger Ausschluss Mutual Precedence tid]){ lock[tid] = 0; sleep(1); lock[tid] aus? (Globals, lock(), = 1; } return 0; } int unlock(long tid) { unlock()) lock[tid] = 0; return 0; } Welche Lösung zur Sicherung des kritischen Abschnitts ohne OS- Ein Twofold Lock with Mutual Unterstützung erfüllt Access by Peterson alle funktionalen und nichtfunktionalen Anforderungen Welche Gründe - Overhead wird durch Hardware- sprechen für eine OS- Optimierungen reduziert - Locken basierte Lösung zur und Unlocken sind atomare Sicherung des Operationen kritischen Abschnitts? Alp4-Lernkarten 4 Heruntergeladen durch Dilek Shener ([email protected])  lOMoARcPSD|6917782 Frage Antwort Tags - Threadwechsel erzeugen einen Welchen Einfluss Overhead - Ein haben Threads auf die Geschwindigkeitszuwachs entsteht, Gegenseitiger Ausschluss Performance? wenn das Programm sinnvoll in parallele Abschnitte aufgeteilt wird Entstehung Wenn der anfordernde Wann entsteht ein Thread das Lock nicht innerhalb der Livelock und was ist Gegenseitiger Ausschluss Sleep-Zeit des anderen Threads die Folge? erlangen kann Folge Verhungern 1. Ressourcen werden exklusiv genutzt 2. Threads oder Prozessen Wie lauten die vier ist eine Ressource zugewiesen und Bedingungen für eine sie versuchen, sich eine andere Verklemmung Verklemmung? zuzuweisen 3. Es gibt keine Preemption 4. Es gibt einen Kreis im Wartegraphen Ja, zum Beispiel wenn: - 2 globale Kann es beim Objekte im Speicher liegen - Thread Hauptspeicher als 1 Objekt 1 zugewiesen ist, - Thread Ressource zu einer Verklemmung 2 Objekt 2 zugewiesen ist, - Thread Verklemmung 1 Objekt 2 anfordert und - Thread 2 kommen? Objekt 1 anfordert Kann es bei der CPU Ja, zum Beispiel bei mehreren als Ressource zu einer Threads, deren kritischer Abschnitt Verklemmung Verklemmung mit einem Lock ohne Mutual kommen? Precedence gesichert ist. Welche vier Methoden - Deadlock prevention - Deadlock gibt es für den avoidance - Deadlock detection - Verklemmung Umgang mit Deadlock resolution Verklemmungen? G = B + R v = f + B[+] Wie lauten die (Spaltensummen) Nach jeder Gleichungen für den Verklemmung Terminierung eines Threads t: f := f Bankier-Algorithmus? + B[Zeile t] Welche Lösungen zur Sicherung des kritischen Abschnitts - Mutex - Semaphore - Monitor Gegenseitiger Ausschluss mit OS-Unterstützung gibt es? Alp4-Lernkarten 5 Heruntergeladen durch Dilek Shener ([email protected])  lOMoARcPSD|6917782 Frage Antwort Tags Eine Lösung für gegenseitigen Was ist ein Mutex? Gegenseitiger Ausschluss Ausschluss - Erweiterung der Lock-Variable - Was ist eine Unterschied zum Lock: Es können Semaphore und wie mehrere Threads in den kritischen unterscheidet sie sich Gegenseitiger Ausschluss Abschnitt eintreten - Unterscheid von einem Lock und zum Monitor: Lock und Unlock sind einem Monitor? explizit - Zähler, der anzeigt, wie viele Threads in den kritischen Abschnitt eintreten dürfen - Eintreten ist erst Wie funktioniert eine möglich, wenn der Zähler > 0 ist - Gegenseitiger Ausschluss Semaphore? Beim Eintreten wird der Zähler dekrementiert - Beim Austreten wird der Zähler inkrementiert sem_init: Semaphore initialisieren - sem_t *sem: Zeiger auf Semaphore Was sind die - int pshared: Max. gleichzeitige wichtigsten POSIX- Threads - int value: Initialer Zähler Gegenseitiger Ausschluss Methoden für sem_wait: Warten auf Eintritt - Semaphoren? sem_t *sem: Zeiger auf Semaphore sem_post: Austritt - sem_t *sem: Zeiger auf Semaphore Was ist ein Monitor Ein Objekt, - das Funktionen und und wie unterscheidet Daten enthält - sicherstellt, dass Gegenseitiger Ausschluss er sich von einem Lock immer nur ein Thread gleichzeitig und einer Semaphore? darauf zugreift Was sind Condition - Zeigen an, ob ein Thread innerhalb Variables bei des Monitors freigegeben werden Gegenseitiger Ausschluss Monitoren? kann oder warten muss. Wann ist ein Teil eines Wenn es eine Folge von Petri Netzes Transitionen gibt, durch die Tokens Petri Netze erreichbar? den Teil erreichen können. Schwach lebendig: Wenn es eine Transition gibt, die feuern kann und Wann ist ein Petri-Netz dieses Feuern das Feuern einer stark lebendig und Petri Netze anderen Transition ermöglicht. Stark schwach lebendig? lebendig: Wenn alle Transitionen schwach lebendig sind. Alp4-Lernkarten 6 Heruntergeladen durch Dilek Shener ([email protected])  lOMoARcPSD|6917782 Frage Antwort Tags - Erweiterung von Petri-Netzen - Was sind farbige Petri- Token werden farblich oder mit Netze und wann sind Petri Netze Nummern gekennzeichnet - Sinnvoll sie sinnvoll? bei komplexen Petri-Netzen Welche Probleme wurden in der - Speisende Philosophen - Petri Netze Vorlesung mit Petri- Produzenten und Konsumenten - Netzen modelliert? 1. Partitionierung: Aufteilen des Problems in minimale unabhängige Welche vier Schritte Aufgaben 2. Communication: beinhaltet das Beziehungen zwischen Aufgaben Fostersche rausfinden 3. Agglomeration: Foster Vorgehensmodell zur Aufgaben zu Gruppen Entwicklung paralleler zusammenfassen, die je zusammen Programme? auf einem Prozessor laufen sollen 4. Mapping: Die Gruppen den konkreten Prozessoren zuordnen - Domain and data decomposition: Welche zwei Arten von Voneinander unabhängige Daten - Partionierung gibt es Functional decomposition: Foster im Fosterschen Voneinander unabhängige Vorgehensmodell? Funktionen Komplette Aufteilung ist nicht möglich. Aufteilung ist immer ein Welches Problem tritt Kompromiss zwischen Größe der Foster bei Partitionierung auf? Aufgaben und Kommunikationskosten. - Mehr Aufgaben als Prozessoren - Wenige redundante Berechnungen Wann ist eine und Daten - Aufgaben sind alle Foster Partitionierung gut? gleich groß - Anzahl der Aufgaben proportional zur Problemgröße - Kommunikationsaufwand gleich Wann ist ein auf alle Aufgaben verteilt - Aufgaben Kommunikationsmodell kommunizieren mit wenigen Foster gut? anderne Aufgaben - Kommunikation und Berechnungen sind nebenläufig Alp4-Lernkarten 7 Heruntergeladen durch Dilek Shener ([email protected])  lOMoARcPSD|6917782 Frage Antwort Tags Wann ist ein - Reduziert insgesamt Agglomerationsmodell Kommunikationsaufwand - Foster gut? Änderungsfreundlichkeit Wann ist ein - Volle Auslastung aller Prozessoren Foster Mappingmodell gut? - Geschwindigkeitszuwachs bei parallelen Programmen wird durch Was besagt Amdahls sequentiellen Anteil beschränkt - Je Foster Gesetz? höher der sequentielle Anteil, desto niedriger der Geschwindigkeitszuwachs Partitionierung: - Berechnung der Felder in der Zielmatrix Communication: - Vor Berechnung: Zeile der Eingabematrix A und Spalte der Eingabematrix B vom Root Task zum jeweiligen Untertask Wie wird - Nach Berechnung: Ergebnisse der Matrizenmultiplikation Untertasks zum Root Task mit dem Fosterschen Foster Agglomeration: - Gruppiere Tasks, Vorgehensmodell die die gleichen Zeilen und Spalten modelliert? der Eingabematrizen nutzen Mapping: - Keine Kommunikation zwischen Untertasks - Root Task so zuordnen, dass die Kommunikationskosten zu den Untertasks reduziert wird Alp4-Lernkarten 8 Heruntergeladen durch Dilek Shener ([email protected])  lOMoARcPSD|6917782 Frage Antwort Tags Partitionierung: - Functional decomposition nicht sinnvoll, denn Berechnungen sind voneinander abhängig - Data decomposition nicht sinnvoll, denn Array-Bereiche sind während Laufzeit von Pivot- Element abhängig - Also eine Kombination: Tasks sind die Wie wird Quicksort mit Unterlisten jeder Rekursionsstufe - dem Fosterschen Bei jedem Merge muss Foster Vorgehensmodell synchronisiert werden modelliert? Communication: - Unterlisten bei jeder Rekursion vom Aufrufer zur Unteraufgabe - Nach jeder Berechnung von der Unteraufgabe zum Aufrufer Agglomeration: - Tasks gruppieren, die auf der gleichen Unterliste rechnen Mapping: - Untertasks sollten möglichst nah an ihrem Ersteller liegen Server | ServerSocket s = new ServerSocket(port); Server | s.accept(); Client | Socket s = new Socket(serverURL, serverPort); Wie ist der zeitliche Client | InputStream in = Ablauf für eine Client- s.getInputStream(); Client | Sockets Server-Socket- OutputStream out = Kommunikation? s.getOutputStream(); Server | InputStream in = s.getInputStream(); Server | OutputStream out = s.getOutputStream(); Alp4-Lernkarten 9 Heruntergeladen durch Dilek Shener ([email protected])  lOMoARcPSD|6917782 Frage Antwort Tags Server: ServerSocket s = new ServerSocket(port); s.accept(); InputStream in = s.getInputStream(); BufferedReader reader = new BufferedReader( new Wie sieht der InputStreamReader(in) ); Pseudocode für einen OutputStream out = Echo-Server mit s.getOutputStream(); while(true) { Sockets Sockets aus (Client String line = reader.readLine(); und Server)? if(line.equals(”bye\n”)) { s.close(); break; } out.write() } Client: Socket s = new Socket(serverURL, serverPort); InputStream in = s.getInputStream(); OutputStream out = s.getOutputStream(); - Client verbindet sich zum Server - Client serialisiert Aufrufdaten - Was passiert (bezogen Server akzeptiert Verbindung - auf RMI), wenn eine Server leitet den Aufruf an das Methode eines Remote-Objekt weiter - Server RMI entfernten Objekts serialisiert Ausgabe des Aufrufs - aufgerufen wird? Client empfängt und deserialisiert die Antwort und gibt sie an den Aufrufer zurück Was passiert (bezogen auf RMI), wenn eine Methode eines Es wird eine RemoteException, entfernten Objekts mit genauer eine einem Parameter, das NotSerializableException geworfen, RMI nicht das Serializable- weil die Argumente einer Remote Interface Method serialisierbar sein müssen. implementiert, aufgerufen wird? Welche Java RMI- Interfaces werden - Remote - Serializable RMI benötigt? Alp4-Lernkarten 10 Heruntergeladen durch Dilek Shener ([email protected])  lOMoARcPSD|6917782 Frage Antwort Tags Registry registry = Wie sieht der Code für LocateRegistry.getRegistry(host); einen Fernaufruf einer MyRemoteClass stub = RMI Methode auf dem (MyRemoteClass) Client aus? registry.lookup(”MyRemoteClass”); stub.myMethod(”myParam”); - Server erstellt Stub des Remote- Objekts - Server bindet Stub in der Was muss passieren, Registry - Client holt sich Registry damit ein Client ein vom Server - Client holt sich Stub RMI Vertreter-Objekt des Remote-Objekts aus der erhält? Registry - Der Stub ist das Vertreter- Objekt. Alp4-Lernkarten 11 Heruntergeladen durch Dilek Shener ([email protected])  lOMoARcPSD|6917782 Frage Antwort Tags MPI_Init(int *argc, char ***argv) - Initialisiere Laufzeitumgebung - Verteile Parameter auf alle Prozesse MPI_Finalize() - Beende Laufzeitumgebung - Gib alle Ressourcen frei MPI_Comm_rank(comm, *rank) - Schreibe rank des Aufruferprozesses in *rank MPI_Comm_size(comm, *size) - Schreibe Anzahl der Prozesse in der Gruppe in *size MPI_Send(*smessage, count, datatype, dest, tag, comm) - Sende Inhalt des smessage-Buffers an Wie lauten die Prozess dest - Blockiere, bis Buffer Signaturen der freigegeben ist MPI_Isend(…, MPI wichtigsten MPI- *request) - Wie MPI_Send, aber Befehle? asynchron - Schreibe Anfragedaten in *request - Prüfen, ob fertig mit MPI_Wait() MPI_Recv(*rmessage, count, datatype, source, tag, comm, *status) - Empfange Nachricht von source und schreibe in rmessage- Buffer - Blockiert, bis Nachricht in Buffer steht MPI_IRecv(…, *request) - Wie MPI_Recv, aber asynchron - Schreibe Anfragedaten in *request MPI_Test(*request, *flag, *status) - Schreibe Flag und Status des Requests in *flag und *status MPI_Wait(*request, *status); - Blockiere, bis asynchrone Operation des Requests erfüllt ist Alp4-Lernkarten 12 Heruntergeladen durch Dilek Shener ([email protected])  lOMoARcPSD|6917782 Frage Antwort Tags Pragmas #pragma omp parallel - Parallelisiere nächste Zeile oder Block #pragma omp for - Parallelisiere Iterationen der For- Schleife #pragma omp sections > #pragma omp section - Führe alle sections als Team of Threads aus #pragma omp barrier - Synchronisiere alle Threads Clauses private(varlist) - Variablen Was sind die aus varlist sind nur im jeweiligen wichtigsten Pragmas Thread verfügbar shared(varlist) - OpenMP und Clauses von Variablen aus varlist werden OpenMP? zwische allen Threads geteilt default(shared | none) - Mache alle Variablen shared oder explizit schedule(static | dynamic | guided, chunk size) - Lege Anzahl Iterationen in einem Chunk fest - static → Chunks werden reihum ausgeführt - dynamic → Chunks werden auf Idle-Threads verteilt - guided → Chunk-Größe wird mit jeder Zuweisung verkleinert Wann ist bei einer parallelen For-Schleife statisches, wann Dynamisch - wenn die Iterationen dynamisches unterschiedliche Kosten haben - Scheduling sinnvoll Nachteil: Größerer Overhead als OpenMP und was ist ein Statisch Statisch - wenn alle Nachteil des Iterationen gleiche Kosten haben dynamischen Scheduling? Alp4-Lernkarten 13 Heruntergeladen durch Dilek Shener ([email protected])