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

Prüfungsfach: Concurrent Systems

Prüfer: wosch, Beisitzer: Stefan

Athmosphäre/Stimmung: Schön entspannt, hat definitiv nicht die Nervosität gesteigert.

Besonderheit: Online-Prüfung aufgrund Corona und des LOCK-downs über BigBlueButton. Hat gut funktioniert, hätte Graphiktablet gehabt, aber die Konzepte haben sich auch ganz gut ohne Papier erklären lassen.

Fragen:

Was ist Nebenläufigkeit?

  • Programme finden nicht zwingendermaßen gleichzeitig statt,

Wie können Programme so stattfinden, dass man nicht merkt, dass sie voneinander abhängig sind?

  • Ja, da muss man dann synchronisieren.

Welche Arten von Synchronisation gibt es da?

  • blockierend / nicht blockierend

(Überleitung) Was macht denn blockierende Synchronisation aus?

  • nur einer gleichzeitig in kritischem Abschnitt
  • andere blockieren
  • z.B. mit Locks, auf Lock-Variable blockieren

Was für Arten von blockierender Synchronisation gibt es denn noch, ohne Locks?

  • (stand total am Schlauch… gesucht war Semaphore, Mutex, …, war aber mental drauf eingestellt, dass wir Semaphoren und Mutexe ja auch oft mit Locks gebaut haben…)

Gut, jetzt aber wieder zurück zu Locks. Du hattest ja schon erwähnt, dass man mit einem Spinlock auf einer Variable spinnen kann… Ist das denn jetzt gut, weil kurz ist ja auch immer gut…

  • atomar, z.B. mit TAS

Welche Probleme hat man denn hier?

  • unconditional store → schlecht für Cache
  • BUS voll durch dauernde Blockierung für atomaren Zugriff

Wie geht das besser?

  • CAS, da conditional store
  • nächste Stufe: erst Variable checken, dann CAS (Spin-on-read)

Was ist da jetzt das Problem?

  • 1 Thread in kritischem Abschnitt, 1000 andere warten, Thread gibt wieder frei
  • alle 1000 prasseln auf den BUS ein
  • nächster Schritt: Ticketlock

Welches bekannte Verfahren steckt denn hinter dem Ticketlock?

  • Backoff-Verfahren
  • z.B. random Backoff, halt nicht Echtzeitgeeignet

Was ist denn das Ticketlock für ein Backoffverfahren?

  • proportional
  • grob Funktionsweise des Ticketlocks beschrieben

So. In der Übung habt ihr dann ja noch was besseres implementiert - was ist denn das Problem bei dem Ticketlock und wie habt ihr das gelöst?

  • spinnen alle auf eine Variable, obwohl nur eine Änderung interessant ist
  • Queued Lock → MCS-Lock
  • grobe Erklärung, wie das MCS-Lock funktoniert

Gut, du hast jetzt gesagt da ist ne Queue drin. Die muss man ja auch synchronisieren, und ein Lock mit einem Lock implementieren ist ja auch doof…

  • nicht-blockierende Synchronisation :)

Was ist denn das Konzept hinter nichtblockierend, was ist denn die Idee dahinter?

  • man konstruiert sich so einen Algorithmus, dass man alle Zustandsänderungen als Transaktionen modellieren kann, d.h. bei Bedarf mehrfach ausführen kann
  • Zustand austauschen dann Rückgriff auf atomare Operationen, die den vorherigen

Zustand checken

Was kann dabei ein Problem sein / wie heißt das Problem?

  • ABA-Problem erklärt

Gegenmaßnahmen?

  • Generationenzaehler, aber nur Vermeidung (Zähler kann überlaufen)
  • LoadLinked / StoreConditional, muss von Hardware unterstützt werden, Funktionsweise kurz erklärt

Wie bautgenerationenzaehler wie?

  • z.B. mit extra Variable, wenn z.b. uint64_t dann ist Überlauf auch sehr unwahrscheinlich

Und wie geht des noch…?

  • Generationenzaehler in die unteren Bits, die die Speicherstruktur zum Alignment braucht

Kann man das auch in die oberen Bits kodieren?

  • joaaaaaaaa schooooon, aber…

(Diskussion, tldr: wosch war unzufrieden)

Bewertung: Sehr fair, kann man sich nicht beschweren ;)