Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Freispeichermanagement
3 views
Skip to first unread message
Andreas Wagner
Dec 13, 2022, 4:59:31 AM12/13/22
to
Hallo zusammen,
ich arbeite gerade an dem Freispeicher-Management für einen persistenten
AVL-Baums. Also auf Festplatte, in einer Datei. Nach dem Löschen eines
Knotens samt Daten will ich den freigegebenen Speicher wieder nutzen.
Meine Überlegung war, dafür zwei weitere AVL-Bäume zu nutzen, die die
freigegebenen "Löcher" managt:
1. Einen für eine Map, die die Position in der Datei auf die Größe des
freigegebenen Speichers abbildet: (Postition_in_Datei -> Größe_des_Lochs)
2. Eine für eine Map, die die Lochgrößen auf Wurzeln von Mengen von
Positionen von Löchern abbildet. (Lochgröße -> Menge von Positionen)
Beim Löschen wird der freigegebene Block in die Maps eingetragen und ggf.
vereinfacht: Liegt der neue Block neben einem vorhandenen Block, so werden
diese verschmolzen.
Beim Reservieren von Speicher wird erst geschaut, ob ein passender oder
größerer Block in den Maps eingetragen ist. Wird ein größerer Block
genutzt, wird von der Front des Blocks ein Teil abgeschnitten. Gibt es
keinen Block oder nur kleinere, wird das Dateiende verwendet.
Die zwei Maps nutzen das selbe Speichermanagement wie die zu speichernden
Daten. Dabei ist der folgenden Fehler aufgefallen:
remove() ruft removeSpaceReservation() auf, welches wiederum store()
aufruft. Dieses ruft reserveSpace() auf, welches remove() aufruft. Also
klar Failure by Design. Das ginge im Kreis.
Ein separates Speichermanagement für die beiden Maps zu nutzen ergäbe,
dass man beliebig viele dieser Bäume hintereinanderhängen müsste.
Die Alternative, genutzten Speicher die Maps einzutragen, dürfte das selbe
Problem haben.
Die Option, die zwei Maps mit einem Manager zu verwenden, der immer nur
ans Ende anhängt, möchte ich vermeiden.
Wie löst man das Problem des Speichermanagement am elegantesten?
Stichworte wären schon hilfreich.
Gruß
Andreas Wagner
ich arbeite gerade an dem Freispeicher-Management für einen persistenten
AVL-Baums. Also auf Festplatte, in einer Datei. Nach dem Löschen eines
Knotens samt Daten will ich den freigegebenen Speicher wieder nutzen.
Meine Überlegung war, dafür zwei weitere AVL-Bäume zu nutzen, die die
freigegebenen "Löcher" managt:
1. Einen für eine Map, die die Position in der Datei auf die Größe des
freigegebenen Speichers abbildet: (Postition_in_Datei -> Größe_des_Lochs)
2. Eine für eine Map, die die Lochgrößen auf Wurzeln von Mengen von
Positionen von Löchern abbildet. (Lochgröße -> Menge von Positionen)
Beim Löschen wird der freigegebene Block in die Maps eingetragen und ggf.
vereinfacht: Liegt der neue Block neben einem vorhandenen Block, so werden
diese verschmolzen.
Beim Reservieren von Speicher wird erst geschaut, ob ein passender oder
größerer Block in den Maps eingetragen ist. Wird ein größerer Block
genutzt, wird von der Front des Blocks ein Teil abgeschnitten. Gibt es
keinen Block oder nur kleinere, wird das Dateiende verwendet.
Die zwei Maps nutzen das selbe Speichermanagement wie die zu speichernden
Daten. Dabei ist der folgenden Fehler aufgefallen:
remove() ruft removeSpaceReservation() auf, welches wiederum store()
aufruft. Dieses ruft reserveSpace() auf, welches remove() aufruft. Also
klar Failure by Design. Das ginge im Kreis.
Ein separates Speichermanagement für die beiden Maps zu nutzen ergäbe,
dass man beliebig viele dieser Bäume hintereinanderhängen müsste.
Die Alternative, genutzten Speicher die Maps einzutragen, dürfte das selbe
Problem haben.
Die Option, die zwei Maps mit einem Manager zu verwenden, der immer nur
ans Ende anhängt, möchte ich vermeiden.
Wie löst man das Problem des Speichermanagement am elegantesten?
Stichworte wären schon hilfreich.
Gruß
Andreas Wagner
Stefan Reuther
Dec 13, 2022, 12:28:47 PM12/13/22
to
Am 13.12.2022 um 10:59 schrieb Andreas Wagner:
> Meine Überlegung war, dafür zwei weitere AVL-Bäume zu nutzen, die die
> freigegebenen "Löcher" managt:
> 1. Einen für eine Map, die die Position in der Datei auf die Größe des
> freigegebenen Speichers abbildet: (Postition_in_Datei -> Größe_des_Lochs)
> 2. Eine für eine Map, die die Lochgrößen auf Wurzeln von Mengen von
> Positionen von Löchern abbildet. (Lochgröße -> Menge von Positionen)
[...]
> Meine Überlegung war, dafür zwei weitere AVL-Bäume zu nutzen, die die
> freigegebenen "Löcher" managt:
> 1. Einen für eine Map, die die Position in der Datei auf die Größe des
> freigegebenen Speichers abbildet: (Postition_in_Datei -> Größe_des_Lochs)
> 2. Eine für eine Map, die die Lochgrößen auf Wurzeln von Mengen von
> Positionen von Löchern abbildet. (Lochgröße -> Menge von Positionen)
> remove() ruft removeSpaceReservation() auf, welches wiederum store()
> aufruft. Dieses ruft reserveSpace() auf, welches remove() aufruft. Also
> klar Failure by Design. Das ginge im Kreis.
Ich würde versuchen, die Verwaltungsdaten in den Blöcken selbst zu
> aufruft. Dieses ruft reserveSpace() auf, welches remove() aufruft. Also
> klar Failure by Design. Das ginge im Kreis.
speichern. Ein allokierter Block besteht aus Header+Payload, ein
freigegebener Block besteht aus Header+Knoten1+Knoten2, wobei Knoten1/2
die Knoten in der ersten und zweiten Map sind. Die Basisoperationen sind
dann nicht store() und remove(), sondern insertNode() und unlinkNode(),
die einfach nur den Knoten ein- oder ausketten und dabei keine neuen
Knoten anlegen.
Beim Allokieren muss dann halt aufgepasst werden, dass die Payload eine
minimale Größe einhält, so dass nach dem Freigeben die beiden Knoten
reinpassen.
Stefan
Andreas Wagner
Dec 13, 2022, 2:19:15 PM12/13/22
to
Hallo!
Ich vermute ja, dass meine Implementierung doch funktionieren könnte,
wenn es eine Abbruchbedingung in removeSpaceReservation() gibt. Wenn zum
Beispiel ein Block nur neu in der Größe justiert wird, dann muss kein
erneutes store() aufgerufen werden. Da reicht ein Update, das keine
reserveSpace() benötigt.
Ich habe das hete mal eingebaut und der Fehler hat sich deutlich
geändert. Da werde ich dann demnächst mal genauer schauen.
Am 13.12.2022 um 18:28 schrieb Stefan Reuther:
> Ich würde versuchen, die Verwaltungsdaten in den Blöcken selbst zu
> speichern. Ein allokierter Block besteht aus Header+Payload, ein
> freigegebener Block besteht aus Header+Knoten1+Knoten2, wobei Knoten1/2
> die Knoten in der ersten und zweiten Map sind. Die Basisoperationen sind
> dann nicht store() und remove(), sondern insertNode() und unlinkNode(),
> die einfach nur den Knoten ein- oder ausketten und dabei keine neuen
> Knoten anlegen.
Meinst Du bei "Header+Knoten1+Knoten2", dass jeweils Speicherpositionen
von Knoten 1 und 2 angegeben werden? Mir stellt sich die Frage, wonach
der Baum sortiert sein soll, der mit dem Header organisiert ist. Größe
und Position haben ja jeweils schon eine Map.
Mir ist auch noch keine Idee gekommen, wie man den Knoten auswählt, der
bei insertNode() wiederverwendet werden soll.
Gruß
Andreas
Ich vermute ja, dass meine Implementierung doch funktionieren könnte,
wenn es eine Abbruchbedingung in removeSpaceReservation() gibt. Wenn zum
Beispiel ein Block nur neu in der Größe justiert wird, dann muss kein
erneutes store() aufgerufen werden. Da reicht ein Update, das keine
reserveSpace() benötigt.
Ich habe das hete mal eingebaut und der Fehler hat sich deutlich
geändert. Da werde ich dann demnächst mal genauer schauen.
Am 13.12.2022 um 18:28 schrieb Stefan Reuther:
> Ich würde versuchen, die Verwaltungsdaten in den Blöcken selbst zu
> speichern. Ein allokierter Block besteht aus Header+Payload, ein
> freigegebener Block besteht aus Header+Knoten1+Knoten2, wobei Knoten1/2
> die Knoten in der ersten und zweiten Map sind. Die Basisoperationen sind
> dann nicht store() und remove(), sondern insertNode() und unlinkNode(),
> die einfach nur den Knoten ein- oder ausketten und dabei keine neuen
> Knoten anlegen.
von Knoten 1 und 2 angegeben werden? Mir stellt sich die Frage, wonach
der Baum sortiert sein soll, der mit dem Header organisiert ist. Größe
und Position haben ja jeweils schon eine Map.
Mir ist auch noch keine Idee gekommen, wie man den Knoten auswählt, der
bei insertNode() wiederverwendet werden soll.
Gruß
Andreas
Stefan Reuther
Dec 14, 2022, 1:57:27 PM12/14/22
to
Am 13.12.2022 um 20:19 schrieb Andreas Wagner:
> Am 13.12.2022 um 18:28 schrieb Stefan Reuther:
>> Ich würde versuchen, die Verwaltungsdaten in den Blöcken selbst zu
>> speichern. Ein allokierter Block besteht aus Header+Payload, ein
>> freigegebener Block besteht aus Header+Knoten1+Knoten2, wobei Knoten1/2
>> die Knoten in der ersten und zweiten Map sind. Die Basisoperationen sind
>> dann nicht store() und remove(), sondern insertNode() und unlinkNode(),
>> die einfach nur den Knoten ein- oder ausketten und dabei keine neuen
>> Knoten anlegen.
>
> Meinst Du bei "Header+Knoten1+Knoten2", dass jeweils Speicherpositionen
> von Knoten 1 und 2 angegeben werden? Mir stellt sich die Frage, wonach
> der Baum sortiert sein soll, der mit dem Header organisiert ist. Größe
> und Position haben ja jeweils schon eine Map.
>
> Mir ist auch noch keine Idee gekommen, wie man den Knoten auswählt, der
> bei insertNode() wiederverwendet werden soll.
Wenn wir das mal mit RAM statt Datei durchspielen, meinte ich verstanden
> Am 13.12.2022 um 18:28 schrieb Stefan Reuther:
>> Ich würde versuchen, die Verwaltungsdaten in den Blöcken selbst zu
>> speichern. Ein allokierter Block besteht aus Header+Payload, ein
>> freigegebener Block besteht aus Header+Knoten1+Knoten2, wobei Knoten1/2
>> die Knoten in der ersten und zweiten Map sind. Die Basisoperationen sind
>> dann nicht store() und remove(), sondern insertNode() und unlinkNode(),
>> die einfach nur den Knoten ein- oder ausketten und dabei keine neuen
>> Knoten anlegen.
>
> Meinst Du bei "Header+Knoten1+Knoten2", dass jeweils Speicherpositionen
> von Knoten 1 und 2 angegeben werden? Mir stellt sich die Frage, wonach
> der Baum sortiert sein soll, der mit dem Header organisiert ist. Größe
> und Position haben ja jeweils schon eine Map.
>
> Mir ist auch noch keine Idee gekommen, wie man den Knoten auswählt, der
> bei insertNode() wiederverwendet werden soll.
zu haben, dass dir sowas vorschwebt:
struct Node {
struct Node* left;
struct Node* right;
int payload;
};
void store(struct Node* root, int payload)
{
struct Node* new_node = malloc(sizeof(struct Node));
new_node->payload = payload;
// hier den Knoten einketten, also z.B.
new_node->left = root->left;
root->left = new_node;
// (AVL-tree-insert bekomm ich aus dem Kopf jetzt nicht hin)
}
// und zum Freigeben von Speicher dann
store(addrlist_root, address);
store(sizelist_root, size);
Ich meine, pack die Metadaten direkt in die Speicherblöcke, so dass
keine separate Allokation notwendig ist:
struct FreeBlock {
// ...hier Headerinformationen, falls du welche brauchst
struct Node in_addrlist;
struct Node in_sizelist;
};
void insertNode(struct Node* root, struct Node* node)
{
// hier nur das Einketten
node->left = root->left;
root->left = node;
}
// und zum Freigeben von Speicher dann
struct FreeBlock* p = (struct FreeBlock*) address;
p->in_addrlist.payload = address;
insertNode(addrlist_root, &p->in_addrlist);
p->in_sizelist.payload = size;
insertNode(sizelist_root, &p->in_sizelist);
VG,
Stefan
Andreas Wagner
Dec 14, 2022, 7:40:14 PM12/14/22
to
Hallo Stefan!
Am 14.12.2022 um 19:55 schrieb Stefan Reuther:
> Wenn wir das mal mit RAM statt Datei durchspielen, meinte ich verstanden
> zu haben, dass dir sowas vorschwebt:
>
> struct Node {
> struct Node* left;
> struct Node* right;
> int payload;
> };
Ich würde parent mit hinzunehmen. Den braucht man zum Rebalancieren.
>
> void store(struct Node* root, int payload)
> {
> struct Node* new_node = malloc(sizeof(struct Node));
> new_node->payload = payload;
> // hier den Knoten einketten, also z.B.
> new_node->left = root->left;
> root->left = new_node;
Das hängt das ja nicht in einen Binärbaum ein. Ich kann dir hier nicht
folgen.
> // (AVL-tree-insert bekomm ich aus dem Kopf jetzt nicht hin)
> }
>
> // und zum Freigeben von Speicher dann
> store(addrlist_root, address);
> store(sizelist_root, size);
free_spaces_by_pos.store(&new_node, new_node.get_payload_size());
free_spaces_by_size(new_node.get_payload_size(), &new_node);
ist ungefähr, was ich gemacht habe.
> Ich meine, pack die Metadaten direkt in die Speicherblöcke, so dass
> keine separate Allokation notwendig ist:
>
> struct FreeBlock {
> // ...hier Headerinformationen, falls du welche brauchst
> struct Node in_addrlist;
> struct Node in_sizelist;
> };
Wenn die Payload überschrieben ist, habe ich kein brauchbares
Sortierkriterium mehr.
> void insertNode(struct Node* root, struct Node* node)
> {
> // hier nur das Einketten
> node->left = root->left;
> root->left = node;
> }
> // und zum Freigeben von Speicher dann
> struct FreeBlock* p = (struct FreeBlock*) address;
> p->in_addrlist.payload = address;
> insertNode(addrlist_root, &p->in_addrlist);
> p->in_sizelist.payload = size;
> insertNode(sizelist_root, &p->in_sizelist);
Wie sind hie address und size definiert?
Was meine bisherige Implementierung angeht, hätte ich wohl in
de.sci.med.psychiatrie zu posten. Die macht wirklich nicht mehr das, was
ich programmiert habe.
Grüße
Andreas
Am 14.12.2022 um 19:55 schrieb Stefan Reuther:
> Wenn wir das mal mit RAM statt Datei durchspielen, meinte ich verstanden
> zu haben, dass dir sowas vorschwebt:
>
> struct Node {
> struct Node* left;
> struct Node* right;
> int payload;
> };
>
> void store(struct Node* root, int payload)
> {
> struct Node* new_node = malloc(sizeof(struct Node));
> new_node->payload = payload;
> // hier den Knoten einketten, also z.B.
> new_node->left = root->left;
> root->left = new_node;
folgen.
> // (AVL-tree-insert bekomm ich aus dem Kopf jetzt nicht hin)
> }
>
> // und zum Freigeben von Speicher dann
> store(addrlist_root, address);
> store(sizelist_root, size);
free_spaces_by_size(new_node.get_payload_size(), &new_node);
ist ungefähr, was ich gemacht habe.
> Ich meine, pack die Metadaten direkt in die Speicherblöcke, so dass
> keine separate Allokation notwendig ist:
>
> struct FreeBlock {
> // ...hier Headerinformationen, falls du welche brauchst
> struct Node in_addrlist;
> struct Node in_sizelist;
> };
Sortierkriterium mehr.
> void insertNode(struct Node* root, struct Node* node)
> {
> // hier nur das Einketten
> node->left = root->left;
> root->left = node;
> }
> // und zum Freigeben von Speicher dann
> struct FreeBlock* p = (struct FreeBlock*) address;
> p->in_addrlist.payload = address;
> insertNode(addrlist_root, &p->in_addrlist);
> p->in_sizelist.payload = size;
> insertNode(sizelist_root, &p->in_sizelist);
Was meine bisherige Implementierung angeht, hätte ich wohl in
de.sci.med.psychiatrie zu posten. Die macht wirklich nicht mehr das, was
ich programmiert habe.
Grüße
Andreas
Stefan Reuther
Dec 15, 2022, 5:32:52 AM12/15/22
to
Am 15.12.2022 um 01:40 schrieb Andreas Wagner:
> Am 14.12.2022 um 19:55 schrieb Stefan Reuther:
>> Wenn wir das mal mit RAM statt Datei durchspielen, meinte ich verstanden
>> zu haben, dass dir sowas vorschwebt:
>>
>> struct Node {
>> struct Node* left;
>> struct Node* right;
>> int payload;
>> };
>
> Ich würde parent mit hinzunehmen. Den braucht man zum Rebalancieren.
[...]
> Am 14.12.2022 um 19:55 schrieb Stefan Reuther:
>> Wenn wir das mal mit RAM statt Datei durchspielen, meinte ich verstanden
>> zu haben, dass dir sowas vorschwebt:
>>
>> struct Node {
>> struct Node* left;
>> struct Node* right;
>> int payload;
>> };
>
> Ich würde parent mit hinzunehmen. Den braucht man zum Rebalancieren.
> Das hängt das ja nicht in einen Binärbaum ein. Ich kann dir hier nicht
> folgen.
Gut möglich. War nur zur Illustration, eine Baum-Implementierung
> folgen.
schüttel ich nicht mal eben für ein Posting aus dem Ärmel, da müsstest
du eben deine Verkettungslogik einsetzen. Wenn ich einen Baum brauche,
nehme ich normalerweise std::map :) Und wenn ich einen Allokator baue,
reicht mir normalerweise eine einfache Liste.
>> // und zum Freigeben von Speicher dann
>> store(addrlist_root, address);
>> store(sizelist_root, size);
>
> free_spaces_by_pos.store(&new_node, new_node.get_payload_size());
> free_spaces_by_size(new_node.get_payload_size(), &new_node);
(Baum-)Nutzdaten 'new_node.get_payload_size()' ablegen zu können? Dann
stehst du vor dem von dir beschriebenen Problem. Eine Lösung wäre halt,
der Funktion nicht zu sagen "hier ist ein Datum, kümmer dich selber, wie
du die Verkettungsdaten ablegst" sondern "hier ist ein Knoten mit Platz
für deine Verkettungsdaten, füge den ein". Und wenn du einen Knoten aus
einer Map auskettest, hast du immer einen weiteren Knoten, um ihn in
eine andere einzuketten.
Ein Stichwort wäre "intrusive data structure".
>> void insertNode(struct Node* root, struct Node* node)
>> {
>> // hier nur das Einketten
>> node->left = root->left;
>> root->left = node;
>> }
>
>> // und zum Freigeben von Speicher dann
>> struct FreeBlock* p = (struct FreeBlock*) address;
>> p->in_addrlist.payload = address;
>> insertNode(addrlist_root, &p->in_addrlist);
>> p->in_sizelist.payload = size;
>> insertNode(sizelist_root, &p->in_sizelist);
>
> Wie sind hie address und size definiert?
speichern wolltest eben.
Stefan
Andreas Wagner
Dec 18, 2022, 6:28:47 AM12/18/22
to
Am Thu, 15 Dec 2022 11:30:24 +0100 schrieb Stefan Reuther:
> Ein Stichwort wäre "intrusive data structure".
Das schaue ich mir bei Gelegenheit mal an.
> Ein Stichwort wäre "intrusive data structure".
Mein Eigenbau ist unter
https://gitlab.com/andreas.wagner/persistent-avl-tree
zu finden. test_avl() schlägt mir bei bei Test 3 fehl. Ohne
Freispeichermanagement hat es mal komplett geklappt.
Ich bin da gerade auf "Guru Meditation" und lasse es sein, zu
experimentieren.
Wie die Readme schon sagt: Es fehlt noch eine gute Programmier-
schnittstelle. Die Cache-Effizienz dürfte aber gut sein, da der Kern
Datentypunabhängig ist. Es wird also nicht durch Templates unnötig
aufgebläht.
Wenn ich die Schnittstelle fertig habe, frage ich hier mal nach Feedback.
Gruß
Andreas
0 new messages