FSI Informatik/pruefungen/hauptstudium/ls4/cs-2020-03-06

Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 4 » cs-2020-03-06 (Übersicht)

Pruefung: CS

Pruefer: wosch

Dauer: ca 20 Minuten

Beisitzer: Stefan

An diesem Tag waren es 2 Pruefungen, mit aehnlichem Ablauf, der nachfolgend Skizziert wird.

F: Nebenlaeufigkeit. Was ist das?
A: zwei Prozesse die unabhaenging voneinander laufen
F: Wenn ich den C-Compiler am laufen habe und jemand anders auf dem gleichen Rechner VIM nutzt. Gibt es da unter Umstaenden ein Problem?
A: Die zwei Prozesse laufen zwar auf der logischen Ebene Nebenlaeufig, auf der physikalischen Ebene gibt es aber Abhaengigkeiten: z.B. Bus/CPU wird geshared
F: Wie bekommt man denn Nebenlaeufigkeit? Was gibt es da so fuer Moeglichkeiten?
A: Kritische Abschnitte Blockierend / Nicht-Blockierend synchronisieren
F: Womit wollen wir denn anfangen?
A: Blockierend
F: Was ist denn so das Einfachste Blockierungs/Verfahren?
A: Spinlock mit TAS hingemalt
F: gibts da Probleme?
A: Cache Invalidierungen und Access Contention
F: naja, Access Contention tritt ja erst bei der Art der Verwendung von TAS auf. Das Hauptproblem sind die Cache Invalidierungen. Warum treten diese auf?
A: TAS schreibt immer 1 in die abgefragte Variable.
F: OK, es gibt ja auch TAS die auf integern arbeiten. Kann es da zu Problemen kommen?
A: Falls ich auf einer 16Bit Architektur mit 32Bit Integern rumhantier, womoeglich ja. [Eigentlich wollte er hier auf die Wortlaenge hinaus, die ja unter umstaenden nicht Atomar ist. Das scheint aber trotzdem kein Problem bei TAS zu sein, da er ja immer nur auf das 0.Bit testet]
F: Jetzt mal eine philosophische Frage: warum hat man denn TAS so genannt? Eigentlich ist es ja eher ein FetchAndSet.
A: puh… weil es so verwendet wird, als ob atomar was getestet und geschrieben wird?
F: Ja, Naja, irgendwie schon.. ist ja auch gar nicht so wichtig…
F: Wie wuerde man denn ein Lock bauen, ohne diese ganzen Probleme die so auftreten koennen?
A: CAS mit Spin on Read und Backoff Verfahren
F: Was ist denn ein bekanntes Backoff Verfahren?
A: Das Ticketlock. Das ist ein proportionales Backoff-Verfahren.
F: Was macht denn ein proportionales Backoff-Verfahren so aus?
A: Man zieht ein Ticket und wartet solange bis das naechste zu bearbeitende Ticket meiner Ticket-Nummer entspricht. → Delta zwischen MeinTicket-CurTicket
F: Was ist denn der Unterschied zu CAS/TAS?
A: Fairness. Beim Ticketlock verhungert niemand.
F: Genau, Ticketlock ist also ziemlich schick. Es hat aber trotzdem ein Problem. Welches?
A: 1. Ticket-Counter koennte theoretisch Ueberlaufen 2.Alle Ticketinhaber warten auf eine Variable.
F: In der Uebung habt ihr 2. geloest. Wie?
A: MCS Lock. Wartende reihen sich in eine Queue ein und warten auf eine Variable, in dem element der Queue. Ist ein Prozess fertig, signalisiert dieser seinem Nachfolger, dass er an der Reihe ist.
F: Und diese Queue muss nicht weiter Synchronisiert werden? -Doch! - Wie wuerde man so eine Queue denn Synchronisieren? Es ist ja ziemlich doof, wenn ich dann wieder auf eine Variable spinnen muesste…
A: Wenn man nicht spinnen moechte, sollte man die Queue Nicht-Blockierend synchronisieren. [kurzer Schweisausbruch, dass es jetzt mit Nich-Blockierend weiter geht]
F: Und schon sind wir bei dem Thema Nicht-Blockierende Synchronisation. Wie wuerde man jetzt diese Queue Nicht-Blockierend Synchronisieren? [schaut auf die Uhr] Ach das schaffen wir wohl nicht mehr in der Zeit… Wie ist denn ein FAA mit CAS realisiert?
A: FAA mit CAS hingemalt.
F: Ist diese Implementierung aequivalent mit der richtigen FAA implementierung?
A: Ne, wegen CAS kann man Verhungern. Das geht beim richtigen FAA nicht. Man sollte ggf auch auf ABA aufassen [das ist hier aber nicht der Fall]
F: Wie schaut denn das ABA Problem aus?
A: ABA erklaert.

Pruefungsatmosphaere gewohnt LOCKer :)