Hi
Ich arbeite an einem kleinen OS und brauche dafür eine Datenstruktur, um freie Seiten (Pages) zu halten, um zu wissen, welche physischen Adressen verfügbar sind.
Zwei Datenstrukturen sind mir für diesen Zweck bekannt:
Free-List: Freie Pages sind in einer (Double Linked) Liste gespeichert; eine Freigabe fügt die page wieder in die Liste ein, eine Allozierung nimmt einfach ein Element aus der Liste heraus.
alloc: O(1)
free: O(1)
Speicher: O(3 * n) (1 prev, 1 next, 1 value).
Hierbei störte mich jedoch der Speicheraufwand gewaltig (mehr als unbedingt nötig, also O
, will ich nicht aufwenden).
Free-Bitmap/Array:
alloc: O
free: O(1)
Speicher: O (yippie!)
Die alloc-Kosten waren mir da aber wesentlich zu teuer.
Also eine kleine Modifikation des Ganzen:
Zusätzlich werden zwei Sentinels gehalten: min_free und max_free.
Der Algorithmus:
Init:
array = {0}^n //1 == used, 0 == free
min_free = 0;
max_free = n;
Bei der Analyse tue ich mir ein bisschen schwer, daher gehe ich die einzelnen Fälle durch:
1) max_free == n
Das bedeutet, dass der gesamte obere Bereich des Arrays (oberhalb von min_free) frei ist, ein alloc also O(1)-komplex ist
2) max_free == 0
Das bedeutet, dass es gar keinen Platz mehr hat (implizit: min_free == n). Diese Tatsache ist in O(1) feststellbar.
Die restlichen Fälle sind nur erreichbar, wenn mindestens 1 Element freigegeben worden ist.
Beweis: min_free wird nie verkleinert werden, da monoton wachsend in alloc.
3) Nach der ersten Freigabe in einem nicht-vollen Array
Da alles in [min_free; max_free[ frei ist, und alles in [0, min_free[ besetzt, kann nur min_free verändert werden.
Nun gibt es 2 Optionen:
min_free + 1 = max_free
Nun gibt es 2 Optionen:
Meine Frage ist nun:
Ist das ein guter Algorithmus?
Die Analyse zeigt klar, dass er in nur wenigen Spezialfällen sehr gut ist (aus Sicht von alloc, free ist durch Random Access ja immer O(1), ausser, man amortisiert):
Die Fragen, die sich nun stellen, sind:
Gruss
cwriter
Ich arbeite an einem kleinen OS und brauche dafür eine Datenstruktur, um freie Seiten (Pages) zu halten, um zu wissen, welche physischen Adressen verfügbar sind.
Zwei Datenstrukturen sind mir für diesen Zweck bekannt:
Free-List: Freie Pages sind in einer (Double Linked) Liste gespeichert; eine Freigabe fügt die page wieder in die Liste ein, eine Allozierung nimmt einfach ein Element aus der Liste heraus.
alloc: O(1)
free: O(1)
Speicher: O(3 * n) (1 prev, 1 next, 1 value).
Hierbei störte mich jedoch der Speicheraufwand gewaltig (mehr als unbedingt nötig, also O
, will ich nicht aufwenden).Free-Bitmap/Array:
alloc: O
free: O(1)
Speicher: O
(yippie!)Die alloc-Kosten waren mir da aber wesentlich zu teuer.
Also eine kleine Modifikation des Ganzen:
Zusätzlich werden zwei Sentinels gehalten: min_free und max_free.
Der Algorithmus:
Init:
array = {0}^n //1 == used, 0 == free
min_free = 0;
max_free = n;
Code:
alloc:
if(min_free >= max_free)
fail();
array[min_free] = 1;
while (++min_free < max_free)
if (array[min_free] == 0)
break;
if(min_free >= max_free)
max_free = 0;
Code:
free: index i
array[i] = 0;
min_free = min(min_free, i);
max_free = max(max_free, i+1);Bei der Analyse tue ich mir ein bisschen schwer, daher gehe ich die einzelnen Fälle durch:
1) max_free == n
Das bedeutet, dass der gesamte obere Bereich des Arrays (oberhalb von min_free) frei ist, ein alloc also O(1)-komplex ist
2) max_free == 0
Das bedeutet, dass es gar keinen Platz mehr hat (implizit: min_free == n). Diese Tatsache ist in O(1) feststellbar.
Die restlichen Fälle sind nur erreichbar, wenn mindestens 1 Element freigegeben worden ist.
Beweis: min_free wird nie verkleinert werden, da monoton wachsend in alloc.
3) Nach der ersten Freigabe in einem nicht-vollen Array
Da alles in [min_free; max_free[ frei ist, und alles in [0, min_free[ besetzt, kann nur min_free verändert werden.
Nun gibt es 2 Optionen:
- Es folgt ein alloc.
min_free wird sofort wieder besetzt und in O nach vorne iteriert, Kosten von alloc also prev - i,
wobei prev = min_free vor dem free(i) und i der Parameter vom free ist.
- Es folgt ein weiteres free.
min_free bleibt dabei entweder gleich oder wird noch kleiner. Fragmentierung beginnt.
min_free + 1 = max_free
Nun gibt es 2 Optionen:
- Es folgt ein alloc.
min_free wird sofort wieder besetzt, aber nur um 1 Schritt iteriert. max_free wird wieder 0. Kosten: O(1)
- Es folgt ein weiteres free.
min_free bleibt dabei entweder gleich oder wird noch kleiner. Späteres Einfügen kostet wieder O.
Meine Frage ist nun:
Ist das ein guter Algorithmus?
Die Analyse zeigt klar, dass er in nur wenigen Spezialfällen sehr gut ist (aus Sicht von alloc, free ist durch Random Access ja immer O(1), ausser, man amortisiert):
- Der Array ist voll
- Der Array hat genau 1 freies Element
- Der Array hat keine Fragmentierung. Eine minimale Verbesserung wäre, min_free und max_free als modulo n anzugeben, damit "bitonische" Sequenzen möglich sind (i.e. 0 <= block_1 <= block_2 <= block_3 <= n, wobei block_1 und block_3 free sind und block_2 besetzt, was im angegebenen Algorithmus eine Fragmentierung darstellt, wenn sie auch nur Θ(|block_2|) kostet)
- Wenig Fragmentierung ist gut, da alloc: Θ(next_free - min_free)
(alloc: O(max_free - min_free), falls Platz vorhanden, O(1) sonst) - Am teuersten ist daher {0, 1...1, 0}, da n-2 Schritte gemacht werden müssen.
Schlimmer wird es, wenn dann immer wieder "free(0); alloc" folgt (O für alloc, sogar schlechter als einfacher Array-Ringbuffer (O(n/2). Allerdings kann dieses Verhalten durch die oben genannte Optimierung auch für diesen Algorithmus hergestellt werden).
Die Fragen, die sich nun stellen, sind:
- Wie wahrscheinlich sind diese Spezialfälle?
- Kann man diese Spezialfälle irgendwie häufiger auftreten lassen?
- Gibt es generell bessere Algorithmen für diesen Zweck?
- Wie teuer ist dieser Algorithmus im Durchschnitt? Kann er als effizient betrachtet werden?
- Wäre es sinnvoll, das setzen der Indizes lazy zu machen, also die Indizes nur setzen, wenn durch eine Löschung keine Fragmentierung entsteht, dafür eine dirty-flag zu setzen und wenn der Array voll wird und die dirty-flag gesetzt ist, die Indizes auf min_index = 0 und max_index = n zurückzusetzen und nochmals zu suchen?
(Meine Angst hier ist, dass dadurch andere Nachteile entstehen, die mir gerade nicht einfallen) - Gibt es anderes Feedback?
Gruss
cwriter
