Seitentabelle - Ich verstehe nicht, wie diese Tabelle erstellt wurde [geschlossen]

Sie haben vier physische Speicherseiten und acht virtuelle Seiten. Alle physikalischen Seiten beginnen ohne Zuordnung für einen bestimmten Zweck. Die virtuelle Tabelle mit acht Einträgen beginnt damit, dass alle virtuellen Seiten ungültig sind.

Das ist die Ausgangssituation. Ein weiteres Detail kann hier nützlich sein – die Definition, WIE neue physische Seiten zugewiesen werden. Angesichts der Ergebnisse denke ich, dass es klar ist, dass die Zuweisungsmethode zunächst mit der Zuweisung der physischen Seite 0 beginnt. Dann physische Seite 1. usw. Sobald alle physischen Seiten mindestens einmal zugewiesen wurden, kommt der LRU-Algorithmus (am längsten verwendet) ins Spiel.

Damit ist der Prozess eingerichtet.

Eine weitere Sache könnte nützlich sein, um das Hinzufügen in Betracht zu ziehen. So wird die LRU selbst gehandhabt. Stellen Sie sich das wie einen Stapel aus acht Karten vor. Eine Karte, die jede virtuelle Seite repräsentiert. Nennen wir die Karten also aus offensichtlichen Gründen 0, 1, 2, 3 usw. Das Deck enthält immer acht Karten. Anfänglich beginnt der Stapel mit 01234567 (oder einer anderen Reihenfolge, die Sie möchten). Wenn Sie eine neue Seite zuweisen, nehmen wir immer die oberste Karte (die hier die Ziffer ganz links sein wird) aus dem Stapel und verwenden die physische Seite, die sie anzeigt , und legen Sie diese Karte dann wieder unter den Stapel. Wenn wir also zum Beispiel eine neue physische Seite benötigen, gehen wir zu diesem Anfangsstapel von „0123“, ziehen die oberste Karte (die „0“ ist), weisen diese physische Seite zu und legen diese Karte dann wieder hinein das Deck ganz unten. Das neue Deck wäre also "1230" nachdem wir mit diesem Schritt fertig waren. Jedes Mal, wenn auf eine physische Seite zugegriffen wird, finden wir ihre Karte in diesem Stapel und verschieben sie ebenfalls nach unten.

Um das LRU-Deck zusammenzufassen: Wenn wir eine neue physische Seite brauchen, nehmen wir immer die oberste Karte und verwenden die Seite, die durch den Wert dort angezeigt wird, und verschieben diese Karte dann an die untere Seite des Decks. Wann immer wir auf eine physische Seite zugreifen, finden wir immer die Karte, die dieser Seite zugeordnet ist, und verschieben sie an das Ende des Stapels.

Das ist es. Ich zeige das Deck zusammen mit jedem gemachten Schritt.

Jetzt müssen Sie sich nur noch "wie der Computer verhalten" und die Arbeit von Hand erledigen, indem Sie die Liste der aufeinanderfolgenden Adressen der Reihe nach durchgehen. Es ist nur einfache Handarbeit.

Jede virtuelle Adresse hat eine Seite und einen Offset . Der Offset- Wert sind die niederwertigen 9 Bits der virtuellen Adresse und die Seite sind die oberen 3 Bits der virtuellen Adresse. Die Logik ist wie folgt:

Wenn der virtuelle Tabelleneintrag ungültig ist, dann weise eine Seite aus einer Liste freier physischer Seiten zu. Wenn jedoch keine freien physikalischen Seiten übrig sind, dann ordnen Sie aus einer Suche nach gültigen virtuellen Tabelleneinträgen die physikalische Seite aus dem virtuellen Tabelleneintrag zu, der die am längsten nicht verwendete Seite enthält. Markieren Sie in diesem Fall auch den gefundenen Eintrag in der virtuellen Tabelle als ungültig, da die physische Seite, die ihm gehört, jetzt neu zugewiesen wird. Nehmen Sie dann diese physische Seite und platzieren Sie sie in den aktuellen virtuellen Tabelleneintrag und markieren Sie sie als gültig. Ziehen Sie schließlich diesen virtuellen Tabelleneintrag an den Anfang der LRU-Liste, um anzuzeigen, dass er erst vor kurzem verwendet wurde.

Wenn der virtuelle Tabelleneintrag als gültig markiert ist, dann ziehe diesen virtuellen Tabelleneintrag an den Anfang der LRU-Liste, was wiederum anzeigt, dass er erst vor kurzem verwendet wurde.

