Implementierung einer Freispeicherverwaltung

1. Aufgabe

1.1. Einführung

Programmiersprachen wie C, C++, Java und C# legen in Bezug auf die Verwaltung des Speichers sehr unterschiedliche Strategien an den Tag. In C und C++ liegen Speicherplatzanforderungen und -freigabe komplett in der Hand des Anwenders. Die fraglichen Funktionen lauten in C malloc und free, in C++ haben wir es mit den Operatoren new und delete zu tun. Beim Anfordern des Speichers gibt es zwischen den einzelnen Sprachen – aus Anwendersicht – keinen signifikanten Unterschied. Etwas anders sieht dies bei der Speicherfreigabe aus. Vergisst ein Anwender in einem C- oder C++-Programm, reservierten Speicher wieder freizugeben, ist dieser ein für alle Zeiten im Programm nicht mehr verfügbar.

Die moderneren Programmiersprachen Java und C# legen die Speicherverwaltung – und hier speziell die Speicherfreigabe – komplett in die Obhut eines Laufzeitsystems. Speicherplatzanforderungen müssen zunächst wie bei C oder C++ durch den Anwender initiiert werden. Die Freigabe hingegen erfolgt durch Aktivitäten das Laufzeitsystems, die für den Anwender nicht unmittelbar erkennbar sind. Ein so genannter Garbage Collector erkennt, wann bestimmte Speicherbereiche von der Anwendung nicht mehr erreichbar sind und gibt diese dann zu nicht deterministisch vorhersehbaren Zeitpunkten frei.

Auf Grund der Bedeutung der Speicherverwaltung für die Programmentwicklung betrachten wir in dieser Fallstudie eine einfache Implementierung, wie sie in C- und C++-Programmen zum Einsatz kommt. Wir stellen eine einfache Realisierung für zwei Methoden Allocate und Release vor, die als Verallgemeinerung von malloc und free bzw. von new und delete angesehen werden können.

In einer zweiten Stufe könnte ein Test Ihrer Realisierung auch durch ein Stück realen Quellcodes erfolgen, das in starkem Maße die dynamische Speicherallokation einsetzt. An Stelle der zwei C++-Operatoren new und delete würde man alternativ die von Ihnen selbst geschriebenen Methoden Allocate und Release verwenden, um auf diese Weise eine Anbindung an die von Ihnen realisierte Speicherverwaltung herzustellen.

1.2. Klasse Memory

Eine Speicherverwaltung vergibt Speicher, der aus möglichst großen, vom Betriebssystem zur Verfügung gestellten, zusammenhängenden Speicherblöcken stammt (so genannten Pages). Die Betrachtungen dieser Aufgabe beziehen sich ausschließlich auf eine einzige Page! Mit Allocate wird in einer Page Speicherplatz einer bestimmten Länge angefordert, das Gegenstück Release gibt diesen Speicherplatz wieder an die Laufzeitumgebung zurück.

Zur Vereinfachung der Aufgabe legen wir den zu verwaltenden Speicher in die Obhut einer Klasse. Diese hat den bezeichnenden Namen Memory und allokiert in ihren Instanzdaten ein dynamisches Array vom Typ unsigned char. Objekte der Klasse Memory verwalten also ein einziges, größeres zusammenhängendes Stück Speicher. Gegenstand dieser Aufgabe ist die Betrachtung der dynamische Belegung einzelner Abschnitte dieses Arrays durch Allocate- und Release-Aufrufe.

Die Entscheidung für ein Array (in der Klasse Memory) vereinfacht sowohl die Implementierung als auch den Test der Implementierung, da wir bei der Allokation bzw. Freigabe von Teilabschnitten Indizes dieses Arrays betrachten können – und damit keine realen Adressen von Speicherzellen. Im Beispiel von Abbildung 1 finden wir ein Memory-Objekt mit einem dynamisch angelegten unsigned char-Array der Länge 4096 Bytes vor:

Ein Repräsentant für freien Speicher: Objekt der Klasse Memory.

Abbildung 1. Ein Repräsentant für freien Speicher: Objekt der Klasse Memory.


Beginnen Sie mit der Entwicklung einer Klasse Memory an Hand ihrer – nicht notwendigerweise vollständigen – Spezifikation in Tabelle 1:

Element

Beschreibung

Instanzvariable m_mem

unsigned char* m_mem;

Zeigt auf ein dynamisch zu allokierendes Array des Typs unsigned char.

Standardkonstruktor

Memory ();

Das dynamisch zu allokierende Array sollte per Voreinstellung 128 Bytes lang sein.

Benutzerdefinierter Konstruktor

Memory (int len);

Der Parameter len spezifiziert die Länge des dynamisch zu allokierenden Arrays.

Methode SetMemory

void SetMemory (char c);

Methode, um das gesamte Array m_mem mit einem einzigen Zeichen c zu füllen. Mit Hilfe von SetMemory sollte bei der Erzeugung eines Memory-Objekts das dynamisch allokierte Array sinnvoll vorbelegt werden.

Methode WriteString

void WriteString (int ofs, char* s);

Methode, um eine (null-terminierte) Zeichenkette s ab dem Offset ofs in das Array des Memory-Objekts zu kopieren.

Methode DumpMemory

void DumpMemory (ostream& os);

Generiert zum Zwecke der Fehlerdiagnose einen Dump (hexadezimaler Speicherauszug) des verwalteten Speicherbereichs auf der Konsole.

Tabelle 1. Spezifikation der Klasse Memory.


Testen Sie Ihre Implementierung der Klasse Memory an folgenden Codefragmenten. Bei Ausführung von

Memory m (64);
m.SetMemory ('!');
m.DumpMemory (cout);

sollte die Ausgabe so aussehen:

00000000  21 21 21 21 21 21 21 21  21 21 21 21 21 21 21 21   !!!!!!!!!!!!!!!!
00000010  21 21 21 21 21 21 21 21  21 21 21 21 21 21 21 21   !!!!!!!!!!!!!!!!
00000020  21 21 21 21 21 21 21 21  21 21 21 21 21 21 21 21   !!!!!!!!!!!!!!!!
00000030  21 21 21 21 21 21 21 21  21 21 21 21 21 21 21 21   !!!!!!!!!!!!!!!!

Das Codefragment

Memory m (32);
m.SetMemory (' ');
m.WriteString (0, "1234");
m.WriteString (12, "6789");
m.WriteString (20, "ABCDEFGH");
m.WriteString (31, "Z");
m.DumpMemory (cout);

resultiert in folgender Programmausführung:

00000000  31 32 33 34 20 20 20 20  20 20 20 20 36 37 38 39   1234        6789
00000010  20 20 20 20 41 42 43 44  45 46 47 48 20 20 20 5A       ABCDEFGH   Z

1.3. Klasse MemoryFragment

Um in einem Block während der gesamten Laufzeit des Programms den Überblick zu haben, welche Teilbereiche frei und welche vergeben sind, verwaltet man eine Liste, die alle freien Teilbereiche des Blocks beschreibt, die so genannte Freispeicherliste (engl. free entry list). Jedes Element dieser Liste ist eine Instanz der Klasse MemoryFragment und beschreibt ein zusammenhängendes Stück freien Speichers, das bei einer Anforderung vergeben werden könnte (Abbildung 2):

Ein einzelnes Element der Freispeicherliste: Objekt der Klasse MemoryFragment.

Abbildung 2. Ein einzelnes Element der Freispeicherliste: Objekt der Klasse MemoryFragment.


In Tabelle 2 folgt eine Kurzspezifikation der Instanzvariablen der Klasse MemoryFragment, soweit diese aus Abbildung 2 nicht schon visuell ersichtlich geworden ist:

Instanzvariable

Beschreibung

m_frag

int m_frag;

Indiziert ein Element (und damit den Anfang eines freien Stück Speichers) im Array des korrespondierenden Memory-Objekts.

m_size

int m_size;

Gibt an, wie viele Bytes der korrespondierende, freie Teilabschnitt groß ist.

m_next

MemoryFragment* m_next;

Zeiger auf das nächste MemoryFragment-Objekt, die als einfach verkettete Liste verwaltet wird.

Tabelle 2. Instanzvariablen der Klasse MemoryFragment.

1.4. Arbeitsweise eines Speicherallokators

Die Arbeitsweise einer Freispeicherverwaltung besteht nun darin, das Array eines Memory-Objekts – präziser formuliert: die freien Teilabschnitte in diesem Array – mit einer einfach verketteten Liste von MemoryFragment-Objekten zu verwalten. Dieser Abschnitt dient nur dazu, einen ersten Einblick in die Arbeitsweise des Speicherallokators überblicksmäßig zu skizzieren. Warten Sie mit der Weiterarbeit an Ihrer Implementierung noch so lange ab, bis in den nachfolgenden Abschnitten die beteiligten Methoden Allocate und Release präzise spezifiziert werden.

