Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Traps und Determinismus bei Page Faults
In der Klausur vom SS16 Aufgabe 1g) ist folgende Multiple Choice Aussage richtig:
“Bei der mehrfachen Ausführung eines unveränderten Programms
mit gleicher Eingabe treten Traps immer an den gleichen Stellen auf.”
Den Satz haben wir so ähnlich auch öfter mal in der Übung gesagt. Im FSI Paß ist die Auswahlmöglichkeit auch als richtig markiert und der Rest ergibt keinen Sinn.
Bei Page Faults stimmt das doch aber eigentlich nicht. So wie ich das sehe, kann das nur passieren, wenn das Programm keine Parallelität durch Threads hat, die Ersetzungsstrategie beim Paging nur lokal ist und keine Seiteneffekte wie z.B. Generation von Zufallszahlen verwendet wird.
Bei globaler Ersetzung könnten Seitenrahmen des Programms, das wir mehrmals ausführen und Traps an der gleichen Stelle auftreten sollen, durch eine Seiteneinlagerung eines anderen Prozesses ausgelagert werden. Da wir keine Ahnung von anderen Prozessen haben, geschieht das für uns zufällig.
Bei mehreren Threads könnte die Reihenfolge, in der wir Daten referenzieren, stark variieren und somit die Anzahl der Traps bei jeder Ausführung stark unterschiedlich sein.
Bei anderen Seiteneffekten (wie der Generation von Zufallszahlen) könnten wir ganz anderen Code zur Ausführung bringen und somit ein Programm unverändert mehrmals laufen lassen und die Traps können an ganz anderen Stellen auftreten. Bei Generation von Zufallszahlen könnten auch andere Traps wie z.B. ein Trap durch Division mit 0 mal Auftreten und mal nicht auftreten.
Selbst wenn wir davon ausgehen, dass jegliche Zufallszahlen als Eingaben zählen, können wir weiterhin nicht garantieren, dass ein Page Fault genau an der gleichen Stelle auftritt wegen der globalen Ersetzung und Multithreading.
Wo ist hier der Fehler? Irgendwie kann doch die Aussage aus der Klausur nicht stimmen, wir haben das aber sicher auch so in der Art in Übung gesagt. Man bräuchte noch den Zusatz, dass das Programm unter exakt den gleichen Bedingungen ausgeführt werden muss. Dann könnten wir aber gleich sagen, dass auch Interrupts an der gleichen Stelle auftreten würden…
Siehe https://fsi.cs.fau.de/forum/thread/16270
Zufallszahlen wuerde ich auch als Eingabe zaehlen, da sie ja von irgendwelchen aeusseren Werten (z.B. der Uhrzeit) abhaengig sind,
welche bei mehreren Programmablaeufen normalerweise unterschiedlich sind.
Das hab ich ja im etwa so schön geschrieben (dass man von mir aus Uhrzeit usw. als Eingabe annimmt). Das verlinkte Thema geht zwar darauf ein, warum ein Page Fault ein Trap ist, aber nicht auf die zitierte Aussage der Klausur SS16.
Mir ist klar, dass ein Page Fault ein Trap sein muss. Aber warum sollten diese vorhersagbar sein? Insbesondere hinsichtlich globaler Ersetzungsstrategie.
Und ja, der Beitrag geht auch auf globale Ersetzung ein, aber nicht in genau dem Zusammenhang.
Prinzipiell koennte man argumentieren, dass Informationen wie ersetzte Seiten Teil der “Eingabe” sind (genau wie Seeds fuer Zufallszahlen, etc.). Aber du hast Recht, das ist bei Page Faults eine recht schwache Argumentation. Wir wuerden die Frage heute nicht mehr so stellen.