Laboration 1: Minneshantering
- Complementary thread library -
Inlämningsdatum: 23-nov-2001 17:00
Introduktion
Denna laboration ska ge en empirisk introduktion till minneshantering i
ett operativsystem. Vidare ska den även ge en grundläggande introduktion
till de problem som design av ett operativsystem medför. De algoritmer
som skall implementeras och studeras lite mera ingående är FIRST-FIT,
WORST-FIT och BEST-FIT, detta är tre grundläggande
algoritmer för hantering av minne.
Regler och förordningar
Denna laboration ska lösas individuellt.
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_create allokerar en "pool" av minne från systemet
(med hjälp av malloc) med storleken size bytes,
funktionen ska returnera -1 om önskad minnesstorlek inte kunde
allokeras. Den andra parametern, algoritm, beskrivs mera utförligt
nedan. thr_mem_alloc allokerar en delmängd av den tidigare
allokerade "poolen" av minne, den ska returnera en NULL
pekare om önskad allokering inte kan utföras. thr _mem_free
avallokerar det minnesområde som pekas ut av mem_ptr och
returnerar minnet till systemet. thr_mem_destroy avser att återlämna
allt allokerat minne till operativsystemet, det vill säga allt minne
som har allokerats med thr_mem_create.
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
När så thr_mem_alloc(size) anropas går minneshanteraren
igenom listan över ledigt minne för att söka efter ett ledigt
minnesblock med en storlek större än eller lika med size.
Minneshanteraren tar då "bort" size bytes från det
lediga blocket och reserverar detta minne som allokerats för en specifik
tråd. När minne återlämnas till minneshanteraren
med thr_mem_free ska den först kontrollera om detta minnesblock
är direkt angräsande till något existerande ledigt minnesblock
. Om så är fallet ska dessa två minnesblock slås
ihop och bilda ett kontinuerligt ledigt minnesblock, annars ska detta minnesblock
läggas till listan över 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
Funktionen för thr_mem_alloc ska alltså implementeras
så att den hanterar dessa, ovan angivna algoritmer för minnesallokering.
Parametern algoritm till funktionen thr_mem_create avgör
alltså vid initiering av minneshanteraren vilken algoritm som ska
användas vid allokering. Det ska alltså inte gå
att ändra algoritm för minnesallokering efter det att minneshanteraren
har blivit initierad.
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
En rapport, på svenska eller engelska, med en utförlig analys
av respektive algoritm. Analysen ska avhandla minst följande områden:
-
Vilken algoritm är snabbast?
-
Vilken algoritm utnyttjar bäst tillgängligt minne?
Samt en mindre diskussion angående hastighet vs. minnesutnyttjande!
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.6, 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
Denna laboration har utvecklats av Anders Selander, selander@cs.umu.se
Laborationen har modifierats något av Claes Gahlin, claes@cs.umu.se
|