Anregungen: Verwalten einer "Dynamischen Menge"

[Panke]

Die Aufgabe scheint es doch zu sein, eine Dynamische Verwaltung für eine Unbestimmte Menge an Objekten zu programmieren. Diese Verwaltung muss schnell und Sparsam sein. Du hast nur die Möglichkeit 4kb Blöcke anzufragen, sodass einfach für jedes Objekt einen neuen Block anzufragen nicht Funktioniert. Und das ist egt alles, was ich finde wichtig ist für dieses Problem das es zu Lösen gilt.

Ja, das ist das, was uns hier als Aufgabe gestellt wurde. Ich finde, dass ist bereits ein
Lösungsansatz, zu einer Problemstellung, die wir aber nicht kennen. Ob es der richtige Lösungsansatz ist, kann man aber nicht beurteilen. Sicher stecken da auch eine Menge impliziter Annahmen drin, von denen wir (aber) auch nichts wissen.

Wenn man die Güte einer Speicherverwaltung bewerten will, muss man halt ihren Kontext kennen. Siehe fat-lobytes Nachfragen. Ich möchte halt mehr wissen, bevor ich anfange loszuraten.

Tut mir Leid, wenn das bei dir irgendwie arrogant ankam oder ähnlich.

Edit: Ich fange dann mal an loszuraten

Egal was du baust, ich denke es wird immer darauf hinauslaufen, dass du die Elemente irgendwann umspeichern musst, um eine Defragmentierung zu vermeiden. Es sei denn, du kannst die Reihenfolge beim Löschen mit einer gewissen Wahrscheinlichkeit garantieren.

Wenn du aber umspeicherst, musst du Referenzen anpassen, denn die sollen ja bei dir
gültig bleiben. Das wird immer lange dauern, für eine gewisse Definition von "lange".

Vor dem gleichen Problem steht auch eine Garbage Collection, nur dass die noch selber
rausfinden müssen, wann ein Objekt Müll ist und wann nicht. Vielleicht kriegst du da noch weitere Anregungen.

Von mir hier ein Ansatz:

2. Eine eigene Hashtable, wie von cloidnerux vorgeschlagen. In "Algorithmen und Datenstrukturen" von Saake, Sattler wird eine Hashtable vorgestellt, die dynamisch wachsen kann, indem mehr bits vom Schlüssel signifikant werden. Das könntest du adaptieren.

[canlot]

Weißt du überhaupt was Speicherverwaltung ist?
Es kommt ihrgentwie rüber dass du keiner Ahnung davon hast.

[Xin]

Weißt du überhaupt was Speicherverwaltung ist?
Es kommt ihrgentwie rüber dass du keiner Ahnung davon hast.

Da Lob in bedenklicher Orthographie als solche nicht gut verständlich sind, bitte ich entweder auf Rechtschreibung zu achten oder Höflichkeiten dieser Art gleich anders zu formulieren.

Ich habe mir den Thread nun auch mal angeguckt. Die interessanten Threads verschiebe ich oft auf später und dann sehe ich sie irgendwann nicht mehr, weil sie ja nicht mehr neu sind. *grummel*

Zum Thread:
Interessante Problemstellung. Ich sehe hier drei Konzepte, die man kombinieren könnte:

