Speicherverwaltung implementieren

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Speicherverwaltung implementieren

    Ich hab hier so mein Problem mit dieser Aufgabenstellung:


    Listen arbeiten optimal mit Datenelementen unterschiedlicher Größe. Die Speicherverwaltung des C++ Heaps ist als Liste implementiert.

    Implementieren Sie eine eigene Speicherverwaltung die einen zusammenhängenden Speicherblock eigenständig verwaltet. Ein Speicherblock von 20MB soll durch ein eigenes Heap Management aufgeteilt werden. Funktionen zum Belegen und freigeben von Speicher sind zu realisieren. Die Funktionalität soll durch eine Testroutine geprüft werden können, die die vorhandene Liste durchläuft und die Verwaltungsdaten der Blöcke ausgibt. Dabei sollen Fehler ausfindig gemacht werden können.
    Die Speicherverwaltung ist durch eine Testroutine zu prüfen welche Speicher belegt und dessen Inhalt vollständig mit aufsteigenden ganzen Zahlen beschreibt. Dazu sind im Wechsel sind Blöcke zu belegen und freizugeben.
    Jede Belegung im Testprogramm führt die Testroutine aus und deren Verwaltungsdaten sind auf der Konsole auszugeben. Die Verwaltungsdaten umfassen mindestens Blockgröße und die Belegt Information.
    Testen Sie die Fragmentierung des Heaps, in dem Sie jeden zweiten Speicherblock freigeben und danach einen doppelt großen neuen Block belegen.



    Ich versteh jetzt einfach nicht, wie ich mir nen 20MB Speicherblock holen soll.
    Die Verwaltung ist dann kein Problem. Aber wie bekomme ich den 20MB Block den ich verwalten soll???

    Ich will keine Lösung, nur ne Idee wie ich an den Speicherblock komme.

    Hab mir das so vorgestellt:
    s. Bild

    In den Verwaltunsinfos dann halt immer nen Zeiger auf die nächsten Verwaltungsinfos.
    In den Vinfos dann
    - belegt/frei
    - Größe des Blocks
    Bilder

    • aufgabe2.JPG

      15,11 kB, 581×265, 900 mal angesehen

  • Also ich hab mir das jetzt so gedacht:

    1. Ich alloziiere 20MB Speicher
    char *ptrAuf20MB = new char[20*1024*1024];

    2. Habe ich mir eine Struct geschreiben
    struct Verwaltungsinfos
    {
    int nummer;
    bool belegt;
    Verwaltunsinfos *next;
    };


    Jetzt stehe ich aber vor folgendem Problem:
    Wie passe ich den Struct in den alloziierten Speicher ein?

    Oder hat jemand ne total andere Idee das zu Verwirklichen?


    :!: Ich will keine fertige Implementierung nur nen Schubs in die richtige Richtung :!:

  • Wenn du das so machst alloziierst du den Speicher auf dem Stack und er wird vom Programm verwaltet (du kannst ihn nicht freigeben). Wenn du eine eigene Speicherverwaltung schreiben willst, musst du dir selber Speicher auf dem Heap alloziieren. Das geht zum Beispiel mit malloc(). Details stehen dazu in den manpages. Da das was du da vorhast ein wenig aussieht wie eine verkettete Liste, würde ich dir empfehlen dir mal davon eine Implementation rauszusuchen und da einzulesen.
    ~ mfg SeBa

    Ich beantworte keine PMs zu Computer-/Programmierproblemen. Bitte wendet euch an das entsprechende Forum.

    [Blockierte Grafik: http://i.creativecommons.org/l/by-sa/3.0/80x15.png]

  • Das geht zum Beispiel mit malloc().

    Ich dachte new und malloc sind dasselbe.
    malloc ist nur C und new C++.
    Wir reden doch jetzt über
    char *ptrAuf20MB = new char[20*1024*1024];

    oder???
    Also so wie ich das verstanden habe holle ich mir den Speicher vom Heap.



    Ja ich will dann eine verkette Liste, weiß auch wie ich das implementiere.
    Mein Problem ist aber die Liste aus Verwaltunsdaten in den 20MB Block einzufügen.

  • Ooops :oops: Das new hatte ich übersehen. Klar, ist richtig. Dein Hauptproblem ist, dass du dein Speicher nicht dann besorgst wann du ihn brauchst, sondern beim Programmstart.
    Der Vorteil von verketteten Listen gegenüber Arrays ist, dass sie dynamisch je nach Bedarf Speicher reservieren und der auch nicht zusammenhängen muss. Bei Arrays holst du dir zusammenhängenden Speicher, wenn die Größe geändert wird, muss u.U. alles umgeschichtet werden. Dafür kann man ein Array linear Adressieren was viel schneller ist.

    Bei deiner Lösung holst du dir eine feste Menge Speicher aber verzichtest auf lineare Adressierung, deswegen würde mich interessieren wieso du das so machen willst.

    Solltest du das wirklich so machen wie du das geplant hast, musst du gucken, wie groß dein struct ist, und dann linear in deinem alloziierten Speicher adressieren. Angenommen dein struct ist 6 Byte groß, dann musst alle 6Byte darumschreiben. Das ist aber ein erheblicher mehraufwand, weil das freigeben von Elementen lücken in deinem Speicher erzeugt und du irgendwann anfangen musst mittendrin einzufügen oder umzuschichten und alle Zeiger umzubiegen. Mein dringender Rat deswegen: Mach es nicht so :!:

    Wie man das wirklich macht: Mann fängt an mit einer einelementigen Liste. Der Zeiger fürs nächste Element zeigt auf NULL. Soll ein neues Element eingefügt werden und die Reihenfolge ist egal, alloziert man sich Speicher, schreibt seine Nutzdaten darein und lässt next aufs erste Element zeigen. Der Trickt ist, man besorgt sich Speicher erst dann, wenn ein neues Element angefügt werden soll und speichert den Zeiger darauf ab.
    ~ mfg SeBa

    Ich beantworte keine PMs zu Computer-/Programmierproblemen. Bitte wendet euch an das entsprechende Forum.

    [Blockierte Grafik: http://i.creativecommons.org/l/by-sa/3.0/80x15.png]

  • @GetIt:
    So verstehe ich die Aufgabenstellung auch :wink: .
    Du sollst ja keine LinkedList erstellen sondern 20MB verwalten.
    Such doch mal einfach bei google nach Freispeicherverwaltung.Da wirst du mit Links und Beispielimplementierungen totgeschlagen.
    Da kannst du dir dann auch ne Methode aussuchen mit der du nach freien Speicherblöcken suchst.Da gibt es ja auch wieder unterschiedliche Vorgehensweisen.

    Gruß void
    "Probleme kann man niemals mit derselben Denkweise lösen,
    durch die sie entstanden sind." (A. Einstein)

  • Ich habe die Aufgabenstellung so verstanden: Du solltst 20 MB verwalten (z.B. mit einer verketteten Liste), allerdings liegen die Verwaltungsdaten dafür nicht in den 20 MB, sondern in zusätzlichem Speicher. Wenn ihr davon die ganze Zeit redet, dann hab ich wohl die ganze Zeit was missverstanden, sorry.
    Also: Innherhalb der 20MB kannst du linear adressieren, ptrAuf20MB ist also dein absoluter (statischer) Offset zu dem du immer einen variablen Anteil x addieren musst um, an Stelle x im Speicher zu kommen.. An welcher Stelle sich was befindet organisiert dann die Liste.
    ~ mfg SeBa

    Ich beantworte keine PMs zu Computer-/Programmierproblemen. Bitte wendet euch an das entsprechende Forum.

    [Blockierte Grafik: http://i.creativecommons.org/l/by-sa/3.0/80x15.png]

  • @GetIT:
    Ohne mir die Seiten genauer angeschaut zu haben sollten folgende Links doch diverse nützliche Informationen bieten:
    dcl.hpi.uni-potsdam.de/teaching/pt2/freemem.pdf
    fmi.uni-stuttgart.de/fk/lehre/…nfo_II/inf2ss02kap2t5.pdf
    sec.informatik.tu-darmstadt.de…2/bs1/folien/kapitel6.pdf

    Gruß void
    "Probleme kann man niemals mit derselben Denkweise lösen,
    durch die sie entstanden sind." (A. Einstein)

  • @ void:
    Also Danke!!!

    Hab aber trotzdem ein Problem:

    Habe mit malloc() 20MB angefordert:
    void *ptrAuf20MB = malloc(20*1024*1024);

    Jetzt möchte ich die verkette Liste (aus Verwaltungsdaten + Inhalt) in diesen angeforderten Speicher einfügen.

    s. Bild

    HILFE!!!!
    Bilder

    • aufgabe2.2.JPG

      14,08 kB, 569×455, 475 mal angesehen

  • Naja nen einfaches problem hasst dir dabei nicht rausgesucht ...

    Jetzt möchte ich die verkette Liste

    Ne verkettete Liste iss eigentlich nur ne ablagevorschrift fuer structuren unterschiedlicher groesse im speicher ....

    wichtig zu wissen ist, wie die structuren (daten) implementieren willst.

    verwendest c++ und klassen,

    oder plain c strukturen ....

    bei plain c isses ziemlich easy ...

    deinen speicher hasst ja schon angefordert, du musst den compiler nur sagen, dass du speicherstelle x als struktur y "behandeln" willst .... -> casten heisst das zauberwort. Hin und herrechnen mit speicheradressen ist auch easy, da speicherbloecke und deren adressen auch linear sind ....

    structY * sy = (structY *)ptrAuf20MB;

    damit sagts dem compiler das er deine 20MB als riesiges Array von structY sehen soll.

    willst am anfang zb platz fuer was lassen , z.b. 10 elemente vom typ structZ:

    structY * sy = (structY *)(ptrAuf20MB + 10 * sizeof(structZ));

    pointer arythmetic halt ....

    Arbeitest du mit klassen, ist die sache klein wenig komplizierter .....

    klassen dynamisch legt man mit new an ...
    das normale new holt sich aber den speicher selbst, also muss man das normale new "aushebeln", quasi fuer deine klasse ueberladen.
    replacement new ist dazu das Stichwort. damit bekommst die klasse dann auch in vorgefertigten speicher konstruiert ....

    BTW verkettete liste und speicher in einem block beisst sich bisserl ^^ sei denn du implementierst die komplette speicherverwaltung neu .... normal sollte ne verkettete Liste speicher immer kleckerweise anfordern koennen, sonst macht sie keinen sinn ....

    Ciao ...

  • @Sussi
    Des Problem hat sich leider unser Dozent rausgesucht.

    Quellcode

    1. struct Verwaltungsdaten
    2. {
    3. bool belegt;
    4. int groesse;
    5. Verwaltungsdaten *next;
    6. };
    7. Verwaltungsdaten *ptrAufVerwaltungsdaten;


    Quellcode

    1. void *ptrAuf20MB = malloc(20*1024*1024);


    Beim initialisiern des Speichers hats geklappt: :D

    Quellcode

    1. ptrAufVerwaltungsdaten = new Verwaltungsdaten;
    2. ...
    3. *((struct Verwaltungsdaten*)ptrAuf20MB) = *ptrAufVerwaltungsdaten;


    So jetzt hab ich natürlich noch mehr Verwaltungsdaten, dafür hab ich mir ne Variable geschaffen, die zählt an welcher Stelle im Speicher die neuen Verwaltungsdaten eingefügt werden sollen:

    Quellcode

    1. int speicherBelegt = 0;


    Die zähle ich immer um sizeof(struct Verwaltungsdaten) und die Grösse die ich angefordert habe hoch.

    Nachdem ich den Speicher initialisiert habe und einen Block von 3MB geschrieben habe, ist der Wert von speicherBelegt = 3145740.
    Also müssen die nächsten Verwaltungsinfos an ptrAuf20MB + speicherBelegt.
    Aber der Code

    Quellcode

    1. *(((struct Verwaltungsdaten*)ptrAuf20MB) + speicherBelegt) = *ptrAufVerwaltungsdaten;

    schlägt fehl. Warum???

  • Des Problem hat sich leider unser Dozent rausgesucht.

    Ja so Probleme von Dozenten sind meist nicht wirklich praktischer Natur ^^

    void *ptrAuf20MB = malloc(20*1024*1024);
    ptrAufVerwaltungsdaten = new Verwaltungsdaten;

    boese boese boese ... entscheide dich ! C oder c++

    bei C hat new ! nix zu suchen !
    malloc und new in der selben uebersetzungseinheit vom selben Coder !

    Und noch ne allgemeine C / C++ Regel !

    Lege nur das dynamisch an, was du auch dynamisch brauchst.
    Warum muessen deine verwaltungsdaten aufn Freestore liegen .... IMHO ne lokale variable taet es da auch ....

    schlägt fehl. Warum???

    der compiler oder die runtime ?

    was fuern fehler bekommst ?


    Und noch was strukturelles ....
    Du sollst (so will es dein dozent) ne eigene Speicherverwaltung schreiben ....
    Trotz dieser neuen anforderung sollt dein C Code sich weiterhin an C gaengige vorgehensweissen halten .....
    In der praxis bewaehrt sich da unter anderem die substitutionsmethode.

    Schreib den code (deine verkettete Liste) in normalen C ! (malloc / free)
    Beispiele findest da im Inet
    danach musst einfach das malloc und free durch eigene methoden austauschen, die dir den speicher halt aus nen vorher definierten block holen ....
    und voila bist fertisch ....
    Beim programmieren ist die kunst, nen komplexes problem in teilprobleme zu zerlegen ... das auch in c, nicht nur in den hoeheren sprachen . Damit tust dich viel leichter und verrennst dich ned so schnell .... ausserdem kann man (und sollte man) standard probleme viel besser durch abkupfern loesen ^^

    Ciao ...

  • @Sussi

    Herzlichen Dank!!!!
    Allerdings glaube ich das ich die Aufgabe jetzt so in etwas gelöst habe :D

    Habe aber ne Frage:
    Du sagst ich soll C - und C++-Code nicht mischen. Ich wollte ja alles mit new machen.
    Aber bei new kann ich halt net angeben wie viel Speicher ich will?

    Oder?

    Mal meine Lösung(?):

    C-Quellcode

    1. #include <iostream>
    2. #include <malloc.h>
    3. #include <assert.h>
    4. #include <crtdbg.h>
    5. using namespace std;
    7. #define MB 1024*1024
    9. struct Verwaltungsdaten
    10. {
    11. bool belegt;
    12. int groesse;
    13. Verwaltungsdaten *next;
    14. };
    16. //Variablen
    17. void *ptrAuf20MB, *hilfsZeigerAuf20MB;
    18. Verwaltungsdaten *ptrAufVerwaltungsdaten, *anfang, *hilfszeiger;
    19. int speicherBelegt = 0;
    20. int freiSpeicher;
    21. int sizeOfVerwaltungsdaten = sizeof(struct Verwaltungsdaten);
    22. int anzahlVerwaltungsdaten;
    23. int aktuellePos, einfuegePos;
    25. //Funktionsprototypen
    26. void initialisiereSpeicher(void);
    27. void myMalloc(int);
    28. void einfuegen(int);
    29. void schreibe(int, int);
    30. void auslesenVerwaltungsdaten(void);
    31. void loeschen(void);
    32. void speicherFreigeben(void);
    34. int main()
    35. {
    36. initialisiereSpeicher();
    37. //myMalloc(1*MB);
    38. //myMalloc(2*MB);
    39. //myMalloc(3*MB);
    40. //myMalloc(4*MB);
    41. //myMalloc(5*MB);
    42. //myMalloc(6*MB);
    43. //myMalloc(7*MB);
    44. myMalloc(2*MB);
    45. myMalloc(2*MB);
    46. myMalloc(2*MB);
    47. myMalloc(2*MB);
    48. myMalloc(2*MB);
    49. myMalloc(2*MB);
    50. myMalloc(2*MB);
    51. myMalloc(2*MB);
    52. myMalloc(2*MB);
    53. myMalloc(2*MB);
    54. loeschen();
    55. auslesenVerwaltungsdaten();
    56. myMalloc(6*MB);
    57. speicherFreigeben();
    59. //in 20MB passen 5*1MB*int (da int = 4Byte)
    60. /*ptrAuf20MB = malloc(20*MB);
    61. cout << _msize(ptrAuf20MB) << endl;
    62. for (int i = 1; i <= 5; i++)
    63. {
    64. *(((int*)ptrAuf20MB) + 1*MB * i) = i;
    65. }*/
    67. _CrtDumpMemoryLeaks();
    68. }
    70. void initialisiereSpeicher()
    71. {
    72. //Speicher anfordern und testen ob OK
    73. ptrAuf20MB = malloc(20*MB);
    74. assert(ptrAuf20MB);
    75. hilfsZeigerAuf20MB = ptrAuf20MB;
    77. //Verwaltungsdaten erstellen und mit Werten befüllen
    78. ptrAufVerwaltungsdaten = new struct Verwaltungsdaten;
    79. ptrAufVerwaltungsdaten->belegt = false;
    80. ptrAufVerwaltungsdaten->groesse = 20*MB - sizeOfVerwaltungsdaten;
    81. ptrAufVerwaltungsdaten->next = 0;
    82. anfang = ptrAufVerwaltungsdaten;
    83. hilfszeiger = ptrAufVerwaltungsdaten;
    84. anzahlVerwaltungsdaten = 1;
    86. aktuellePos = 0;
    87. *((struct Verwaltungsdaten*)ptrAuf20MB) = *ptrAufVerwaltungsdaten; //Verwaltungsdaten im Speicher einfügen
    89. speicherBelegt = sizeOfVerwaltungsdaten;
    90. freiSpeicher = 20*MB - speicherBelegt;
    91. cout << "speicherBelegt: " << speicherBelegt << "Bytes" << endl;
    92. cout << "\t1*Verwaltungsdaten" << endl;
    93. cout << "freiSpeicher: " << freiSpeicher << endl;
    94. cout << "--------------------------------" << endl;
    95. }
    97. void myMalloc(int groesse)
    98. {
    99. hilfszeiger = anfang;
    100. while (hilfszeiger)
    101. {
    102. if (hilfszeiger->groesse >= groesse && hilfszeiger->belegt == false)
    103. {
    104. einfuegen(groesse);
    105. break;
    106. }
    107. hilfszeiger = hilfszeiger->next;
    108. }
    109. if (!hilfszeiger)
    110. {
    111. cerr << "Konnte Block der Groesse " << groesse << "Byte nicht reservieren" << endl;
    112. }
    113. }
    115. void einfuegen(int groesse)
    116. {
    117. anzahlVerwaltungsdaten++;
    118. speicherBelegt += sizeOfVerwaltungsdaten + groesse;
    119. freiSpeicher = 20*MB - speicherBelegt;
    120. cout << "speicherBelegt: " << speicherBelegt << "Bytes" << endl;
    121. cout << "\t" << anzahlVerwaltungsdaten << "*Verwaltungsdaten" << endl;
    122. cout << "\t" << speicherBelegt - (anzahlVerwaltungsdaten * sizeOfVerwaltungsdaten)<< "Bytes Daten" << endl;
    123. cout << "freiSpeicher: " << freiSpeicher << endl;
    125. int anfang = speicherBelegt;
    126. schreibe(anfang, anfang + groesse - 1);
    128. ptrAufVerwaltungsdaten = new struct Verwaltungsdaten;
    129. ptrAufVerwaltungsdaten->belegt = false;
    130. ptrAufVerwaltungsdaten->groesse = 20*MB - speicherBelegt;
    131. ptrAufVerwaltungsdaten->next = 0;
    133. einfuegePos = (anzahlVerwaltungsdaten * sizeOfVerwaltungsdaten) + speicherBelegt;
    134. //cout << "einfuegePos:" << einfuegePos << endl;
    136. //ptrAuf20MB um einfuegePos-Bytes weiter setzten
    137. for (int i = aktuellePos; i <= einfuegePos; i++)
    138. {
    139. *(((char*)ptrAuf20MB) + i);
    140. }
    141. *((struct Verwaltungsdaten*)ptrAuf20MB) = *ptrAufVerwaltungsdaten;
    142. aktuellePos = einfuegePos;
    144. hilfszeiger->belegt = true;
    145. hilfszeiger->groesse = groesse;
    146. hilfszeiger->next = ptrAufVerwaltungsdaten;
    147. auslesenVerwaltungsdaten();
    149. hilfszeiger = ptrAufVerwaltungsdaten;
    150. }
    152. void schreibe(int anfang, int ende)
    153. {
    154. //cout << "Anfang:" << anfang << " :: Ende:" << ende << endl;
    155. int intEnde = ende / 4;
    157. for (int i = anfang, j = 1; i < intEnde; i++, j++)
    158. {
    159. *((int*)ptrAuf20MB + i) = j;
    160. }
    161. }
    163. void auslesenVerwaltungsdaten()
    164. {
    165. Verwaltungsdaten *temp = anfang;
    167. while (temp)
    168. {
    169. cout << "Belegt: " << temp->belegt << " :: Groesse: " << temp->groesse << endl;
    170. temp = temp->next;
    171. }
    172. cout << "--------------------------------" << endl;
    173. }
    175. void loeschen(void)
    176. {
    177. cout << "--------------------------------" << endl;
    178. cout << "Jetzt wird jeder 2.Block freigegeben:" << endl;
    180. int zaehler = 1;
    181. hilfszeiger = anfang;
    183. while(hilfszeiger)
    184. {
    185. hilfszeiger = hilfszeiger->next;
    186. zaehler++;
    188. if (zaehler % 2 == 0)
    189. {
    190. speicherBelegt -= hilfszeiger->groesse;
    191. hilfszeiger->belegt = false;
    192. }
    193. }
    194. }
    196. void speicherFreigeben(void)
    197. {
    198. hilfszeiger = anfang;
    200. while(hilfszeiger)
    201. {
    202. hilfszeiger = hilfszeiger->next;
    203. delete hilfszeiger;
    204. }
    206. delete ptrAuf20MB;
    207. }
    Alles anzeigen


    Nur die Methode speicherFreigeben() hat noch macken, aber sonst läufts.

  • Du solltest an einigen Stellen mit lokalen Variablen arbeiten, nicht mit globalen. Das ist sonst Spaghetti-Code. Das freigeben nicht geht ist klar, mit einem hilfszeiger wirds schwierig:

    Quellcode

    1. void speicherFreigeben(void)
    2. {
    3. Verwaltungsdaten, *hilfszeiger1, *hilfszeiger2;
    4. hilfszeiger1 = anfang;
    6. while(hilfszeiger2)
    7. {
    8. hilfszeiger1 = hilfszeiger2;
    9. hilfszeiger2 = hilfszeiger2->next;
    10. delete hilfszeiger1;
    11. }
    12. delete ptrAuf20MB;
    13. }
    Alles anzeigen


    Versuchs mal irgendwie so. Das Problem war, dass du den Zeiger aufs nächste Element setzt, aber anschließen freigibst. Damit verlierst du die Information wo das darauffolgende Element nun war.
    ~ mfg SeBa

    Ich beantworte keine PMs zu Computer-/Programmierproblemen. Bitte wendet euch an das entsprechende Forum.

    [Blockierte Grafik: http://i.creativecommons.org/l/by-sa/3.0/80x15.png]

  • Du sagst ich soll C - und C++-Code nicht mischen. Ich wollte ja alles mit new machen.

    c++ befehle im C Style schreiben ist aber genau so mies ^^

    Naja, die aufgabenstellung ist halt bisserl unguenstig, weil im richtigen schoenen c++ stil unmöglich, weil du immer eine Grundregel verletzen wuerdest:
    Implementiere nie etwas, was es schon gibt ! ^^ (std:list + eigenener Allokator)

    Iss ja auch halt ne uebungsaufgabe.


    Aber bei new kann ich halt net angeben wie viel Speicher ich will?

    Nur indirekt !
    Wir wissen dass sizeof(char) immer 1 ist (siehe definition von char)
    damit ist char immer 1 byte gross (siehe definition von byte)
    damit allokiert man 20MB:

    void * p20MB = new char [1024*1024*20];

    auch logisch das es nur indirekt geht weil c++ definiert sich als streng typsicher. und bei typsicherheit braucht man undefinierten speicher eigentlich ned wirklich ^^

    Aber wie gesagt, nur new benutzen hilft dir nicht .... wenn du trotzdem c style schreibst. C++ ist nicht die Sprache, sondern mehr der Style. dieses new da oben sollte also "gut versteckt" in ner klasse sein ^^

    wenn du das problem wirklich selber in c++ loesen woelltest, aehliches vorgehen wie bei c:
    Schreib die doppelt verkettete liste mit normalen c++ klassen ....
    schreib nen eigenen allokator
    ueberschreib das new der klassen das es deinen allokator aufruft ...
    voiala ....

    Ciao ...