Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Allgemein:

Allgemein:

Prüfer: Professor Philippsen, Beisitzer: Patrick Kreutzer, Marius Kamp Die Beisitzer haben alle Fragen gestellt, Philippsen hat nur mitgeschrieben, nichts weiter gesagt. Insgesamt eine lockere und gute Athmosphäre. Es kamen keine wirklich überraschenden Fragen, es waren nie wirklich tiefe Details gefragt, ein guter Überblick über die Themen war eher wichtig.

  • F: Frage (einer der Beisitzer)
  • A: Antwort

Teil 1, Fragen zum Blockpraktikum und JIT:

  • F: Was ist eine Virtuelle Maschine?
  • A: Zwischencodedefinition und Abbildung auf niedrigere Ebene
Lader, Interpreter:
  • F: Was tut der Loader?
  • A: Lädt Programm aus Datei, löst Namen etc. auf
  • F: Was kommt danach?
  • A: Interpreter, dann eine kurze Erklärung darüber wie der Interpreter funktioniert (Schleife, switch, …)
  • A: Vorteile und Nachteile der einfachen Interpretation erklärt.
  • F: Woher kommen denn die vielen Sprünge bei der Interpretation?
  • A: Schleife, Switch, Funktionsaufrufe
  • F: Und wenn man das schneller machen möchte?
  • A: Indirekt durchgefädelte Interpretation erklärt, warum das besser ist, Vor- und Nachteile erklärt
  • F: Noch schneller?
  • A: Vorübersetzung erklärt mit Vor- und Nachteilen (Speicher, Startzeit, weniger Sprünge)
JIT1:
  • F: Ok, als nächstes haben wir dann in JIT1 direkt übersetzt, was sind denn da die Probleme?
  • A: Codeerzeugung selber, Trampolinfunktion erklärt (was tut sie, wie funktioniert sie)
  • F: Wie könnte man die Trampolinfunktion schneller machen?
  • A: Teilweises einbetten der Trampolinfunktion in den Aufrufer
  • F: Wie würde man denn in der Trampolinfunktion herausfinden welche Funktion man noch optimieren muss?
  • A: Profiling, entweder Zählen oder Sampling
  • F: Wann funktioniert denn Sampling und wann nicht?
  • A: Im Interpreter funktioniert Sampling nicht
  • F: Warum?
  • A: Man sieht nur die Interpreterfunktion
JIT2:
  • F: Was haben wir dann bei JIT2 gemacht?
  • A: Registervergabe für die Instruktionen
  • F: Wie?
  • A: Erst Berechnung der starken Zusammenhangskomponenten (Algorithmus nicht erklärt).
  • F: Worauf?
  • A: Auf dem Kontrollflussgraph
  • F: Warum nicht direkt auf den Instruktionen selber?
  • A: Instruktionen sind nicht sortiert, weiter oben könnten welche stehen die erst von unten angesprungen werden mit Rücksprung
  • F: Was machen wir dann mit den Zusammenhangskomponenten?
  • A: Lebensspannen von erster bis zu letzter Verwendung in den topologisch sortierten Zusammenhangskomponenten. Linear Scan erklärt.
  • F: Wieso als Heuristik den aus der Aktivliste rauswerfen der das späteste Ende der Lebensspanne hat?
  • A: Hat die meisten Kollisionen mit anderen Lebensspannen
  • F: Wie gut ist die Heuristik, gibt es bessere?
  • A: Nicht optimal, z.B. Variablen in Schleifen sollten bevorzugt werden für Register
JIT3:
  • F: Inlining, wie machen wir das?
  • A: auf Zwischencodebene, da müssen keine Variablen etc. umbenannt werden, auf Assemblerebene schwieriger wegen unterschiedlich langen Instruktionen.
  • F: Und wie führen wir das dann durch?
  • A: Argumente moven, Variablenindizes erhöhen, bei returns move und jump einfügen, alle Sprungziele entsprechend anpassen …
Sonstiges:
  • F: Sagen wir wir haben eine Funktion die wir noch optimieren wollen, die aber schon läuft, was tun wir?
  • A: On stack replacement, kurz erklärt
  • F: Was müssen wir dabei beachten?
  • A: Kann man nicht überall machen, wähle Definierte Punkte (z.B. Rücksprünge), an denen die Optimierungen keine Probleme bereiten …

Teil 2: Allgemeine Fragen zu der Vorlesung

