CS 2019-03-25

Fach: Conncurrent Systems

Prüfer: Wosch

Beisitzer: Timo Hönig

Dauer: 30 min

Semester: WS 2018/19

Fragen sind so gut wie vollständig, mit Ausnahme von ein paar unwichtigen Fragen zwischendurch, die dann dazu dienten, auf die Antwort zu kommen.

Prüfer: Was ist Nebenläufigkeit?

Student: Wenn zwei Programme gleichzeitig ausgeführt werden

Prüfer: So was wie Gleichzeitigkeit gibt es ja eigentlich gar nicht (Er wollte darauf hinaus, dass gleichzeitige Ausführung nicht ausschlaggebend ist.)

Student: Also sie müssen auch noch Datenabhängigkeiten haben.

Prüfer: Naja, nicht so ganz. [hat auf die VL verwiesen, 2-6]

Student: [Fragender Blick]

Prüfer: Zwei Prozesse sind nebenläufig wenn sie unabhängig voneinander sind. Jetzt wo wir wissen, was Nebenläufigkeit ist: es kann ja jetzt sein, dass ein Programm auf einer höheren Abstraktionsebene nebenläufig ist, aber unten auf der Hardware nicht mehr. Wie kann das passieren?

Student: Z.B. bei Pseudo-Parallelität kann es sein, dass zwar die einzelnen Maschineninstruktionen sequentiell ausgeführt werden, aber der High-Level-Function-Call nicht.

Prüfer: Nein das meinte ich nicht.

[ Einiges Hin und Her ]

Prüfer: [Malt drei Kästchen hin; eines für Memory und jeweils eines für eine CPU, also zwei CPUs, ein Memory] Wie sind diese Komponenten denn verbunden?

Student: Durch einen BUS

Prüfer: Aha! Und was ist das Problem, wenn ZWEI CPUs über EINEN BUS kommunizieren, obwohl die ausgeführten Programme jeweils auf komplett unterschiedlichen Variablen im Memory arbeiten?

Student: Achso, naja, dann ist die Kommunikation effektiv serialisiert.

Prüfer: Ja genau, so kann es zu so einem Szenario kommen. Wir brauchen also Mechanismen, um damit klarzukommen. Was gibt es denn da so?

Student: Naja, da gibt es atomare Operationen wie TAS oder CAS.

Prüfer: Genau, und was kann man damit machen?

Student: Man kann zum Beispiel Mutual Exclusion bauen.

Prüfer: Und was will man damit schützen?

Student: Einen kritischen Abschnitt.

Prüfer: Ja genau. [Malt einen Zeitstrahl hin mit zwei Markern. Erklärt dass man beim ersten Marker in den kritischen Abschnitt eintritt, beim zweiten wieder aus. Zeigt auf den ersten Marker] Was ist denn jetzt das einfachste was man an dieser Stelle machen kann um Mutual Exclusion zu bauen?

Student: [TAS-Loop hingemalt]

Prüfer: Braucht man denn überhaupt zwingend eine atomare Operation um einen kritischen Abschnitt zu schützen?

Student: Naja, um Race-Conditions durch einen Read-Modify-Write-Zyklen zu vermeiden, braucht man in solchen Fällen immer atomare Operationen.

Prüfer: Naja, wenn ich jetzt so ein Schleifen-Konstrukt habe [Malt eine nicht-atomare schleife hin, die flag überprüft und setzt], dann stimmt das, da braucht man eine atomare Operation zwingend. Aber brauch ich denn unbedingt immer so einen Ansatz?

Student: [War ein bisschen verloren. Einiges Hin- und Her mit Wosch]

Prüfer: [Schreibt „Dekker“ hin?]

Student: Achso, ja bei Dekker fällt das weg, weil es eine Speziallösung für nur zwei Threads ist.

Prüfer: Naja, wie ist das denn bei dem Algorithmus von Dijkstra zur Synchronisierung?

Student: Weiß ich nicht auswendig

Prüfer: Der arbeitet auf N > 2 Threads und braucht auch keine atomare Operation. Also braucht man atomare Operationen zwingend für Synchronisation?

Student: Achso, ja dann wohl nicht.

