Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 4 » Betriebssysteme » Scheduling   (Übersicht)

Scheduling

  • Was ist ein Scheduler?
    1. Habe hier einfach Aufgaben und Funktionen des Schedulers erklärt.
  • Wonach kann man beim Scheduling priorisieren?
    1. Ich habe Beispiele dafür gegeben, was für die Priorisierung ausschlaggeben sein kann (z.B. Bevorzugen interaktiver Prozesse, möglicht hoher Durchsatz, etc.), da ich die Fachbegriffe nicht alle im Kopf hatte. Das war aber völlig in Ordnung.
  • Ein weiterer Faktor zum Priorisieren ist auch die CPU, auf der ein Prozess das letzte mal gelaufen ist. Warum kann das ein sinnvolles Kriterium sein?
    1. Moderne CPUs haben Caches, wenn ich den Thread auf der gleichen CPU laufen lasse, dann liegen potentiell die meisten Daten, die der Thread braucht, noch im Cache der CPU und somit läuft i.d.R. das Programm schneller.
  • Jetzt hat man noch das Problem, dass evtl. immer nur der gleiche Thread dran kommt, wenn man nur nach der letzten CPU priorisiert, wie lässt sich das Problem lösen?
    1. Habe eine Kombination aus Round-Robin (das was MPStuBS im Moment macht) und Priorisierung via letzter CPU vorgeschlagen. Also z.B. eine Run-Queue pro CPU, in die Threads, nachdem sie ihre Zeitscheibe aufgebraucht haben, hinten eingefügt werden.
  • Bei Multiprozessorsystemen mit einer einzelnen Run-Queue hat man ja das Problem dass die CPUs sich gegenseitig blockieren, kann man da etwas dagegen machen?
    1. Man kann z.B. eine Run-Queue pro CPU benutzen, was dann zur nächsten Frage überleitete.
  • Was passiert bei dieser Lösung, wenn die Run-Queue einer CPU leer ist? Ist das überhaupt ein Problem?
    1. Man kann die entsprechende CPU entweder idlen lassen oder, besser, man implementiert einen Work-Stealing-Mechanismus, d.h. die CPU holt sich aus der Runqueue einer anderen CPU einen Thread.
  • Es gibt ja zwei Arten, wie man schedulen kann
    1. Kooperativ (also freiwillig die CPU abgeben) und präemptiv (nicht freiwillig, z.B. via timer-interrupt).
  • Und wie läuft so ein präemptiver Kontextwechsel letztlich ab?
    1. Habe hier erklärt, dass es einen Hardwaretimer braucht, der regelmäßig interrupts schickt, dass der Interrupthandlercode dann den Interrupt an den Treiber weiterleitet, der Prolog ackt nur den interrupt und der Epilog ruft dann die Schedulerfunktion auf.
    2. Zur Schedulerfunktion habe ich die relevanten Teile zur Kontextsicherung und -wiederherstellung erwähnt (also was toc_switch macht, Instruktionszeiger wird implizit durch Rücksprungadresse gesichert etc.).

Synchronisation

  • Schreibe mir doch mal die P()- und V()-Funktion für eine Semaphorenimplementierung auf.
    1. Habe die Funktionen in etwa so aufgemalt, wie sie in MPStuBS implementiert wurden und habe noch bemerkt, dass man bei dieser Implementierung beachten muss, dass vorher das Big Kernel Lock gelockt werden muss, damit sie fehlerfrei funktioniert.
  • Folgefrage: Wenn ich in P() das Big Kernel Lock locke, und dann blockiere, dann hängt doch die CPU, weil das Big Kernel Lock nicht mehr freigegeben wird oder?
    1. Nein, da der andere Thread ja auch bereits schon einmal weggescheduled wurde, gibt er das Big Kernel Lock im Programmfluss garantiert wieder frei, weil er es auch schon mal gelockt haben muss.
  • Wenn das nicht richtig synchronisiert ist, gibt es da ja diverse Race-Conditions, die da vorkommen können oder?
    1. Neben anderen (Lost Update) gibt es vor allem noch ein Lost-Wakeup-Problem. Lost-Wakeup war wohl das Gewünschte. Bin auch noch näher darauf eingegangen, wie genau es zum Lost-Wakeup-Problem kommt.

