Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 4 » Concurrent Systems Exam 2021-04-09   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:hauptstudium:ls4:cs-2021-04-09 [09.04.2021 15:58] – angelegt Marcel[Inf]pruefungen:hauptstudium:ls4:cs-2021-04-09 [09.04.2021 20:13] (aktuell) – Marcel[Inf]
Zeile 1: Zeile 1:
-====== Concurrent Systems Prüfung 2021-04-09 ======+====== Concurrent Systems Exam 2021-04-09 ======
  
 {{indexmenu>:pruefungen:hauptstudium:ls4:cs-2021-04-09#1|navbar}} {{indexmenu>:pruefungen:hauptstudium:ls4:cs-2021-04-09#1|navbar}}
 +
 +<note tip>My own summary that I have created for exam preparation is available at https://github.com/ComFreek/uni-concurrent-systems-summary/. Pull requests welcome!</note>
  
 ===== Meta Information ===== ===== Meta Information =====
Zeile 12: Zeile 14:
     * during the semester: attending every lecture, active collaboration in exercise briefings     * during the semester: attending every lecture, active collaboration in exercise briefings
     * three (non full-time) weeks of preparation before the exam     * three (non full-time) weeks of preparation before the exam
- * I have gone through the slides non-linearly, starting with non-blocking synchronization. I really recommend reading the slides non-linearly: the introductory slide decks introduce careful terminology that is neither important for general understanding nor for the exam. E.g. it is not important to get the difference between "concurrent", "simultaneous", and "parallel". +    * I have gone through the slides non-linearly, starting with non-blocking synchronization. I really recommend reading the slides non-linearly: the introductory slide decks introduce careful terminology that is neither important for general understanding nor for the exam. E.g. it is not important to get the difference between "concurrent", "simultaneous", and "parallel". 
- * I have created a summary of every slide deck. E.g. for the slide deck on locks, I had a collection of code snippets for all the variants of locks together with comments of their (dis)advantages. +    * I have created a summary of every slide deck. E.g. for the slide deck on locks, I had a collection of code snippets for all the variants of locks together with comments of their (dis)advantages. 
- * For selected terms of the lecture, I have consulted the glossary, which turned out to be _immensely helpful_.+    * For selected terms of the lecture, I have consulted [[https://www4.cs.fau.de/DE/~wosch/glossar.pdf|wosch's glossary]], which turned out to be _immensely helpful_. 
 +    * After all, except for the MCS lock, the content of the exercises wasn't super exam-relevant. I have only read through the notes that I have created during the exercise debriefings (which e.g. said "ticket locks perform bad when #threads > #cores"), but even that turned out to not be necessary during the exam. 
 +    * I think the exercises teaches you _a lot_ of things, but once you've done them during the semester, there's isn't necessarily a point in revising them for the exam. (And e.g. the relevant things like the lock implementations are featured on the slides, too. So if you stick to the slides, you get all the important things anyway in my opinion.)
   * Evaluation   * Evaluation
     * The exam is fair! You can achieve 1.0 even with errors.     * The exam is fair! You can achieve 1.0 even with errors.
Zeile 21: Zeile 25:
 ===== Prüfung ===== ===== Prüfung =====
  
-=== Einführung ===+Das untenstehende Protokoll sollte relativ vollständig sein. Ich habe es "didaktisch komprimiert", d.h. z.B. Hänger von mir ausgelassen.
  
-* Was ist Nebenläufigkeit?+==== Einführung ==== 
 + 
 +  * Was ist Nebenläufigkeit?
  
 > Zwei Ereignisse nebenläufig, wenn keines Ursache oder Wirkung des anderen. > Zwei Ereignisse nebenläufig, wenn keines Ursache oder Wirkung des anderen.
Zeile 30: Zeile 36:
 > Vergleichbare Elemente müssen zur Laufzeit zwingend sequentialisiert werden; dafür gibt es verschiedene Methoden. > Vergleichbare Elemente müssen zur Laufzeit zwingend sequentialisiert werden; dafür gibt es verschiedene Methoden.
  
-* Kann es denn zwei Ereignisse geben, die zwar nebenläufig sind, aber trotzdem auf unterer Ebene sequentialisiert werden müssen?+  * Kann es denn zwei Ereignisse geben, die zwar nebenläufig sind, aber trotzdem auf unterer Ebene sequentialisiert werden müssen?
  
 > Ja, beim Übersetzen nach tieferen Ebenen können vorher nebenläufige Ereignisse nun gekoppelt in Erscheinung treten. > Ja, beim Übersetzen nach tieferen Ebenen können vorher nebenläufige Ereignisse nun gekoppelt in Erscheinung treten.
 > Als Beispiel betrachte zwei Programme, deren Prozesse zur Laufzeit beide auf den Speicher zugreifen. Diese Zugriffe können dann durch den Bus sequentialisiert werden. > Als Beispiel betrachte zwei Programme, deren Prozesse zur Laufzeit beide auf den Speicher zugreifen. Diese Zugriffe können dann durch den Bus sequentialisiert werden.
  
-=== Blockierende Synchronisation, Verklemmungen ===+==== Blockierende Synchronisation, Verklemmungen ====
  
-* Was ist blockierende Synchronisation?+  * Was ist blockierende Synchronisation?
  
 > Prozesse geben Kontrolle über Geschehen ab; wechseln in Zustand "blockiert". > Prozesse geben Kontrolle über Geschehen ab; wechseln in Zustand "blockiert".
Zeile 43: Zeile 49:
 > * Beispiel 2: Programm nutzt in Anwendungssoftware kodierte Umlaufsperren um zu blockieren. => Zur Ausführung gibt der Anwendungsprozess die Kontrolle ab, der kernel-level Prozess aber nicht. > * Beispiel 2: Programm nutzt in Anwendungssoftware kodierte Umlaufsperren um zu blockieren. => Zur Ausführung gibt der Anwendungsprozess die Kontrolle ab, der kernel-level Prozess aber nicht.
  
-* Nachteile von blockierender Synchronisation?+  * Was für Techniken gibt es für blockierende Synchronisation? 
 + 
 +> Sperren, Semaphore, Mutexe 
 + 
 +  * Was ist der Unterschied zwischen Mutexe und Semaphore? 
 + 
 +> Mutexe sind Methoden zur Sicherstellung wechselseitigen Ausschlusses [siehe Anhang des Foliensatzes zu Mutexe zum Thema Mutexe vs. Mutexentitäten]. Mutexentitäten sind Objekte mit einer `acquire` und einer `release`, wobei `release` überprüft, ob der aufrufende Prozess auch der war, der `acquire` vorher vollendet hatte. Allgemeine Semaphore können für unilaterale Synchronisation eingesetzt werden, typischerweies innerhalb des Produzenten-Verbraucher-Musters. Hierbei kann der Produzent nach dem Produzieren neuer Daten das Signal, dass neue Daten verfügbar sind, absetzen, indem er `V` aufruft. Und der Konsument kann auf den Erhalt dieses Signals synchronisieren, indem er `P` aufruft. Spezialisiert mensch den allgemeinen Semaphor auf den Wertebereich `{0, 1}` zu einem binären Semaphor und fügt einen Autorisierungsprüfung um `V` herum hinzu, so erhält mensch eine Mutexentität. 
 + 
 +  * Nachteile von blockierender Synchronisation?
  
 > * Verklemmungen möglich > * Verklemmungen möglich
 > * je nach Sofware sind Ein- und Austrittsprotokolle von Sperren unverhältnismäßig teuer im Vergleich zu dem kritischen Abschnitt, den sie schützen sollen > * je nach Sofware sind Ein- und Austrittsprotokolle von Sperren unverhältnismäßig teuer im Vergleich zu dem kritischen Abschnitt, den sie schützen sollen
  
-* Was sind die klassischen 4 Bedingungen für Verklemmungen?+  * Was sind die klassischen 4 Bedingungen für Verklemmungen?
  
 > (i) Anforderung von Ressourcen mit wechselseitigem Ausschluss, (ii) iterative Anforderung dieser, (iii) keine Präemption dieser, (iv) zirkuläres Warten > (i) Anforderung von Ressourcen mit wechselseitigem Ausschluss, (ii) iterative Anforderung dieser, (iii) keine Präemption dieser, (iv) zirkuläres Warten
  
-* Was ist Verklemmungsvermeidung?+  * Was ist Verklemmungsvermeidung?
  
 > Zur Laufzeit überprüfen wir bei jeder Ressourcenanforderung, ob damit ein unsicherer Zustand eingenommen werden würde -- unter Ausnutzung von a priori Informationen über die Programmstruktur. Ein unsicherer Zustand ist ein Zustand, aus dem -- egal mit welcher zukünftiger Planerstrategie -- immer eine Verklemunng resultieren wird. > Zur Laufzeit überprüfen wir bei jeder Ressourcenanforderung, ob damit ein unsicherer Zustand eingenommen werden würde -- unter Ausnutzung von a priori Informationen über die Programmstruktur. Ein unsicherer Zustand ist ein Zustand, aus dem -- egal mit welcher zukünftiger Planerstrategie -- immer eine Verklemunng resultieren wird.
 > Solche Anforderungen lehnen wir ab oder führen den anfordernden Prozess dem long-term-scheduling zu. > Solche Anforderungen lehnen wir ab oder führen den anfordernden Prozess dem long-term-scheduling zu.
  
-* Welche der 4 Bedingungen entkräftet Verklemmungsvermeidung?+  * Welche der 4 Bedingungen entkräftet Verklemmungsvermeidung?
  
-Nur (iv) zirkuläres Warten.+> Nur (iv) zirkuläres Warten.
  
-* Was ist der Unterschied zwischen Verklemmungsvorbeugung und Verklemmungsvermeidung?+  * Was ist der Unterschied zwischen Verklemmungsvorbeugung und Verklemmungsvermeidung?
  
 > Vorbeugung ist ein konstruktiver Ansatz, um eine der Bedingungen zu entkräften; Vermreidung ein analytischer Ansatz, um zur Laufzeit unsichere Zustände zu vermeiden. > Vorbeugung ist ein konstruktiver Ansatz, um eine der Bedingungen zu entkräften; Vermreidung ein analytischer Ansatz, um zur Laufzeit unsichere Zustände zu vermeiden.
  
-* Was gibt es neben den beiden noch?+  * Was gibt es neben den beiden noch?
  
-Wir können die Flinte ins Korn werfen und Verklemmungserkennung betreiben -- d.h. reagieren wenn es eigentlich schon zu spät ist.+> Wir können die Flinte ins Korn werfen und Verklemmungserkennung betreiben -- d.h. reagieren wenn es eigentlich schon zu spät ist.
  
-* Wie genau funktioniert Verklemmungserkennung? Was muss das BS alles machen dafür?+  * Wie genau funktioniert Verklemmungserkennung? Was muss das BS alles machen dafür?
  
 > Jede Ressourcenanforderung und -freigabe mitprotokollieren in einem Graphen. Dann regelmäßig (z. B. wenn Systemdurchsatz weniger wird oder soagr exzessiv bei jeder Ressourcenanforderung) überprüfen, ob dieser Graph einen Zyklus enthält. > Jede Ressourcenanforderung und -freigabe mitprotokollieren in einem Graphen. Dann regelmäßig (z. B. wenn Systemdurchsatz weniger wird oder soagr exzessiv bei jeder Ressourcenanforderung) überprüfen, ob dieser Graph einen Zyklus enthält.
Zeile 76: Zeile 90:
 > Bei general-purpose BS können wir eigentlich nur Prozesse terminieren (unschön). > Bei general-purpose BS können wir eigentlich nur Prozesse terminieren (unschön).
  
-=== Umlaufsperren ===+==== Umlaufsperren ====
  
-* Was ist der Unterschied zwischen einem Ticketlock und einem TAS-basierten Lock?+  * Was ist der Unterschied zwischen einem Ticketlock und einem TAS-basierten Lock?
  
 > Ticketlock ist fair/verhungerungsfrei, da first-come-first-serve. > Ticketlock ist fair/verhungerungsfrei, da first-come-first-serve.
 > Außerdem weniger Bussperren. > Außerdem weniger Bussperren.
  
-* Wie viele Bussperren haben denn beide Sperrvarianten genau?+  * Wie viele Bussperren haben denn beide Sperrvarianten genau?
  
 > Ticketlock hat im `lock()` genau eine (fetch-and-add zum Ziehen einer Wartemarke); TAS/CAS-basierte Locks haben unbegrenzt viele. > Ticketlock hat im `lock()` genau eine (fetch-and-add zum Ziehen einer Wartemarke); TAS/CAS-basierte Locks haben unbegrenzt viele.
  
-* Im Ticketlock spinnen wir nur auf einer Variable, quasi spin-on-read, ohne atomare Befehlssatzbefehle. Hat das denn auch irgendwelche Nachteile?+  * Im Ticketlock spinnen wir nur auf einer Variable, quasi spin-on-read, ohne atomare Befehlssatzbefehle. Hat das denn auch irgendwelche Nachteile?
  
 > Ja, angenommen 100 Prozesse konkurrieren im Eintrittsprotokoll, der 101-te Prozess hält das Ticketlock und macht dann ein `unlock()`. Das führt dann im Extremfall zu 100 Cache update/invalidate Requests mit nachfolgenden 100 (ggf. sequentialisierten) Ladeanfragen über den Bus. > Ja, angenommen 100 Prozesse konkurrieren im Eintrittsprotokoll, der 101-te Prozess hält das Ticketlock und macht dann ein `unlock()`. Das führt dann im Extremfall zu 100 Cache update/invalidate Requests mit nachfolgenden 100 (ggf. sequentialisierten) Ladeanfragen über den Bus.
  
-* Wie habt ihr das Ticketlock in der Übung dann verbessert?+  * Wie habt ihr das Ticketlock in der Übung dann verbessert? (hint: MCS lock)
  
 > Wir haben den Zähler verallgemeinert zur einer Warteschlange. Jeder Prozess korrespondiert zu einem Eintrag in dieser Warteschlange und jeder Eintrag besitzt zwei Felder: einen next-Zeiger und eine boolsche Variable zum Spinnen. > Wir haben den Zähler verallgemeinert zur einer Warteschlange. Jeder Prozess korrespondiert zu einem Eintrag in dieser Warteschlange und jeder Eintrag besitzt zwei Felder: einen next-Zeiger und eine boolsche Variable zum Spinnen.
Zeile 97: Zeile 111:
 > Und wenn ein Prozess `unlock()` ausführt (also Kopf der Warteschlange war), so invalidiert dieser nur die boolsche Variable desjenigen Prozesses, der nach ihm folgt (also nächster innerhalb der Warteschlang war). > Und wenn ein Prozess `unlock()` ausführt (also Kopf der Warteschlange war), so invalidiert dieser nur die boolsche Variable desjenigen Prozesses, der nach ihm folgt (also nächster innerhalb der Warteschlang war).
  
-* Wie kann mensch dann diese Warteschlange, also eine dynamische Datenstruktur, implementieren? +  * Wie kann mensch dann diese Warteschlange, also eine dynamische Datenstruktur, implementieren? Warum wäre es keine gute Idee, ein Ticketlock derart zu implementieren, dass es seine interne Warteschlange mittels einer anderen Umlaufsperre blockierend synchronisiert?
-* Warum ist es keine gute Idee, ein Ticketlock zu implementieren, was intern seine Warteschlange mittels einer anderen Umlaufsperre blockierend synchronisiert?+
  
 > Das Ticketlock ja u.a. deswegen schick ist, weil es zu keinen Buslock Bursts führt, so wie bei TAS/CAS-basierten Umlaufsperren. > Das Ticketlock ja u.a. deswegen schick ist, weil es zu keinen Buslock Bursts führt, so wie bei TAS/CAS-basierten Umlaufsperren.
Zeile 105: Zeile 118:
 > (Hier wollte wosch das recht genau wissen, obige Antwort ist die Zusammenstellung dessen, was er und ich dann in der Prüfung "erarbeitet" haben. Es lohnt sich wohl sich das nochmal anzusehen und womöglich präziser auszuformulieren.) > (Hier wollte wosch das recht genau wissen, obige Antwort ist die Zusammenstellung dessen, was er und ich dann in der Prüfung "erarbeitet" haben. Es lohnt sich wohl sich das nochmal anzusehen und womöglich präziser auszuformulieren.)
  
-=== Nichtblockierende Synchronisation ===+==== Nichtblockierende Synchronisation ====
  
-* Wie könnte mensch die Warteschlange also sonst implementieren?+  * Wie könnte mensch die Warteschlange also sonst implementieren?
  
 > nichtblockierend, sogar wartefrei. > nichtblockierend, sogar wartefrei.
  
-* Habt ihr da CAS benutzt? Gab es deswegen ein ABA-Problem?+  * Habt ihr da CAS benutzt? Gab es deswegen ein ABA-Problem?
  
 > Ich glaube wir haben nur im `unlock()` ein CAS benutzt. Nichtdestrotrotz war unsere Implementierung nicht ABA-kritisch -- gegeben durch das spezielle Zugriffsmuster, das wir hatten. > Ich glaube wir haben nur im `unlock()` ein CAS benutzt. Nichtdestrotrotz war unsere Implementierung nicht ABA-kritisch -- gegeben durch das spezielle Zugriffsmuster, das wir hatten.
 > (Nicht sicher, ob das tatsächlich stimmt -- aber wosch wollte nur darauf hinaus, dass Nutzung von CAS manchmal ABA-kritisch sein kann und manchmal es nicht ist.) > (Nicht sicher, ob das tatsächlich stimmt -- aber wosch wollte nur darauf hinaus, dass Nutzung von CAS manchmal ABA-kritisch sein kann und manchmal es nicht ist.)
  
-* Wie kann mensch das ABA-Problem lösen?+  * Wie kann mensch das ABA-Problem lösen?
  
 > Getaggte Zeiger (aber unschön) oder -- wenn die CPU das unterstützt -- LoadLinked/Store Conditional (LL/SC). > Getaggte Zeiger (aber unschön) oder -- wenn die CPU das unterstützt -- LoadLinked/Store Conditional (LL/SC).
- +> 
-(Wir waren schon am Ende der Prüfung, daher hat diese kurze Antwort gereicht.)+> (Wir waren schon am Ende der Prüfung, daher hat diese kurze Antwort gereicht.)