In Abbildung 3 ist der Ausgangszustand der Freispeicherverwaltung abgebildet. Eine einzige MemoryFragment-Instanz zeigt mit ihrer m_frag-Instanzvariablen auf das erste Element des Arrays im korrespondierenden Memory-Objekt.


Achtung

Sie können die Freispeicherliste entweder im letzten Element mit einem NULL-Zeiger terminieren oder die Liste als Ring (circularly linked list) organisieren. Sie müssen nur darauf achten, dass zu jedem Zeitpunkt des Programms mindestens ein Element in der Liste enthalten ist! In den Abbildungen zu dieser Aufgabe finden Sie stets eine ringförmige Liste vor.


Ausgangszustand der Freispeicherverwaltung.

Abbildung 3. Ausgangszustand der Freispeicherverwaltung.


Zum Reservieren von Speicher gibt es die Methode Allocate. Sie liefert einen Index zurück, der sich auf das m_mem-Array bezieht. Möchte man diesen Teilabschnitt des Arrays wieder freigeben, ist eine Methode Release mit dem von Allocate zurückgelieferten Index aufzurufen. Liegt eine Speicherplatzanforderung vor, also zum Beispiel die Anweisung

Memory mem (128);
...
int n = mem.Allocate (10);

wird zunächst die Liste der Freispeicherelemente so lange durchlaufen, bis ein Element mit passender Größe gefunden wird – sprich die m_size-Instanzvariable ist größer oder gleich als die angeforderte Anzahl. Wird kein Element in der Liste mit dieser Eigenschaft gefunden, kann die Speicherplatzanforderung offensichtlich nicht befriedigt werden (Situation „out of memory“). Nach dem Start eines Programms dürfte diese Situation allerdings niemals eintreten, da das erste Element der Freispeicherliste den komplett zur Verfügung stehenden Speicher beschreibt.

Ist der gefundene Freispeicherabschnitt zu groß, wird er geteilt: Der obere Teil wird dem Benutzer übergeben, der untere Teil verbleibt in der Freispeicherliste, siehe dazu Abbildung 4. Es ist in diesem Fall nur die Längenangabe des betroffenen Freispeicherelements entsprechend zu verkleinern.

Speicherplatzanforderung von 10 Bytes.

Abbildung 4. Speicherplatzanforderung von 10 Bytes.


In Abbildung 4 finden Sie ein wichtiges Detail in der Arbeitsweise des Speicherallokators vor: Werden beispielsweise 10 Bytes angefordert, sucht der Speicherallokator in Wirklichkeit nach einem Abschnitt der Größe 12. In den untersten zwei Bytes des zugewiesenen Teilabschnitts wird die tatsächliche Größe (hier: 12) eingetragen. Der Anwender bekommt davon nur 10 Bytes zu sehen. Der von Allocate zurückgelieferte Index (hier: 118) ist also um 2 Bytes oberhalb des vom System tatsächlich reservierten Speichers positioniert!

Weshalb diese Vorgehensweise? In der Freispeicherliste werden nur Speicherbereiche verwaltet, die frei sind. Über die reservierten Teilabschnitte sind in der Freispeicherliste (wie der Name zum Ausdruck bringt) keinerlei Informationen enthalten. Wird ein reserviertes Stück Speicher wieder freigegeben, bekommt Release die Anfangsadresse (in dieser Aufgabe: den Index in das Array des Memory-Objekts) übergeben. Die noch fehlende Information (wie groß ist dieser Teilabschnitt?) findet der Allokator indirekt in den untersten zwei Bytes des reservierten Teilabschnitts vor. Auf diese Weise kann der Allokator ein passendes MemoryFragment-Objekt für die Freispeicherliste erzeugen, wie wir noch sehen werden!

Folgt nach dem ersten Allocate-Aufruf ein weiterer Aufruf, zum Beispiel mit dem Argument 20, sieht die Situation wie in Abbildung 5 gezeigt aus:

Weitere Speicherplatzanforderung von 20 Bytes.

Abbildung 5. Weitere Speicherplatzanforderung von 20 Bytes.


Diese beiden Beispiele für Speicherplatzanforderungen mögen Ihnen einen ersten Eindruck von der Arbeitsweise des Speicherallokators vermitteln. Die notwendigen Hinweise zur Realisierung folgen nun in den nächsten zwei Abschnitten.

1.5. Methode Allocate

Für die allgemeine Beschreibung der Allocate-Methode legen wir den Zustand der Freispeicherliste aus Abbildung 6 zu Grunde. Im gesamten Speicherbereich des Memory-Objekts (bestehend aus 128 Bytes) existieren drei freie Teilabschnitte, also liegen in der Freispeicherliste drei MemoryFragment-Objekte miteinander verkettet vor.

Eine Freispeicherliste mit drei freien Teilabschnitten der Größe 8, 10 und 90.

Abbildung 6. Eine Freispeicherliste mit drei freien Teilabschnitten der Größe 8, 10 und 90.


Beim Eintreffen einer Anforderung ist die Freispeicherliste solange zu traversieren, bis ein MemoryFragment-Objekt ein hinreichend großes Speicherstück beschreibt. Ist in der ganzen Liste kein solches Objekt vorhanden, kann die Anforderung aktuell nicht erfüllt werden, die Allocate-Methode liefert -1 zurück. Nun gibt es zwei Möglichkeiten:

  1. Die Größe des gefundenen freien Teilabschnitts ist identisch mit der aktuellen Anforderung.

  2. Der gefundene freie Teilabschnitt ist größer als die aktuelle Anforderung.

Wir gehen zunächst auf die erste Möglichkeit ein und studieren in Abbildung 7 die Anweisung

Memory mem (128);
...
int n = mem.Allocate (8);

Der erste freie Teilabschnitt ist zu klein! Neben den 8 angeforderten Bytes müssen zusätzlich noch 2 Bytes für die Ablage der Teilabschnittslänge berücksichtigt werden! Im zweiten MemoryFragment-Objekt finden wir die Instanzvariable m_size mit dem Wert 10 vor, sprich die Anforderung von 8 Bytes – intern 10 Bytes – kann exakt befriedigt werden. In diesem Fall ist einfach das MemoryFragment-Objekt aus der Freispeicherliste zu entfernen und die passende Anfangsadresse (hier: Index 20) an den Aufrufer zurückzuliefern (Abbildung 7):

Ein freier Teilabschnitt ist so groß wie die aktuelle Anforderung.

Abbildung 7. Ein freier Teilabschnitt ist so groß wie die aktuelle Anforderung.


Die zweite Möglichkeit einer Speicheranforderung besteht darin, dass ein Teilabschnitt in der Freispeicherliste enthalten ist, der größer als die Anforderung ist. In diesem Fall bleibt die Liste in ihrer Struktur unverändert, es wird nur das gefundene MemoryFragment-Objekt bzgl. der m_size-Instanzvariablen entsprechend verkleinert. In Abbildung 8 können Sie dieses Szenario am Aufruf

Memory mem (128);
...
int n = mem.Allocate (2);

nachverfolgen.

Ein freier Teilabschnitt ist größer als die aktuelle Anforderung.

Abbildung 8. Ein freier Teilabschnitt ist größer als die aktuelle Anforderung.

1.6. Methode Release

Das Freigeben eines Speicherbereichs erfolgt prinzipiell so: Zunächst einmal werden in der Freispeicherliste das linke und rechte Nachbarelement des freizugebenden Teilabschnitts gesucht. Achten Sie deshalb darauf, dass in der Freispeicherliste stets alle Elemente mit aufsteigenden m_frag-Instanzvariablen enthalten sind, so dass die korrespondierenden Teilabschnitte geordnet vorliegen! Kommt der freizugebende Speicherbereich unmittelbar neben einem seiner Nachbarn zum Liegen, werden die korrespondierenden MemoryFragment-Elemente verschmolzen – also zu einem einzigen MemoryFragment-Objekt umstrukturiert. Dieses Zusammenschmelzen wird, falls möglich, für beide Nachbarn durchgeführt. Auf diese Weise wird vermieden, dass der zur Verfügung stehende Speicher zu sehr durch viele kleine Elemente in der Freispeicherliste zerteilt wird!

Im anderen Fall (weder der linke noch der rechte Nachbar begrenzen den freizugebenden Speicherbereich direkt) ist in der Freispeicherliste ein neues Element hinzuzufügen, das den freizugebenden Speicher beschreibt.