1.) MemoryPool: Du alloziierst Speicher für gleich 2^n Objekte am Stück. Die Anforderung an das OS, um Speicher zu erhalten, ist sehr kostenintensiv. Du hast so 2^n Elemente, die Du mit "internen Indizes" addressieren kannst (wobei die internen Indizes im Idealfall gleich die Adresse im Array sind)
Da Du freigeben kannst brauchst Du für jeden Memorypool eine doppelt verkettete Liste allen internen Indizes. Vorne die freien, am Ende die belegten Elemente. Brauchst du ein Element, nimmst Du Dir links einen Index raus und packst ihn ans Ende. Gibst Du ihn frei, packst Du den Index wieder an den Anfang.
2.) Referenzen: Jeder Memory-Pool braucht eine Tabelle mit den externen Indizes, die von 0 bis (2^n)-1 gehen. In der Tabelle steht der interne Index, so dass Du mit dem externen Index direkt weißt, wo Du die Daten im MemoryPool findest.
3.) Bereiche im Index. Ein Memory Pool ist immer 2^n Elemente groß. Ist n == 5, hast Du pro Pool 32 Elemente. Brauchst Du mehr Elemente, so brauchst Du weitere Memory-Pools. Du brauchst also einen Wrapper, der mit den hinteren 5 Bit das Element im Pool raussucht und mit den höherwertigen Bits aus einem eigenen Pool-Array den richtigen Memory-Pool herausholt.

Damit hast Du pro Zugriff die Zerlegung des Index, den Zugriff auf das Memorypool-Array, den Zugriff auf die Referenztabelle im Memorypool und dann den Zugriff auf das Datenelement.
Die Liste im Memorypool, die die freien und belegten Elemente verwaltet, kannst Du Dir auch in den Wrapper legen, so dass Du schnell weißt, in welchem Pool noch Elemente frei sind und wo nicht - dann sind die Indizes nach einer Freigabe allerdings nicht mehr fortlaufend, sondern würden wiederverwertet.

Der Worstcase in dem Szenario sind 1000 Elemente, die auf 32000 alloziierten Elementen verteilt sind. Würde ich aber als unwahrscheinlich ansehen. Wenn Du zwischen den Pools verschieben willst, musst Du für den festen, externen Index eine Hashtabelle für die "externen Index" aufbauen.

[canlot]

Da Lob in bedenklicher Orthographie als solche nicht gut verständlich sind, bitte ich entweder auf Rechtschreibung zu achten oder Höflichkeiten dieser Art gleich anders zu formulieren.

Hm.
Deutsch war noch nie meine Stärke und wird es auch wohl nie sein

[Xin]

Da Lob in bedenklicher Orthographie als solche nicht gut verständlich sind, bitte ich entweder auf Rechtschreibung zu achten oder Höflichkeiten dieser Art gleich anders zu formulieren.

Hm.
Deutsch war noch nie meine Stärke und wird es auch wohl nie sein

Die Rechtschreibung interessiert mich in dem Fall nicht, sondern der Austausch von Höflichkeiten.
Fachliches, Fakten, Smalltalk und Spaß - kein Problem. Jemanden runter zu machen, ist nicht erwünscht. Wenn man es besser weiß, darf man sich gerne korrigierend zu Wort melden und auf das Missverständnis hinweisen.
Ohne irgendein Fakt hinzulegen, jemanden runterzumachen, das darf man sich schenken.

Formuliere Deine Aussagen bitte so, dass sie nicht als Angriff aufzufassen sind - auch nicht im Ansatz.

Wenn es eine Regel gibt, die ich hier auch nicht im Ansatz diskutieren werde, dann die eines akzeptablen Umgangs miteinander.
Akzeptiert? Dann ist dieses Thema hiermit gegessen.

In "Algorithmen und Datenstrukturen" von Saake, Sattler wird eine Hashtable vorgestellt, die dynamisch wachsen kann, indem mehr bits vom Schlüssel signifikant werden. Das könntest du adaptieren.

Narf... Java... :-/

In Sachen D&A will ich meine Bibliothek aufrüsten. Ist zwar alles portabel, aber Java nervt trotzdem.

[Dirty Oerti]

Ja, das ist das, was uns hier als Aufgabe gestellt wurde. Ich finde, dass ist bereits ein
Lösungsansatz, zu einer Problemstellung, die wir aber nicht kennen. Ob es der richtige Lösungsansatz ist, kann man aber nicht beurteilen. Sicher stecken da auch eine Menge impliziter Annahmen drin, von denen wir (aber) auch nichts wissen.