Prüfer: Genau, man braucht sie nicht zwingend. Ich hab ja nicht nach den effizientesten Lösungen gefragt, sondern, ob man sie immer zwingend braucht. Jetzt gehen wir aber mal davon aus, wir haben so eine TAS-Loop. Ist das eine gute Lösung?

Student: Naja, TAS hat ein paar Probleme. Erstmal sind da schlechte Cache-Effekte. Das TAS setzt Variable bedingungslos und das sorgt für viele Cache-Invalidierungen

Prüfer: Und was gibt es noch für ein Problem?

Student: Access Contention: Viele verschiedene Threads führen gleichzeitig atomare Operation aus.

Prüfer: Was kann man denn gegen die Probleme von TAS tun?

Student: Also gegen die Cache-Effekte von TAS kann man CAS nutzen, das die Variable nur bedingt ändert. Die Access contention ist damit nicht gelöst. Da könnte man jetzt Spin-On-Read einsetzen. Aber auch spin-on-read löst das Problem nicht zufriedenstellend, wenn die konkurrierenden Prozesse im Gleichtakt arbeiten, da die atomare Operation dann immer auf denselben Takt fällt.

Prüfer: Naja, also vor allem ist es dann ein Problem, wenn die kritischen Abschnitte kurz sind. Warum?

Student: [?]

Prüfer: [Malt Operation i++ hin, umrahmt von lock() und unlock(), zeigt auf lock()] Wie lang bleibt denn ein Prozess da drin?

Student: Naja, so lange bis er halt durch kommt.

Prüfer: Was glauben sie denn wie lange das ungefähr dauert?

Student: Geht bei so kurzem kritischen Abschnitt vermutlich sehr schnell.

Prüfer: Genau - Und das sorgt für die hohe Access contention trotz spin-on-read. Gibt es jetzt noch was, das man dagegen tun kann?

Student: Ja, man kann Backoff-Verfahren einsetzen.

Prüfer: Was ist denn ein Backoff-Verfahren.

Student: Warteverhalten, wenn man nicht in den kritischen Abschnitt rein kommt.

Prüfer: Genau. Was ist denn ein gängiges Beispiel das auch oft verwendet wird?

Student: Man kann z.B. einen Counter shiften. Das wäre ein exponentieller Backoff

Prüfer: Kann man machen, meine ich aber jetzt nicht.

Student: Man könnte sich auch schlafen legen und aufwecken lassen.

Prüfer: Ja, das geht schon auch, aber da braucht man ja dann das Betriebssystem. Ich meine was anderes.

Student: Achso, man kann auch ein Ticket-Lock verwenden.

Prüfer: Ahh, genau, das ist ein Backoff-Verfahren! Was denn für eines?

Student: Ein inkrementelles.

Prüfer: Wieso inkrementell? Dauert die Wartezeit wohl immer länger je öfter man es versucht?

Student: Naja, nicht direkt.

Prüfer: Wovon ist die Wartezeit denn abhängig?

Student: Von der Anzahl an Threads, die warten.

Prüfer: Ja genau und dann ist das ein proportionales Backoff-Verfahren. Jetzt gibt es aber bei Ticket-Locks auch noch ein Problem. Welches denn?

Student: Eigentlich können da nur die globalen Variablen Probleme machen. Es gibt ja da auch wieder eine atomare Operation.

Prüfer: Ja, aber die ist ja nicht in der Schleife.

Student: Stimmt. Dann kann eigentlich nur der Lese-Zugriff auf die „current“-Variable ein Problem sein.

Prüfer: [War unzufrieden. Erklärt MCS-Verfahren und sagt, dass man das ja auch in der Übung implementiert hat (hat man aber nicht zwingend, war eine mögliche Implementierung von mehreren).]

Note: 2,7

Ich wusste dass es jetzt keine 1,0 wird, war aber überrascht dass es dann doch so schlecht ausgefallen ist. Wosch hat sich allerdings Zeit genommen, um mir das nachvollziehbar zu erklären.

Insgesamt war die Prüfungsatomsphäre sehr locker. Wosch hat fair geprüft. Bei mir hat er z.B. gemerkt, dass ich auf die Locks raus wollte und hat die Prüfung dann auch ein bisschen in die Richtung gelenkt, nachdem er den Teil zu Nebenläufigkeit und was sie ausmacht rum hatte.