1 Aufgabe 4: Speicherverwaltung (11 Punkte) · PDF file1 128 KiB X 64 KiB A B C 2 F X Szenario 3: t A D S 64 KiB 64 KiB 64 KiB 64 KiB 64 KiB 64 KiB 64 KiB 64 KiB 1 A 64 KiB B C 64

Betriebssysteme Übungsaufgabe 4 Speicherverwaltung

1 Aufgabe 4: Speicherverwaltung (11 Punkte)

In dieser Aufgabe soll eine kleine, einfache Speicherverwaltung (angelehnt an das in C zur Verfügungstehende malloc(3) und free(3)) selbst implementiert werden.

ACHTUNG: Zu den untenstehenden Aufgaben existieren Vorgaben in Form von C-Dateien mit ei-nem vorimplementierten Code-Rumpf, die ihr in den Aufgaben erweitern sollt. Diese Vorgaben sindvon der Veranstaltungswebsite herunterzuladen, zu entpacken und zu vervollständigen! Die Dateivorgaben-A4.tar.gz lässt sich unter Linux/UNIX mittels tar -xzvf vorgaben-A4.tar.gz aus-packen.

1.1 Speicherverwaltung und Bitoperationen (⇒ antworten.txt, 4 Punkte)

1) Buddy-Verfahren (2 Punkte) In den folgenden Tabellen wird schematisch Speicher nach demBuddy-Verfahren verwaltet. Die erste Spalte kennzeichnet den Zeitverlauf t. A für steht fürdie Aktion (B = Belegung, F = Freigabe), die mit Datenblock D durchgeführt werden soll.Die Größe des dabei angeforderten Speichers findet sich in der 4. Spalte „S“, der zur Verfü-gung stehende Speicher hat eine Gesamtgröße von 512 KiB1. Für den Zeitpunkt t = 1 ist injedem Szenario bereits eine Speicherbelegungssituation vorgegeben. In den 8 rechten Spalten(„64 KiB“) stehen die Buchstaben jeweils für bereits belegte Speicherblöcke der entsprechendenGröße. Wie wird die Speicherverwaltung zum Zeitpunkt t = 2 in den einzelnen, voneinanderunabhängigen Szenarien, also für die Datenblöcke W, X, Y und Z, durchgeführt? Erklärt dabeiinsbesondere, wenn Blöcke aufgespalten bzw. verschmolzen werden oder eine Anforderung nichterfüllt werden kann.

Szenario 1:t A D S 64 KiB 64 KiB 64 KiB 64 KiB 64 KiB 64 KiB 64 KiB 64 KiB

1 – – – A 128 KiB 256 KiB2 B W 171 KiB


1 – – – 128 KiB X 64 KiB A B C2 F X –


1 – – – A 64 KiB B C 64 KiB D2 B Y 65 KiB


1 – – – 512 KiB2 B Z 3 KiB

2) Bitoperationen (2 Punkte) Erklärt in eigenen Worten genau, wie die in der vorgegebenen Dateinextfit.c implementierte Funktion clear_bit funktioniert. (Nicht nur, was sie tut – das sagt jaihr Name schon!) Geht dabei insbesondere auf die verwendeten Operatoren ein.

1512 Kibibyte = 512×1024 Bytes = 524.288 Bytes

c© 2010 TU Dortmund, Informatik 12, Arbeitsgruppe Eingebettete Systemsoftware


1.2 Dynamische Speicherverwaltung (7 Punkte)

In der Vorgabe befinden sich drei Dateien:

malloctest.c Ein vorgegebenes Testprogramm, das eure selbstgebaute dynamische Speicherverwal-tung testet.

nextfit.c, nextfit.h Hier sollt ihr die Funktionen nf_alloc und nf_free mit Hilfe einer ganzen Reihevon vorgegebenen Hilfsfunktionen implementieren.

Makefile Eine Steuerdatei für Make, mit der ihr das Testprogramm malloctest erstellen könnt.Das Programm kann mit einem optionalen Parameter aufgerufen werden, der die Anzahl dersequentiellen Speicherbelegungen steuert (z. B. malloctest 42).

Abzugeben sind nur die Dateien antworten.txt, nextfit.c und nextfit.h. Dementsprechend solltetihr nicht die Schnittstelle der beiden Funktionen (nf_alloc, nf_free) ändern, da sonst unser Test-programm nicht mehr damit funktioniert.

Im Modul nextfit (nextfit.c, nextfit.h) soll eine einfache Freispeicherverwaltung implementiert wer-den, die vom Testprogramm über die Funktionen void *nf_alloc(size_t size); undvoid nf_free(void *ptr, size_t size); verwendet wird. nf_alloc soll dabei einen Speicherbe-reich der Größe size Bytes belegen und dessen Startadresse zurückliefern; nf_free soll diesen (unterAngabe seiner Startadresse und seiner Länge) wieder freigeben.