Der obige Algorithmus wird immer wieder für jede Ihrer virtuellen Adressen der Reihe nach wiederholt. Es ignoriert die Details der Bildung der vollständigen physikalischen 11-Bit-Speicheradresse. Aber um diesen Teil brauche ich mich nicht zu kümmern, denn Ihre Frage bezieht sich nicht darauf, sondern darauf, wie dieser Tisch in den Zustand geraten ist, in dem er war. Ich vernachlässige dieses Detail, um hier übermäßige Details zu vermeiden.

Hier sind die Schritte mit Ihren Adressen in der angegebenen Reihenfolge:

$$\begin{array}{lrllll} \underline{\textrm{Step}} & {\underline{~~~~~~~~~~~~~~~~~~~~\textrm{Action}~~}} & \underline{\textrm{Free}} & \underline{\textrm{LRU}} & \underline{\textrm{Valid}~~~~~~~~~~~} & \underline{\textrm{Frame}~~~~} \\ & & 0123 & & \textrm{FFFFFFFF} & \textrm{oooooooo} \\ & \textbf{new address 1:265} & & & & \\ (1) & alloc = free & 123 & & \textrm{FFFFFFFF} & \textrm{oooooooo} \\ (2) & frame_1 = alloc & 123 & & \textrm{FFFFFFFF} & \textrm{o0oooooo} \\ (3) & valid_1 = true & 123 & & \textrm{FTFFFFFF} & \textrm{o0oooooo} \\ (4) & LRU(1) & 123 & 1 & \textrm{FTFFFFFF} & \textrm{o0oooooo} \\ & \textbf{new address 3:511} & & & & \\ (1) & alloc = free & 23 & 1 & \textrm{FTFFFFFF} & \textrm{o0oooooo} \\ (2) & frame_3 = alloc & 23 & 1 & \textrm{FTFFFFFF} & \textrm{o0o1oooo} \\ (3) & valid_3 = true & 23 & 1 & \textrm{FTFTFFFF} & \textrm{o0o1oooo} \\ (4) & LRU(3) & 23 & 31 & \textrm{FTFTFFFF} & \textrm{o0o1oooo} \\ & \textbf{new address 2:175} & & & & \\ (1) & alloc = free & 3 & 31 & \textrm{FTFTFFFF} & \textrm{o0o1oooo} \\ (2) & frame_2 = alloc & 3 & 31 & \textrm{FTFTFFFF} & \textrm{o021oooo} \\ (3) & valid_2 = true & 3 & 31 & \textrm{FTTTFFFF} & \textrm{o021oooo} \\ (4) & LRU(2) & 3 & 231 & \textrm{FTTTFFFF} & \textrm{o021oooo} \\ & \textbf{new address 2:76} & & & & \\ (4) & LRU(2) & 3 & 231 & \textrm{FTTTFFFF} & \textrm{o021oooo} \\ & \textbf{new address 1:34} & & & & \\ (4) & LRU(1) & 3 & 123 & \textrm{FTTTFFFF} & \textrm{o021oooo} \\ & \textbf{new address 0:129} & & & & \\ (1) & alloc = free & & 123 & \textrm{FTTTFFFF} & \textrm{o0o1oooo} \\ (2) & frame_0 = alloc & & 123 & \textrm{FTTTFFFF} & \textrm{3021oooo} \\ (3) & valid_0 = true & & 123 & \textrm{TTTTFFFF} & \textrm{3021oooo} \\ (4) & LRU(0) & & 0123 & \textrm{TTTTFFFF} & \textrm{3021oooo} \\ & \textbf{new address 6:129} & & & & \\ (1) & alloc = frame_{LRU} & & 012 & \textrm{TTTFFFFF} & \textrm{3021oooo} \\ (2) & frame_6 = alloc & & 012 & \textrm{TTTFFFFF} & \textrm{3021oo1o} \\ (3) & valid_6 = true & & 012 & \textrm{TTTFFFTF} & \textrm{3021oo1o} \\ (4) & LRU(6) & & 6012 & \textrm{TTTFFFTF} & \textrm{3021oo1o} \\ \end{array}$$

Ich denke, Sie sollten in der Lage sein, den letzten Eintrag oben mit Ihrer Tabelle abzugleichen. Der einzige Trick besteht hier darin, zu beachten, dass der virtuelle LRU-Tabelleneintrag „3“ ist, aber die physische Seite, die diesem virtuellen Tabelleneintrag gehört, die physische Seite „1“ ist. Der virtuelle Tabelleneintrag für '3' wird als falsch markiert, aber die alloc- Variable wird auf 1 gesetzt, da dies die physische Seite ist, die dort zugewiesen wurde.