Nun zu den Details, bei der Implementierung der Release-Methode lassen sich 4 Fälle unterscheiden:

  1. Links und rechts vom freizugebenden Stück Speicher befindet sich reservierter Speicher.

  2. Der Speicher links vom freizugebenden Speicher ist nicht reserviert – im Gegensatz zur anderen Seite.

  3. Der Speicher rechts vom freizugebenden Speicher ist nicht reserviert – im Gegensatz zur anderen Seite.

  4. Links und rechts vom freizugebenden Speicher befindet sich nicht reservierter Speicher.

Im Folgenden gehen wir auf die unterschiedlichen Strategien ein, die die Release-Methode bei der Freigabe eines Teilabschnitts an den Tag zu legen hat.

1.6.1. Links und rechts vom freizugebenden Stück Speicher befindet sich reservierter Speicher.

Ist auf beiden Seiten eines freizugebenden Teilabschnitts der Speicher reserviert, bedeutet dies, dass in der Freispeicherliste ein neues Element aufzunehmen ist, das den freizugebenden Teilabschnitt beschreibt. In Abbildung 9 finden Sie beispielsweise auf beiden Seiten des Teilabschnitts ab Adresse 20 reservierten Speicher vor.

Der freizugebende Teilabschnitt ist beidseitig von reserviertem Speicher umgeben.

Abbildung 9. Der freizugebende Teilabschnitt ist beidseitig von reserviertem Speicher umgeben.


Nach dem Aufruf von

mem.Release (22);

ist die Freispeicherliste an der adäquaten Stelle um ein neues MemoryFragment-Listenelement erweitert.

1.6.2. Der Speicher links vom freizugebenden Speicher ist frei.

Die Vorgehensweise ist etwas anders, wenn auf genau einer der beiden Seiten des freizugebenden Teilabschnitts der Speicher nicht reserviert ist. In diesem Fall muss in der Freispeicherliste ein MemoryFragment-Element existieren, das den benachbarten Freispeicher beschreibt. In diesem Fall ergibt es keinen Sinn, ein neues MemoryFragment-Element in die Liste aufzunehmen. Der Inhalt des bereits vorhandenen, benachbarten MemoryFragment-Elements ist stattdessen so zu modifizieren, dass es den freizugebenden Teilabschnitt zusätzlich mit beschreibt. Im Beispiel von Abbildung 10 finden Sie die Situation vor, dass der Speicher links vom freizugebenden Teilabschnitt nicht reserviert ist. Das m_size-Element des korrespondierenden MemoryFragment-Listenelements ist nun einfach um die Länge des freizugebenden Teilabschnitts zu vergrößern.

Der Speicherbereich links vom freizugebenden Stück Speicher ist frei.

Abbildung 10. Der Speicherbereich links vom freizugebenden Stück Speicher ist frei.

1.6.3. Der Speicher rechts vom freizugebenden Speicher ist frei.

Der Vollständigkeit halber illustrieren wir auch die entgegengesetzte Situation: Der auf den freizugebenden Teilabschnitt folgende Speicherbereich ist frei und folglich durch ein MemoryFragment-Listenelement beschrieben. In diesem Fall ist zum einen das m_size-Element entsprechend zu vergrößern, zum andern ist die Anfangsadresse des Freispeichers zu ändern, wie man am einfachsten aus Abbildung 11 entnehmen kann.

Der Speicherbereich rechts vom freizugebenden Stück Speicher ist frei.

Abbildung 11. Der Speicherbereich rechts vom freizugebenden Stück Speicher ist frei.

1.6.4. Links und rechts vom freizugebenden Speicher befindet sich freier Speicher.

Bleibt noch der letzte Fall zu betrachten: Auf beiden Seiten des freizugebenden Teilabschnitts befindet sich freier Speicher. Dies bedeutet zunächst, dass für diese zwei Freispeicherabschnitte zwei MemoryFragment-Listenelemente existieren. Der freizugebenden Teilabschnitt kann in eines der zwei MemoryFragment-Listenelemente integriert werden. Das zweite wird dann aber überflüssig und ist aus der Liste zu entfernen. Die Details dieser Operation können Sie Abbildung 12 entnehmen:

Sowohl links als auch rechts vom freizugebenden Stück Speicher befindet sich freier Speicher.

Abbildung 12. Sowohl links als auch rechts vom freizugebenden Stück Speicher befindet sich freier Speicher.


In Abbildung 12 erkennen wir, dass der freizugebende Teilabschnitt in das MemoryFragment-Listenelement verschmolzen wird, das den Freispeicher links vom freizugebenden Teilabschnitt beschreibt. Das MemoryFragment-Listenelement, das den Freispeicher rechts vom freizugebenden Teilabschnitt beschreibt, ist jetzt überflüssig geworden. Da im Beispiel aus Abbildung 12 nach der Release-Anweisung keinerlei reservierter Speicher mehr vorhanden ist, besteht die Freispeicherliste nur noch aus einem einzigen Element.

2. Lösung

Quellcode: Siehe auch https://github.com/peterloos/Cpp_MemoryManagement

In einem ersten Ansatz ließen sich die beiden Klassen Memory und MemoryFragment ohne Problem voneinander getrennt realisieren. Beide Klassen stehen jedoch in einem sehr engen Verhältnis zueinander. Mit Hilfe mehrerer MemoryFragment-Objekte soll ja gerade die verfügbare Speicherplatzsituation in einem Memory-Objekt beschrieben werden. Da der Benutzer eines Memory-Objekts zwar Speicher anfordert und freigibt, sich für Internas der Speicherverwaltung aber weniger interessiert bzw. auf diese überhaupt nicht direkt zugreifen können sollte, bietet sich das C++-Sprachmittel geschachtelter Klassen (engl. nested classes) an, um die Klasse MemoryFragment im Namensraum der Memory-Klasse vor dem Anwender zu verbergen.

Die Arbeitsweise der beiden zentralen Methoden Allocate und Release wurde in der Aufgabenstellung bereits sehr ausführlich beschrieben. Bei der Implementierung fällt auf, dass es gerade Ausnahmesituationen wie etwa „Speicher komplett vergeben“ oder aber „Freispeicherliste besteht nur aus einem einzigen Element“ sind, die eine etwas komplexere bzw. länglich geratene Realisierung nach sich ziehen. Man könnte hier mit einigen simplen Tricks entgegensteuern, wie z.B. dass der freie Speicher nicht komplett zuteilbar ist, was eine kompaktere Realisierung nach sich ziehen würde. Auf der anderen Seite ist präzises Arbeiten bei der softwaretechnischen Entwicklung ein immens wichtiges Gut, deshalb habe ich bei der Realisierung diesen Weg eingeschlagen und muss deshalb bei den abschließenden Testszenarien auf keinerlei Einschränkungen verweisen.

Nach dieser ungewollten, aber notwendigen Einführung können wir uns einem Lösungsvorschlag für die Klasse Memory in Listing 1 zuwenden:

01: typedef int HANDLE;
02: 
03: class Memory
04: {
05: public:
06:     static const int Max = 128;
07: 
08: private:
09:     class MemoryFragment
10:     {
11:     public:
12:         int m_frag;              // index (pointer) to first byte of memory block
13:         int m_size;              // size of this memory block
14:         MemoryFragment* m_next;  // pointer to next free memory block
15: 
16:     public:
17:         // c'tors
18:         MemoryFragment ();
19:         MemoryFragment (int start, int size);
20:     };
21: 
22: private:
23:     unsigned char*  m_mem;   // pointer to first byte of memory
24:     int             m_len;   // total length of memory
25:     MemoryFragment* m_root;  // root of free entry list
26: 
27: public:
28:     // c'tors / d'tor
29:     Memory ();
30:     Memory (int);
31:     ~Memory ();
32: 
33:     // getter / setter
34:     int Length ();
35: 
36:     // allocation / deallocation methods
37:     HANDLE Allocate (int);
38:     void Release (HANDLE);
39: 
40:     // read / write access
41:     void SetMemory (char);
42:     void WriteShort (HANDLE ofs, short value);
43:     void WriteInteger (HANDLE ofs, int value);
44:     void WriteString (HANDLE ofs, char* s);
45:     short ReadShort(HANDLE ofs) const;
46:     int ReadInteger(HANDLE ofs) const;
47: 
48:     // dump support 
49:     void DumpFreeMemory (ostream& os);
50:     void DumpMemory (ostream& os);
51: 
52: private:
53:     // internal helper methods
54:     void DumpLine (ostream& os, HANDLE ofs, int count);
55: };

Beispiel 1. Klassen Memory und MemoryFragment: Schnittstelle.


