Thema: Memory Management

[rochus]

Hi,
wollt mal eure Meinung zum Memory Management wissen:
was ist besser, zwei stacks (also einen für den zusammenhängenden Speicher, den z.B. DMA braucht und einen für "normalen" speicher), ein Stack (für alles eins), ein Bitmap? oder was kennt ihr noch bzw. welche Kombination?

gruß
rochus

PS: bitte qualifizierte antworten, d.h. begründet eure meinung bitte.

[mwoidt]

Ich denke mal, dass dein Betriebssystem Paging verwendet. Wenn nicht kannst du das Wort Page im folgenden auch als Sektor interpretieren. Ich halte auf jeden Fall Bitmaps für am schlechtesten, da man die Bitmap erstmal  durchsuchen muss, bevor man die nächste freie Page im Ram bekommt. Stacks sind meiner Meinung nach schon besser (Ich versteh unter Stack mal, dass die nächste freie Page immer oben drauf liegt). Für Paging sind leider auch Stacks nicht besonders toll, da man möglichst erstmal alles belegt haben will, bevor man anfängt auszulagern. Also sollte man vielleicht einen Stack für freie Pages verwenden und ein Speichermodell das ich gleich noch näher erläutere für Pages die ausgelagert werden können. Das Speichermodell, das die Pages, die ausgelagert werden können, verwaltet muss so funktionieren, dass jederzeit an einer beliebigen Stelle etwas eingefügt werden kann, da manche Pages seltener genutzt werden als andere und somit auch eher ausgelagert werden sollten. Ich bin grad mit der Entwicklung eines Memmory Managements für ein mein Betriebssystem beschäftigt und habe mir die oben

[mwoidt]

Irgendwie wurde nich alles oben angezeigt. Also hier der Rest:
genannten Kriterien mal überlegt. Die Problematik mit DMA war mir noch überhaupt nicht bewusst. Da muss ich mir auch mal was überlegen.

[TeeJay]

Also ich hatte mal folgende Idee in einem Buch gelesen und fand diese recht gut.

Jedes Programm enthält ja seinen eigenen Adressraum.
Und da hat jedes Programm ja auch einen Heap. Also einen "großen" Speicherbereich, der noch frei ist und mit Daten gefüllt werden kann.

Dieser Datenbereich ist nun durch ein Tag beschrieben. Dieses Tag sollte vom Kernel verwaltet werden. Es beinhaltet die Startadresse und die Größe des Speicherbereichs. Wenn nun Speicher vom Programm angefordert wird, so teilt der Kernel das Tag in 2. Ein Tag beschreibt nun den belegten und das andere den freien Bereich. Für jede Speicheranforderung wird immer ein neues Tag erstellt. Somit kann ich dann auch recht einfach per free() oder delete() den angeforderten Speicherbereich freigeben.

Das mit den Pages sollte mehr im Hintergrund laufen. Hat IMHO mit Speicherverwaltung im eigentlichen Sinne nicht so viel zu tun. Paging ist ja mehr dafür gedacht, das jedes Programm seinen eigenen Adressraum haben kann und das diese PAges auf Platte ausgelagert werden können, um Platz im Physikalischem Speicher zu schaffen.

Klar gehört Paging somit auch zum Memory Management, jedoch ist das halt auf einer sehr tiefen ebene. Und von dieser Ebene sollte ein Programm später nichts mehr mitbekommen.

mfg
TeeJay

[TeeJay]

Nachtrag:

Das mit dem Bitmap is auch eine schlechte Idee. Man benötigt ja dann theoretisch 1 Bit um 1 Byte im Speicher markieren zu können, ob dieses belegt oder frei ist.

Und jetzt rechne mal das du 1 GB Speicher hast. Du bräuchtest alleine ein Achtel nur um den Speicher zu verwalten. Sprich 128 MB. Das wäre wohl ein zu hoher Preis.

Klar könnte man auch mit einem Bit mehrere Bytes im Speicher ansprechen, was aber wieder zu fragmentierung und SPeicherverlust führt.

Stack finde ich auch nicht gut, weil du dann nicht die komplette Übersicht behälst. Du hast immer nur Adressen die auf den Stack gepusht oder gepopt werden. Wie machst du es dann wenn du mal Speicher brauchst, dessen Adresse erst in der Mitte des Stacks auftaucht?
Klar könnte man das auch berechnen und durch umkopieren des Stacks erreichen. Jedoch auch wieder viel Overhead. Speichermanagement sollte schnell sein

mfg
TeeJay

[mwoidt]

Du sagst ja nur das jedes Programm seinen eigenen Adressraum haben soll. Das is ja auch ganz nett. Aber woher willst du wissen wo im Physikalischen Ram noch speicher frei ist?

[TeeJay]

Ja das ist dann aufgabe des Codes der die Pages verwaltet. Der muß natürlich wissen welches Pages im RAM belegt sind und welche auf Platte ausgelagert sind.

Hier könnte man natürlich ein einfaches Bitmap ansetzen.
Jedoch wäre das zu einfach. Man muß ja die Pages auch effizient auslagern. Sprich die am wenigst benutzen Pages zuerst auf Platte auslagern. Also müsste man wohl schon etwas mehr als nur ein Bitmap benutzen um die Pages zu verwalten.

[mwoidt]

