581332 Rinnakkaisohjelmointi (4 op / 2 ov) /Liisa Marttinen
HUOM! Andrewsin kirjaan perustuva, syksyllä 2005 luennoitu kurssi
Erilliskoe 2.2.2007
Kirjoita jokaiseen vastauspaperiin nimesi ja nimikirjoituksesi, henkilötunnuksesi tai opintonumerosi sekä kokeen nimi ja päivämäärä.
KARHU,
HUNAJAPURNUKKA JA MEHILÄISET SEMAFORISSA [15 p]
KAIVURI
JA KUORMA-AUTOT MONITORIKUOPASSA[15 p]
Ratkaisu ei takaa järjestyksen säilymistä. Järjestys saadaan säilymään käyttämällä
condition passing -tekniikkaa edellyttäen, että sekä monitorissa että monitoriin
pyrittäessä jonot ovat FIFO-jonoja.
Arvostelusta:
prosessi varattu maxtarve
A B C A B C
p1 1 2 2 3 5 3
p2 2 1 0 2 2 1
p3 0 2 1 3 4 2
Prosessi p1 pyytää
saada lisää yhden A-resurssin. Voidaanko se myöntää?
Perustele vastauksesi esittämällä pankkiirin algoritmin suoritusvaiheet.
Mitä tapahtuu, jos prosessille
ei voida myöntää sen tarvitsemia resursseja? ( 6 p)
Kirjoita
koodit karhuprosesille ja mehiläisprosesseille, kun niiden
toimintojen koordinointi hoidetaan
semaforeja käyttäen. (10 p)
sem mutex = 1, # mutual exlusion
pot_full = 0; # is the pot full of honey
int portions =0; # portions in the pot
process bee[i=1 to N] {
while (true) {
collect_honey();
P(mutex);
portions ++;
if (portions = = H) V(pot_full); # let the bear eat
else V(mutex); # let the next bee in to fill
}
}
process bear {
while (true) {
P(pot_full); # 'sleep' = wait until the pot is full
portions =0; # eat all the honey
V(mutex); # let the bees start filling the pot again;
}
}
Pienellä
hiekkakuopalla on töissä yksi kaivuri ja useita
kuorma-autoja. Kaivuri on hiekkakuopan pohjalla ja mättää
hiekkaa autoihin.Yksi kuorma-auto kerrallaan ajaa kuopan pohjalle,
odottaa kunnes kuorma on täynnä ja sitten poistuu
kuopalta. Kaivuri taas odottaa kunnes hiekkakuopan pohjalla on
kuorma-auto ja täyttää auton lavan hiekalla. Anna
monitoria käyttävä ratkaisu kaivurin ja
kuorma-autojen toiminnan synkronointiin. Esitä myös
monitoria käyttävien kaivuri- ja kuorma-autoprosessien
koodit.
monitor Sandpit {
cond start_loading; # kaivuri saa alkaa täyttää
cond loaded; # kuorma-auto saa poistua
cond proceed; # kuorma-auto saa ajaa kuopalle
boolean occupied =false; # sandpit is occupied
procedure Lorry_loading(){
while (occupied) wait (proceed); # jos kuopassa jo toinen auto, mene odottamaan
occupied = true;
aja kuopan pohjalle;
signal (start_loading);
wait (loaded);
aja pois kuopalta;
occupied = false;
if (!empty(proceed)) signal_all(proceed); # herätetään kaikki odottavat autot kilpailemaan
# pääsystä hiekkakuopalle!
}
procedure Fill_lorry() { # tämä prosessi on koko ajan monitorissa: joko odottamassa
while (true) { # kuormattavaa tai kuormaamassa!
if (!occupied) wait(start_loading); # jos lastattavaa autoa ei ole, mene odottelemaan
fill the lorry;
signal (loaded);
}
}
}
process Digger()}
call Sandpit.Fill_lorry();
}
process Lorry[i=1 to n](){
while (true) {
ajele hiekkakuopalle;
call Sandpit (Lorry_loading);
vie hiekka jonnekin;
}
}
Itseasiassa juuri tällainen monitori kuvastaa tilannetta hiekkakuopalla.
Kaivuri on koko ajan kuopassa joko työn touhussa tai odottelemassa.
Yksi kuormuri pääsee ajamaan kuopalle, jossa odottelee kuorman lastauksen ajan
ja ajaa sitten pois kuopasta. Muut lastaamaan tulleet kuormurit
odottelevat vuoroaan kuopan reunalla.
procedure Lorry_loading(){
if (occupied) wait (proceed); # if there is a lorry already in the sandpit, start waiting
else occupied = true;
aja kuopan pohjalle;
signal (start_loading);
wait (loaded);
aja pois kuopalta;
if (!empty(proceed)) signal(proceed); # päästetään seuraava jo monitorissa odottava
else occupied =false ; # tai 'uusi tulija' hiekkakuopalle
{
Arvostelusta:
Esitä "nukkuvan
parturin ongelman" ratkaisu käyttäen
sanomanvälitystä. Partureita oletetaan olevan useita.
chan service(int clientid, ...); # tässä voisi myös ilmoittaa, mitä palvelua haluaa chan client[n](int barberid); chan barber[m](int barberid); process client [i=1 to N] { int barnerid; while (true) { ......... mene parturiin; send service(i); # ilmoita oman kanavasi tunnus receive client[i](barberid); # jää odottamaan tietoa parturilta siirry 'oman' parturisi tuoliin; send barber[barberid](i); # ilmoita parturille olevasi valmis receive client[i](barberid) #odota parturin ilmoitusta työn valmistumisesta nouse tuolista; send barber[barberid](i); #ilmoita poistuneesi } process barber[j=1 to M]{ int clientid; while(työaika) { receive service(clientid); # odottele asiakkaita ja ota seuraavan tunnus kanavasta send client[clientid](j); # ilmoita asiakkaalle oma tunnuksesi receive barber[j](clientid); # odottele, kunnes asiakas istuu tuoliin suorita tukan leikkkuu tms; send client[clientid](j); # ilmoita toimenpiteen valmistumisesta receive barber[j](clientid) # odota, että asiakas on poistunut }Ratkaisussa kullakin asiakkaalla ja parturilla on oma yksityinen kanavansa. Parturin täytyy tietää asiakkaan kanavatunnus ja asiakkaan parturin kanavatunnus. Muu viestien sisältö ei ole tärkeää. Jo pelkkä viestien saapuminen riittää tahdistamaan toiminnan.
Arvostelusta:
Muistin virkistämiseksi =>