Free Element Array - Feedback für Algorithmus

cwriter

Erfahrenes Mitglied
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(n), will ich nicht aufwenden).

Free-Bitmap/Array:
alloc: O(n)
free: O(1)
Speicher: O(n) (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:
  1. Es folgt ein alloc.
    min_free wird sofort wieder besetzt und in O(n) nach vorne iteriert, Kosten von alloc also prev - i,
    wobei prev = min_free vor dem free(i) und i der Parameter vom free ist.
  2. Es folgt ein weiteres free.
    min_free bleibt dabei entweder gleich oder wird noch kleiner. Fragmentierung beginnt.
4) Nach der ersten Freigabe in einem vollen Array:
min_free + 1 = max_free

Nun gibt es 2 Optionen:
  1. Es folgt ein alloc.
    min_free wird sofort wieder besetzt, aber nur um 1 Schritt iteriert. max_free wird wieder 0. Kosten: O(1)
  2. Es folgt ein weiteres free.
    min_free bleibt dabei entweder gleich oder wird noch kleiner. Späteres Einfügen kostet wieder O(n).

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)
Weitere Feststellungen:
  • 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(n) 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:
  1. Wie wahrscheinlich sind diese Spezialfälle?
  2. Kann man diese Spezialfälle irgendwie häufiger auftreten lassen?
  3. Gibt es generell bessere Algorithmen für diesen Zweck?
  4. Wie teuer ist dieser Algorithmus im Durchschnitt? Kann er als effizient betrachtet werden?
  5. 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)
  6. Gibt es anderes Feedback?


Gruss
cwriter
 
Von der Seite:
C:
static ULONG first_frame() // find the first free frame in frames bitset
{
    ULONG index, offset;
    for(index=0; index<(NFRAMES/32); ++index)
    {
        if(frames[index] != ULONG_MAX)
        {
            for(offset=0; offset<32; ++offset)
            {
                if( !(frames[index] & 1<<offset) ) // bit set to zero?
                    return (index*32 + offset);
            }
        }
    }
    return ULONG_MAX; // no free page frames
}
Das ist O(n) für's finden des ersten freien Elements. Jedes Mal. Und dann noch massives Bitbanging für etwas, wofür es Instruktionen gibt (CLZ z.B., oder x86: LZCNT).
Also ist das genau die Variante, die mir zu lahm ist.

Free-Bitmap/Array:
alloc: O(n)
free: O(1)
Speicher: O(n) (yippie!)

cwriter
 
Hallo cwriter,

hast Du schonmal in die Quellen von ReactOS geschaut?
ist für Anfänger gut beschrieben - also keine magischen Bezeichner.
Ich selbst habe vor paar Wochen damit begonnen Änderungen am
System vorzunehmen, da mir das Booting + die Darstellung nen kraus
waren und ich den VideoSpeicher mit einen "memset" auf Turbo gebracht
habe.

Die vorhandenen Funktionen haben den Nachteil, das sie entweder jedesmal
das BIOS Anfragen oder ein Zeichen jedesmal in einer For Schleife angezeit
und/oder ausgewertet wurde/wird.

Interessant ist das Projekt schon.
Aber die Arbeiten schon 10 Jahre dran ....
 
Zurück