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

Vorbereitung

  • Projektübung gemacht (ist nicht so wirklich gute Vorbereitung, aber sehr cool)
  • Während des Semesters alle Vorlesungen und Übungen besucht (Vorlesung war immer um 8, das war hart, aber lohnt sich, Philipsen hat einen schönen Vortragsstil)
  • Folien gelesen
  • Übungsfolien gelesen
  • Übungsaufgaben gemacht (alle zumindest gelesen, die zu den Verfahren gerechnet)
  • Mit meinem Übungspartner 3 Tage vor der Klausur angefangen, gegenseitig Prüfungsprotokolle durch zu gehen (dafür ist es gut, wenn man am selben Tag Prüfung hat)

Prüfung

  • P: Prüfer (Florian Mayer) und Beisitzer (Prof. Michael Philipsen)
  • I: Ich

Unspezifiziertes Verhalten

  • P: Was ist denn unspezifiziertes Verhalten?
  • I: Undefiniertes Verhalten erklärt (in Sprachspezifikation nicht definiert, Compiler ist da frei zu tun was auch immer er will)
  • P: Und das ist jetzt unspezifiziertes Verhalten?
  • I: Ups, das war undefiniertes Verhalten. Unspezifiziertes Verhalten erklärt (in Sprachspezifikation sind Möglichkeiten gegeben, Compiler darf beliebig, sogar undeterministisch, daraus wählen, selbst in einem Programm können verschiedene Möglichkeiten verwendet werden)

Funktionsaufrufe

  • P: gibt e2 Code mit Funktionen, die sich gegenseitig, aber nicht rekursiv aufrufen
func bar(p: int): int
    var l: int;
    l := foo(p);
    return l + p;
end
func foo(p: int): int
    return bazz() + quux();
end
func bazz(): int
    return 3;
end
func quux(): int
    return 2 * bazz();
end
  • P: Was fällt ihnen hier auf?
  • I: Die Funktionen rufen sich nicht rekursiv auf.
  • P: Was könnte man dann machen?
  • I: Statisch allozierte Aktivierungsrahmen.
  • P: Wie funktioniert das?
  • I: erklärt (Argument und lokale Variablen liegen in statisch alloziertem Speicher)
  • P: Wenn sich die jetzt rekursiv aufrufen würden, was würde dann passieren?
  • I: erklärt warum das nicht geht (bei rekursivem Aufruf würde man seine eigenen Argument überschreiben)
  • P: Was macht man stattdessen?
  • I: Aktivierungsrahmen auf dem Stack
  • I: Stackdiagramm gemalt, gleich mit Caller-/Callee-Save-Register (das wäre die nächste Frage gewesen, meinte P)
                      /- | ...                  |
                      |  | Lokale Variable 2    |
                      |  | Lokale Variable 1    |
                      |  | Callee-Save-Register |
  Aktivierungsrahmen  |  | Framepointer         | -> ab hier kümmert sich die aufgerufene Funktion
    der aufgerufenen <   | Rücksprungaddresse   | -> das kommt durch die Call Instruktion
            Funktion  |  | Argument 1           | -> bis hier kümmert sich die aufrufende Funktion
                      |  | Argument 2           |
                      |  | ...                  |
                      |  | Argument n           |
                      \_ | Caller-Save-Register |
                         |----------------------|
  Aktivierungsrahmen  /- | ...                  |
     der aufrufenden <   | ...                  |
            Funktion  \_ | ...                  |
                         | ...                  |
  • P: Warum teilt man die Register in Caller- und Callee-Save ein, und möchte man Register welcher Sorte verwenden?
  • I: Bei kleinen funktionen nur Caller-Save-Register? (hier war ich etwas unsicher)
  • P: Was sind kleine Funktionen?
  • I: Ich hatte keine Antwort, habe etwas drumrum geredet.
  • P: Können die andere Funktionen aufrufen?
  • I: hier ist es mir eingefallen (Funktionen die keine anderen Funktionen aufrufen (sog. Blattfunktionen), können, wenn sie nur Caller-Save-Register verwenden, auf den Callee-Save Schritt verzichten)
  • P: Braucht man den Framepointer immer?
  • I: Nein, es geht auch ohne, aber Stackpointer-relative Addressierung ist komplizierter und fehleranfälliger.
  • P: Wofür braucht man den Framepointer noch?
  • I: hier ist mich nichts mehr eingefallen
  • P: Denk mal an das allerletzte Kapitel der Vorlesung.
  • I: Instruktionsanordnung? Ah, Debugging! Mit dem Framepointern, die auf den Stack gesichert werden, kann der Debugger alle Aktivierungsrahmen des Callstacks ablaufen, und lokale Variablen und Parameter anschauen.

Geschachtelte Funktionen

  • P: gibt Codeschnipsel mit geschachtelten Funktionen
func foo(p: int): int
    func bar(q: int): int
        func bazz(): int
            return p * 2;
        end
        return bazz() + 2;
    end
    func quux(): int
        return bar(42) + 69;
    end
    return quux() + bar();
end
  • P: Was ist denn das besondere an diesem Codebeispiel?
  • I: geschachtelte Funktionen, darauf hingewiesen, das innere Funktionen auf Variablen und Parameter äußerer Funktionen zugreifen können
  • P: Und wie könnte man das umsetzen?
  • I: SV-Verweis, um auf Aktivierungsrahmen von textuell umschließender Funktion zuzugreifen
  • P: Warum SV-Verweis, das ist doch immer der umschließende Funktionsrahmen?
  • I: Nein, z.B. im Beispiel ruft quux bar auf, aber die umschließende Funktion von bar ist foo.