Wenn man die Güte einer Speicherverwaltung bewerten will, muss man halt ihren Kontext kennen. Siehe fat-lobytes Nachfragen. Ich möchte halt mehr wissen, bevor ich anfange loszuraten.

Ok, also diese Speicherverwaltung ist gedacht für die Verwaltung der Prozesse/Tasks meines Kernels.
Die Vorgabe mit den 4KB Blöcken bekomme ich also von der Hardware, genauer gesagt der MMU (Memory Management Unit) und deren Paging.

Eine Task-Struktur ist in diesem Fall definiert als eine Ansammlung (10, wenn ich mich nicht irre) Bytes, die eben wichtige Informationen (Adresse des Page Directories, ID, sonstwas) enthält.

Nun ist auch klar, es kann viele dieser Strukturen geben (wenn viele Task's laufen), aber eben auch wenige.

Tut mir Leid, wenn das bei dir irgendwie arrogant ankam oder ähnlich.[/qoute]
Kein Problem

Egal was du baust, ich denke es wird immer darauf hinauslaufen, dass du die Elemente irgendwann umspeichern musst, um eine Defragmentierung zu vermeiden. Es sei denn, du kannst die Reihenfolge beim Löschen mit einer gewissen Wahrscheinlichkeit garantieren.

Das ist das Problem, ich muss möglichst die Fragmentierung klein halten, da nachträglich defragmentieren meist viel zu zeitintensiv ist.
Die Reihenfolge beim Löschen kann ich nicht garantieren, es ist zwar oft so, dass Tasks, die früher starten, auch früher beenden, aber es ist auch klar, dass es dafür mehr als genug Ausnahmen gibt "Init" z.B. ^^

2. Eine eigene Hashtable, wie von cloidnerux vorgeschlagen. In "Algorithmen und Datenstrukturen" von Saake, Sattler wird eine Hashtable vorgestellt, die dynamisch wachsen kann, indem mehr bits vom Schlüssel signifikant werden. Das könntest du adaptieren.

Hm, wie eine Hashtabelle funktioniert weiß ich (Algo-Dat von Cormen et al)
Problem ist eben, wie fordere ich den Speicher für die Tabelle an?
Ich bekomme nur 4KB Blöcke Und ich muss auch die genaue Adresse (virtuelle) selbst festlegen, sprich ich bekomme keinen Zeiger, sondern muss mir überlegen, wo der Speicherbereich hin soll.

Weißt du überhaupt was Speicherverwaltung ist?

Ich? Ja ^^ Sehr genau sogar, im Bezug auf die unterschiedlichsten Abstraktionsstufen einer Speicherverwaltung. Ich weiß auch, wie das "echte" malloc funktioniert und implementiert ist.

1.) MemoryPool: Du alloziierst Speicher für gleich 2^n Objekte am Stück. Die Anforderung an das OS, um Speicher zu erhalten, ist sehr kostenintensiv. Du hast so 2^n Elemente, die Du mit "internen Indizes" addressieren kannst (wobei die internen Indizes im Idealfall gleich die Adresse im Array sind)
Da Du freigeben kannst brauchst Du für jeden Memorypool eine doppelt verkettete Liste allen internen Indizes. Vorne die freien, am Ende die belegten Elemente. Brauchst du ein Element, nimmst Du Dir links einen Index raus und packst ihn ans Ende. Gibst Du ihn frei, packst Du den Index wieder an den Anfang.
2.) Referenzen: Jeder Memory-Pool braucht eine Tabelle mit den externen Indizes, die von 0 bis (2^n)-1 gehen. In der Tabelle steht der interne Index, so dass Du mit dem externen Index direkt weißt, wo Du die Daten im MemoryPool findest.
3.) Bereiche im Index. Ein Memory Pool ist immer 2^n Elemente groß. Ist n == 5, hast Du pro Pool 32 Elemente. Brauchst Du mehr Elemente, so brauchst Du weitere Memory-Pools. Du brauchst also einen Wrapper, der mit den hinteren 5 Bit das Element im Pool raussucht und mit den höherwertigen Bits aus einem eigenen Pool-Array den richtigen Memory-Pool herausholt.