In den Zeilen 8 bis 20 von Listing 1 finden Sie die Definition der geschachtelten Klasse MemoryFragment vor. Ihre Instanzvariablen sind alle öffentlich, da die umgebende Memory-Klasse den direkten Zugriff benötigt. Dies stellt keine Beeinträchtigung bzgl. der zuverlässigen Arbeitsweise der Memory-Klasse dar, da die innere Klasse MemoryFragment mit der Zugriffsklasse private versehen ist und folglich außerhalb ihrer umgebenden Klasse überhaupt nicht sichtbar ist.

Bezüglich des durch die Memory-Klasse zugeteilten Speichers wurde noch ein kleiner Abstrahierungsgrad eingebaut. Natürlich sind Indizes in einem Array immer vom Typ int und sollten folglich auch als solche deklariert werden. Der besseren Lesbarkeit halber wurde aber an dieser Stelle der Metadatentyp HANDLE eingeführt. Er soll zum Ausdruck bringen, dass immer, wenn Variablen des Typs HANDLE verwendet werden, diese ein Stück frei verfügbaren Speichers aus der selbst implementierten Speicherverwaltung adressieren.

Bei der Realisierung der MemoryFragment-Klasse erkennt man in Listing 2, dass diese im Wesentlichen nur dazu da ist, einzelne Knoten einer einfach verketteten Liste für Freispeicherblöcke zu beschreiben:

01: #include <iostream>
02: #include <iomanip>
03: using namespace std;
04: 
05: #include "Memory.h"
06: 
07: // c'tors / d'tor
08: Memory::MemoryFragment::MemoryFragment ()
09: {
10:     m_frag = 0;            // begin of memory block
11:     m_size = Memory::Max;  // maximum available memory
12:     m_next = this;         // circularly linked list
13: }
14: 
15: Memory::MemoryFragment::MemoryFragment (int frag, int size)
16: {
17:     m_frag = frag;  // begin of memory block
18:     m_size = size;  // size of memory block
19:     m_next = this;  // circularly linked list
20: }

Beispiel 2. Klasse MemoryFragment: Implementierung.


Wir fahren mit der Realisierung der Memory-Klasse in Listing 3 fort:

001: #include <iostream>
002: #include <iomanip>
003: using namespace std;
004: 
005: #include "Memory.h"
006: 
007: // c'tors / d'tor
008: Memory::Memory ()
009: {
010:     // allocate memory
011:     m_len = Memory::Max;
012:     m_mem = new unsigned char[m_len];
013: 
014:     // initialize memory
015:     SetMemory (' ');
016: 
017:     // initialize free entry list
018:     m_root = new MemoryFragment (0, Memory::Max);
019: }
020: 
021: Memory::Memory (int len)
022: {
023:     // allocate memory
024:     m_len = len;
025:     m_mem = new unsigned char[m_len];
026: 
027:     // initialize memory
028:     SetMemory (' ');
029: 
030:     // initialize free entry list
031:     m_root = new MemoryFragment (0, m_len);
032: }
033: 
034: Memory::~Memory ()
035: {
036:     // delete memory
037:     delete[] m_mem;
038: 
039:     // delete free entry list
040:     MemoryFragment* anchor = m_root;
041:     MemoryFragment* item = m_root;
042: 
043:     // delete each single element
044:     do
045:     {
046:         // store current node pointer
047:         MemoryFragment* current = item;
048: 
049:         // advance to next node
050:         item = item -> m_next;
051: 
052:         // delete 'current' node pointer
053:         delete current;
054:     }
055:     while (item != anchor);
056: }
057: 
058: // getter / setter
059: int Memory::Length ()
060: {
061:     return m_len;
062: }
063: 
064: // public interface
065: void Memory::SetMemory (char c)
066: {
067:     for (int i = 0; i < m_len; i ++)
068:         m_mem[i] = c;
069: }
070: 
071: void Memory::WriteString (int ofs, char* s)
072: {
073:     for (int i = 0; s[i] != '\0'; i ++)
074:         m_mem[ofs + i] = s[i];
075: }
076: 
077: void Memory::WriteShort (HANDLE ofs, short value)
078: {
079:     * ((short*) (m_mem + ofs)) = value;
080: }
081: 
082: void Memory::WriteInteger (HANDLE ofs, int value)
083: {
084:     * ((int*) (m_mem + ofs)) = value;
085: }
086: 
087: short Memory::ReadShort(HANDLE ofs) const
088: {
089:     return * ((short*) (m_mem + ofs));
090: }
091: 
092: int Memory::ReadInteger(HANDLE ofs) const
093: {
094:     return * ((int*) (m_mem + ofs));
095: }
096: 
097: int Memory::Allocate (int bytes)
098: {
099:     // check argument
100:     if (bytes <= 0)
101:         return -1;
102: 
103:     // need extra two bytes for size
104:     bytes += 2;
105: 
106:     // traverse free entry list
107:     MemoryFragment* frag = m_root;
108:     MemoryFragment* last = m_root;
109: 
110:     do
111:     {
112:         /* fragment's size too small
113:         */
114:         if (frag -> m_size < bytes)
115:         {
116:             // advance to next entry
117:             last = frag;
118:             frag = frag -> m_next;
119:         }
120:         /* fragment's size equals requested size
121:         */
122:         else if (frag -> m_size == bytes)
123:         {
124:             // drop current block from list
125:             int ofs = frag -> m_frag;
126: 
127:             // poke size of this block into memory
128:             * (short*) (m_mem + ofs) = bytes;
129: 
130:             // free entry list contains of a single node
131:             if (frag -> m_next == m_root)
132:             {
133:                 // setup single fragment with size of zero
134:                 frag -> m_size = 0;
135:             }
136:             else
137:             {
138:                 // drop current block from list
139:                 MemoryFragment* tmp = frag;
140:                 last -> m_next = frag -> m_next;
141:                 delete tmp;
142:             }
143: 
144:             return ofs + 2;
145:         }
146:         /* fragment's size is larger than the requested size
147:         */
148:         else
149:         {
150:             // calculate start offset
151:             int ofs = frag -> m_frag + frag -> m_size - bytes;
152: 
153:             // poke requested block size into memory
154:             * (short*) (m_mem + ofs) = bytes;
155: 
156:             // reduce size of current memory fragment
157:             frag -> m_size -= bytes;
158: 
159:             return ofs + 2;
160:         }
161:     }
162:     while (frag != m_root);
163: 
164:     // no fragment found, suitable memory fragment not available
165:     return -1;
166: }
167: 
168: void Memory::Release (int idx)
169: {
170:     // make idx point to begin of memory block
171:     idx -= 2;
172: 
173:     // retrieve size of current memory block
174:     short size = * (short*) (m_mem + idx);
175: 
176:     // only one free entry available
177:     if (m_root == m_root -> m_next)
178:     {
179:         /* is begin of current block adjacent with end of preceding free block
180:         */
181:         if (m_root -> m_frag + m_root -> m_size == idx)
182:         {
183:             // expand preceding block
184:             m_root -> m_size += size;
185:         }
186:         /* is end of current block adjacent with next free block
187:         */
188:         else if (idx + size == m_root -> m_frag)
189:         {
190:             m_root -> m_frag = idx;
191:             m_root -> m_size += size;
192:         }
193:         /* current block is not adjacent with single block in free entry list
194:         */
195:         else
196:         {
197:             // single block in free entry list describes non-empty memory block
198:             if (m_root -> m_size != 0)
199:             {
200:                 MemoryFragment* fp = new MemoryFragment (idx, size);
201: 
202:                 if (idx < m_root -> m_frag)
203:                 {
204:                     fp -> m_next = m_root;
205:                     m_root -> m_next = fp;
206:                     m_root = fp;
207:                 }
208:                 else
209:                 {
210:                     m_root -> m_next = fp;
211:                     fp -> m_next = m_root;
212:                 }
213:             }
214:             else
215:             {
216:                 m_root -> m_frag = idx;
217:                 m_root -> m_size = size;
218:             }
219:         }
220:     }
221:     else
222:     {
223:         /* locate left and right neighbour in free entry list
224:         */
225:         MemoryFragment* leftFrag = m_root;
226:         MemoryFragment* rightFrag = m_root -> m_next;
227: 
228:         MemoryFragment* tmp = m_root;
229:         while (true)
230:         {
231:             // end of list reached
232:             if (tmp -> m_next == m_root)
233:                 break;
234: 
235:             leftFrag = tmp;
236:             rightFrag = tmp -> m_next;
237: 
238:             // is memory block between these two free memory blocks?
239:             if (tmp -> m_frag < idx && idx < tmp -> m_next -> m_frag)
240:                 break;
241: 
242:             tmp = tmp -> m_next;
243:         }
244: 
245:         // 1.) block to release is before the first free memory area
246:         if (idx < leftFrag -> m_frag)
247:         {
248:             // a) blocks are adjacent
249:             if (idx + size == leftFrag -> m_frag)
250:             {
251:                 leftFrag -> m_frag = idx;
252:                 leftFrag -> m_size += size;
253:             }
254:             // b) blocks are not adjacent
255:             else
256:             {
257:                 MemoryFragment* fp = new MemoryFragment (idx, size);
258: 
259:                 // insert node at begin of list
260:                 fp -> m_next = leftFrag;
261: 
262:                 // last node has to point to new first node
263:                 while (rightFrag -> m_next != m_root)
264:                     rightFrag = rightFrag -> m_next;
265:                 rightFrag -> m_next = fp;
266: 
267:                 // make root pointing to new first node
268:                 m_root = fp;
269:             }
270:         }
271: 
272:         // 2.) block to release is after the last free memory area
273:         else if (idx >= rightFrag -> m_frag + rightFrag -> m_size)
274:         {
275:             // a) blocks are adjacent
276:             if (idx == rightFrag -> m_frag + rightFrag -> m_size)
277:             {
278:                 rightFrag -> m_size += size;
279:             }
280:             // b) blocks are not adjacent
281:             else
282:             {
283:                 MemoryFragment* fp = new MemoryFragment (idx, size);
284:                 fp -> m_next = m_root;
285:                 rightFrag -> m_next = fp;
286:             }
287:         }
288: 
289:         // 3.) block to release is between two free memory areas
290:         else
291:         {
292:             /* is current block adjacent with both neighbouring blocks
293:             */
294:             if (leftFrag -> m_frag + leftFrag -> m_size == idx &&
295:                 rightFrag -> m_frag == idx + size)
296:             {
297:                 // expand preceding block
298:                 leftFrag -> m_size += size;
299:                 leftFrag -> m_size += rightFrag -> m_size;
300: 
301:                 // drop next block from list
302:                 leftFrag -> m_next = rightFrag -> m_next;
303:                 delete rightFrag;
304:             }
305:             /* is begin of current block adjacent with end of preceding free block
306:             */
307:             else if (leftFrag -> m_frag + leftFrag -> m_size == idx)
308:             {
309:                 // expand preceding block
310:                 leftFrag -> m_size += size;
311:             }
312:             /* is end of current block adjacent with next free block
313:             */
314:             else if (rightFrag -> m_frag == idx + size)
315:             {
316:                 // expand next block
317:                 rightFrag -> m_frag = idx;
318:                 rightFrag -> m_size += size;
319:             }
320:             /* current block is not adjacent with both neighbouring blocks
321:             */
322:             else
323:             {
324:                 // insert new MemoryFragment descriptor into linked list
325:                 MemoryFragment* fp = new MemoryFragment (idx, size);
326:                 fp -> m_next = rightFrag;
327:                 leftFrag -> m_next = fp;
328:             }
329:         }
330:     }
331: }
332: 
333: void Memory::DumpFreeMemory (ostream& os)
334: {
335:     os << "Dump of Free List:" << endl;
336: 
337:     MemoryFragment* frag = m_root;
338:     do
339:     {
340:         os << "Start: " << setfill (' ') << dec << setw (3) << frag -> m_frag << " - "
341:            << "Size: "  << setfill (' ') << dec << setw (3) << frag -> m_size << endl;
342: 
343:         frag = frag -> m_next;
344:     }
345:     while (frag != m_root);
346: 
347:     os << endl;
348: }
349:     
350: void Memory::DumpMemory (ostream& os)
351: {
352:     for (int line = 0;; line += 16)
353:     {
354:         int count = (m_len - line) < 16 ? m_len - line : 16;
355:         DumpLine (os, line, count);
356: 
357:         if (count < 16)
358:             break;
359:     }
360: }
361: 
362: // internal helper methods
363: void Memory::DumpLine (ostream& os, int ofs, int count)
364: {
365:     if (count== 0)
366:         return;
367: 
368:     os << setfill ('0') << setw (8) << hex << ofs << "  " ;
369: 
370:     // writing binary representation of byte
371:     for (int i = 0; i < count; i ++)
372:     {
373:         int byte = m_mem[ofs + i];
374:         os << setw (2) << setfill ('0') << hex << uppercase << byte << ' ';
375: 
376:         if ((i + 1) % 8 == 0)
377:             os << ' ';
378:     }
379:     os << ' ';
380: 
381:     // writing readable representation of byte
382:     for (int i = 0; i < count; i ++)
383:     {
384:         unsigned char c = (m_mem[ofs + i] >= ' ' && m_mem[ofs + i] < '~') ?
385:             m_mem[ofs + i] : '.';
386:         os << c;
387:     }
388:     os << endl;
389: }