Namens- und Typanalyse bei objektorientierten Sprachen

  • P: gibt Codeschnipsel mit Klassen und Einfachvererbung
class Widget
    var i: int;
end
class Button : Widget
    var text: String;

    func foo(): int
        return i * 2;
    end
end

func main(): int
    var w: Widget;
    w := new Button();
    w.foo();
end
  • P: Bei Objektorientierung ist ja Vererbung wichtig, wie würde sich das auf die Namens- und Typanalyse in e2 auswirken?
  • I: Die müssen dann in einem Schritt passieren, um eben zu wissen, welchen Typ ein Objekt hat, um Membervariablen und deren Typen zu bestimmen.
  • P: Ist das dann immer noch so mit den Sichtbarkeitsschachteln?
  • I: Jein, Klassendefinitionen werden später auch noch benötigt, und werden nicht beim Verlassen der Klassendefinition verworfen, aber für lokale Variablen gibt es noch Sichtbarkeitsschachteln, die beim Verlassen des Scopes verworfen werden.
  • P: gibt mir Schablone des Analysevorgangs aus der Vorlesung (Foliensatz 8, Folie 7, Stand 2024-02-29)
  • P: Führen sich das doch hier mal durch.
  • I: führe es durch
  • P: Und wie sieht so ein Objekt im Speicher aus?
  • I: Erkläre Memorylayout bei Einfachvererbung, das geerbte Attribute am Anfang liegen, davor noch der Klassendeskriptor, hab ein Blatt umgedreht und das aufgemalt (Foliensatz 8, Folie 30, Stand 2024-02-29). Auch Vtables erklärt, es war den Prüfern wichtig, das ich erwähne, das so die Attribute immer am gleichen Offset liegen, unabhängig vom dynamischen Typ

Debugger

  • P: Wie kann jetzt überhaupt ein Programm debuggt werden?
  • I: Der Debugger kann sich mit PTRACE an den zu debuggenden Prozess anhängen.
  • P: Also es gibt 3 Akteure: der zu debuggende Prozess, den Debugger, und das Betriebssystem. Bitte sagen Sie immer, welcher Akteur was macht.
  • I: Der Debugger ruft PTRACE Syscall auf, um dem Betriebssystem zu sagen, das er sich an diesen Prozess anhängen möchte.
  • P: Was bedeutet anzuhängen?
  • I: konnte ich nicht genau sagen, aber hab dann einfach noch begründet warum das Betriebssystem da mitspielen muss
  • P: Und wie kann man damit jetzt debuggen?
  • I: int 3 Befehl, ist extra nur ein Byte lang, löst eine Trap aus, die das Betriebssystem dem Debugger zustellt
  • P: Das bedeutet übrigens Anhängen, Traps des Prozess werden dem Debugger zugesetllt.
  • I: Ahh, das macht Sinn.
  • I: Genau, aber nach dem int 3 kann der Debugger Speicher und Register lesen/schreiben.
  • P: Wie ist das mit den Debugregistern?
  • I: Manche CPUs haben Debugregister, die die Ausführung anhalten, wenn die Speicheradresse aus einem der Debugregister gelesen wird
  • P: wirft blick auf die Uhr: noch 5 min

Codierungsphase: Dynamische Programmierung

  • P: Kommen wir zur Codierungsphase.
  • P: gibt Zwischencode
  • P: Sie kennen das Verfahren zur Codeselektion mit dynamischer Programmierung, wie würde Sie hier vorgehen?
  • I: Zuerst aus dem Zwischencode Ausdrucks-DAG erzeugen.
  • P: Warum ist das ein DAG?
  • I: Variablen könne mehrfach gelesen werden, z.B. kommt a in Ausdruck öfter vor, also gibt es mehrere Kanten zu a.
  • P: Okay
  • I: Den DAG zerschneidet man zu einem Ausdrucksbaum
  • P: gibt einen Ausdrucksbaum und ein Maschinenmodell
    • Maschinenmodell, zwei verfügbare Register
NameInstruktion Kosten
L $r_i = M_x$ 2
S $M_x = r_i$ 2
RoR $r_i = r_i \circ r_j$2
RoM $r_i = r_i \circ M_x$2
  • P: Wenden Sie bitte hier das DP Verfahren an.
  • P: blickt zur Uhr: 2 Minuten
  • I: mache DP Algorithmus, fange bei den Blättern an, erkläre woher der Name kommt
  • I: mache noch einen innere Knoten, erkläre Vorgehen, auch die Betrachtung der Reihenfolge
  • P: Wie ist das jetzt mit dem ersten Eintrag in diesem Array, was bedeutet der?
  • I: erkläre, das das die Kosten für die vorgezogene Auswertung und speichern im Speicher sind
  • P: Und wie ist das mit der Reihenfolge bei RoM Befehlen?
  • I: da gibt es nur eine Reihenfolge.

Zeit um.

Danach selbstverständlich noch die Frage, was ich mir selbst geben würde, hab das etwas begründet, gesagt das ich eigentlich alles wusste, mich nicht aufs Glatteis führen habe lassen, nur bei undefiniertem/unspezifiziertem Verhalten mich verhört habe. Meine Debugger Erklärung waren nicht ganz sauber, aber richtig und gut.

  • P: Also welche note?
  • I: Muss ich ne Zahl sagen? Ja dann 1.0
  • P: Joa, stimmt.