Omlaboration 1: Minneshantering

Introduktion

Regler och förordningar

Laborationen lämnas in för bedömning till någon av handledarna. För att laborationen ska godkännas (G) krävs att programmet fungerar korrekt samt en utförlig rapport som analyserar och dokumenterar lösningen. I övrigt gäller att mindre oklarheter (K) medför muntlig förklaring eller kommentar. Felaktigheter eller brister i rapport eller program (O) medför ny inlämning av korrigerad rapport eller program. Om "fusk" eller liknande upptäcks, kommer lämpliga åtgärder att vidtas och laborationen kommer att betraktas som underkänd (U).

Problemspecifikation

pthread-biblioteket hanterar trådar (threads) på användar-nivå. I denna laboration ska följande utökning för minneshantering till detta bibliotek implementeras:

 int thr_mem_create(int size, int algoritm);
 int thr_mem_destroy();
 void *thr_mem_alloc(int size);
 void thr_mem_free(void *mem_ptr);

 void thr_mem_print();

thr_mem_print fungerar som en debughjälp. Funktionen ska skriva ut, på ett överskådligt sätt, en lista över minnesblock som är allokerade eller lediga. För allokerad minnesblock ska även framgå vilken tråd som allokerat just det blocket.

För att hantera denna "pool" av minne, krävs följande:

• Hantera en lista med ledigt minne, lämpligtvis en länkad lista innehållande områden som är lediga och kan allokeras. I exemplet nedan är ledigt minne markerat med grått
• Hantera en lista med upptaget (allokerat) minne, lämpligtvis i form även länkad lista som innehåller information om vilket område som har allokerats av vilken tråd. I exemplet nedan är allokerat minne för trådarna T1, T2 och T3 markerat med vitt.

Omedelbart efter anropet till thr_mem_create, innehåller listan med ledigt minne endast ett element vilket består av hela minnespoolen. Allt eftersom olika trådar allokerar respektive avallokerar minne, det vill säga anropar thr_mem_alloc och thr_mem_free, kommer ledigit minne att fragmenteras till mindre spridda delar i den totala minnespoolen.

Varje element i listan över ledigt minne ska innehålla följande:

• Storleken på kontinuerligt ledigt minne
• En pekare till nästa lediga minnesblock

För att bestämma vilken algoritm som ska användas ska följande "defines" användas som argument till int thr_mem_create(int size, int algoritm)

  #define FIRST_FIT 0
  #define BEST_FIT  1
  #define WORST_FIT 2

Ett minimalt minnesskydd ska även implementeras. Detta kommer att bestå av att endast den tråd som har allokerat (thr_mem_alloc) minnet ska kunna återlämna (thr_mem_free) det till systemet.

Notera:

Funktionerna thr_mem_alloc och thr_mem_free ska använda mutex, det vill säga exklusiv uteslutning, för att säkerställa en korrekt funktionalitet även med flera konkurerande trådar på ett operativsystem med preemptive schedulering av processer (se 'Operating System Concepts' för mer information angående preemptive schedulering).

För att testa dessa funktioner för minneshantering ska ett testprogram skrivas som startar upp några trådar. thr_mem_create anropas alltså endast en gång före det att trådarna skapas. Implementera någon form att testsekvens där thr_mem_alloc och thr_mem_free används. Vilken algoritm som används för allokering av minne ska vara en parameter till programmet.

Dessa testkörningar behöver inte någon enorm minnespool, utan några 1000 bytes är tillräckligt, och enskilda allokeringar kan vara allt från något 10-tal upp till några 100-tal bytes.

Tänk på att designa testprogrammet så att den utdata som programmet ger är relevant för uppgiften och att det går att tyda. Att bara skriva ut all data rakt upp och ner är alltså inte att rekommendera!

Implementera funktionerna i en separatkompilerad modul. Notera att det kan vara smidigare att göra två testprogram, ett för att testa korrekt funktion för algoritmerna och ett att basera den empiriska analysen på.

Redovisning

• Vilken algoritm är snabbast?
• Vilken algoritm utnyttjar bäst tillgängligt minne?

Vidare ska testkörningar bifogas, vilka visar att de implementerade rutinerna fungerar korrekt för samtliga implementerade algoritmer. Tänk då på att presentera testkörningarna på ett bra och intuitivt sätt!

Vid samtliga testkörningar ska fyra (4) trådar användas, konstruera därför ett program som testar dessa rutiner utförligt.

I övrigt krävs att laborationen innehåller problembeskrivning, systembeskrivning, algoritmbeskrivning, problem och reflektioner, testkörningar samt väl kommenterad källkod. Ett körbart program kompilerat för SunOS 5.8, samt fungerande "makefile".

Blandade tips

Följande manualsidor kan vara av intresse för denna laboration:
pthreads(3T), malloc(3C), mutex(3T)

Det är inget tvång att använda sig av två listor enligt beskrivningen ovan. Det ska bara ses som tips för att komma igång.

För kännedom