Nun, ich möchte in dem Anhang zur Platzierungsstrategie noch mal auf das Halbierungsverfahren zu sprechen

können.

Bei NuryBuddy hatten wir ja kurz betrachtet, hat ja gewisse Nachteile dieses Verfahrens,

hatte ich schon erwähnt, aber einfach zum besseren Verständnis dieses Verfahrens möchte

ich mal hier so ein Beispiel durchgehen, wie sich das sozusagen verhält bei der Anforderung

wie auch bei der Freigabe.

Nehmen wir mal an, wir wollen ein Speicherstück der Größe von 42 bytes anfordern.

Dann wissen wir, dass die kleinste Zweierpotenz, ein Loch mit der kleinsten Zweierpotenzgröße

dazu gefunden werden müsste.

Das wäre denn 64.

Wir müssen also ein Loch von 64 bytes identifizieren in unserer Liste, um den praktischen Anforderungen

von 42 erfüllen zu können.

Wir wissen sofort, damit haben wir eine interne Fragmentierung, weil wir zu viel rausgeben

werden.

Wir sehen in der Listenstruktur jetzt halt einen Zustand, wo wir sagen, das eine Loch,

was existiert ist, 1024 KB groß.

Unterstellungen fest, das ist viel zu groß im Endeffekt.

Das heißt, wir würden jetzt durch SUXIS die Besplittung dieses Lochs von 1024 Beits dann

halt nach und nach unser passendes Loch dann halt aufsuchen.

Das heißt, also wir fangen an, halbieren praktisch 1024, kriegen 2 mal 512 Beits dann

letztendlich halt raus.

Oder Kilo Beits in dem Beispiel.

Stellenfest ist immer noch zu groß, wir halbieren nochmals.

Stellenfest 250 ist immer noch zu groß.

Haben die 128 als zwei Buddys dann gefunden durch Halbierung von dem einen 256er Anteil.

Und dann halbieren wir nochmal, 128 ist immer noch zu groß.

Kommen wir auf die 64, stellen fest 64 ist okay, weil das nächste Objekt wäre 32, der

nächste Buddy, der nächste kleinere Buddy wäre 32 und die reicht dann nicht mehr aus,

um diese 42 Beits dann halt zu erfüllen.

Das heißt, hier hätten wir jetzt unsere passenden Löcher und davon würden wir jetzt eins rausgeben.

Und zu passend für so eine Darstellung wäre dann durchaus eine zweidimensionelle Tabelle

oder eine Repräsentation einer solchen Lochliste, wo wir dann Tabelle haben, wo wir die Buddy-Knassen

dann halt haben.

Der Index in der Tabelle steht dann praktisch wie eine entsprechende Zweierpotenzgröße.

Das würden wir lokal im Betriebssystem speichern.

Dann hätten wir in jedem Tabelleneintrag eine lineare Liste gleicher Buddys.

Realistisch würden da höchstens immer zwei Buddys dann stehen, weil wir ja sagen könnten,

dass diese beiden Buddys verschwolzen werden könnten und ein Buddy praktisch in der nächsthöheren

Tabellenebene dann bilden würden.

Aber gehen wir mal logisch von einer Listenstruktur denn aus, die dort existiert wurde, in die

lineare Liste gleicher Buddys dann für gewöhnlich relativ klein ist.

Und die würde man dann durchaus, so würde es bei unserer Lochliste gesehen haben, durchaus

auch in den Hohlräumen da selbst speichern können.

Das muss man nicht machen, aber das wäre denkbar.

Nun, da gibt es jetzt bei dem Verfahren bestimmte Randbedingungen, die man so ausmachen kann,

einfach aufgrund der Tatsache, dass wir hier mit Zweierpotenzen arbeiten.

Wenn wir also so ein beliebiges Stück in zwei Hälften teilen, wir haben all und wir wissen

dieses beliebige Stück hat eine Zweierpotenzgröße, denn entstehen eben zwei Buddys, wo die Größe

des jeweiligen Buddys jeweils wieder eine Zweierpotenzgröße hat.

Und umgekehrt, wenn wir die jetzt kombinieren würden, dann entsteht dann eben ein größerer