Concurrent & Distributed Systems Flashcards
Aus welchen Teileinheiten besteht ein Prozessor? Erkläre diese.
Steuerwerk - Steuerung der Programmausführung
ALU (Arithmetisch-Logische Einheit, Rechenwerk) - führt Berechnungen durch für Dinge in Registern
(Allgemeine) Register: Schneller Zwischenspeicher von Daten
Spezielle Register:
Befehlszähler (BZ): Zeigt auf aktuellen Befehl im Speicher
Befehlsregister (BR): Zwischenspeicher für aktuellen Befehl
Statusregister (SR): Abspeichern von charakteristischen Eigenschaften des Ergebnisses der letzten ALU-Operation
Was verarbeitet ein Prozessor?
Der Prozessor verarbeitet die einzelnen Befehle eines Befehlssatzes (Menge der Maschinenbefehle) - diese enthalten meist einen Opcode und einen oder mehrere Operanden
Was ist der Von-Neumann-Zyklus? Erkläre diesen näher.
= Prinzip der sequentiellen Programmausführung
1) Fetch –> hol nächsten Befehl aus dem Speicher entsprechend der Adresse im Befehlszähler
2) Decode –> Befehl wird durch Steuerwerk in Schaltinstruktionen für das Rechenwerk aufgelöst
3) Fetch Operands -> schaut sich Operanden an, holt dese aus dem Hauptspeicher (Operanden = Parameter)
4) Execute -> Operation wird ausgeführt
5) Write Back -> Wenn notwendig, wird Ergebnis der Berechnung in den Hauptspeicher zurückgeschrieben
Was sind Vor- und Nachteile der Von-Neumann-Architektur?
+ Streng sequentieller Ablauf vereinfacht Programmierung
- Daten- und Adressbus werden zum Engpass (Bottleneck) zwischen Prozessor und Speicher (wenn Bus nicht schnell genug ist, kommt es zu Performance-Problemen - immer nur eine Sache auf einmal)
Was besagt Moore’s Law?
Verdopplung der Transistorzahl alle 18 Monate, also dass sich die Komplexität der CPUs verdoppelt alle 18 Monate
Was sind die Grenzen der Leistungssteigerung?
Taktraten der CPUs können nicht beliebig erhöht werden (kleine physikalische Größen von Systemen)
CPU <–> Arbeitsspeicher Bandbreite ist begrenzt (RAM kann mit Geschwindigkeit der CPUs nicht mithalten)
Wie sind Prozessoren mit mehreren Kernen aufgebaut?
= Mikroprozessoren mit mehreren vollständigen CPUs - jeder Kern hat eine eigene ALU und einen eigenen individuellen Speicher, was die Parallelisierung der Programmausführung erleichtert
Wie sieht die Speicherhierarchie in modernen Computern aus?
Register - 300 ps (1 KB)
L1 Cache - 1 ns (64 KB)
L2 Cache - 3 - 10 ns (256 KB)
L3 Cache - 10 - 20 ns (2 - 4 MB)
Arbeitsspeicher - 50 - 100 ns (4 - 64 GB)
Hauptspeicher - 5 - 10 ms (4 - 16 TB)
Was sind Cache-Lines?
Wenn Daten aus dem Speicher geholt werden, dann in Form von Cache-Lines - diese halten 64 Byte und holen immer diese Größe von Daten: wenn man Matrizen z.B. Zeilenweise einliest, so ist dies viel schneller als wenn man diese spaltenweise einliest
Was ist Concurrency (Nebenläufigkeit)?
Es werden mehrere Aufgaben gleichzeitig ausgeführt, aber ein Kern führt mehrere Tasks gleichzeitig durch (Multitasking)
Was ist Parallele Verarbeitung?
Ein Rechner mit einer parallelen Architektur kann Operationen gleichzeitig auf mehrere Haupt- oder Grafikprozessoren durchführen
Was ist Shared Memory?
= Geteilter Speicher
Alle Kerne haben Zugriff auf den selben gemeinsamen Speicher
Was ist Distributed Memory?
Alle Kerne haben ihren eigenen lokalen Speicher und sind über ein Kommunikationsnetzwerk (Interconnet) miteinander verbunden
Was ist Amdahls Law? Wie lautet die Formel?
Das Gesetz wird im Bereich des parallelen Rechnen benutzt zur Festlegung der theoretisch maximal erreichbren Speedups
Jedes Problem hat einen sequentiellen Anteil, der nicht parallelisiert werden kann - ist der sequentielle Anteil 0, ist das Problem vollständig parallel ausführbar -> der parallel auführbare Anteil des Problem ergibt sich aus (1 - f)
Die gesamte Laufzeit des Algorithmus ergibt sich aus dem sequentiellen Anteil plus dem parallelen Anteil
Formel:
Speedup = 1 / (f + (1 - f) / p)
f = sequentieller Anteil
p = Anzahl der Prozessoren
Welche Kritik gibt es an Amdahls Law?
Effekte durch Caches in der CPU bleiben unberücksichtigt
Problemgröße verändert sich nicht
Zu welchem Problemen kann es bei der Parallelisierung kommen?
Kommunikation zwischen Prozessen ist ein Problem
Race Condition: Bug, wenn Operationen zeitlich abhängig von anderen Threads sind und das Ergebnis einer Operation beeinflussen (zeitliche Ausführung kann bei Threads nicht garantiert werden)
Data Race: Zwei Threads greifen zur selben Zeit auf gleiche Daten zu und verändern diese
Deadlock / Verklemmung: Zwei Prozesse warten gegenseitig auf ein Ergebnis vom anderen Prozess und es kommt zu einem Stillstand
Was bedeutet thread-safety?
Ein Programm oder eine Methode ist thread-sicher, wenn es keine Unbestimmtkeit gegenüber irgendeinem Multithreading Szenario aufweist.
Wie kann ein Data Race gelöst werden?
Mit Sperrsynchronisation mitteln Locking
Was ist ein Prozess? Was enthält ein Prozess?
Führt ein Programm auf einem Prozessor aus (Instanz vom Programm) - wird vom Betriebssystem erzeugt und besitzt eigenen Speicherbereich für Programmcode, statische und dynamische Daten als auch einen eigenen Stack
Was gehört zu einem Prozess?
(Virtueller) Adressraum (Heap, Stack)
Prozesskontext (CPU Register, Zugriffsrechte)
Daten (Prozessspezifische Daten)
Identität (pid = process id, uid = user id, gid = group id)
Was ist ein Stack? Was speichert dieser?
Ein Speicherbereich im virtuellen Adressraum (LIFO)
Lokale Variablen, Funktionsparameter, Rückgabewerte und Rücksprungadressen
Was ist der Heap? Was speichert dieser?
Beim Heap muss Speicher explizit angefordert werden (new)
Anlegen und freigeben von Objekten ist langsam - Daten auf dem Heap können global zugegriffen werden (shared memory)
Statische Variablen landen immer am Heap
Was ist ein Thread?
= Sequentieller Ausführungspfad innerhalb eines Prozesses mit minimalen eigenem Kontext (CPU-Registersatz, Stack, Identifikationsnummer, Priorität…)
Alle Threads eines Prozesses benutzten denselben Adressraum sowie weitere Betriebsmittel des Prozesses gemeinsam
Außerhalb von Prozessen gibt es keine Threads - jeder Thread braucht seinen eigenen Stack
Welche Zustände kann ein Prozess annehmen?
Bereit - Prozess ist bereit und hat alle Daten, die er braucht; muss nur mehr einer CPU zugewiesen werden
Aktiv - Prozess / Thread hat einen Prozessor zugeteilt bekommen
Blockiert - Prozess / Thread wartet auf ein Ergebnis
Suspended - Prozess / Thread wurde aufgehalten
Warum wird ein Prozess suspendiert? Kurzfristige Überlastung, Benutzer will Prozess stoppen, kein virtueller Speicher mehr frei
Zombie - Zwischenzustand bevor ein Prozess das System verlässt (Prozess hat Aufgabe erledigt und muss nur noch einen Status an seinen Vaterprozess liefern)
Was ist und macht der Scheduler?
Scheduling ist die globale Ablaufplanung der Prozesse / Threads
Scheduler kann verschiedene Strategien haben:
Stapelbetrieb - möglichst hoher Durchsatz (wenig Prozesswechsel)
Dialogbetrieb - möglichst kurze Antwortzeiten (viele Prozesswechsel)
Echtzeitbetrieb - garantierte Antwortzeiten
Was ist und macht der Dispatcher?
Kümmert sich um Prozesswechsel
Ändert den Zustand des Prozesses
Reiht Prozesse in Warteschlange ein
Sucht nächsten Prozess
Startet Prozess
Welche Zustände können Threads annehmen?
Unstarted
Running
Stopped
Suspended
Blocked
Was sind kritische Bereiche?
Kritische Bereiche (Critical Sections) sind Bereiche wo auf den gemeinsamen Speicher zugegriffen wird, wo nicht mehr als nur ein Thread auf diesen Bereich gleichzeitig zugreifen darf
Wie kann man einen gelockten Zugriff in kritischen Bereichen garantieren?
Konzept von Monitoren anwenden - man verwendet ein LockObjekt (muss am Heap liegen), welches verhindert, dass andere Threads auf den Bereich zugreifen dürfen, solange ein anderer Thread in diesem Bereich ist
lock(_lockObject)
{
Console.Write(“Hello”);
Thread.Sleep(1000);
Console.Write(“I just woke up”);
}
Was sind Monitore (in Bezug auf Multithreading)? Welche Methoden bieten diese an?
Monitore sind nichts anderes als Objekte - Monitore stellen sicher, dass nur ein Prozess zu einem Zeitpunkt seine Prozeduren (Funktionen benutzt
Methoden:
Enter, TryEnter: markieren den Beginn eines kritischen Bereichs - kein andere THread kann die Sektion betreten
Wait: Freigeben von einem Lock und erlaubt anderen Threads das Locken und Zugreifen auf das Objekt (Calling Threads warten bis ein Thread auf das Objekt zugreifen möchte, Pulse Signale werden verwendet, um wartende Threads über Änderungen am Objekt-State zu benachrichtigen)
Pulse, PulseAll: signalisieren, reagiere auf bestimmtes Objekt -> Signal senden zu wartenden Threads
Exit: gibt einen exklusiven Lock frei vom spezifizierten Objekt (Ende eines kritischen Bereichs)
Elegantere Methoden: Monitor.Enter(lock) und Monitor.Exit(lock) mit try-finally Block
Welche Bedingungen müssen für einen Deadlock bestehen?
1) No Preemption - geteilte Ressourcen werden ausschließlich durch die Prozesse selbst freigegeben
2) Hold and Wait - Prozesse fordern geteilte Ressourcen an un dbehalten aber zugleich den Zugriff auf andere
3) Mutual Exclusion - Zugriff auf geteilte Ressourcen ist exklusiv
4) Circular Wait - Mindestens zwei Prozesse besitzen bezüglich der geteilten Ressourcen eine zirkuläre Abhängigkeit
Sobald eine dieser Bedingungen nicht gilt, gibt es einen Weg, den Deadlock aufzulösen
Was ist ein Mutex? Welche Operationen bieten Mutex?
Mutex sind prozessübergreifend und die Abkürzung für Mutual Exclusion (wechselseitiger Ausschluss)
Ein Mutex verhält sich wie ein Lock, nur, dass ein Mutex die Verwendung über mehrere Prozesse hinweg erlaubt (auch 50x langsamer als lock())
Operationen:
WaitOne() - sperrt ein Synchronisierungsobjekt, ein Timeout kann angegeben werden
ReleaseMutex() - entsperrt das Synchronisierungsobjekt (Mutex kann nur von den Threads freigegeben werden, der ihn erhalten hat)
Was ist eine Semaphore?
Eine Semaphore ist eine Datenstruktur, die aus einer Ganzzahl und den Nutzungsoperationen P (Reservieren / Probieren) und V (Freigeben) besteht
Semaphoren eigenen sich insbesonders zur Verwaltung beschränkter (zählbarere) Ressourcen
P = ich will rein in den kritischen Bereich
V = ich will raus aus dem kritischen Bereich
Was unterscheidet Semaphoren von einem Monitor?
Semaphoren erlauben mehr als einem Thread den Zutritt zu einem kritischen Bereich
Was ist das Erzeuger / Verbraucher Problem? Wie kann dieses gelöst werden?
Ein Prozess erzeugt Daten und ein anderer verbraucht die Daten, gekoppelt über einen gemeinsamen Puffer - Erzeuger darf nicht in vollen Puffer schreiben und Verbraucher darf nicht aus leerem Puffer lesen
Man benötigt drei Semaphoren:
Mutex-Semaphore, die mit 1 initialisiert wird (für wechselseitigen Ausschluss)
Empty-Semaphore, die die Anzahl der leeren Slots im Puffer mitzählt (mit n initialisieren)
Full-Semaphore, die die Anzahl der vollen Slots mitzählt (mit 0 initialisieren)
Producer:
do{
//produce an item
wait(empty);
wait(mutex);
//place in buffer
signal(mutex);
signal(full);
}while(true)
Consumer:
do{
wait(full);
wait(mutex);
// consume item from buffer
signal(mutex);
signal(empty);
}while(true)
Wie funktionieren Semaphoren grundsätzlich?
Initialisierung: Semaphore semaphore = new Semaphore(2, 3);
2 = Startwert der Semaphore, 3 = Maximalwert
WaitOne() -> P
Wenn der Wert der Semaphore größer als 0, darf der Thread in den kritischen Bereich (Wert–)
Release() -> V
Thread verlässt den kritischen Bereich (Wert++)
Was ist eine binäre Semaphore?
Eine Semaphore, die mit 1 initialisiert wird und nur die Werte 0 oder 1 annehmen kann (Mutex)
Was sind Threadpools? Wofür werden diese verwendet?
Beim Start eines Threads müssen Datenstrukturen vorbereitet werde + 1 MB pro Thread –> Threadpools kümmern sich darum, dass Threads nicht erzeugt und beendet werden müssen - wenn ein Thread gestartet werden soll, wird dieser aus dem Pool entnommen und wenn dieser fertig ist, geht der Thread wieder zurück in den Pool
Was sind Tasks in C#?
Ein Thread, der automatisch aus einem Threadpool genommen wird - Tasks können aneinandergekettet werden
Was sind RPCs?
Aufrufender Prozess und aufgerufene Prozess laufen auf verschiedenen Computern (Hosts) - Aufruf- und Ergebnisparameter müssen in Nachrichten verpackt und über das Netzwerk übertragen werden (Stub und Skeleton - automatisch generierter Code)
Welche Aufrufparameter gibt es bei RPC?
Werteparameter (call-by-value) - der Parameterwert wird vom Klient als Kopie an den Server gesendet
Referenzparameter (call-by-reference) - am Server ausgeführte Änderungen würden nur am Original und nicht der Kopie stattfinden - macht aber keinen Sinn, da verschiedene Systeme
Was sind Stub und Skeleton?
= Codemodule, die alle notwendigen Funktionen kapseln, um einen lokalen Aufruf an einem entfernten Rechner zu übermitteln und Daten zu empfangen; Stub und Skeleton übernehmen das “einpacken” der Nachricht
Welche Fehlersemantiken können bei RPC Aufrufen auftreten?
Maybe: Wir machen den Aufruf, egal ob es ankommt oder nicht (Verwendung bei Loggings oder Warning)
At-least-once: Mindestens einmalige Ausführung (nur bei idempotenten Operation - Operationen, die bei mehrfacher Anwendung nicht das Ergebnis verändern) -> Verwendung bei Berechnungen
At-most-once: Erkennung und Löscung von Duplikaten - Ausführung nur, wenn keine Rechnerausfälle vorliegen
Exactly-once: Auführung genau einmal
Was ist gRPC?
gRPC ist ein high-performance Framework von Google und bietet Services an - wir definieren ein Service (Bibliothek) und ermöglichen den Aufruf von diesen Methoden
Was sind Remote Method Invocations (RMI)?
Objekte kapseln Methoden und Daten - Zugriff auf das Objekt ist durch dessen Schnittstelle geregelt - ermöglicht das Platzieren von einer Schnittstelle auf einem Rechner, während das Objekt auf einem anderen Rechner liegt - der Client Stub heißt in diesem Fall Proxy (Man in the Middle) und nimmt den Remote Aufruf entgegen
RMIs erlauben Kommunikation zwischen weit entfernten Objekten
Was ist ein entferntes Objekt (remote Object)?
Ein entferntes Objekt ist auf einem anderen Rechner (Adressraum) instanziiert - Zugriff auf das Objekt nur über Interface (Schnittstelle) möglich - der im Objekt gekapselte Zustand liegt am Server und ist nicht verteilt (bei RMI liegen Remote-Objekte also am Server)
Was ist der Unterschied zwischen RPC und RMI?
RPC erlaubt primitve Datentypen und structs als Parameer, RMI erlaubt Objekte als Parameter
RPC Systeme codieren Daten binär (serialisieren von Objekten)
RMI kapseln Services in Service Oriented Architectures (SOA)!