Mir ging es eigendlich mehr um den Code, der die Pages verwaltet .
Naja is ja auch egal. Das mit dem lokalen Speicherraum für alle Prozesse find ich eigendlich auch sinnvoll. Dal ließe sich ja auch leicht über eine LDT machen. Man sollte aber vielleicht darüber nachdenken, eine möglichkeit einzubauen, dass mehrere Threads sich einen Adressraum teilen können (ich glaub das nennt sich forken aber ich bin mir ehrlichgesagt in solchen Sachen nich so sicher)

[TeeJay]

Du brauchst nichtmal ne LDT. Alleine wenn du für jeden Prozess eine eigene Pagetable hast genügt das ja.

Und um sich adressraum zu teilen, richtest du einfach Pagetabels ein, die jedem Prozess zur Verfügung stehen. Du hast ja 4GB Adressraum zum aufteilen.
Da kannst du ja 2 GB für den Prozess selbst nehmen und die anderen 2 GB für gemeinsamen Adressraum (DLLs usw) und Kernel aufteilen.

Windows verfährt so.

[rochus]

hmm. mal in hinblick auf die 64bit CPU generation: der adressraum ändert sich von 2^32 auf 2^64, was ein verwalten der pagetables mit normalem pagin nicht mehr möglich macht (wird wahnsinnig groß!). da gibts dann die inverted page tables.

hat das schonmal jemand so implementiert, dass es klappt und hat es größere leistungs einbußen?

gruß

[TeeJay]

Was sind denn inverted Pagetables?

Davon hab ich noch nicht gehört.

Auch wenn du einen Adressraum von 2^64 hast, denke ich nicht das ein Betriebssystem diesen auch Grundsätzlich zu Verfügung stellet.

Man überlege das das 16777216 TerraByte sind

[rochus]

wie kommst du auf diese größe? ich les gerade "modern operating systems" von a.tanenbaum und der meinte, bei dem adressraum wird die page table 30 gigabyte groß. hmm..


naja, mit inverted page tables kannst du den adressraum wie folgt zur verfügung stellen:
bei normalen page tables hast du ja für jede virtual page nen eintrag in der page table. bei inverted hast du halt für jeden page frame nen eintrag. damit das suchen von virtual page -> page frame trotzdem schnell geht, nutzt man ne hardware table (TLB) mit ca. 64 einträgen..

[rochus]

achso, du meintest nur die 2^64 okay.. *langsam ist*

[TeeJay]

Der Clou is ja das man 4 MB benötigt um alleine die PageTables für einen 4 GB Adressraum zu verfügung zu stellen.

Man stelle sich vor das man für jeden Prozess der gerade läuft diese 4 MB an Pagetables erstellen würde. Da wäre das System ratz fatz dicht.

Als Ansatz würde ich sagen das man zuerst einfach mal nur das Page Directory erstellt. Das benötigt 4 KB. Dann kann man noch ein paar Page Tables erstellen. Diese benötigen ebenfalls je 4 KB. Pro Pagetable kann man 4 MB speicher adressieren.

Wenn dann mehr speicher benötigt wird, müssen halt neue Pagetables erstellt werden.

Jedenfalls wäre es blödsinn von vornherin schon 4 MB Pagetables zu erstellen.


Die Translation Lookaside Buffer (TLB) werden beim Paging automatisch benutzt.

Ich versteh immer noch nicht was du mit Inverted Pagetables meinst und was das bezwecken soll.

[FlashBurn]

Wieso ist eine Verwaltung mit Hilfe von Bitmaps shclecht, bzw. langsam? Man kann die Arbeit mit Bitmaps optimieren.

Ich nutze sie in meinem OS und es ist die einzigste Möglichkeit die mir eingefallen ist. Denn ich möchte nicht nur 4KiB Pages, sondern auch 4MiB Pages anfordern können! So dass die Stackvariante rausfällt. Zumal wenn man Multitasking einsetzt, wird man Paging nutzen und dort kann man immer nur 4KiB (im standard Modus) als kleinste Einheit verwenden, was die Bitmap auf 128KiB schrumpfen lässt. Diese 128KiB sind für mich vertretbarer als wenn ich einen Stack nutzen würde. Dann mal zu der DMA Geschichte. Darum würde ich mir keine Gedanken machen, denn ausser dem Floppydrive nutzt keiner mehr ISA-DMA, welcher nämlich auf 16MiB begrenzt ist. Wer eine Festplatte über IDE ansprechen will, kannn für DMA die vollen 4GiB nutzen!

[GhostCoder]

Hiho,

für die physikalischen pages benutz ich einen Stack, das brauchst zwar mehr Speicher, ist aber um einiges schneller, vorallem, da ich nie direkt aufeinander folgende Blöcke benötige (wegen Paging).

Für die virtuellen pages scanne ich einfach die pagetables des aktuellen prozesses nach freien hintereinanderliegenden blöcken, dadurch spare ich mir die bitmap und der code läuft schneller durch dwords als durch bits, da der pagetable ja sowieso vorhanden sein muss, also in jedem fall speicher brauch, ob bitmap oder nicht.

MfG GhostCoder

[JensFZ]

Hiho

Hat zwar nichts mit der unterhaltung zu tun aber der Athlon64 hat keine 64 Adressleitungen sonder nur 40 Physische und 48 inkl. virtuellen Adressleitungen

Nachzulesen unter http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/24659.PDF

[chr15]

G5 undf i64 haben auch noch nicht alle 64 Adressleitungen (irgendwie hat einer von denen 56 virtuelle oder so....). Stand mal alles in einer C'T