www.jammni.de

Gepostet:
25.11.2009 19:35

Speicher in Haskell

Aufgabe:

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).

class 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) .

Meine Ideen:

Feld, allocate: Durchlaufe Feld und suche freien, zusammenhängenden Bereich, welcher der Größe der Anfrage entspricht. Markiere gefundene Feldelemente als belegt oder erzeuge Ausnahme/Fehler, wenn nicht genug Platz.

Feld, deallocate: Überprüfe Parameter und entferne Markierung.

Freispeicherliste, allocate: Durchlaufe Freispeicherliste und überprüfe für jedes Element, ob Größe der Anfrage entspricht. Wird das Freispeicherlis- tenelement vollständig durch die Anfrage aufgebraucht, entferne es aus der Freispeicherliste, ansonsten verkleinere es entsprechend.

Freispeicherliste, deallocate: Überprüfe Parameter. Füge neues Element der Freispeicherliste hinzu, welches dem freigegebenen Bereich ent- spricht. Sortiere Freispeicherliste und verbinde zusammenhängende Be- reiche zu einem Freispeicherlisteneintrag.

Nun habe ich ein Problem ich hatte nie Haskell und habe dementsprechend von der Syntax keine Ahnung, ich weiß worum es geht und was ich mache müsste nur wie man das in einer funktionalen Programmiersprache anwendet habe ich keine Ahnung.
Ich hoffe ihr könnt mir da etwas helfen und mir das vieleicht auch erklären wenn ihr Quellcodes angeben solltet damit ich nicht dumm sterbe :(

Zum Seitenanfang

Siracusa

Gepostet:
25.11.2009 20:51

Hallo,

wenn du noch nie in Haskell programmiert hast, solltest du erstmal über eins der Tutorials hier fliegen: http://www.haskell.org/haskellwiki/Tutorials, für den Start empfielt sich da z.B. das: http://en.wikibooks.org/wiki/Haskell/YAHT/Language_basics. Noch besser für Einsteiger ist m.E. aber Programming in Haskell von Graham Hutton, in jeder gut sortierten Uni-Bibliothek erhältlich. ;-)

Die Algorithmen klingen prinzipiell in Ordnung. Versuch doch mal mit Hilfe der Tutorials erste Ansätze zu programmieren, damit man bei Problemen eine Basis hat über die man diskutieren kann.

Viele Grüße,

Siracusa

Zum Seitenanfang

bRainLaG

Gepostet:
26.11.2009 00:34

Ich habe ja bereits schonmal angefangen, woran es bei mir hackt, ist wie ich eine Liste durchlaufen kann,
Angefangen habe ich so:

class Memory m where

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

data List a | Nil cons a (List a)
List a :: [boolean] -> int

instance Memory a where
a < 0 = error

Soweit ich das nachgelesen habe packe ich hier eine leere Liste und ein Element a zusammen zu einer neuen Liste a
Desweiteren deklariere ich boolean als Datentyp und int soll die Anzahl der Speicherblöcke sein. Wenn a < 0 das heißt die Liste nichts enthält, soll ein Error zurückgegeben werden.

Nun komme ich nicht dahinter, wie ich die Liste durchlaufen kann und Elemente praktisch markieren kann. Das habe ich auch in keinem Tutorial gefunden :(
Das doofe ist ich steh auch echt unter Zeitdruck was das angeht, da ich die Aufgabe schon haben sollte, ich mich allerdings vergebens durchs Internet quäle ansonsten würde ich ungern nach Lösungen fragen.

Zum Seitenanfang

Siracusa

Gepostet:
26.11.2009 02:37

Du brauchst dir keinen Datentyp List erstellen, in Haskel gibt es bereits Listen. Das heißt für 1.) verwendest du [Boolean] (Groß-/Kleinschreibung beachten!) und für 2) bspw. [(Int, Int)]. Was du dann machst, ist dir für die Klasse Memory m zwei Instanzen anzulegen, und zwar instance Memory [Boolean] und instance Memory [(Int, Int)]. In beiden Klassen implementierst du jeweils die Funktionen allocate und deallocate, wobei der Typ m dann entweder für [Boolean] oder [(Int, Int)] steht.

Listen kannst du z.B. mit rekursiven Aufrufen der gleichen Funktion durchlaufen:

summe :: [Int] -> Int
summe []     = 0
summe (x:xs) = x + summe xs

Die erste Zeile besagt, dass die Funktion summe aus einer Liste von Int wieder einen einzelnen Int macht. Dann folgt die Definition der Funktion; jede Zeile gibt ein Muster an. Wenn das Muster auf der linken Seite vom Gleichheitszeichen mit dem Aufruf zusammenpasst (durch pattern matching), dann wird die rechte Seite berechnet, ansonsten zur nächsten Zeile gesprungen und dort versucht zu matchen.

Die zweite Zeile ist hier das Rekursionsende, es wird also 0 zurückgegeben, wenn eine leere Liste als Parameter übergeben wird. Die dritte Zeile enthält den eigentlichen rekursiven Aufruf. Das x ist das erste Element der Liste, xs die Restliste. Es wird nun x plus die rekursiv berechnete Summe der Restliste xs berechnet.

Das ist das grundlegende Prinzip Listen per Rekursion zu durchlaufen. In deinem Fall prüfst du bei jedem Rekursionsschritt dann bspw., ob (x:xs) am Anfang n Mal True zu stehen hat beim Allokieren.

Hier findest du übrigens viele nützliche Hilfsfunktionen für Listen: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html

Viele Grüße,

Siracusa

Zum Seitenanfang

Haskell-Forum