IPC

  • Welche Mechanismen gibt es dafür?
    1. Shared Memory und Nachrichten
  • Welche von beiden ist mächtiger?
    1. Es sind beide gleich mächtig und man kann sie jeweils aufeinander abbilden.
  • Ja dann mach das mal.
    1. Habe beide Richtungen kozeptionell erklärt, also Nachrichten mit Shared Memory (Semaphore und Queue) und Virtual Shared Memory mit Nachrichten (MMU und Page faults).
  • Im Normalfall nimmt man ja lieber shared memory, weil das schneller ist. Wenn man Nachrichten richtig macht, kriegt man das aber auch schnell hin. Was muss man als Programmierer dabei beachten?
    1. Hab hier gesagt, dass man Schreiboperationen am besten immer gebündelt vornehmen kann, so dass nicht für jede Operation die Pagefaultmechanik laufen muss.
  • Hast du schon mal etwas von Raytracing gehört? Der genaue Ablauf ist für die Frage aber nicht unbedingt relevant. Worauf muss ich achten, um das im CIP (d.h. auf mehrere Rechner verteilt) schnell zu kriegen?
    1. Ich wusste tatsächlich nur, dass es irgendein Grafikalgorithmus ist; Man will das Bild in möglichst gleich große Stücke aufteilen, dass jede CPU ihren Bereich möglichst selbstständig berechnen kann. Eventuell müssen sich die einzelnen Rechner dann nur an den Rändern unterhalten (scheint beim Raytracing aber nicht nötig zu sein).
  • Alle Rechner brauchen ja die Szenerie, auf der sie rechnen sollen. Was muss ich dabei beachten?
    1. Da ich das Verfahren nicht kannte, habe ich hier nochmal nachgefragt, ob sich die Szenerie im Laufe des Algorithmus verändert, oder ob sie gleich bleibt. Die Annahme war, dass sie sich nicht verändert, also habe ich gesagt, dass man die Szenerie dann ja nur am Anfang jedem Rechner schicken muss und dieser sie dann am besten im eigenen Speicher vorrätig halten sollte, da Zugriffe dann deutlich schneller sind, weil sie lokal sind.

Nochmal Synchronisation

  • Okay, es gibt ja noch ein weiteres häufiges Synchronisationsproblem, bei dem man gemeinsame Daten hat, die häufig gelesen und seltener geschrieben werden, beispielsweise bei Datenbanken, wie löse ich dieses Problem?
    1. Dafür gibt es Read-Write-Locks/Shared-Exclusive-Locks
  • Genau, worauf muss man beim Implementieren achten?
    1. Habe hier konzeptionell erklärt, wie sich die einzelnen Funktionen aus der Vorlesung zusammensetzen (startRead, startWrite, endRead, endWrite).
  • Jetzt hat man bei dieser Implementierung ja das Problem, dass die Reihenfolge, in der die einzelnen Funktionen aufgerufen werden dürfen, schwierig einzuhalten ist, gibt es da alternative Möglichkeiten, die das vereinfachen?
    1. Zunächst mal ist das grundlegende Problem, dass das Protokoll zum Schreiben und Lesen explizit vom Programmierer eingehalten werden muss. Als alternative Möglichkeit habe ich den Monitor angegeben. Anschließend habe ich die wichtigsten Eckpunkte, wie ein Monitor funktioniert und was durch das Verwenden eines Monitors beim Lese-Schreiber-Problem einfach wird erläutert.
  • Jetzt ist das mit dem Monitor teilweise immer noch nicht perfekt, was sind denn Pfadausdrücke?
    1. Auch hier wieder eine Erklärung, dass es sich dabei um ein Sprachkonstrukt handelt, bei dem man - losgelöst von der Implementierung von Funktionen - deren Synchronisationsvoraussetzungen ausdrücken kann. Habe dann noch erklärt, wie es im Groben funktioniert (z.B. wie sich die Ausdrücke zusammensetzen können). Habe außerdem noch erwähnt, dass es bis jetzt ein theoretischer Ansatz ist, der noch von keiner Sprache implmentiert wird und dass das Ganze in einen Automaten umgerechnet wird und dass die Synchronisation des Automaten der potentielle Falschenhals des Systems ist.

Atmosphäre

Die Atmosphäre war sehr entspannt, Herr Sieh war sehr freundlich. Ich habe bei manchen Fragen kurz nachdenken müssen, was ihm aber lieber war, als wenn man einfach ohne Nachzudenken irgendwas sagt.