speicherverwaltung < C/C++ < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:25 So 15.06.2008 | | Autor: | gianna |
| Aufgabe | Schreibt zunächst ein einfaches Testpro-
gramm (malloctest.c, ein Teil davon ist bereits in der Vorgabe auf der Webseite implementiert),
das die Bibliotheksfunktionen malloc(3) und free(3) testet. Fordert dazu N Speicherbereiche zufäl-
liger Gröÿe an (malloc(3)) und schreibt an den Anfang eines jeden Speicherbereichs dessen laufende
Nummer (Datentyp unsigned int; die Gröÿe eines solchen Speicherbereichs muss demnach minde-
stens sizeof(unsigned int) betragen!). Gebt dann zuerst jeden Speicherbereich mit einer durch
drei teilbaren laufenden Nummer wieder frei (free(3)), danach alle übrigen. Überprüft vor dem Frei-
geben jedes Bereichs, ob dessen laufende Nummer noch richtig im Speicher steht: Ist das nicht der
Fall, gebt eine entsprechende Fehlermeldung aus.2 Wiederholt den Zyklus Anfordern/Freigeben ein
Mal.
Die Anzahl der Speicherbereiche N soll der Benutzer auf der Kommandozeile bestimmen können. So
soll ein Aufruf des Programms mit
$ ./malloctest 42
dazu führen, dass N=42 Speicherbereiche angefordert werden (int main(int argc, char **argv),
atoi(3) oder strtoul(3)). Falls das Programm ohne Parameter aufgerufen wird, soll der Defaultwert
N=100 verwendet werden (dieser Teil ist bereits in der Vorgabe enthalten).
b) First-Fit-Speicherallokation und -Freigabe (5 Punkte) Nun soll in einem separaten Modul
(firstfit.c + firstfit.h) void [mm] *ff_alloc(size_t [/mm] size) und void ff_free(void *ptr)
implementiert werden. Holt euch dazu von der Webseite die Dateien firstfit.c, firstfit.h und
das Makefile, das malloctest.c und firstfit.c übersetzt und linkt, so dass euer Testprogramm
(nach Ersetzung von malloc mit _alloc bzw. free mit _free) die eigene Implementierung testet.
Die Freispeicherverwaltung soll den freien Speicher (der Einfachheit halber bei uns ein globales char-
Array der Gröÿe 1 Megabyte) in einer einfach verketteten Liste verwalten (siehe Graphik). Am Anfang
eines freien Speicherbereichs steht jeweils eine Verwaltungsstruktur (bereits in der Vorgabe: struct
mem_block) mit der Gröÿe des freien Speichers und einem Zeiger auf den nächsten freien Bereich
(Ende der Liste: next=NULL). Ein globaler Zeiger (Vorgabe: struct mem_block *free_mem) zeigt
auf den Anfang der Liste.
Vervollständigt die Funktionen _alloc und _free in firstfit.c. Beim ersten Aufruf von _alloc
ist die Freispeicherliste zu initialisieren und in die globale Freispeicherliste einzuhängen (in der Vor-
gabe bereits implementiert!). Die Funktion _alloc sucht den ersten freien Speicherbereich in der
verketteten Freispeicherliste, der für den geforderten Speicherbereich und die Verwaltungsstruktur
groÿ genug ist ( rst- t). Ist der Speicherbereich gröÿer als benötigt und verbleibt genügend Rest, so
ist dieser Rest mit einer neuen Verwaltungsstruktur am Anfang wieder in die Freispeicherliste einzu-
hängen. In die Verwaltungsstruktur vor dem belegten Speicherbereich wird die Gröÿe des Bereichs
und statt des next-Zeigers eine Kennung mit dem Wert 0xDEADBABE eingetragen. Der von _alloc
zurückgelieferte Zeiger zeigt hinter die Verwaltungsstruktur, wie in der Abbildung für den Bereich
A eingezeichnet. Die Funktion _free hängt einen zuvor mit _alloc allozierten Speicherbereich
wieder in die Freispeicherliste ein. Vor dem Einhängen ist die Kennung zu überprüfen: Besitzt diese
nicht den Wert 0xDEADBABE, soll das Programm abgebrochen werden (abort(3)). |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
/* Parameter vorhanden? */
if (argc < 2) {
/* nein -> Defaultwert */
num_areas = DEFAULT_NUM_AREAS;
} else {
/* ja -> nach unsigned long konvertieren */
char *endptr;
num_areas = strtoul(argv[1], &endptr, 0);
if (endptr == argv[1]) {
fprintf(stderr, "ungueltiger [mm] Parameter\n");
[/mm]
return 1;
}
}
printf("Anzahl Speicherbereiche: [mm] %lu\n", [/mm] num_areas);
/* Speicher fuer Zeigerarray besorgen */
#ifdef FIRSTFIT
data = ff_alloc(num_areas * sizeof(*data));
#else
data = malloc(num_areas * sizeof(*data));
#endif
if (!data) {
fprintf(stderr, "Speicher fuer Zeigerarray konnte nicht alloziert [mm] werden\n");
[/mm]
return 1;
}
srand(time(NULL));
dieser teil ist uns für den ersten aufgabenbereich schon gegeben, nun weiß ich jedoch nicht,wie ich weitermachen soll. habe als erstes eine einfache methode für zufallswerte geschrieben, da ja jeder speicherbereich eine zufällige größe haben soll.
speicher ich die größen der speicherbereiche mittels:
data[i]=malloc(sizeof(zufallswert));
und setze dann die laufende nummer mit:
*(int *)data[i]= i;
dann könnte ich das ja alles in eine for schleife packen?
und beim 2.aufgabenteil versteh ich die prüfung des freienspeicherbereichs nicht, also das müsste ja blockgröße - verwaltungsstruktur >= anforderung sein?
doch woher nehm ich die daten der verwaltungsstruktur und der blockgröße?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:20 Mo 16.06.2008 | | Autor: | rainerS |
Hallo!
> Schreibt zunächst ein einfaches Testpro-
> gramm (malloctest.c, ein Teil davon ist bereits in der
> Vorgabe auf der Webseite implementiert),
> das die Bibliotheksfunktionen malloc(3) und free(3)
> testet. Fordert dazu N Speicherbereiche zufäl-
> liger Gröÿe an (malloc(3)) und schreibt an den Anfang
> eines jeden Speicherbereichs dessen laufende
> Nummer (Datentyp unsigned int; die Gröÿe eines solchen
> Speicherbereichs muss demnach minde-
> stens sizeof(unsigned int) betragen!). Gebt dann zuerst
> jeden Speicherbereich mit einer durch
> drei teilbaren laufenden Nummer wieder frei (free(3)),
> danach alle übrigen. Überprüft vor dem Frei-
> geben jedes Bereichs, ob dessen laufende Nummer noch
> richtig im Speicher steht: Ist das nicht der
> Fall, gebt eine entsprechende Fehlermeldung aus.2
> Wiederholt den Zyklus Anfordern/Freigeben ein
> Mal.
> Die Anzahl der Speicherbereiche N soll der Benutzer auf
> der Kommandozeile bestimmen können. So
> soll ein Aufruf des Programms mit
> $ ./malloctest 42
> dazu führen, dass N=42 Speicherbereiche angefordert werden
> (int main(int argc, char **argv),
> atoi(3) oder strtoul(3)). Falls das Programm ohne
> Parameter aufgerufen wird, soll der Defaultwert
> N=100 verwendet werden (dieser Teil ist bereits in der
> Vorgabe enthalten).
> b) First-Fit-Speicherallokation und -Freigabe (5 Punkte)
> Nun soll in einem separaten Modul
> (firstfit.c + firstfit.h) void *ff_alloc(size_t size) und
> void ff_free(void *ptr)
> implementiert werden. Holt euch dazu von der Webseite die
> Dateien firstfit.c, firstfit.h und
> das Makefile, das malloctest.c und firstfit.c übersetzt
> und linkt, so dass euer Testprogramm
> (nach Ersetzung von malloc mit _alloc bzw. free mit
> _free) die eigene Implementierung testet.
> Die Freispeicherverwaltung soll den freien Speicher (der
> Einfachheit halber bei uns ein globales char-
> Array der Gröÿe 1 Megabyte) in einer einfach verketteten
> Liste verwalten (siehe Graphik). Am Anfang
> eines freien Speicherbereichs steht jeweils eine
> Verwaltungsstruktur (bereits in der Vorgabe: struct
> mem_block) mit der Gröÿe des freien Speichers und einem
> Zeiger auf den nächsten freien Bereich
> (Ende der Liste: next=NULL). Ein globaler Zeiger (Vorgabe:
> struct mem_block *free_mem) zeigt
> auf den Anfang der Liste.
> Vervollständigt die Funktionen _alloc und _free in
> firstfit.c. Beim ersten Aufruf von _alloc
> ist die Freispeicherliste zu initialisieren und in die
> globale Freispeicherliste einzuhängen (in der Vor-
> gabe bereits implementiert!). Die Funktion _alloc sucht
> den ersten freien Speicherbereich in der
> verketteten Freispeicherliste, der für den geforderten
> Speicherbereich und die Verwaltungsstruktur
> groÿ genug ist ( rst- t). Ist der Speicherbereich gröÿer
> als benötigt und verbleibt genügend Rest, so
> ist dieser Rest mit einer neuen Verwaltungsstruktur am
> Anfang wieder in die Freispeicherliste einzu-
> hängen. In die Verwaltungsstruktur vor dem belegten
> Speicherbereich wird die Gröÿe des Bereichs
> und statt des next-Zeigers eine Kennung mit dem Wert
> 0xDEADBABE eingetragen. Der von _alloc
> zurückgelieferte Zeiger zeigt hinter die
> Verwaltungsstruktur, wie in der Abbildung für den Bereich
> A eingezeichnet. Die Funktion _free hängt einen zuvor mit
> _alloc allozierten Speicherbereich
> wieder in die Freispeicherliste ein. Vor dem Einhängen ist
> die Kennung zu überprüfen: Besitzt diese
> nicht den Wert 0xDEADBABE, soll das Programm abgebrochen
> werden (abort(3)).
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt
> | 1: |
| | 2: | > /* Parameter vorhanden? */
| | 3: | > if (argc < 2) {
| | 4: | > /* nein -> Defaultwert */
| | 5: | > num_areas = DEFAULT_NUM_AREAS;
| | 6: | > } else {
| | 7: | > /* ja -> nach unsigned long konvertieren */
| | 8: | > char *endptr;
| | 9: | > num_areas = strtoul(argv[1], &endptr, 0);
| | 10: | > if (endptr == argv[1]) {
| | 11: | > fprintf(stderr, "ungueltiger [mm]Parameter\n");[/mm]
| | 12: | > return 1;
| | 13: | > }
| | 14: | > }
| | 15: | > printf("Anzahl Speicherbereiche: [mm]%lu\n",[/mm] num_areas);
| | 16: | >
| | 17: | > /* Speicher fuer Zeigerarray besorgen */
| | 18: | > #ifdef FIRSTFIT
| | 19: | > data = ff_alloc(num_areas * sizeof(*data));
| | 20: | > #else
| | 21: | > data = malloc(num_areas * sizeof(*data));
| | 22: | > #endif
| | 23: | >
| | 24: | > if (!data) {
| | 25: | > fprintf(stderr, "Speicher fuer Zeigerarray konnte nicht
| | 26: | > alloziert [mm]werden\n");[/mm]
| | 27: | > return 1;
| | 28: | > }
| | 29: | >
| | 30: | > srand(time(NULL));
| | 31: | > |
>
> dieser teil ist uns für den ersten aufgabenbereich schon
> gegeben, nun weiß ich jedoch nicht,wie ich weitermachen
> soll. habe als erstes eine einfache methode für
> zufallswerte geschrieben, da ja jeder speicherbereich eine
> zufällige größe haben soll.
> speicher ich die größen der speicherbereiche mittels:
> data=malloc(sizeof(zufallswert));
Das kann nicht stimmen, denn sizeof(zufallswert) ist immer gleich. Du meinst
data[i]=malloc(zufallswert);
> und setze dann die laufende nummer mit:
> *(int *)data= i;
> dann könnte ich das ja alles in eine for schleife packen?
Ja.
> und beim 2.aufgabenteil versteh ich die prüfung des
> freienspeicherbereichs nicht, also das müsste ja blockgröße
> - verwaltungsstruktur >= anforderung sein?
Im Prinzip ist deine Ungleichung richtig.
Kannst du genauer sagen, was du nicht verstehst?
> doch woher nehm ich die daten der verwaltungsstruktur und
> der blockgröße?
Da musst du dir überlegen, was du an Verwaltungsinformationen brauchst; zum Beispiel musst du beim freigeben ja wissen, wieviel du freigeben darfst. Diese Information muss also Teil der Verwaltungsinformationen sein.
Eine der meiner Meinung nach besten Darstellungen dieses Themas findest du in: Donald E. Knuth, The Art of Computer Programming I: Fundamental Algorithms, Abschnitt 2.5.
Viele Grüße
Rainer
|
|
|
|