Exceptions:
  • F: Was gibt es für Möglichkeiten mit Exceptions umzugehen?
  • A: stack cutting, stack unrolling, beide Verfahren kurz erklärt mit Vor- und Nachteilen
  • F: Warum wollen wir denn im Nicht-Exception Fall schnell sein und dafür bei einer Exception potentiell langsam?
  • A: Optimalerweise ist Exceptionfall selten
  • F: Was machen denn die Exceptions mit der SSA Form?
  • A: Wegen den Exceptions müsste man sehr viele Move Instruktionen erzeugen, da SSA Phi Instruktionen viele Argumente hätten. Stattdessen schreibt man Adapter für das Exceptionhandling, der die Moves macht, sodass man keine weiteren Moves im Ausnahmefreien Fall machen muss.
  • F: Und was ist mit den Optimierungen?
  • A: Erkläre faktorisierten KFG, zeige an Beispiel dass der normale Fixpunktalgorithmus hier kaputt geht und dass man ihn anpassen muss.
Wettlaufsituationen:
  • F: Was könnte man tun um Wettlaufsituationen zu erkennen oder zu verhindern?
  • A: Erkläre Locksetanalyse (hier war es wichtig zu sagen dass nicht immer exakt die gleichen Locks für eine Variable gehalten werden müssen, aber dass die Schnittmenge aller Locks nicht leer sein darf → es gibt ein Lock das immer für die Variable gehalten wird)
  • A: Erkläre kurz Happened Before Analyse (nicht auf Thread Sanitizer eingegange, nur sehr grob erklärt → strikte partielle Ordnung, Elemente die nicht in Relation stehen haben potentiell Wettlaufsituation bei Zugriff auf die gleiche Variable)
  • A: Erkläre kurz Ablaufplanerzeugung mit SMT Solver
  • F: Aber es gibt ja jetzt auch noch statische Verfahren (?)
  • A: Richtig, mit Typsystem (kurze Erklärung dazu)
Statische Ausführung:
  • F: Stell dir vor du arbeitest in einer Firma und die anderen Programmierer machen zu viele ArrayIndexOutOfBoundsExceptions, der Boss sagt dass du die fixen sollst. Was tust du?
  • A: Finde mögliche AIOBE durch statische Analyse.
  • A: Erkläre kurz abstrakte Interpretation mit Intervallen
  • A: Erkläre kurz symbolische Ausführung
  • F: Wie konstruiert man die Pfadbedingung denn?
  • A: Kurze erklärung dazu
  • F: Aber wieso so kompliziert, die Variablen haben doch nur einen Wert, es wir doch am Ende nur ein Pfad durchlaufen?
  • A: Symbolische Ausführung durchläuft nicht für konkreten Wert, sondern gewissermaßen für alle möglichen Werte gleichzeitig.
  • F: Jetzt sagt der Boss aber dass die Verfahren entweder immer zu viele false positives haben oder zu viele false negatives. Er will dass du exakt die falschen Stellen findest und nur die.
  • A: Geht nicht, unentscheidbar wegen Halteproblem
  • F: Wo konkret?
  • A: Bei Schleifen und Rekursion
  • F: Bei Schleifen immer?
  • A: Wenn die Iterationszahl klar ist ist es kein Problem, nur wenn eine komplexe Schleifenbedingung vorhanden ist, dann müsste man eine Schleifeninvariante konstruieren
Funktionale Sprachen:
  • F: Bei funktionalen Sprachen muss man oft den Typen nicht angeben, wie handelt man dass denn?
  • A: Erkläre kurz Typinferenz und wie man die durchführen würde (nicht an einem Beispiel)
  • F: Bei Funktionsaufrufen gibt es jetzt zwei Möglichkeiten (?)
  • A: Habe erst mal kurz was zu unterversorgten Funktionen und Partial Application Pointern erzählt, der Prüfer wollte aber den Unterschied zwischen Eval/Apply und Push/Enter wissen. Habe dann kurz erklärt wie die beiden gehen
  • F: Und ist eines davon jetzt besser als das andere?
  • A: Nein, aber Eval/Apply ist unter Umständen einfacher zu implementieren
  • F: Was ist denn Striktheitsanalyse?
  • A: Kurz Striktheitsanalyse erklärt, wozu man die braucht, was Striktheit in einem Argument bedeutet

Ergebnis

Am Ende die klassische Frage, was ich denn als Ergebnis erwarte. Ergebnis: sehr gut