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.
Klausur WS2013/2014
Hi,
ich haenge gerade bei Aufgabe 3 (die auch fast 1:1 mal in einer Uebung dran kam).
Und zwar wird in der 2. Aufgabe nach den noetigen Seiten fuer die Verwaltungsinformationen gefragt
und in der 3. nach der Anzahl der Seiten fuer die Nutzdaten.
Kann mir jemand erklaeren, was genau mit Verwaltungsinformationen und Nutzdaten gemeint ist
und wie ich das aus den Angaben rauslesen kann?
Verwaltungsinformationen sind alle Tabellen, die man fuer die Paging-Datenstruktur braucht, also Page Directory und die dazugehoerigen Page Tables.
Nutzdaten sind diejenigen Daten, die mit den Tabellen verwaltet werden sollen, also die eigentlichen Betriebssystem- oder User-Pages.
Die Anzahl laesst sich entweder durch Abzaehlen der jeweiligen Seiten selbst bestimmen, oder man zaehlt die Eintraege in den Datenstrukturen:
Die Anzahl der Page Tables entspricht der Anzahl der gueltigen (Present-Bit) Eintraege in der Page Directory (denn fuer jeden solchen Eintrag existiert eine Page Table [1]). +1 fuer die Page Directory und du hast die Anzahl der Seiten fuer die Verwaltungsdaten.
Die Anzahl der Seiten fuer die Nutzdaten bekommst du analog, indem du alle gueltigen (Present-Bit) Eintraege in allen Page Tables zaehlst [2].
[1] Gibt genau genommen auch Huge Pages, da ist das etwas anders, nicht relevant fuer GRa.
[2] Außer wenn mehrere Eintraege auf die selbe physikalische Seite zeigen sollten, nicht relevant fuer GRa.
Ich kann ja aber nichts zählen, da steht ja nur, welche Bits wofür eingesetzt werden.
Laut Aufgabenstellung sind:
- die Bits 31-12 der virtuellen Adresse die höherwertigen Bits der physikalischen Adresse
- die Bits 11-4 unbenutzt
- die Bits 3-0 Flags
Ich muss doch bestimmt anhand der Angaben rausfinden können, wie viele Seiten für Verwaltungsinformationen und wie viele Seiten für die Nutzdaten verwendet werden.
Sorry, wenn ich mich da gerade dumm anstelle, aber ich kann mir das nicht herleiten.
Ja, das kannst du ja auch, denn die Adressbereiche sind ja gegeben.
Fuer die Nutzdaten bietet es sich hier an, ganz einfach die Größen der Adressbereiche zu bestimmen und aufzuaddieren. Fuer die Verwaltungsinformationen gehst du vor, wie oben beschrieben: Rausfinden, wie viele unterschiedliche Indices in Page Directory und Page Tables verwendet werden, indem die Adressen der Adressbereiche gemäß der Adressaufteilung in Indices und Offset zerlegt werden.
Hey hi 
schön dass wir hier mal über das THema reden. BIn grade auch davor.
Was ich nicht verstehe : ich habe eine 32 bit adresse 0x00001 002
bei dieser adresse, fungieren die ersten 10 bits von 00001 als index für das page directory, und die weiteren 10 bits von 00001 als index für die page.
Wann man dem Zeiger in der Page nachläuft dann benutzt man den offset um an den richtigen ort zu kommen.
in der aufgabenstellung heist es:
-31-12: höherwertige Bits der physikalische nAdresse
-11-4:unbenutzt
-(flag)3:Cache-disable-bit
-(flag)2:execute enable bit
-(flag)1:write-enable bit
-(flag)0:present-bit
meine höherwertigen bits sind die indices für pagedirectory und page oder ?
11-4 ist unbenutzt ? wo ist der offset hin, wo steht der ? gehören die flags mit zum offset?
und danach hast du (bro*) ja schon gut erklärt, kannst du uns vll kurz die lösung sagen, damit wir beim rechnen wissen ob wir richtig liegen, bzw. wenn nicht können wir nochmal an der rechnung rumbasteln bis sie stimmt. so lerne ich am besten
problem 1: “Berechnen Sie wie viele Seiten für die Verwaltungsinformation benötigt wird”
laut bro* alle pagedir einträge +1 → also 2^10 +1 ? richtig?
problem 2:“wie viele Seiten im Arbeitsspeicher werden für die Nutzdaten benötigt?”
arbeitspeicher ist doch viel zu klein, da passen doch selten alle Seiten rein, also ist es doch wurst wie viel seiten benötigt werden oder? also den satz an sich verstehe ich nicht so 
naja du hast gesagt “alle gültigen present bit einträge in den pagetables”
woher weiß ich bei wie vielen einträgen das presentbit gesetzt ist? 
Fragen über fragen, aber ist echt interessant das mal zu checken, wäre cool wenn du uns nochmal kurz an deinem wissen teilhaben lässt, dear br0gr4mm3r (will sagen : danke, dude, danke!!! )
Achtung, dabei handelt es sich um das Format der Eintraege in den Tabellen, nicht um die Adressaufteilung der virtuellen Adressen, die zur Bestimmung der Indices verwendet wird.
Die Grundidee beim Paging ist doch folgende: Wir wollen Speicherschutz, d.h. wir wollen zum einen eine Form von Zugriffschutz (nicht jeder Prozess darf einfach ueberall im Speicher rum schreiben, sondern nur an bestimmten Stellen, die ihm vom Betriebssystem zugewiesen wurden), zum anderen eine Art Rechteverwaltung (was darf der Prozess mit dem Stueck Speicher machen - lesen/schreiben/ausfuehren?). Wir haben einen byteweise adressierbaren Speicher, aber fuer jedes Byte einzeln Zugriffschutz und Rechteverwaltung aufzusetzen ist nicht praktikabel, denn der Overhead waere viel zu groß. Also teilt man den Speicher in zusammenhaengende Stuecke gleicher Groeße ein, die sog. Pages oder Seiten. Man setzt also eine Abbildung von virtuellen Seiten auf physikalische Seiten auf.
Wie du schon gesagt hast: Wenn ich einmal weiß, wo die physikalische Seite, die zu der referenzierten virtuellen Seite gehoert, im Speicher anfaengt, dann kann ich jedes Byte darin ueber einen Offset ansprechen. Dieser Offset besteht ganz einfach aus den letzten paar Bits der virtuellen Adresse (bei einer Seitengroeße von 4K = 2**12 Byte sind das entsprechend die hintersten 12 Bits).
Auf der Ebene dieser Pages setzen wir nun Zugriffschutz und Rechteverwaltung auf, d.h. zu jeder Page muss irgendwo die Information stehen, ob der Prozess auf diese Page zugreifen darf, und wenn ja, was er damit machen darf. Nun kann man sich bei einer typischen Page-Groeße von 4K (= 2^12 Byte) ueberlegen, dass man dann bei einem 32-Bit-Adressraum ganze 220 (= 232/212) Seiten verwalten muss. Gehen wir davon aus, dass man fuer jede Seite Informationen speichern muss, die man in 4 Byte abspeichern kann, so haette man 4MB alleine fuer die Verwaltungsinformationen, und das je Prozess! Das ist etwas viel Speicher und außerdem benutzt selten ein Prozess den gesamten Adressraum, d.h. es gibt „Luecken“ im virtuellen Adressraum, also Adressbereiche darin, die der Prozess nicht benutzen darf. Hier waere es schoen, wenn man fuer diese teilweise riesigen Luecken kaum Speicher fuer Verwaltungsinformationen „verschwenden“ wuerde. Man hat sich deshalb mehrstufiges Paging ueberlegt, also nicht eine einzelne Tabelle mit 220 Eintraegen sondern eine Tabellenhierarchie. Bei uns ist diese Hierarchie zweistufig, d.h. der zu einer virtuellen Adresse gehoerende Eintrag in der ersten Stufe (Page Directory) enthaelt einen Verweis auf eine Tabelle in der zweiten Stufe (Page Table). Innerhalb dieser Tabelle muss wieder mit der virtuellen Adresse der dazugehoerige Eintrag bestimmt werden, dieser enthaelt dann die eigentliche Verwaltungsinformation (also ob die Seite fuer den Prozess zugreifbar ist und was der Prozess damit machen darf). Die Information ist so codiert, wie von dir oben angegeben, d.h. jeder Eintrag besteht aus 4 Byte, die aussagen, wo die Seite physikalisch liegt und was der Prozess damit machen darf.
Jeder Eintrag in der Page Table verwaltet also eine Seite, d.h. ein Stueck zusammenhaengender Speicher der Groeße 4K. Jeder Eintrag in der Page Directory hingegen verwaltet eine ganze Menge an Seiten (alle die Seiten, die eben durch die entsprechende Page Table verwaltet werden) - wenn jetzt aber keine einzige dieser Seiten gueltig ist (d.h. der Prozess auf keine einzige dieser Seiten zugreifen darf), dann kann man sich die Page Table sparen und markiert ganz einfach in dem Eintrag der Page Directory, dass der ganze Bereich ungueltig ist (dies geschieht, indem das Present Bit des Eintrags nicht gesetzt wird - dadurch existiert keine Page Table fuer diesen Eintrag und alle Adressen, die in den durch den Eintrag verwalteten Bereich fallen, sind ungueltig). Das spart bei Luecken im Adressraum Speicher fuer Verwaltungsinformationen, weil wir dann weniger Page Tables brauchen.
Nun ist noch die Frage, wie wir die korrekten Eintraege in Page Directory und Page Table bestimmen. Dies funktioniert genau wie von dir beschrieben: Nachdem wir den Offset von der virtuellen Adresse „weggeschmissen“ haben, bleiben noch die vordersten 20 Bit uebrig. Die ersten 10 Bit davon nehmen wir als Index in die Page Directory, die restlichen 10 Bit als Index in die dazugehoerige Page Table. Warum 10 Bit? Naja, damit ergeben sich jeweils 2**10 Eintraege in den Tabellen, wobei jeder Eintrag eben 4 Byte groß ist, d.h. jede einzelne Tabelle ist dann 4K groß - und passt damit genau in eine Page (was die Verwaltung fuer Betriebssystem und Hardware deutlich einfacher macht). Fuer eine virtuelle Adresse ist also der Index in Page Directory und Page Table eindeutig festgelegt. Wenn ich die Informationen zu einer virtuellen Adresse wissen will, dann nehme ich zunaechst die Adressaufteilung vor. Anschließend schau ich mit dem Page-Directory-Index in der Page Directory nach. Dort finde ich die Information, ob zu diesem Eintrag eine Page Table existiert (Present-Bit, hier: Bit 0). Wenn ja, dann geben mir die vordersten 20 Bit die (physikalische) Anfangsadresse der Page Table an, womit ich Zugriff auf die Page Table bekomme (Hinweis: hier spielen die Flags, also Bits 1 bis 3, keine Rolle). Darin schaue ich dann mit dem Page-Table-Index nach. Der entsprechende Eintrag liefert mir dann die Information, ob die Seite zugreifbar ist (Present-Bit, hier: Bit 0), was ich damit machen darf (hier Bits 1-3), und wo die Seite physikalisch im Speicher liegt (hier: Bits 12-31).
Nein, kann ich nicht, denn die Loesung habe ich nicht 
Aber ein kleines Beispiel:
Angenommen, im virtuellen Adressbereich von 0xaa 0b b0 00 bis 0xaa 0b eF FF soll Code liegen (merke: 4 Pages). Zunaechst nehmen wir am Besten die Adressaufteilung von Anfangs- und Endadresse vor:
- Anfangsadresse:
** PD-Index: 0x2a8
** PT-Index: 0x0bb - Endadresse:
** PD-Index: 0x2a8
** PT-Index: 0x0be
Was bedeutet dies nun? Da PD-Index von Anfangs- und Endadresse gleich ist, gilt dies auch fuer alle Adressen, die dazwischen liegen, d.h. alle Adressen in diesem Adressbereich werden mit einem Eintrag in der Page Directory verwaltet, naemlich von dem Eintrag mit Index 0x2a8. Entsprechend muss fuer diesen Eintrag eine Page Table angelegt werden. Innerhalb dieser Page Table gehoeren die Eintraege 0x0bb, 0x0bc, 0x0bd und 0x0be (merke: 4 Eintraege, da 4 Pages) zu diesem Adressbereich, d.h. diese Eintraege werden als gueltig markiert (Present-Bit), die Flags werden gesetzt (fuer Code am wahrscheinlichsten nur das Execute-Enable-Bit), und die physikalischen Adressen werden eingetragen (das Betriebsystem sucht in diesem Fall 4 freie physikalische Seiten, kopiert den Code an diese Stelle und passt die Eintraege entsprechend an).
Die Situation ist nun also folgende: Wir haben eine Page Directory mit einem gueltigen Eintrag (0x2a8), alle anderen Eintraege sind ungueltig. Dementsprechend haben wir eine Page Table, in der vier Eintraege gueltig sind und auf Seiten verweisen, alle anderen 1020 Eintraege sind ungueltig. Mehr ist es nicht.
Nein, siehe oben. Nur fuer gueltige Eintraege existiert eine Page Table. Angenommen, der Adressbereich fuer den Code im obigen Beispiel ist der einzige gueltige Adressbereich. In diesem Fall haetten wir genau 2 Seiten fuer Verwaltungsinformationen (1 Seite fuer Page Directory, 1 fuer die einzige Page Table).
Das wiederum verstehe ich nicht… Im obigen Beispiel waeren es 4 Seiten (die 4 Seiten fuer den Code).
Adressaufteilungen wie oben gezeigt fuer alle gegebenen Adressbereiche machen und schauen, was dabei rauskommt.
3 Likes
Berechnung der Seiten
Nur nochmal dazu wie man die Anzahl der Seiten am leichtesten ausrechnet.
In der Übung wurde es leider nicht erklärt sondern direkt mit dezimal umgewandelten Zahlen gezeigt.
Das is aber für die Klausur nicht sinnvoll, denn es steht ja auch da, dass die Ergebnisse hexadezimal angegeben werden dürfen/sollen.
Wenn z.B ein Bereich von 0x00030000 bis 0x0003ffff geht, dann ist er ja 0x0000ffff groß, nun muss ich das ja noch durch 0x400 (1024 dez) teilen.
Klingt vll doof, aber wie geht das denn am einfachsten? (Sorry Zahlensysteme waren nie meine größte Stärke)
Nein, er ist dann 0x10000 groß, und du musst durch 2^12 teilen (Groeße einer Seite). Division durch eine Zweierpotenz 2^x ist das Gleiche wie ein Shift nach Rechts um x Stellen.
Du meinst dann also 4096 ist 16^3 und deswegen ein dreier-Shift nach rechts?! 
Ja, im Binaersystem 12 Stellen, im Hexadezimalsystem entsprechend 3.
Vielen vielen Dank brogr4mm3r.
Jetzt ist es echt klar
Dankeee habens jetzt voll gecheckt, danke fuer die muehe