a) nf_alloc (5 Punkte) Die Speicherverwaltung verwaltet der Einfachheit halber Speicher auseinem 12 KiB großen (die Größe ist mittels #define MEM_POOL_SIZE festgelegt), globalen char-Array (char mem_pool[]). Speicher aus diesem Array wird nur in Stücken („Chunks“) der Größe 32Bytes (als CHUNK_SIZE definiert) belegt; „ungerade“ Speicheranforderungen sollen auf das nächsteVielfache einer Chunk-Größe (z. B. von 37 auf 64 Bytes) aufgerundet werden. Die Hilfsfunktion si-ze_to_chunks berechnet aus einer gegebenen, noch nicht aufgerundeten Größe die Anzahl der zubelegenden Chunks.

Die Information, ob ein solches Speicherstück der Größe CHUNK_SIZE belegt ist, wird in einer Bit-liste (char free_list[]) abgelegt: Eine 0 an der entsprechenden Stelle der Liste besagt, dass dasSpeicherstück frei ist, eine 1 dessen Belegung (siehe Abb. 1).

Geht bei der Implementierung von nf_alloc schrittweise vor:

• Zunächst müsst ihr ausrechnen, wie viele Chunks ihr belegen müsst; das ist mit der Hilfsfunktionsize_to_chunks leicht bewerkstelligt.

• Nun müsst ihr (unter Verwendung der vorgegebenen Hilfsfunktionen bit_is_set/set_bit) einefreie Stelle (frei = genügend 0-Bits hintereinander) im Freispeicher-Bitfeld finden, die groß genugist, die Speicheranforderung aufzunehmen, und diese mit 1-Bits belegen. Diese „Lückensuche“soll nach der Platzierungsstrategie Next Fit erfolgen: Ihr sucht also ab der zuletzt-gefundenenLücke und startet gegebenenfalls wieder am Anfang. Wenn keine Lücke groß genug ist, liefertNULL an den Aufrufer zurück und signalisiert ihm damit, dass die Anforderung fehlgeschlagenist.

• Ansonsten liefert dem Aufrufer die Speicherstelle innerhalb des mem_pool zurück, die der ge-fundenen Stelle in der Freispeicher-Bitliste entspricht.

b) nf_free (2 Punkte) In nf_free soll nun zuvor reservierter Speicher wieder freigegeben werden.Dazu müssen lediglich die entsprechenden Bits in der Freispeicher-Bitliste gelöscht werden.

• Die Position dieser Bits könnt ihr leicht anhand der Differenz des übergebenen Zeigers ptr undder Startadresse des Speicherpools mem_pool ausrechnen. Denkt daran, dass ein Bit immer füreinen ganzen Chunk steht!



Abbildung 1: Freispeicher-Bitliste mit den zugehörigen Chunks im Speicher

• Die Anzahl der zu löschenden Bits lässt sich, wie in nf_alloc, mit Hilfe des Parameters sizeund der Hilfsfunktion size_to_chunks berechnen.

• Die Hilfsfunktion clear_bit löscht ein Bit im übergebenen Bitfeld.

c) fmalloc, ffree (optional) F Implementiert in einem separaten Modul (fmalloc.{c,h}) dieFunktionen fmalloc und ffree, die (unter Verwendung des zuvor erstellten nf_alloc undnf_free) die gleiche Schnittstelle zur Verfügung stellen sollen, wie die C-Funktionen mal-loc(3) und free(3). ffree soll also nicht, wie zuvor nf_free, die Größe des freizugebendenSpeichers übergeben bekommen! Überlegt euch vorher, wo ihr euch die Größe des reserviertenSpeicherbereichs „merken“ könnt, damit ihr sie in ffree beim Aufruf von nf_free wieder zurVerfügung habt.

• Baut Testausgaben in euer Programm ein, um Programmierfehlern leichter auf die Schliche zu kommen. DieHilfsfunktion dump_free_mem könnt ihr dazu verwenden, an geeigneter Stelle den momentanen Zustand derFreispeicher-Bitliste auszugeben.

• Zu Testzwecken empfiehlt es sich evtl. auch, die Speicherpool-Größe (#define MEM_POOL_SIZE) zu verkleinern.Achtet dabei darauf, dass sie durch die CHUNK_SIZE teilbar bleibt.

• Kommentiert euren Quellcode ausführlich, so dass wir auch bei Programmierfehlern im Zweifelsfall noch Punktevergeben können! (We mean it!)

• Das Programm malloctest soll dem ANSI-C- und POSIX-Standard entsprechen und sich mit dem gcc auf denLinux-Rechnern im FBI-Pool übersetzen lassen, wozu ihr das mitgelieferte Makefile verwenden könnt. Mit demAufruf make clean löscht ihr das Testprogramm.

• Es empfiehlt sich der Besuch der Tafelübung, da wir dort die Aufgabe ausführlicher vorbesprechen werden.

Abgabe: bis spätestens Dienstag 08:00 in der Woche nach der Tafelübung, d. h. 15. Juni(Übungsteilnehmer 1./3./5./. . . Woche) bzw. 22. Juni (2./4./6./. . . Woche)


Documents

1 Aufgabe 4: Speicherverwaltung (11 Punkte) · PDF file1 128 KiB X 64 KiB A B C 2 F X Szenario 3: t A D S 64 KiB 64 KiB 64 KiB 64 KiB 64 KiB 64 KiB 64 KiB 64 KiB 1 A 64 KiB B C 64