Ok, Punkt 1 hat mir sehr geholfen, speziell die Idee mit der frei/nicht frei Liste, die du da hast.
Die werde ich annehmen für die Speicherverwaltung, die noch näher an der Hardware ist (also die, die sagt, welcher 4KB Block - physikalische Adresse - frei ist und welcher nicht)
Punkt 2 verstehe ich jetzt nicht ganz. Meinst du damit einfach nur die Umrechnung externer Indizes auf interne?
Punkt 3 hat mich an meine Implementierung der grundlegenden Speicherverwaltung erinnert:
Ein Bitfeld, dass angibt, welche Blöcke frei sind und welche nicht (die Adresse des Blocks berechnet sich aus der Position eines Bits im Bitfeld, und umgekehrt)
Dann noch ein "Master-Bitfeld", welches anstatt Blöcke die anderen Bitfelder verwaltet.
Hierbei hatte ich natürlich den Vorteil, genau zu wissen, wieviele Speicherblöcke ich verwalten muss. Deren Anzahl ändert sich ja nun auch nicht. Bei der Verwaltung der Tasks habe ich aber das Problem...

Damit hast Du pro Zugriff die Zerlegung des Index, den Zugriff auf das Memorypool-Array, den Zugriff auf die Referenztabelle im Memorypool und dann den Zugriff auf das Datenelement.
Die Liste im Memorypool, die die freien und belegten Elemente verwaltet, kannst Du Dir auch in den Wrapper legen, so dass Du schnell weißt, in welchem Pool noch Elemente frei sind und wo nicht - dann sind die Indizes nach einer Freigabe allerdings nicht mehr fortlaufend, sondern würden wiederverwertet.

Das ist nicht weiter drastisch, nach einer Freigabe kann ein Index ruhig wieder verwendet werden.

Wie verhindere ich zu starke Fragmentierung?

Der Worstcase in dem Szenario sind 1000 Elemente, die auf 32000 alloziierten Elementen verteilt sind. Würde ich aber als unwahrscheinlich ansehen. Wenn Du zwischen den Pools verschieben willst, musst Du für den festen, externen Index eine Hashtabelle für die "externen Index" aufbauen.

Hm, damit hab ich wieder das Problem, wie ich die Hashtabelle organisiere?

[canlot]

canlot hat geschrieben:Weißt du überhaupt was Speicherverwaltung ist?


Ich? Ja ^^ Sehr genau sogar, im Bezug auf die unterschiedlichsten Abstraktionsstufen einer Speicherverwaltung. Ich weiß auch, wie das "echte" malloc funktioniert und implementiert ist.

Nicht du Ich meinte Panke
ich weiß das du dich damit bis ins Detail auskennst, weil du dein BS programmierst.

[Xin]

1.) MemoryPool: Du alloziierst Speicher für gleich 2^n Objekte am Stück. Die Anforderung an das OS, um Speicher zu erhalten, ist sehr kostenintensiv. Du hast so 2^n Elemente, die Du mit "internen Indizes" addressieren kannst (wobei die internen Indizes im Idealfall gleich die Adresse im Array sind)
Da Du freigeben kannst brauchst Du für jeden Memorypool eine doppelt verkettete Liste allen internen Indizes. Vorne die freien, am Ende die belegten Elemente. Brauchst du ein Element, nimmst Du Dir links einen Index raus und packst ihn ans Ende. Gibst Du ihn frei, packst Du den Index wieder an den Anfang.
2.) Referenzen: Jeder Memory-Pool braucht eine Tabelle mit den externen Indizes, die von 0 bis (2^n)-1 gehen. In der Tabelle steht der interne Index, so dass Du mit dem externen Index direkt weißt, wo Du die Daten im MemoryPool findest.
3.) Bereiche im Index. Ein Memory Pool ist immer 2^n Elemente groß. Ist n == 5, hast Du pro Pool 32 Elemente. Brauchst Du mehr Elemente, so brauchst Du weitere Memory-Pools. Du brauchst also einen Wrapper, der mit den hinteren 5 Bit das Element im Pool raussucht und mit den höherwertigen Bits aus einem eigenen Pool-Array den richtigen Memory-Pool herausholt.

