Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 4 » CS 2016-03-18

CS 2016-03-18

Modul: Concurrent Systems (CS) (5ECTS)

Prüfer: Wosch

Beisitzer: Gabor Drescher

Dauer: 20 min

Hinweis: Es gab zuvor 3 andere Prüfungen, die vom Verlauf und den Fragen her sehr ähnlich waren.

Ich bin mir grad nicht sicher, ob ich gedutzt oder gesiezt wurde. Angenehme Atmosphäre, wobei ich mdl. Prüfungen nicht mag und meist sehr hektisch reagiere, so auch in dieser Prüfung. Entsprechend kam am Ende der Prüfung der Hinweis ich solle das nächste mal doch vielleicht den Prüfer ausreden und eine Frage formulieren lassen bevor Antworten eingeworfen werden.

Fragen

F: Unterschied (Nicht-)Blockierende Synchronisierung?

A:

  1. Unterschied Fortschrittsgarantie vs. blockieren à la schlafen legen, passiv warten (Kontext- und Adressraumwechsel) vs. erneuter Beitritts-Versuch.
  2. Wie viele Prozesse befinden sich jeweils im kritischen Abschnitt und wie viele warten am Eingang
  3. Bei den Nachfragen wusste ich nicht so recht auf was Wosch hinaus wollte, da ich ein etwas anderes Bild von blockierender Synchronisation hatte und Wosch ein wenig zu häufig unterbrach, indem ich hektisch viele Dinge einwarf, die unter bestimmten Umständen sein könnten. Beispielsweise wurde mir in dem Gespräch erklärt, dass Spinlock eine blockierende Synchronisation abbildet, obwohl intern NB-Mechanismen verwendet werden.

F: Wie sieht denn eine Implementierung von dem naivsten Lock aus?

A: Implementierung von TAS hingeschrieben. Siehe VL

F: Und wie sieht ein Spinlock mit TAS-Unterbau aus?

A: Vorherigen Code zu einem Spinlock ergänzt. Siehe VL

F: Und ist das gut?

A: Naja, TAS hat folgende Nachteile:

  1. Deleterious Effect - Invalidierung von Cache Lines
  2. Bus-Traffic - Cache Kohärenz-Protokoll - Aktualisierung der Cache Lines
  3. Access Contention

F: Aber das Access Contention Problem besteht doch weiterhin bei einer möglichen Verbesserung! Welche Verbesserung gibt es da?

A:

  1. CAS
  2. Problem Access Contention erläutert - Beeinflussung von Prozessen, die am Lock unbeteiligt sind (Sperren von Interrupts + Bus)

F: Was kann man also gegen Access Contention tun?

A: Spin on Read kann helfen, muss es bei kurzen kritischen Abschnitten aber nicht weil das aktive Warten trotzdem auf dem CAS erfolgt.

F: Aber jedes Lehrbuch sagt kritische Abschnitte haben kurz zu sein?!

A: Ja, aber es existiert ein Trade-Off Contention vs. Overhead.

F: Gut, auf die Diskussion wollen wir nicht einsteigen. Zurück zum vorherigen Thema!

A: Es besteht weiterhin die Gefahr von Access-Contention Bursts, da sich ähnliche Prozesse auch ähnlich verhalten.

F: Ja, wie kann man das verbessern?

A: Backoff

F: Was für Backoff-Verfahren gibt es?

A:

  1. Exponentiell
  2. Inkrementell

F: Wie sehe eine exponentielle Implementierung aus?

A: Beispielsweise ein Shift von einem Counter

F: Was gibt es noch für Verfahren?

A: Fragender Blick des Prüflings

F: Naja, es gibt ja noch andere Lock-Verfahren, die wir bisher nicht besprochen haben und dann kommt von Ihnen ein Lock und dann kann man da weiter zum Backoff fragen.

A: Ich hab mich gefühlt eine Minute an dem „Backoff“ aufgehangen, bis ich den Hinweis verwendet habe und Ticketlock einwarf.

F: Aha, ja Ticket Lock - ist ein Backoff verfahren!

A: Ich war erstmal verdutzt

F: Ok, Sie sind irritiert, erklären Sie doch mal wie ein Ticket Lock funktioniert!

A:

  1. Atomar verwaltete Counter (FAA).
  2. Ein Counter der das nächste zu ziehende Ticket repräsentiert.
  3. Ein Counter der das aktuell bearbeitete Ticket repräsentiert.
  4. Generell immer wieder überlaufende Counter als Problem aufgeführt.
  5. Ah ja stimmt, kann man als Backoff ansehen - das hier ist ein dynamisches, proportionales Verfahren

F: Wenn man bei Gabor in der Übung war, dann weiß man was daran problematisch ist und wie sich das verbessern lässt.

A:

  1. Problematisch sind die lesenden Zugriffe auf globale Variablen.
  2. Optimierung durch vorhalten von lokalen Variablen, die verwendet werden. Hier fiel dann von Wosch der Begriff MCS, wozu in den Übungen ein Paper bereit gestellt wurde.

F: Wie sieht eine Implementieren von FAA mithilfe von CAS aus?

A: siehe VL

Bewertung

Note 1.3

Vorbereitung

Über das Semester habe ich eine ausführliche Zusammenfassung verfasst und gegen Ende des Semesters noch mal intensivst überarbeitet. Deren Inhalt habe ich insgesamt ca.1 Woche gelernt, was ohne die Zusammenfassung zwangsläufig mehr gewesen wäre. Für die Bearbeitung der Übungsaufgaben hatte ich leider keine Zeit, war aber in jeder Besprechung, wusste worum es geht und hatte mir die Grundideen hinter den Aufgaben verdeutlicht.