Beispiel 3. Klasse Memory: Implementierung.


Im folgenden Testrahmen testen wir die beiden Methoden Allocate und Release zusammen. Bei der Allokation haben wir es darauf angelegt, dass die 128 zur Verfügung stehenden Bytes komplett allokiert werden:

void main ()
{
    Memory mem (128);
    mem.DumpFreeMemory (cout);

    HANDLE n;

    for (int i = 0; i < 12; i ++)
    {
        n = mem.Allocate (8);
        cout << "Allocate: n=" << n << endl;
    }

    // allocate final remaining 6(+2) bytes
    n = mem.Allocate (6);
    cout << "Allocate: n=" << n << endl;
    mem.DumpFreeMemory (cout);

    for (int i = 1; i <= 12; i ++)
    {
        cout << "Release: " << i * 10 << endl;
        mem.Release (i * 10);
    }    

    cout << "Release: " << 2 << endl;
    mem.Release (2);
    mem.DumpFreeMemory (cout);
}

Ausführung:

Dump of Free List:
Start:   0 - Size: 128

Allocate: n=120
Allocate: n=110
Allocate: n=100
Allocate: n=90
Allocate: n=80
Allocate: n=70
Allocate: n=60
Allocate: n=50
Allocate: n=40
Allocate: n=30
Allocate: n=20
Allocate: n=10
Allocate: n=2
Dump of Free List:
Start:   0 - Size:   0

Release: 10
Release: 20
Release: 30
Release: 40
Release: 50
Release: 60
Release: 70
Release: 80
Release: 90
Release: 100
Release: 110
Release: 120
Release: 2
Dump of Free List:
Start:   0 - Size: 128

Wir bewegen uns in schnellen Schritten auf das eigentliche Ziel dieser Aufgabe zu: An Hand einer einfachen Real-World Application wollen wir unsere selbst implementierte Speicherverwaltung zum Einsatz bringen. Im Untermenü „Dynamische Datenstrukturen“ dieses Portals finden Sie eine Simulation des Josephus-Problems vor. Eine der vorgestellten Lösungen basiert auf einer einfach verketteten Liste. Diese Aufgabe ist also nahezu prädestiniert dazu, von der C++-Standardspeicherverwaltung auf unsere Klasse Memory portiert zu werden.

Der Fairness halber ist zu erwähnen, dass die beiden Methoden Allocate und Release – im Gegensatz zu den beiden C++-Operatoren new und delete – nur untypisierte Speicherbereiche verwalten. An Stelle der Klasse Soldier, deren Objekte im Original-Lösungsvorschlag die Knoten der verketteten Liste bilden, müssen wir nun die dynamisch allokierten Speicherbereiche selbst verwalten. Am vorliegenden Beispiel ist dies nicht sonderlich schlimm, da wir nur Nummern der Soldaten sowie Indizes der Listenknoten zu betrachten haben. Mit den vier Methoden WriteShort, WriteInteger, ReadShort und ReadInteger lässt sich dies einfach bewerkstelligen. Ohne tieferen Hintergrund habe ich für die Nummer eines Soldaten zwei Bytes Speicher vorgesehen, die beiden Methoden ReadShort und WriteShort sind damit unsere Kandidaten zum Ein- und Auszulesen einer Nummer. Um die einzelnen Speicherabschnitte miteinander zu verketten, habe ich für den next-Index vier Bytes Speicher reserviert. Die zwei Methoden WriteInteger und ReadInteger sind damit auch im Spiel. Die genaue Lage der Informationen innerhalb eines Speicherabschnitts müssen wir ebenfalls noch festlegen, Abbildung 13 zeigt das genaue Speicherabbild auf:

Speicherlayout eines selbstverwalteten Listenknotens.

Abbildung 13. Speicherlayout eines selbstverwalteten Listenknotens.


Die Portierung der Klasse Josephus (Schnittstelle und Realisierung) können Sie nun in Listing 4 und Listing 5 entnehmen. Wenn mir kein Fehler unterlaufen ist, sollten Sie die beiden C++-Operatoren new und delete nirgends mehr vorfinden, dafür aber entsprechende Lese- und Schreibzugriffe auf ein Memory-Objekt:

