Obligatorisk oppgave 3
			       INF1070
			      V?ren 2005

I mange spr?k (som C og assemblerspr?k) er ikke dynamisk allokering av
minne bygget inn i spr?ket men tilgjengelig som biblioteksrutiner, for
eksempel `malloc? og `free?.

Oppgaven er ? skrive to funksjoner `mgrab? og `mdrop? som oppf?rer seg
likt `malloc? og `free?; de skal skrives i x86-kode som virker med gcc
p? Ifis maskiner. Sett ogs? av et omr?de (en s?kalt ?heap? eller
?haug? p? norsk) p? 4096 byte hvor det skal allokeres minne:

        .align 4
haug:   .fill 4096

Det anbefales ? bruke lister til ? implementere `mgrab? og `mdrop?,
men om noen vil bruke en annen teknikk som for eksempel et
?buddy-system?, er det OK. Men det settes da strengere krav til at
koden er godt kommentert.

I slike systemer er det vanlig at datastrukturen (for eksempel
listepekerne) ligge i selve dataomr?det, s? det er helt OK at ikke
alle 4096 byte er tilgjengelig for brukeren. Ofte vil 4088 byte v?re
den st?rste blokken brukeren kan f?, men den n?yaktige grensen
avhenger av hvordan minne er oorganisert.

P? kursets nettside (p? siden med pensumoversikt) ligger en referanse
til en kort innf?ring til hvordan man kan implementere `mgrab? og
`mdrop? med lister med et eksempel i C. V?r oppmerksom at denne
innf?ringen skiller seg fra denne obligatoriske oppgaven p? f?lgende
punkter:

* Eksemplet er i C; dere skal skrive i x86-assembler.

* Eksemplet henter blokker fra et minneomr?de p? 64 byte; dere skal
  hente fra et p? 4096 byte (se over). Dette medf?rer blant annet at
  blokkst?rrelsene m? v?re p? minst 2 byte (mens de i eksemplet er p?
  1 byte). 

* Eksemplets `mgrab? returnerer en indeks 0-63 som ogs? brukes som
  parameter til `mdrop?. Dere skal i stedet bruke en full 32-bits
  adresse til lagerlokasjonene. Hvis det ikke finnes noe ledig omr?de,
  skal funksjonen returnere 0.

* Debug-koden (omsluttet av ?#if DEBUG ... #endif?) og koden som
  skriver ut en oversikt over hva som skjer (omsluttet av ?#if INFO
  ... #endif?) skal ikke tas med.

All koden (unntatt et eventuelt testprogram) skal skrives i x86
assemblerkode for GNUs assembler. ~inf1070/programmer/test-grabdrop.c
(http://www.ifi.uio.no/~inf1070/programmer/test-grabdrop.c) er et
testprogram som gruppel?rerne vil bruke i sin testing. 

Innleveringsfristen er

			mandag 2. mai kl 12.00

Gruppel?reren bestemmer hvorledes innleveringen skal skje.

Noen ytterligere punkter:

* `malloc? vil be operativsystemet om mer minne n?r haugen er brukt
  opp. Det skal ikke `mgrab? gj?re; den skal bare returnere 0.

* Legg vekt p? ? skrive velstrukturert og godt kommentert kode. Om
  koden er vanskelig ? forst?, vil gruppel?reren nekte ? rette den.

* Alle innleverte besvarelser vil bli testet av et eget hemmelig
  testprogram. De fem raskeste vil bli plassert p? en hedersliste p?
  kursets nettside, og den aller beste vil f? en premie.

10. april 2005
Litt oppdatert 21. april 2005
Dag L