Hallo Ich möchte eine malloc Funktion selber schreiben. Mein Problem dabei ist der Ansatz. Meine ersten Überlegungen dazu sind: Als Heap hab ich ein Char-array mit einer fixen Größe. Des Weiteren braucht man einen Header pro Speicherblock indem festgehalten wird wie groß der Speicherblock ist und ob er frei ist oder nicht. Dazu würde sich eine Struktur eigenen. Mein Problem dabei ist nun, wie ich das Char-Array mit den Headern verknüpfe. Muss in die Struktur noch ein Char-Pointer? Wird dann nicht sehr viel Speicher nur für die Verwaltung verbraucht? Zudem muss man zu begin schon ein Header-Array erzeugen mit der gleich Anzahl an Bytes des Speichers. Dadurch wird es ja extrem ineffizient.
Klaus schrieb: > Ich möchte eine malloc Funktion selber schreiben Du möchtest (Interesse/Bedarf) oder du musst (Hausaufgabe)? Bei Bedarf: Einen bestehenden Allokator nehmen (wenn du auf einem fixen Buffer arbeiten möchtest z.B. den http://www.gii.upv.es/tlsf/). Bei Interesse: Entweder selber grübeln und ausprobieren. Oder eben schauen was die anderen so machen(z.B. http://g.oswego.edu/dl/html/malloc.html). Dann endest du aber dabei einen anderen Allokator nachzubauen und kannst es eigentlich gleich lassen...
Ich habe das vor vielen Jahren auch mal selber gemacht. Damals gab es nur das C Buch von Kernighan&Ritchie mit einem Beispielcode. http://stackoverflow.com/questions/13159564/explain-this-implementation-of-malloc-from-the-kr-book
Klaus schrieb: > Wird dann nicht sehr viel Speicher nur für die Verwaltung verbraucht? Von nix kommt nix. malloc bedeutet Overhead, sowohl was Speicherplatz als auch was Laufzeit bei Allokation und Freigabe angeht. > Zudem muss man zu begin schon ein Header-Array erzeugen mit der gleich > Anzahl an Bytes des Speichers. Dadurch wird es ja extrem ineffizient. Du kannst dir ja mal Implementationen von malloc anschauen, wobei die natürlich auch OS-abhängig sind. Beispiele: Newlib: https://sourceware.org/git/gitweb.cgi?p=newlib-cygwin.git;a=blob_plain;f=newlib/libc/stdlib/malloc.c https://sourceware.org/git/gitweb.cgi?p=newlib-cygwin.git;a=blob_plain;f=newlib/libc/stdlib/mallocr.c AVR-LibC: http://svn.savannah.nongnu.org/viewvc/*checkout*/avr-libc/trunk/avr-libc/libc/stdlib/malloc.c GNU C Library (glibc), gleich ein ganzes Verzeichniss voll: https://sourceware.org/git/?p=glibc.git;a=tree;f=malloc
Das wirklich große Problem bei der Entwicklung solch einer Speicherverwaltung besteht darin, die im Laufe der Zeit entstehende Speicherfragmentierung in den Griff zu bekommen. Ansonsten kann es passieren, dass plötzlich zwar 80% des Speichers ungenutzt sind, sich aber keine hinreichend großen Blöcke mehr allozieren lassen. Aus diesem Grund runden manche Allokatoren auf feste Blockgrößen auf, vorzugsweise in Zweipotetnzen. Eine Betriebssysteme bieten auch die Möglichkeit, sog. Memory Pools zu verwenden, d.h. sich je nach Verwendungszweck aus dem einen oder anderen Speicher zu bedienen.
Super schwer ist das jetzt nicht. Das Stichwort heisst in-place-Liste. Kurz: man verwaltet belegte Blöcke und freie Löcher in einer Liste, deren Listenknoten und die Nutzdaten in demselben Bereich liegen: oberhalb vom data-segment bis zur sog. "Bruchstelle" (break), die man mit bspw. dem Systemcall sbrk() verschieben kann. Das ist das Prinzip und überall gleich. Man ist daran interessiert, die sog. externe Fragmentierung zu vermeiden (s.o.). Mögliche Allokationsstrategien sind etwa: first-fit, next-fit, best-fit, worst-fit. Oder ein Buddy-System mit Allokationsgrößen in 2'er Potenzen. Beim free() muss/sollte man natürlich angrenzenden freie Löcher wieder verschmelzen. Du kannst an den Adressen von malloc() der libc leicht erkennen, dass hier so gearbeitet wird mit bspw. einem Listenknoten der Größe 8 Byte. Deine eigene Implementierung kannst Du dann ggf. mit dem ld.so (*nix-Systeme) in bestehende Programme injizieren.
Erstmal Danke für die vielen Antworten. moep schrieb: > Du möchtest (Interesse/Bedarf) oder du musst (Hausaufgabe)? Es ist wirklich nur Interesse. Ich hab jetzt mal eine Version geschrieben. Hab eine einfach verketteten Liste für die Verwaltung verwendet. Leider hab ich ein Pointer-Problem. Hier der Code:
1 | static char heap[SIZE_OF_HEAP]; |
2 | struct header *headerstart = NULL; |
3 | static int Size_OF_Free_Space; |
4 | struct header *help = NULL; |
5 | void mem_init(void) { |
6 | |
7 | for (int i = 0; i < SIZE_OF_HEAP; i++) { |
8 | |
9 | heap[i] = 0; |
10 | }
|
11 | Size_OF_Free_Space = SIZE_OF_HEAP; |
12 | |
13 | headerstart = mem_init_alloc(sizeof(struct header)); |
14 | Size_OF_Free_Space -= sizeof(struct header); |
15 | headerstart->size = SIZE_OF_HEAP-sizeof(struct header); // Header 12 Byte |
16 | headerstart->state = 'F'; |
17 | headerstart->speicher = mem_init_alloc(headerstart->size); |
18 | for (int i = 0; i < headerstart->size; i++) { |
19 | |
20 | headerstart->speicher[i] = 'F'; |
21 | }
|
22 | |
23 | |
24 | }
|
25 | void* mem_init_alloc(int size) { |
26 | if (Size_OF_Free_Space < size) { |
27 | |
28 | return NULL; |
29 | }
|
30 | else
|
31 | {
|
32 | |
33 | return &heap[SIZE_OF_HEAP-Size_OF_Free_Space]; |
34 | }
|
35 | |
36 | |
37 | }
|
38 | void* mem_alloc(int size) { |
39 | if (headerstart->size < size + sizeof(headerstart)) { |
40 | |
41 | return NULL; // Falls kein Speicher mehr frei ist |
42 | }
|
43 | else { |
44 | help = headerstart; |
45 | |
46 | |
47 | while(help != NULL) |
48 | {
|
49 | help = help->next; |
50 | |
51 | }
|
52 | if (help == NULL) { |
53 | help = &heap[SIZE_OF_HEAP - Size_OF_Free_Space]; |
54 | Size_OF_Free_Space -= sizeof(struct header); |
55 | headerstart->size = Size_OF_Free_Space; |
56 | help->size = size; |
57 | help->state = 'A'; |
58 | help->next = NULL; |
59 | help->speicher = &heap[SIZE_OF_HEAP - Size_OF_Free_Space-1]; // Stringende |
60 | |
61 | for (int i = 0; i < size; i++) { |
62 | help->speicher[i] = 'A'; |
63 | |
64 | }
|
65 | help->speicher[size] = '\0'; |
66 | return help->speicher; |
67 | |
68 | |
69 | }
|
70 | |
71 | |
72 | }
|
73 | |
74 | }
|
75 | |
76 | void mem_dump(void) { |
77 | help = headerstart; |
78 | printf("Komplett freier Speicher --> %d\n", headerstart->size); |
79 | while (help != NULL) |
80 | {
|
81 | |
82 | printf("%C | %d | %s \n", help->state, help->size,help->speicher); |
83 | help = help->next; |
84 | |
85 | }
|
86 | |
87 | }
|
Headerstart zeigt immer auf den Anfang des Speichers. In der Funktion mem_alloc füge ich mit einem Hilfspointer einen neuen Speicherblock ein und weise Ihn Headerstart->next zu. Wenn ich aber nun eine Ausgabe mach ist der Next-pointer vom Headerstart NULL. Warum?
Dein Code schaut recht wirr aus, deswegen kann ich Dir auch nicht sagen, was darin im Moment schief läuft. Aber: Du hast nur eine fixe Größe des Heaps durch Deine globale Variable. Damit kannst Du diese maximale Größe nicht mehr ändern. Du solltest Dir mal sbrk() ansehen (falls Du wirklich vor hast, eine Allokator zu schreiben). Initial hast Du eine leere Liste mit einem Knoten des Typs F (frei). So muss Du Deine Liste initialisieren. Alles weitere ist dann regulär. Vielleicht nimmt Du auch mal ein Buch über Betriebssysteme zur Hand ...
Klaus schrieb: > Muss in die Struktur noch ein Char-Pointer? Üblicherweise liegt der Header im Speicher direkt vor dem Datenblock:
1 | void *data = &header + 1; |
(Für solche Sachen ist die Zeigerarithmetik von C mal nützlich ...) > Wird dann nicht sehr viel Speicher nur für die Verwaltung verbraucht? Das kommt darauf an, wie komplex deine Speicherverwaltung ist. Man kann noch etwas drauflegen, z.B. mit getrennten Speicherbereichen für verschiedene Blockgrößen (um Fragmentierung zu vermeiden), oder extra Verwaltungsaufwand, damit sich mehrere CPUs nicht in die Quere kommen. Oder du implementierts einen Buddy-Allocator; der hat keinen Overhead für belegte Speicherblöcke (die Liste der freien Speicherblöcke kann in den freien Blöcken selbst gespeichert werden): https://en.wikipedia.org/wiki/Buddy_memory_allocation (Und nichts ist umsonst: alle Blöcke werden auf eine Zweierpotenz aufgerundet, und beim free() muss die Größe auch angegeben werden.)
:
Bearbeitet durch User
eine einfache Speicherverwaltung würde etwa so funktionieren.
(Syntax und Datenstrukturen nicht vollständig - es geht darum,
die Idee darzustellen!!)
1. Speicherblöcke auf dem Stack anlegen:
static BYTE pool[16][64];
2. Listen anlegen
static LIST List_freePools;
static LIST List_usedPools;
3. Zeiger auf pools in freePools eintragen
for (i=0; i; i<16; i++)
{
List_freePools.Add(&pool[i]);
}
4. Speicherblock allokieren
BYTE* myAlloc(int size)
{
BYTE * p;
if ( size < 65 )
{
p = List_freePools.Get();
List_usedPools.Add(p);
return p;
}
}
5. Speicherblock deallokieren
void myFree(BYTE* p)
{
//Adresse aus der Liste der benutzen Blöcke austragen
List_usedPools.GetByAddress(p);
//Adresse wieder in die Liste der freien Blöcke eintragen
List_freePools.Add(p);
}
...man kann auch verschieden große Blöcke anlegen, wenn man die Verwaltungsstrukturen ntspr. erweitert. Bei Zugriff aus verschiedenen Threads/Interrupt sind die Listen gegen parallelen Zugriff zu schützen.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.