Ok, Punkt 1 hat mir sehr geholfen, speziell die Idee mit der frei/nicht frei Liste, die du da hast.

Diese Liste implementierst Du aber natürlich nicht als Liste, sondern als Array bei der jedes Element einen mit Zeiger auf den Nachfolger hat. Du hast ja eine fixe Größe der Liste, die weder größer noch kleiner wird. Also brauchst Du keine vollständig implementierte Liste.

Punkt 2 verstehe ich jetzt nicht ganz. Meinst du damit einfach nur die Umrechnung externer Indizes auf interne?

Yepp.
Wobei intern das eigentliche Datenelement ist und "extern" nur der Teil des Index ist, der für den Memorypool zuständig ist.

Punkt 3 hat mich an meine Implementierung der grundlegenden Speicherverwaltung erinnert:
Ein Bitfeld, dass angibt, welche Blöcke frei sind und welche nicht (die Adresse des Blocks berechnet sich aus der Position eines Bits im Bitfeld, und umgekehrt)
Dann noch ein "Master-Bitfeld", welches anstatt Blöcke die anderen Bitfelder verwaltet.
Hierbei hatte ich natürlich den Vorteil, genau zu wissen, wieviele Speicherblöcke ich verwalten muss. Deren Anzahl ändert sich ja nun auch nicht. Bei der Verwaltung der Tasks habe ich aber das Problem...

Wenn Du die Größe der zu verwaltenden Datenstruktur kennst, kannst Du ja mehr Speicher nehmen, als Du brauchst, Du musst ihn ja nicht nutzen.

Damit hast Du pro Zugriff die Zerlegung des Index, den Zugriff auf das Memorypool-Array, den Zugriff auf die Referenztabelle im Memorypool und dann den Zugriff auf das Datenelement.
Die Liste im Memorypool, die die freien und belegten Elemente verwaltet, kannst Du Dir auch in den Wrapper legen, so dass Du schnell weißt, in welchem Pool noch Elemente frei sind und wo nicht - dann sind die Indizes nach einer Freigabe allerdings nicht mehr fortlaufend, sondern würden wiederverwertet.

Das ist nicht weiter drastisch, nach einer Freigabe kann ein Index ruhig wieder verwendet werden.

Wie verhindere ich zu starke Fragmentierung?

Wenn Du gleichgroße Datenstrukturen hast, verhindern Memorypools Fragmentierung, erstens weil sie die Fluktuation verringern und zweitens weil wenige große Blöcke verwendest statt viele kleiner.

Wenn Du die Indizes wiederverwenden kannst, dann solltest Du überhaupt kein Problem mit Fragmentierung haben und leere Memory-Pools kannst Du wieder abbauen. Ordnest Du die Pools nach Belegungsstärke, kannst Du stark belegte Pools füllen, während weniger stark belegte Pools sich leeren und abgebaut werden, wenn sie leer sind.

Der Worstcase in dem Szenario sind 1000 Elemente, die auf 32000 alloziierten Elementen verteilt sind. Würde ich aber als unwahrscheinlich ansehen. Wenn Du zwischen den Pools verschieben willst, musst Du für den festen, externen Index eine Hashtabelle für die "externen Index" aufbauen.

Hm, damit hab ich wieder das Problem, wie ich die Hashtabelle organisiere?

Wo genau ist das Problem?