01: class Josephus
02: {
03: private:
04:     static const int DefaultPassBy = 10;  // default "decimatio"
05: 
06: private:
07:     // memory object
08:     Memory m_mem;
09: 
10:     // root of soldiers
11:     HANDLE  m_root;        // root of linked list of soldiers
12:     HANDLE  m_current;     // current soldier
13: 
14:     int m_count;           // total number of soldiers
15:     int m_alive;           // number of alive soldiers
16:     int m_lastEliminated;  // last eliminated soldier
17:     int m_passby;          // "decimatio"
18: 
19: public:
20:     // c'tor(s), d'tor
21:     Josephus ();
22:     Josephus (int);
23:     ~Josephus (); 
24: 
25:     // getter/setter
26:     int Count () const { return m_count; }
27:     int Alive () const { return m_alive; }
28:     int LastEliminated () { return m_lastEliminated; }
29:     int LastAlive () { return m_mem.ReadShort (m_current); } 
30:     int PassBy () { return m_passby; }
31:     void SetPassBy (int passby) { m_passby = passby; }
32: 
33:     // public interface
34:     bool EliminateNextSoldier();
35:     void EliminateAll();
36: 
37: private:
38:     // private helper methods
39:     void CreateLinkedList();
40: 
41:     // operators
42:     friend ostream& operator<< (ostream&, const Josephus&);
43: };

Beispiel 4. Klasse Josephus: Schnittstelle.


001: #include <iostream>
002: using namespace std;
003: 
004: #include "Memory.h"
005: #include "Josephus.h"
006: 
007: #define  DUMP_MEMORY    1
008: 
009: // c'tor(s), d'tor
010: Josephus::Josephus()
011:     : m_mem(512), m_count(41), m_alive(41), m_lastEliminated(0)
012: {
013: #if defined (DUMP_MEMORY)
014:     m_mem.DumpFreeMemory(cout);
015:     cout << endl;
016:     m_mem.DumpMemory(cout);
017: #endif
018: 
019:     m_passby = Josephus::DefaultPassBy;
020:     CreateLinkedList();
021: }
022: 
023: Josephus::Josephus(int count)
024:     : m_mem(512), m_count(count), m_alive(count), m_lastEliminated(0)
025: {
026: #if defined (DUMP_MEMORY)
027:     m_mem.DumpFreeMemory(cout);
028:     cout << endl;
029:     m_mem.DumpMemory(cout);
030: #endif
031: 
032:     m_passby = Josephus::DefaultPassBy;
033:     CreateLinkedList();
034: }
035: 
036: Josephus::~Josephus()
037: {
038:     HANDLE soldier = m_root;
039:     
040:     // delete each single element
041:     do 
042:     {
043:         // store current node pointer
044:         HANDLE current = soldier;
045:     
046:         // advance to next node
047:         soldier = m_mem.ReadInteger (soldier + 2);
048:     
049:         // delete 'current' node pointer
050:         m_mem.Release (current);
051:     }
052:     while (soldier != m_root);
053: 
054:     cout << endl;
055: 
056: #if defined (DUMP_MEMORY)
057:     m_mem.DumpFreeMemory(cout);
058:     cout << endl;
059:     m_mem.DumpMemory(cout);
060: #endif
061: }
062: 
063: // public interface
064: bool Josephus::EliminateNextSoldier()
065: {
066:     // more than one soldier?
067:     if (m_alive == 1)
068:         return false;
069:         
070:     // locate next soldier
071:     for (int i = 0; i < m_passby - 1; i ++)
072:         m_current = m_mem.ReadInteger (m_current + 2);
073: 
074:     // remove soldier from list
075:     HANDLE node = m_mem.ReadInteger (m_current + 2);
076:     HANDLE next = m_mem.ReadInteger (node + 2);
077:     m_mem.WriteInteger (m_current + 2, next);
078: 
079:     // take care, if root object is removed
080:     if (m_root == node)
081:         m_root = m_mem.ReadInteger (m_root + 2);
082: 
083:     m_lastEliminated = m_mem.ReadShort (node);
084:     m_mem.Release (node);
085:     m_alive --;
086: 
087: #if defined (DUMP_MEMORY)
088:     m_mem.DumpFreeMemory(cout);
089: #endif
090: 
091:     return true;
092: }
093: 
094: void Josephus::EliminateAll()
095: {
096:     while (EliminateNextSoldier())
097:         ;
098: }
099: 
100: // private helper methods
101: void Josephus::CreateLinkedList()
102: {
103:     // allocate memory for first soldier
104:     m_root = m_mem.Allocate (6);
105:     m_mem.WriteShort (m_root, 1);
106:     m_mem.WriteInteger (m_root + 2, (HANDLE) 0);
107: 
108:     m_current = m_root;
109: 
110:     for (int i = 1; i < m_count; i ++)
111:     {
112:         // allocate memory for a new soldier
113:         HANDLE tmp = m_mem.Allocate (6);
114:         m_mem.WriteShort (tmp, i + 1);
115: 
116: #if defined (DUMP_MEMORY)
117:     m_mem.DumpFreeMemory(cout);
118: #endif
119: 
120:         // link previous soldier with current one
121:         m_mem.WriteInteger (m_current + 2, tmp);
122:         m_current = tmp;
123:     }
124: 
125:     // link last soldier with first one
126:     m_mem.WriteInteger (m_current + 2, m_root);
127: }
128: 
129: // output
130: ostream& operator<< (ostream& os, const Josephus& j)
131: {
132:     os << '[';
133:     HANDLE tmp = j.m_root;
134:     do
135:     {
136:         short number = j.m_mem.ReadShort (tmp);
137:         os << number;
138: 
139:         HANDLE next = j.m_mem.ReadInteger (tmp + 2);
140:         if (next != j.m_root)
141:             os << ',';
142: 
143:         tmp = j.m_mem.ReadInteger (tmp + 2);
144:     }
145:     while (tmp != j.m_root);
146:     os << ']';
147:     return os;
148: }

Beispiel 5. Klasse Josephus: Implementierung.


Wenn wir bei der Realisierung nichts verkehrt machen, erhalten wir dasselbe Ergebnis für das Josephus-Problem wie in der Originallösung. Weitaus interessanter sind zusätzliche Traceausgaben der dynamischen Speicherverwaltung, die an zentralen Stellen des Programms ergänzt wurden. Die Ausgabe des Programms ist auf Grund dessen um einiges länger, dafür legt sie das Innenleben der dynamischen Speicherverwaltung auf eindrucksvolle Weise offen. Die Ausgaben des eigentlichen Programms sowie die Traceausgaben treten natürlich miteinander vermischt auf. Der besseren Lesbarkeit halber fangen die Ausgaben des eigentlichen Hauptprogramms mit der Zeichenkette „==>“ an. Am Ende der Programmausführung können Sie sich von zwei wesentlichen Beobachtungen überzeugen: Es wird das korrekte Ergebnis des Josephus-Problems-Problems berechnet, und: Der Speicher der selbst implementierten Speicherverwaltung (512 Bytes) ist am Ende der Programmausführung wieder komplett freigegeben worden.

Damit sind wir am Ende der Lösungsbetrachtungen angelangt, abschließend viel Spaß beim Studium des Lösungsprotokolls zum Josephus-Problem:

Dump of Free List:
Start:   0 - Size: 512


00000000  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000010  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000020  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000030  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000040  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000050  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000060  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000070  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000080  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000090  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
000000A0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
000000B0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
000000C0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
000000D0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
000000E0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
000000F0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000100  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000110  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000120  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000130  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000140  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000150  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000160  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000170  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000180  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000190  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
000001A0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
000001B0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
000001C0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
000001D0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
000001E0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
000001F0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
Dump of Free List:
Start:   0 - Size: 496

Dump of Free List:
Start:   0 - Size: 488

Dump of Free List:
Start:   0 - Size: 480

Dump of Free List:
Start:   0 - Size: 472

Dump of Free List:
Start:   0 - Size: 464

Dump of Free List:
Start:   0 - Size: 456

Dump of Free List:
Start:   0 - Size: 448

Dump of Free List:
Start:   0 - Size: 440

Dump of Free List:
Start:   0 - Size: 432

Dump of Free List:
Start:   0 - Size: 424

Dump of Free List:
Start:   0 - Size: 416

Dump of Free List:
Start:   0 - Size: 408

Dump of Free List:
Start:   0 - Size: 400

Dump of Free List:
Start:   0 - Size: 392

Dump of Free List:
Start:   0 - Size: 384

