# Haskell Speicherallokierung



## bRainLaG (25. November 2009)

Ich hab folgende Aufgabe und wollte einfach mal nachfragen, da ich in Haskell so gut wie keine Erfahrung habe:

Eine stark vereinfache Speicherverwaltung soll in Haskell simuliert und zu diesem Zweck als abstrakter Datentyp implementiert werden.  Die verwalteten Einheiten sind Speicherblöcke.  Als Modell dient eine Liste von Bool-Werten, wobei der n-te Wert dieser Liste ausdrückt, ob der n-te Speicherblock reserviert oder verfügbar ist. Beispiel:

An die Speicherverwaltung werden Anfragen zum Reservieren (allocate) und Freigeben (deallocate) von (zusammenhängenden) Speicherbereichen gestellt. Beim Reservieren wird ein Speicherbereich einer bestimmten Größe (d.h. Anzahl von Blöcken) angefordert; die Speicherverwaltung versucht dann einen solchen Bereich zu finden, reserviert ihn und liefert dessen Startadresse (Nummer des ersten Blocks) zurück. Als Strategie zum Finden eines freien Speicherbereichs soll "first fit" verwendet werden: der Speicher wird beginnend bei 0 nach einem genügend großen (evtl. größeren) freien Speicherbereich durchsucht. Wird ein solcher gefunden, wird darin ein Bereich der angeforderten Länge reserviert. Achtung: eventuell bleibt am Ende eine Lücke, die weiterhin als freier Speicher gilt. 

Beim Freigeben wird die Speicherverwaltung aufgefordert, einen bestimmten Speicherbereich freizugeben (dies ist auch dann möglich, wenn der Speicherbereich – oder Teile davon –  gar nicht reserviert waren).

lass Memory m where

allocate :: m -> Int -> (m, Int)

deallocate :: m -> Int -> Int -> m

1.  Der Speicher soll, entsprechend dem Modell, als Liste von Bool-Werten verwaltet werden.

2.  Der Speicher soll mit Hilfe einer Freispeicherliste verwaltet werden. Diese Liste enthält Paare von Start- und Endadressen der freien Speicherbereiche und könnte beispielsweise so aussehen (passend zum Beispiel oben):  (0,0) (3,4) .


Hat jemand dazu eine Idee, da ich wie gesagt weder von Speicherallokierung noch von der Syntax in Haskell besonders viel Ahnung besitze.


----------



## Matthias Reitinger (25. November 2009)

bRainLaG hat gesagt.:


> Hat jemand dazu eine Idee, da ich wie gesagt weder von Speicherallokierung noch von der Syntax in Haskell besonders viel Ahnung besitze.


Das Modell für die Speicherverwaltung ist ja in der Aufgabenstellung erklärt. Wo hast du denn damit noch Probleme? Wegen Haskell müsstest du dich eben in die Sprache einarbeiten. Einen guten ersten Überblick könntest du dir beispielsweise mit der Gentle Introduction verschaffen.

Grüße,
Matthias


----------

