Paging konstante Größe?
Hallo!
1.) Ist der Grund weshalb man die Pages als gleich Große Blöcke teilt wie die Frames, dass man nur einen Eintrag in der Pagetable machen muss, weil die Größe sich dann sowieso ergibt?
3.) Gibt es Betriebssystem wo die Frames und die Pages unterschiedlich groß sind aber vielfache? Oder gibt es Betriebssysteme die ganz auf Paging verzichten und jedes Programm einen durch Anfangs -und Endadresse kategorisierten Block bekommt?
4.) Warum wird bei Windows der PE-Header in eine eigene Page geschrieben wobei relativ viele Bytes ungenutzt bleiben? Und warum wird der PE-Header überhaupt mit in den RAM geladen?
5.) Was ist wenn ein Programm von Windows 1 Byte anfordert? Schaut dann Windows einfach wo auf der letzten Heap Page Platz ist und nimmt dort die erst beste Adresse und fangt wenn nichts frei ist eine neue Page an? Gibt es eine Funktion um eine Page zu reservieren auch oder nur sowas wie malloc?
Lg
2 Antworten
1.) Auch - aber wenn Du PAaes auslagern willst, bedenke, daß klassische HDDs auch feste Blöcke haben. Insofern tirfft es sich gut, wenn die Pagegröße ein vielfaches der Blockgröße des Hinbtergrundspeichers ist. (HDDs, 512/4096 Bytes). Zweitens, einfache Arithmetik, Pagegrößen von z.B. 4096 BYyes entsprechen 12 Bit, ich kann also den Offset mit einem simplen Shift wegmaskieren.
3.) Nein, wären beide unterschiedlich, könnte die MMU eben nicht mehr umrechnen, die MMU bzw. deren Fähigkeiten geben VOR was realisierbar ist. Ein OS das auf Paging verzichtet ist DOS, es arbeitet im Realmode mit segmentiertem Speicher (zumindest ursächlich).
4.) Frag bei Microsoft nach, warum sie sich für diesen Entwurf entschieden haben. Tipp, es liegt wohl vor allem daran, daß kein PIE verwendet und das Executeable ge-mmap-ed wird.
5.) Ein malloc() ist eine Bibliotheksfunktion, wie diese wiederum den Speicher anfordert entscheidet die Implementierung. Wie Windows den Speicher verwaltet ebenso, aber auch das wurde Dir beides bereits erklärt. Schau halt in der Doku, welche Syscalls Windows so anbietet.
---------
Um nochmal auf 5 genauer einzugehen, eine bestimmte C-Bibliothek auf einer bestimmten Platform allokiert z.B. einfache kleine Anforderungen auf dem Heap und vergrößert diesen ggf. nach Bedarf. Große Allokationen werden dann via priv. anon. mmap erledigt.
Nein, weiß ich nicht.
Windows führt Buch welche Frames (phys Pages) belegt sind. Ferner pflegt es die Pagetables der Prozesse mit der Abbildung virtuell -> physisch.
Dadurch daß Windows 'weiß' welches phys. Frames belegt sind und welche nicht, ergibt sich der Rest - die Pagetable wird hierfür gar nicht benötigt.
Nochmal, nein, die übliche Pagetable funktioniert umgekehrt, da steht für die virtuelle Page drin, welcher physische Frame dahinter liegt, oder eben nicht. Die inverse Variante gibt es auch, die ist natürlich deutlich kleiner.
Sobald ein Kontextwechsel stattgefunden hat, ist Windows quasi weg, es weiß nichts, es macht nichts. Wenn ein Prozess X auf eine virtuelle Adresse zugreift, dann geht die MMU hin und macht einen Indexlookup der virtuellen Adresse in der Seitentabelle respektive den Seitentabellen! Und nein auch die MMU muß nicht in der Seitentabelle suchen, sie schaut direkt in der Seitentabelle nach, der TLB cached nur, damit der Lookup nicht immer einen Speicherzugriff erfordert
Dir wurde mehrfach die Funktionsweise der Abbildung erklärt, nicht nur von mir, es wurden auch Links von anderen Usern gepostet.
Die virtuelle Adresse kodiert die Suchpositionen in den Seitentabellen. Punkt.
Das heißt der Prozess braucht nicht mehr als die Pagetable des Prozesses selbst und es kann sein dass der Prozess aus nur 5 Pages besteht und dann übergibt Windows beim Kontextwechsel diese 5 Einträge und aus denen sucht die MMU die richtigen heraus (schneidet die ersten 20 Bit ab und fügt stattdessen die RAM Adresse ein die bei meinem 4GB RAM wohl auch wieder 20 Bit hat)?
Und die mehrstufigen Tabellen verwendet man, weil eine "einzelne" Pagetable zu groß wird, was man bei 5 Einträgen nicht braucht? Also eine Art Baumzugriff?
Richtig, die Tabelle hat aber immer die gleiche Größe, auch wenn z.B. nur 2 Einträge drin sind.
Reale Implementierung, 1st Level: 10 Bits -> 1024 Einträge a 4 Bytes = 4096 BYtes (also genau eien Page). im Eintrag steht dann die Basisadresse der nächsten Tabelle, gleiches Prinzip.
Ein weitere Vorteil mehrere Level, alles hinter dem 1. Level kann natürlich selbst wieder auf HDD ausgelagert werden.
Funktioniert das ganze dann etwa so:
1.) Kontextwechsel findet statt, der vorherige Prozess wird gespeichert.
2.) Beim erstellen des Prozesses wurde der Prozesskontrollblock mit Daten angefüllt u. a. wo sich im RAM die Pagetable befindet. Sobald ein Prozess eine neue Page allokiert, wird in dessen Pagetable ein Eintrag gemacht, mit der virtuellen Adresse und zu welcher Page das verweist.
3.) Dann wird bei der MMU irgendein Register vom OS auf die Adresse der Page gestellt wo sich der nächste Befehl befindet. Wird jetzt die Page nicht geändert, dann werden bloß die letzten 10 Bit drauf addiert.
4.) Ruft man eine Adresse auf die nicht auf der aktuellen Page ist, dann muss die MMU wieder in die Pagetable gehen und nach der Page suchen, wo sich die virtuelle Adresse befindet. Quasi planlos suchen, weil die MMU nicht weiß, welche virtuelle Adresse auf welcher Page ist? Oder ist das suchen eher weniger das Problem, weil Windows die Pagetable aufsteigend anfüllt? In der Pagetable stehen eigentlich die letzten 10 Bit gar nicht drinnen weil die für das Indexieren überflüssig sind und dieser Offset eh gleich ist oder?
Steht in der Pagetable zu Prozess X dann:
0x400000 - 0x401000 -> RAM Adresse 0x50000 - 0x51000
0x705000 - 0x706000 -> RAM Adresse 0x8001000 - 0x8002000
Und wenn der Prozess was aufruft, dass in der Pagetable nicht vermerkt ist, dann gibt es Error. Und auch der Pagefault ist eigentlich schon aus der Pagetable ersichtlich? Oder steht in der Pagetable nicht ob die Page ausgelagert ist?
Es geht also eher um ein Speicherproblem als ein Suchzeitproblem?
Bei der mehrstufigen Pagetable steht dann 0x400000 befindet sich in Tabelle 30 von der Pagetable 50. Und dann ruft ladet die MMU die Tabelle 50 und dort die Tabelle 30. Das spart dann RAM wenn man die unteren Tabelle auslagert aber dafür sollten die dann nicht ständig angesprungen werden?
Verstehe ich es in etwa richtig?
zu 2.) bzw. wird der MMU bloß die Adresse der Pagetable mitgegeben, wo sie die virtuellen Adressblöcke selber raussuchen muss. Und vermutlich erst wieder ein Lookup gemacht wird wenn man etwas auf einer anderen Page anspringt während die Startadresse zwischengespeichert wird. Und der TLB speichert da die letzten paar Lookups weil es wahrscheinlich ist dass das npchmal adressiert wird, weil man z. B. aus einem Unterprogramm zurückkehrt.
1.) Ja, stell Dir einfach nen Schreibtisch (CPU) vor, der von mehreren Mitarbeitern benutzt wird. Beim Wechsel wird immer der Zustand für den jeweiligen Arbeiter (Prozess) hergestellt, wie er den Tisch verlassne hat.
2.) Ist im Prinzip richtig, Anfangs wird halt die Pagetable so erzeugt, daß eben der Code und die Daten, Heap Stack in physischen Frames liegen und eben die notwendigen Zuordnungen in der Pagetable eingefüllt, später wird dann bei Allokationen die Table einfach modifiziert. Und ja, im Endeffekt wird irgendein Register mit der Basisadresse der Pagetable belegt, das ist dann Teil des Zustandes des Prozesses, wenn ich die Register beim Kontextwechsel wegspeichere und später wieder lade. Nagel mich nicht drauf fest, ich meine je nach Typ und Architektur gibt es bei x86 noch einen Zwischenschritt, da zeigt das Basisregister dann nicht direkt auf die Pagetable, sondern auf eine Datenstruktur mit Informationen über die Pagetable - das ist aber letztlich in Hinblick auf die Arbeitsweise egal.
Der TLB ist im Endeffekt einfach ein Cache, wenn ich jetzt Adresse X brauche, dann schaue ich mir die Basis an (vorderen n-bits) udn schaue, ob diese im Cache liegt - dann spare ich es mir aus dem Speicher den Eintrag zu holen. Und es wird natürlich dadurch nicht für jede angeforderte Adresse ein Cache Eintrag in der TLB erzeugt, sondern nur einer je Page(lookup).
3.) Nein, die MMU macht wie gesagt nur die Abbildung auf Basis der virtuellen Adresse, das ist im Endeffekt ein rein arithmetischer Vorgang. Die Basisadresse gibt eben nur den Startpunkt an. Jede Speicherzugriff läuft über die MMU, die das umrechnet, wenn die notwendigen Daten noch im TLB sind, dann erspart sie sich den Speicherzugriff für den Tabellenlookup. Der TLB ist im Endeffekt nur ein hübscher Name für einen ganz normalen optimierten Cache.
4.) Es ist egal, ob der Zugriff in der gleichen Page ist, oder nicht, die MMU wird immer benötigt - die MMU kann aber in der gleichen Page, weil die Zuordnungsdaten noch in der TLB sind, direkt die physikalische Adresse in einem Schritt bestimmen. Wie gesagt, die virtuelle Adresse kodiert die Indices udn somit den Pfad des BAumes. dadurch ist nichts planlos:
0101101011 1111001101 110011001101
=363 = 973 = 3.277
PTBase+(363*4) holen, enthält PT2base
PT2base+(973*4) ethält PhysBase
Physbase+3277 ist physische Adresse.
Hat der TLB noch Eintrag 363 des ersten Levels kann direkt LEvel zwei geholt werden, liegt Eintrag 973 aus der Tabelle des Level 2 noch im TLB, kann aus dem TLB gehotl werden und im Endeffekt ohne Speicherzugriffe direkt die finale Adresse berechnet werden.
Wenn jetzt im Eintrag der Tabelle steht, daß die Seite nicht im RAM sondern auf HDD liegt, wird gestoppt und der Speichermanager des OS aufgerufen, der dann dafür sorgt einen freien physischen Frame mit der Seite zu belegen, und den Tabelleneintrag aktualisiert. Jetzt kann die MMU weitermachen udn die physische Adresse bestimmen.
Wird auf einen leeren Tabelleneintrag zugegriffen hält die MMU auch an und ruft eine Routine im OS auf -> Resulktat Segfault (auf nicht vorhandenen Speicher zugegriffen)
Wird schreibend auf eine Page zugegriffen, die als read only markiert ist -> Seitenzugriffsfehler/Protection Fault, OS wird aufgerufen.
Die exakten Namen und Bezeichnungen variieren mit Herstellern der Hardware und OS-Implementierungen, konzeptionell ist das aber immer sehr ähnlich aufgebaut.
------
Und ja, die Strategie ob man untergeordnete Tabellen auslagert und nach welchen Kriterien kann sehr unterschiedlich sein. Code hat z.B. oft starke Lokalität, tendenziell tut es aber schon mehr weh, ausgelagerten Code oder Tabellen für den Instruktion Fetch wieder zu laden, als einfache Daten.
Auch bei Daten gilt, selbst wenn mein Prozess 20 GB RAM benötigt. meistens eben nicht alles zeitgleich, meine Undo History wird z.B. meist nie wieder angefragt, die Daten inklusive untergeordnete Pagetables werden meist nie wieder gebraucht.
Nun kann das OS natürlich nich thellsehen, eher überlegt man sich sinnvolle Kriterien, die dafür sorgen, daß solche Szenrarien eben optimal abgehandelt werden.
Ein Eintrag in der Pagetable hat unter anderem folgende Informationsbits:
Dirty, Accessed, User/Supervisor, Read/Write.
Im Prinzip besteht der Sinn von Paging und dem Zerteilen des RAM in gleich große Blöcke dann wohl darin, dass man als höheres Gesetz weiß: Ist die Basis Adresse der Page zugeteilt, so sind auch die nächsten 0x1000 Bytes Offset zugeteilt ohne das explizit zu überprüfen.
Wodurch man sowohl seitens der MMU weniger 20 Bit High Einträge in der Pagetable durchsuchen braucht (falls die MMU überhaupt etwas abgleicht und nicht schon mit korrekten Adressen angesteuert wird und als ALU ähnliches Rechennetz nicht bloß addiert und Bits setzt). Also ich gehe davon aus, dass die MMU dann ein Basisregister erhält mit der Pagetable des Prozesses. Und ab dann mit den ersten 20 Bits die virtuellen Adressen heraussuchen kann durch Art Poitnerarithmetisches vergleichen. Und dann bloß Pagefault heißt "nicht gefunden" und dann das OS die Auslagerungsdatei noch durchsucht und ansonst den Prozess stilllegt, wenn er ungültige Adresse(n) benutzt.
Als auch Speicher spart, weil man dann nicht über jede Adresse seitens des OS buchführen muss, sondern nur über eine Liste von 2 hoch 20 Pages.
Es gibt dann wohl "zwei Listen" im RAM, die eine zeigt von 0x00 bis sizeof(RAM) alles physischen Frames plus Inhalt an und rekurivsiv sieht man in dieser Liste auch noch Pagetables, welche die Information über die Prozesse beinhalten. Und auf alles kann bei mir Windows mehr oder weniger sinnvoll einsehen.
Ist die Pagetable also Teil des Prozesskontrollblocks der vom OS benutzt wird und daneben noch PID und Prozesskontext beinhaltet?
So jetzt zu den verketteten Pagetables: Angenommen ich setze das Baseregister der MMU nicht mit einer Pagetable sondern einem Header mit weiteren Tabellen. Dann rufe ich eine virtuelle Adresse auf. Dann nimmt die MMU die ersten z. B. 12 Bits und such damit eine kleine Liste von 0x1000 Einträgen ab und kann dann schon von jeder Adresse feststellen, ob es die Adresse "in einer weiteren Ordnung geben könnte". Dann bei einem Treffer werdwn die nächsten 10 Bits verwendet um diese verkettete Tabelle zu durchsuchen. Das hätte den Nachteil, dass man nun 2 Speicherzugriffe braucht für eine Adresse und deshalb viel mit TLB machen sollte oder? Aber den großen Vorteil, dass die Pagetables sehr klein werden und bei den ganzen Prozessen im Hintergrund die eh nie was tun ist das ist schon was? Vermutlich funktionieren mit diesem zerteilen von Möglichkeiten auch die meisten Suchalgorithmen. Und weil das Code und Datensegment auf eh auf ein paar Pages limitiert ist und das meiste beim Programm Startup nur einmal ausgeführt wird kann man dann quasi eh alles cachen?
Was mich am Rande interessieren würde, gibt es schon Entwicklungen in Richtung schnelle billige Festplatten, die quasi qls RAM benutzt werden können oder ist das noch in weiter Ferne?
Edit: Achso in der Pagetable steht, dass die Page ausgelagert ist!
Google mal nach NVDIMM, das geht in die Richtung, bis aber auf DRAM verzichtet werden kann, wird es noch eine Weile dauern.
Ich hätte gehofft du verbesserst meinen Essay ein wenig ob das so richtig ist!
Wenn ich gewisse Sachen selber nicht sorgfälltig lese, dann wohl meist weil ich im Vorfeld nicht weiß wer sich auskennt.
Das ganze ist als Monolog zu lesen.
Also: Wie kann die MMU auf einen ausgelagerten oder leeren Eintrag zugreifen, wenn die bloß addieren kann? Ist das eine ALU mit Sonderfeatures?
Weil die schaut ja in die Pagetable bloß ob es die Adresse der Page gibt oder? Und wenn es die Page nicht gibt, gibt es keinen Eintrag? Oder ist die Pagetable immer gleich groß und hat auch Einträge drinn die es gar nicht gibt im physischen Speicher wo dann steht: Nicht vergeben oder auf der HDD?
Was mich am meisten verwirrt hat ist der Begriff berechnen weil ich dachte man braucht da komplexe Formeln wie in Elektrotechnik. Mir fällt gerade auf weil du meintest mit x86
Vielleicht steht im Pagetableheader drinn wie die MMU die ersten 20 Bit interpretieren muss, um hier flexibel große Mehrstufenpagetables zu machen?
Würde mich tatsächlich auch interessieren da ich vor habe mich demnächst mit PE auseinanderzusetzen und weiss daher nicht alles, aber der PE header muss nicht mal geladen werden, gibt z.B. DLL Injections bei denen darauf verzichtet wird damit irgendwelche Schutzmechanismen des Programms nicht den VAS nach PE Headern scannen können. Zu Frage 3: Ja gab es sicher mal, ist aber veraltet und jedes OS nutzt das in irgendeiner Form
Ich glaube man muss das sukzessive logisch nachvollziehen, weil alles der Reihe nach notwendig bzw. praktisch wurde:
Zuerst gab es nur sowas wie Microcontroller, DOS oder glaube sogar die frühen Unix wo man 1 Programm hatte und im Programm die absoluten Adressen verwendet hat.
Dann wollte man weil die CPU teuer war und Computer ausgeliehen wurde usw. 2 oder mehr Programme im RAM haben und das OS war eigens wo und hat die gescheduled.
Jedoch hätte man da immer noch absolute RAM Adressen wissen müssen und demnach wissen wo alle anderen ihre Programme haben was aufwendig wäre.
Darum hat man gesagt, das OS soll die Programme wo hinschreiben und wir benutzen im Programm relative Adressen.
Jedoch kam sofort das Problem mit der Speicherplatz Fragmentierung, weil wenn das OS ein Programm als Block in den Speicher ladet, damit die relativen Adressen stimmen wenn die Baseadresse aufaddiert wird und dann werden Programme wieder freigegeben, dann entstehen Löcher und man kann keine Programme mehr laden, obwohl noch Speicher frei wäre.
Also hat man den virtuellen Speicher erfunden, dessen Prinzip darauf beruht, dass die relativen Programmadressen nicht nur um die Base erweitert werden, sonder quasi jede Adresse in eine physische Adresse umgerechnet wird, damit man diese Lücken ausfüllen kann.
Da ergab sich aber das Problem mit der Buchführung, weil man dann von jeder verwiesenen bzw. gemappten relativen virtuellen Adresse wissen musste, wo das nun tatsächlich steht, weil man ja nicht mehr als großen Block ladet, wo man Anfang und Ende mit einem Gatter abschirmt und das wars.
Im schlimmsten Fall würde man also bei 2GB Userspace, eine Liste mit 2GB Adressen aufzeichnen, wo schon das durchsuchen sehr lange dauert.
Deshalb war das zerteilen in Blöcke eine geschickte Lösung, weil dann muss man sich seitens des OS nur noch merken wo ein Block anfängt und endet.
Jedoch bräuchte man dann vermutlich sehr zeitintensive Algorithmen um die Programmblöcke in den RAM einzuordnen und auch die Einträge werden wieder sehr viele wenn man dann recht kleine Blöcke hat.
Weshalb es am geschicktesten ist, in gleich große Blöcke oder Pages einzuteilen.
Weil wenn man für ein Programm 3 mal 0x1000 Byte braucht, dann merkt man sich einfach 3 Startadressen wo die Blöcke sind. Und wenn man im Programm die relative virtuelle Adresse 0x500 anspringt, dann ersieht die CPU oder MMU aus der Pagetable, welche vermutlich vom OS als Teil des Programmkontext geführt wird, dass diese Adresse auf der 1. Page steht mit der Adresse so und so und dort dann Offset 0x500.
Und was den virtuellen Adressraum angeht, ist das bloß eine Hilfestellung für den Programmierer, da dieser bloß diese Adressen kennen braucht und dann die Adressen 0x700000 im physischen RAM ggf. weit unter der Adresse 0x40100 liegt, weil dann sowie nur die ersten 20 Bytes nur mehr dem Indexieren der richtigen Page dienen und vorm Adressieren dann sowieso verworfen werden.
Da sowieso sich alles im RAM abspielt ersehe ich auch nicht ganz den Grund dann die Pages in Frames umzutaufen. Weil der Frame ist ja die konkrete Adresse wo sich die 0x1000 Bytes befinden im RAM. Und in der Pagetable steht, welche virtuelle Adresse sich in welchem Frame befindet.
Außer mir fehlt hier ein mathematisch Kniff der noch zwischen Pageadresse und Frameadresse unterscheidet oder so.
Weißt du zufällig ob das Sysinternal Programm RAMMap bei phys. Memory die Pages so anzeigt wie sie wirklich im Hardware Memory liegen?
Und Windows führt dann quasi ständig Buch darüber welcher virtuelle Adressraum von 0x1000 Bytes sich auf welcher Page befindet und Punkt.
Und darüber hinaus weiß es durch die Pageliste wie viel Speicher vorhanden ist, reserviert usw.
Und in der Pagetable von Prozess X steht dann konkret drinnen welche expliziten Pages welche virtuellen Adressblöcke beinhalten und wenn jetzt um es zu wiederholen, ein Prozess eine Adresse aufruft, dann braucht Windows gar nicht alle 2 hoch Pages durchgehen um die richtigen Pages zu finden, sondern bekommt beim Kontextwechsel schon die richtigen und seien es 5 Pages eines kleinen Prozesses mit wo sie nachschauen muss, wodurch sich die Hauptaufgabe der MMU dann darauf bezieht festzustellen ob die Page im RAM ist oder ausgelagert? Dann muss sie aber erst wieder 2 hoch 20 Einträge durchsuchen im schlimmsten Fall, wenn der TLB auch nichts weiß?