Dump of Free List:
Start:   0 - Size: 376

Dump of Free List:
Start:   0 - Size: 368

Dump of Free List:
Start:   0 - Size: 360

Dump of Free List:
Start:   0 - Size: 352

Dump of Free List:
Start:   0 - Size: 344

Dump of Free List:
Start:   0 - Size: 336

Dump of Free List:
Start:   0 - Size: 328

Dump of Free List:
Start:   0 - Size: 320

Dump of Free List:
Start:   0 - Size: 312

Dump of Free List:
Start:   0 - Size: 304

Dump of Free List:
Start:   0 - Size: 296

Dump of Free List:
Start:   0 - Size: 288

Dump of Free List:
Start:   0 - Size: 280

Dump of Free List:
Start:   0 - Size: 272

Dump of Free List:
Start:   0 - Size: 264

Dump of Free List:
Start:   0 - Size: 256

Dump of Free List:
Start:   0 - Size: 248

Dump of Free List:
Start:   0 - Size: 240

Dump of Free List:
Start:   0 - Size: 232

Dump of Free List:
Start:   0 - Size: 224

Dump of Free List:
Start:   0 - Size: 216

Dump of Free List:
Start:   0 - Size: 208

Dump of Free List:
Start:   0 - Size: 200

Dump of Free List:
Start:   0 - Size: 192

Dump of Free List:
Start:   0 - Size: 184

==> Number of soldiers: 41
==> Eliminating: Each 3. soldier

Dump of Free List:
Start:   0 - Size: 184
Start: 488 - Size:   8

==> Removed  3
Dump of Free List:
Start:   0 - Size: 184
Start: 464 - Size:   8
Start: 488 - Size:   8

==> Removed  6
Dump of Free List:
Start:   0 - Size: 184
Start: 440 - Size:   8
Start: 464 - Size:   8
Start: 488 - Size:   8

==> Removed  9
Dump of Free List:
Start:   0 - Size: 184
Start: 416 - Size:   8
Start: 440 - Size:   8
Start: 464 - Size:   8
Start: 488 - Size:   8

==> Removed 12
Dump of Free List:
Start:   0 - Size: 184
Start: 392 - Size:   8
Start: 416 - Size:   8
Start: 440 - Size:   8
Start: 464 - Size:   8
Start: 488 - Size:   8

==> Removed 15
Dump of Free List:
Start:   0 - Size: 184
Start: 368 - Size:   8
Start: 392 - Size:   8
Start: 416 - Size:   8
Start: 440 - Size:   8
Start: 464 - Size:   8
Start: 488 - Size:   8

==> Removed 18
Dump of Free List:
Start:   0 - Size: 184
Start: 344 - Size:   8
Start: 368 - Size:   8
Start: 392 - Size:   8
Start: 416 - Size:   8
Start: 440 - Size:   8
Start: 464 - Size:   8
Start: 488 - Size:   8

==> Removed 21
Dump of Free List:
Start:   0 - Size: 184
Start: 320 - Size:   8
Start: 344 - Size:   8
Start: 368 - Size:   8
Start: 392 - Size:   8
Start: 416 - Size:   8
Start: 440 - Size:   8
Start: 464 - Size:   8
Start: 488 - Size:   8

==> Removed 24
Dump of Free List:
Start:   0 - Size: 184
Start: 296 - Size:   8
Start: 320 - Size:   8
Start: 344 - Size:   8
Start: 368 - Size:   8
Start: 392 - Size:   8
Start: 416 - Size:   8
Start: 440 - Size:   8
Start: 464 - Size:   8
Start: 488 - Size:   8

==> Removed 27
Dump of Free List:
Start:   0 - Size: 184
Start: 272 - Size:   8
Start: 296 - Size:   8
Start: 320 - Size:   8
Start: 344 - Size:   8
Start: 368 - Size:   8
Start: 392 - Size:   8
Start: 416 - Size:   8
Start: 440 - Size:   8
Start: 464 - Size:   8
Start: 488 - Size:   8

==> Removed 30
Dump of Free List:
Start:   0 - Size: 184
Start: 248 - Size:   8
Start: 272 - Size:   8
Start: 296 - Size:   8
Start: 320 - Size:   8
Start: 344 - Size:   8
Start: 368 - Size:   8
Start: 392 - Size:   8
Start: 416 - Size:   8
Start: 440 - Size:   8
Start: 464 - Size:   8
Start: 488 - Size:   8

==> Removed 33
Dump of Free List:
Start:   0 - Size: 184
Start: 224 - Size:   8
Start: 248 - Size:   8
Start: 272 - Size:   8
Start: 296 - Size:   8
Start: 320 - Size:   8
Start: 344 - Size:   8
Start: 368 - Size:   8
Start: 392 - Size:   8
Start: 416 - Size:   8
Start: 440 - Size:   8
Start: 464 - Size:   8
Start: 488 - Size:   8

==> Removed 36
Dump of Free List:
Start:   0 - Size: 184
Start: 200 - Size:   8
Start: 224 - Size:   8
Start: 248 - Size:   8
Start: 272 - Size:   8
Start: 296 - Size:   8
Start: 320 - Size:   8
Start: 344 - Size:   8
Start: 368 - Size:   8
Start: 392 - Size:   8
Start: 416 - Size:   8
Start: 440 - Size:   8
Start: 464 - Size:   8
Start: 488 - Size:   8

