Maximal effizientes Speichermanagement ?
-
Hoi!
Ich hab mir mal etwas überlegt, wie man möglichst zeiteffizient Best-Fit Speicher allozieren könnte und hätte gerne ein paar Abschätzungen dazu.
Die meisten Implementierungen von malloc nutzen ja intern verlinkte Listen, in denen benutzter/freier Speicher verwaltet wird, der im Regelfall per First/Next-Fit geholt wird.
Das führt doch im worst Case zu einem linearen Aufwand und die Fragmentierung ist auch relativ hoch.
Jetzt zu meiner Idee: Ich möchte array-basierten, binären Baum schreiben (bewahrt mich davor, Speicherverwaltung für die Speicherverwaltung zu schreiben.) Klar ist das schon mal ein Speicheroverhead, aber da man weder Child- noch Parent-Pointer braucht, da man ja alles anhand des aktuellen Indexes berechnen kann, hält sich das auch stark in Grenzen. Wachsen ist halt recht teuer, sollte aber ja auch nur selten vorkommen.
Als Baumtyp käme wohl nur AVL in Frage, da bei einer arraybasierte Implementierung die optimale Balance fast erforderlich ist.Von diesen Bäumen bräuchte meine Idee 2 Stück, einer enthält die freien Bereiche, die baumtypisch abgehangelt werden (Wenn der aktuelle Bereich zu klein/groß ist, wird das linke/rechte Child besucht, bis man den bestpassenden Bereich gefunden hat). Übriger Speicher wird wieder an den Baum angehängt. Der zweite Baum wäre ein typisches Set mit der Addresse als Key, in dem belegter Speicher verwaltet wird.
Das würde doch immer den perfekten Speicherbereich rausholen, mit einer Worst-Case Komplexität von log(n).
Bevor ich es mal testweise implementiere, spricht etwas dagegen? Hab ich einen Logikfehler? Oder wird das so ähnlich bereits gemacht?
Danke schon mal. ,)
Grüße,
Ethon
-
Ethon schrieb:
Jetzt zu meiner Idee: Ich möchte array-basierten, binären Baum schreiben
Doch nicht am Ende einen Buddy Allokator?
-
volkard schrieb:
Ethon schrieb:
Jetzt zu meiner Idee: Ich möchte array-basierten, binären Baum schreiben
Doch nicht am Ende einen Buddy Allokator?
Meinst du dass meine Idee Buddy sehr ähnlich ist oder Buddy unterlegen ist?
Aber wenn ich das Konzept nicht total falsch verstanden habe, besteht da doch ein riesen Unterschied?
-
Ethon schrieb:
Von diesen Bäumen bräuchte meine Idee 2 Stück, einer enthält die freien Bereiche, die baumtypisch abgehangelt werden (Wenn der aktuelle Bereich zu klein/groß ist, wird das linke/rechte Child besucht, bis man den bestpassenden Bereich gefunden hat).
Also die Größe des Bereichs als Schlüssel.
Ethon schrieb:
Übriger Speicher wird wieder an den Baum angehängt.
Und mit freien Nachbarbereichen gemerged.
Hier liegt ein Pudel begraben.
Du brauchst auch einen Baum für freie Bereiche, der die Adresse als Schlüssel hat.Ethon schrieb:
Der zweite Baum wäre ein typisches Set mit der Addresse als Key, in dem belegter Speicher verwaltet wird.
Wozu? Den belegten Speicher verwaltet der User.
-
Ethon schrieb:
Meinst du dass meine Idee Buddy sehr ähnlich ist oder Buddy unterlegen ist?
Der Buddy wird schneller sein, aber nicht viel mehr als fünfmal so schnell, schätze ich.
Ich wollte nur sichergehen, daß Du den Buddy Allokator kennst, und bewußt etwas anderes machst. Nicht, daß Du in monatelanger Arbeit Deinen Allokator so weit verfrickelst, optimiert, vereinfachst, bist Du beim Buddy ankommst.
Ethon schrieb:
Aber wenn ich das Konzept nicht total falsch verstanden habe, besteht da doch ein riesen Unterschied?
Ja.
-
Als Verbesserung des Buddy Allocators gibt es den http://de.wikipedia.org/wiki/Slab_allocator
-
Th69 schrieb:
Als Verbesserung des Buddy Allocators gibt es den http://de.wikipedia.org/wiki/Slab_allocator
OK, Small-Object-Allocators sollte man nicht vergessen. Um mehr Wert auf große Objekte zu legen und irgendwo ab vielleicht 256 Bytes nicht mehr zu optimieren.
Slab ist nicht Buddy-Spezifisch, sondern nur eine Endstufe, die man hinter jeden allgemeinen Allokator hängen kann. Wobei man als Nicht-Kernel auch nicht genau wie Slab vorgeht.