EDIT: Zu deiner Frage:

Ich verstehe die Reihenfolge der zweiten Tabelle nicht. Warum haben wir mit 11 angefangen, dann 00, dann 10 usw. Das ergibt für mich keinen Sinn...

Wir haben nicht mit 11 begonnen . Diese Spalte ist die physische Seitenzahl. Offensichtlich haben wir die physische Seite 3 (11 binär) nicht sofort zugewiesen. Stattdessen stellte sich heraus, dass bei Adresse 0:129 nur noch eine freie physische Seite übrig war – Seite 3. Aber die kommt natürlich in die virtuelle Seitentabellenreihe 0! Weil die von 0:129 referenzierte virtuelle Seite Zeile 0 in der virtuellen Tabelle ist. Aber die physische Seite (Frame) ist 3. Also wird dort 3 gespeichert (11 binär.)

Die in der ersten Tabelle angegebenen Adressen sind virtuelle Adressen in einem 12-Bit-Adressraum, und der Zweck der Seitentabelle besteht darin, diese physikalischen Adressen zuzuordnen. Da Seiten 512 Bytes groß sind und es 4 physikalische Seiten gibt, sind die physikalischen Adressen 11 Bit, bestehend aus einer 2-Bit-Rahmennummer und einem 9-Bit-Offset. Die Seitentabelle hat acht Schlitze, einen für jede Seite im virtuellen Adressraum. (Das ist natürlich alles völlig unpraktisch, aber das ist die Natur von Lehrbuchproblemen.)

Gemäß der Hypothese der Frage beginnt die Seitentabelle leer mit gültig = 0 in jedem Slot. Nach der Reihenfolge der Speicherreferenzen in der ersten Tabelle ist die erste Referenz auf Seite 1. Das ist ein Seitenfehler, weil das gültige Bit in Steckplatz 1 natürlich 0 ist. Also holen wir Seite 1 von der Platte, legen sie ein physische Seite 0, und aktualisieren Sie die Seitentabelle mit

1: frame=0, valid=1

Der nächste Verweis (2047) ist auf Seite 3 – wieder ein Fehler. Also fügen wir die virtuelle Seite 3 in die physische Seite 1 ein und aktualisieren die Seitentabelle mit

3: frame=1, valid=1

An dieser Stelle (nur um das klarzustellen) enthält die Seitentabelle

0:          valid=0
1: frame=0, valid=1
2:          valid=0
3: frame=1, valid=1
4:          valid=0
5:          valid=0
6:          valid=0
7:          valid=0

so dass für jede virtuelle Seitenzahl, die wir verwendet haben, die Seitentabelle die entsprechende physische Seitenzahl anzeigt. Diese Organisation macht die hardwareimplementierte Übersetzung von virtuellen zu physikalischen Adressen einfach und schnell.

Als nächstes folgt Seite 2, physisch Seite 2. Seitentabelleneintrag:

2: frame=2, valid=1

Der nächste Verweis erfolgt wieder auf die virtuelle Seite 2, so dass dies keinen Seitenfehler verursacht. Dann wieder virtuelle Seite 1, ebenfalls ohne Fehler. Als nächstes kommt die virtuelle Seite 0, die zur physischen Seite 3 gehört

0: frame=3, valid=1

Die letzte Referenz ist die virtuelle Seite 6, die wir vorher noch nicht gesehen haben. Wir müssen einen Seitenrahmen zuweisen, aber zu diesem Zeitpunkt werden alle 4 verwendet, was bedeutet, dass eine vorhandene Seite entfernt werden muss, um Platz zu schaffen. Um das Opfer auszuwählen, befolgen wir eine Ersetzungsrichtlinie, die in Software implementiert ist – und uns wird gesagt, dass wir die Richtlinie „Am wenigsten kürzlich verwendet“ verwenden sollen. Also suchen wir nach der residenten Seite, die am längsten nicht verwendet wurde, und das ist Seite 3. Wir entfernen diese Seite, holen Seite 6 herein und aktualisieren die Seitentabelle zum Lesen

3: (frame=1), valid=0
6: frame=1, valid=1

Das Frame-Feld von Slot 3 spielt keine Rolle, aber wir können es genauso gut bei 1 belassen. Wenn Sie alle Einträge zusammenfügen, erhalten Sie die Seitentabelle, die in Ihrer zweiten Tabelle angezeigt wird. Die Framenummern werden dort natürlich binär angezeigt.