==> Removed 39
Dump of Free List:
Start:   0 - Size: 184
Start: 200 - Size:   8
Start: 224 - Size:   8
Start: 248 - Size:   8
Start: 272 - Size:   8
Start: 296 - Size:   8
Start: 320 - Size:   8
Start: 344 - Size:   8
Start: 368 - Size:   8
Start: 392 - Size:   8
Start: 416 - Size:   8
Start: 440 - Size:   8
Start: 464 - Size:   8
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed  1
Dump of Free List:
Start:   0 - Size: 184
Start: 200 - Size:   8
Start: 224 - Size:   8
Start: 248 - Size:   8
Start: 272 - Size:   8
Start: 296 - Size:   8
Start: 320 - Size:   8
Start: 344 - Size:   8
Start: 368 - Size:   8
Start: 392 - Size:   8
Start: 416 - Size:   8
Start: 440 - Size:   8
Start: 464 - Size:  16
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed  5
Dump of Free List:
Start:   0 - Size: 184
Start: 200 - Size:   8
Start: 224 - Size:   8
Start: 248 - Size:   8
Start: 272 - Size:   8
Start: 296 - Size:   8
Start: 320 - Size:   8
Start: 344 - Size:   8
Start: 368 - Size:   8
Start: 392 - Size:   8
Start: 416 - Size:   8
Start: 432 - Size:  16
Start: 464 - Size:  16
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 10
Dump of Free List:
Start:   0 - Size: 184
Start: 200 - Size:   8
Start: 224 - Size:   8
Start: 248 - Size:   8
Start: 272 - Size:   8
Start: 296 - Size:   8
Start: 320 - Size:   8
Start: 344 - Size:   8
Start: 368 - Size:   8
Start: 392 - Size:  16
Start: 416 - Size:   8
Start: 432 - Size:  16
Start: 464 - Size:  16
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 14
Dump of Free List:
Start:   0 - Size: 184
Start: 200 - Size:   8
Start: 224 - Size:   8
Start: 248 - Size:   8
Start: 272 - Size:   8
Start: 296 - Size:   8
Start: 320 - Size:   8
Start: 344 - Size:   8
Start: 360 - Size:  16
Start: 392 - Size:  16
Start: 416 - Size:   8
Start: 432 - Size:  16
Start: 464 - Size:  16
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 19
Dump of Free List:
Start:   0 - Size: 184
Start: 200 - Size:   8
Start: 224 - Size:   8
Start: 248 - Size:   8
Start: 272 - Size:   8
Start: 296 - Size:   8
Start: 320 - Size:  16
Start: 344 - Size:   8
Start: 360 - Size:  16
Start: 392 - Size:  16
Start: 416 - Size:   8
Start: 432 - Size:  16
Start: 464 - Size:  16
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 23
Dump of Free List:
Start:   0 - Size: 184
Start: 200 - Size:   8
Start: 224 - Size:   8
Start: 248 - Size:   8
Start: 272 - Size:   8
Start: 288 - Size:  16
Start: 320 - Size:  16
Start: 344 - Size:   8
Start: 360 - Size:  16
Start: 392 - Size:  16
Start: 416 - Size:   8
Start: 432 - Size:  16
Start: 464 - Size:  16
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 28
Dump of Free List:
Start:   0 - Size: 184
Start: 200 - Size:   8
Start: 224 - Size:   8
Start: 248 - Size:  16
Start: 272 - Size:   8
Start: 288 - Size:  16
Start: 320 - Size:  16
Start: 344 - Size:   8
Start: 360 - Size:  16
Start: 392 - Size:  16
Start: 416 - Size:   8
Start: 432 - Size:  16
Start: 464 - Size:  16
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 32
Dump of Free List:
Start:   0 - Size: 184
Start: 200 - Size:   8
Start: 216 - Size:  16
Start: 248 - Size:  16
Start: 272 - Size:   8
Start: 288 - Size:  16
Start: 320 - Size:  16
Start: 344 - Size:   8
Start: 360 - Size:  16
Start: 392 - Size:  16
Start: 416 - Size:   8
Start: 432 - Size:  16
Start: 464 - Size:  16
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 37
Dump of Free List:
Start:   0 - Size: 192
Start: 200 - Size:   8
Start: 216 - Size:  16
Start: 248 - Size:  16
Start: 272 - Size:   8
Start: 288 - Size:  16
Start: 320 - Size:  16
Start: 344 - Size:   8
Start: 360 - Size:  16
Start: 392 - Size:  16
Start: 416 - Size:   8
Start: 432 - Size:  16
Start: 464 - Size:  16
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 41
Dump of Free List:
Start:   0 - Size: 192
Start: 200 - Size:   8
Start: 216 - Size:  16
Start: 248 - Size:  16
Start: 272 - Size:   8
Start: 288 - Size:  16
Start: 320 - Size:  16
Start: 344 - Size:   8
Start: 360 - Size:  16
Start: 392 - Size:  16
Start: 416 - Size:   8
Start: 432 - Size:  16
Start: 456 - Size:  24
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed  7
Dump of Free List:
Start:   0 - Size: 192
Start: 200 - Size:   8
Start: 216 - Size:  16
Start: 248 - Size:  16
Start: 272 - Size:   8
Start: 288 - Size:  16
Start: 320 - Size:  16
Start: 344 - Size:   8
Start: 360 - Size:  16
Start: 392 - Size:  32
Start: 432 - Size:  16
Start: 456 - Size:  24
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 13
Dump of Free List:
Start:   0 - Size: 192
Start: 200 - Size:   8
Start: 216 - Size:  16
Start: 248 - Size:  16
Start: 272 - Size:   8
Start: 288 - Size:  16
Start: 320 - Size:  16
Start: 344 - Size:  32
Start: 392 - Size:  32
Start: 432 - Size:  16
Start: 456 - Size:  24
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 20
Dump of Free List:
Start:   0 - Size: 192
Start: 200 - Size:   8
Start: 216 - Size:  16
Start: 248 - Size:  16
Start: 272 - Size:   8
Start: 288 - Size:  24
Start: 320 - Size:  16
Start: 344 - Size:  32
Start: 392 - Size:  32
Start: 432 - Size:  16
Start: 456 - Size:  24
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 26
Dump of Free List:
Start:   0 - Size: 192
Start: 200 - Size:   8
Start: 216 - Size:  16
Start: 240 - Size:  24
Start: 272 - Size:   8
Start: 288 - Size:  24
Start: 320 - Size:  16
Start: 344 - Size:  32
Start: 392 - Size:  32
Start: 432 - Size:  16
Start: 456 - Size:  24
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 34
Dump of Free List:
Start:   0 - Size: 208
Start: 216 - Size:  16
Start: 240 - Size:  24
Start: 272 - Size:   8
Start: 288 - Size:  24
Start: 320 - Size:  16
Start: 344 - Size:  32
Start: 392 - Size:  32
Start: 432 - Size:  16
Start: 456 - Size:  24
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 40
Dump of Free List:
Start:   0 - Size: 208
Start: 216 - Size:  16
Start: 240 - Size:  24
Start: 272 - Size:   8
Start: 288 - Size:  24
Start: 320 - Size:  16
Start: 344 - Size:  32
Start: 392 - Size:  32
Start: 432 - Size:  48
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed  8
Dump of Free List:
Start:   0 - Size: 208
Start: 216 - Size:  16
Start: 240 - Size:  24
Start: 272 - Size:   8
Start: 288 - Size:  24
Start: 320 - Size:  16
Start: 344 - Size:  40
Start: 392 - Size:  32
Start: 432 - Size:  48
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 17
Dump of Free List:
Start:   0 - Size: 208
Start: 216 - Size:  16
Start: 240 - Size:  24
Start: 272 - Size:  40
Start: 320 - Size:  16
Start: 344 - Size:  40
Start: 392 - Size:  32
Start: 432 - Size:  48
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 29
Dump of Free List:
Start:   0 - Size: 232
Start: 240 - Size:  24
Start: 272 - Size:  40
Start: 320 - Size:  16
Start: 344 - Size:  40
Start: 392 - Size:  32
Start: 432 - Size:  48
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 38
Dump of Free List:
Start:   0 - Size: 232
Start: 240 - Size:  24
Start: 272 - Size:  40
Start: 320 - Size:  16
Start: 344 - Size:  40
Start: 392 - Size:  88
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 11
Dump of Free List:
Start:   0 - Size: 232
Start: 240 - Size:  24
Start: 272 - Size:  64
Start: 344 - Size:  40
Start: 392 - Size:  88
Start: 488 - Size:   8
Start: 504 - Size:   8

==> Removed 25
Dump of Free List:
Start:   0 - Size: 232
Start: 240 - Size:  24
Start: 272 - Size:  64
Start: 344 - Size:  40
Start: 392 - Size:  88
Start: 488 - Size:  24

==> Removed  2
Dump of Free List:
Start:   0 - Size: 232
Start: 240 - Size:  24
Start: 272 - Size: 112
Start: 392 - Size:  88
Start: 488 - Size:  24

==> Removed 22
Dump of Free List:
Start:   0 - Size: 232
Start: 240 - Size:  24
Start: 272 - Size: 112
Start: 392 - Size: 120

==> Removed  4
Dump of Free List:
Start:   0 - Size: 264
Start: 272 - Size: 112
Start: 392 - Size: 120

==> Removed 35
Dump of Free List:
Start:   0 - Size: 264
Start: 272 - Size: 240

==> Removed 16

==> Last soldier: 31
==> Last eliminated: 16

Dump of Free List:
Start:   0 - Size: 512


00000000  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000010  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000020  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000030  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000040  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000050  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000060  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000070  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000080  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
00000090  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
000000A0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20
000000B0  20 20 20 20 20 20 20 20  08 00 29 00 F2 01 00 00           ..).....
000000C0  08 00 28 00 F2 01 00 00  08 00 27 00 C2 00 00 00   ..(.......'.....
000000D0  08 00 26 00 F2 01 00 00  08 00 25 00 D2 00 00 00   ..&.......%.....
000000E0  08 00 24 00 DA 00 00 00  08 00 23 00 82 01 00 00   ..$.......#.....
000000F0  08 00 22 00 EA 00 00 00  08 00 21 00 F2 00 00 00   ..".......!.....
00000100  08 00 20 00 F2 00 00 00  08 00 1F 00 0A 01 00 00   .. .............
00000110  08 00 1E 00 0A 01 00 00  08 00 1D 00 0A 01 00 00   ................
00000120  08 00 1C 00 1A 01 00 00  08 00 1B 00 22 01 00 00   ............"...
00000130  08 00 1A 00 1A 01 00 00  08 00 19 00 0A 01 00 00   ................
00000140  08 00 18 00 3A 01 00 00  08 00 17 00 3A 01 00 00   ....:.......:...
00000150  08 00 16 00 0A 01 00 00  08 00 15 00 52 01 00 00   ............R...
00000160  08 00 14 00 52 01 00 00  08 00 13 00 62 01 00 00   ....R.......b...
00000170  08 00 12 00 6A 01 00 00  08 00 11 00 52 01 00 00   ....j.......R...
00000180  08 00 10 00 0A 01 00 00  08 00 0F 00 82 01 00 00   ................
00000190  08 00 0E 00 82 01 00 00  08 00 0D 00 82 01 00 00   ................
000001A0  08 00 0C 00 9A 01 00 00  08 00 0B 00 82 01 00 00   ................
000001B0  08 00 0A 00 AA 01 00 00  08 00 09 00 B2 01 00 00   ................
000001C0  08 00 08 00 AA 01 00 00  08 00 07 00 C2 01 00 00   ................
000001D0  08 00 06 00 CA 01 00 00  08 00 05 00 CA 01 00 00   ................
000001E0  08 00 04 00 82 01 00 00  08 00 03 00 E2 01 00 00   ................
000001F0  08 00 02 00 E2 01 00 00  08 00 01 00 F2 01 00 00   ................