581322
Rinnakkaisohjelmistot (2 ov)
Erilliskuulustelu
5.10.2004
-
Rinnakkainen suoritus (15 p)
a) Tarkastellaan seuraavaa ohjelmaa
int x= 0, y =4;
co while (x!=y)
x=x+1;
// while (x!=y)
y=y-1;
oc
Päättyykö
ohjelman suoritus aina /joskus/ ei koskaan? Perustele vastauksesi. (5
p)
Vastaus:
Suoritus joskus päättyy ja
joskus ei pääty. Päättyminen riippuu prosessien
ajoituksesta.
- Merkintä co // oc suoritetaan
rinnakkain, eikä eri haarojen ajoitusta ole mitenkään
määritelty..
- Missä tahansa tilanteessa,
jossa x:n ja y:n ero eli |x-y| = 1, voi sattua niin, että
kumpikin prosessi tahollaan toteaa eroa olevan ja x kasvattaa ja
y vähentää itseään yhdellä ja
tuloksena on taas sama ero, mutta nyt niin että x > y .
Prosessi ei pääty, vaan kumpikin jatkaa toimintaansa x
kasvattaa itseään ja y vähentää itseään
ja ero vain kasvaa. Esimerkisi tilanteessa x=2 ja y=3 x ja y
kumpikin toteavat , että x!=y ja toimivat niin kuin niiden
pitää: x:= 3 ja y :=2. Taas on eroa ja x:=4 ja y:=1 ja
näin ero vain kasvaa loputtomiin.
- Tilanteessa x= 2 ja y = 4,
samanlainen ajoitus taas johtaisi tilanteeseen: x:=3 ja y:=3, jonka
jälkeen kumpikin tyytyväisenä lopettaa.
Arvostelusta:
- 5 pistettä on saanut sekä
esittämällä esimerkin, jossa suoritus joskus päättyy
ja joskus ei, että perustelemalla asian riittävän
tarkkaan sanallisesti
- 3-4 p jos asia on esitetty hieman
puutteellisesti
- “joskus päättyy,
joskus ei, koska arvot eivät välttämättä
kohtaa” => 2p, koska vain vihjaillaan syystä.
- “saattaa käydä
niin, ettei yhtäsuurta arvoa saavuteta” => 1 p, koska
ei mitään perusteluja
b) Mitkä ovat
lukkiutumistilanteen (deadlock) syntymiselle välttämättömät
ja riittävät ehdot ja
miten kukin näistä
ehdoista täyttyy aterioivien filosofien ongelmassa? Miten
filosofien
tapauksessa lukkiutuminen
voitaisiin estää muuttamalla haarukoiden käyttösääntöjä?
Tarkastele
kutakin sääntöä
erikseen. (10 p
Vastaus:
Välttämättömät
ja riittävät ehdot:
- resurssia saa kerrallaan käyttää
vain yksi (mutual exclusion) ja resursseja ei ole riittävästi
kaikille
- jo varattuja resursseja ei
luovuteta pois puuttuvia odotettaessa (wait and hold)
- resursseja ei saa myöskään
otta pois väkisin (no preemption
- Näiden staattisten ehtojen
lisäksi dynaaminen edellytys: syntyy odotussilmukka, jossa
jokainen odottaja odottaa jotain muiden odottajien hallussa pitämiä
rerursseja.
Filosofien tapauksessa:
- kutakin haarukkaa saa käyttää
vain yksi => yhteiskäyttöiset haarukat (lisää
kertakäyttöhaarukoita)
- ei luovuta jo kädessää
olevaa haarukkaa odottaessaan toista => molemmat haarukat
saatava haltuun samalla kertaa
- naapurilta ei saa riistää
haarukkaa => filosofeille prioriteetit (kuka saa riistää
keneltä haarukan)
- varataan haarukat aina samassa
järjestyksessä (esim. vasen ensin) => joku filosofi
toimii toisin kuin muut (eli varaa ensin oikean)
Arvostelusta:
- 4 ehtoa a' 1 p
- 4 ratkaisua filosofien ongelmassa
a' 1 ½ p
Tankkausta semaforipohjalta (15 p)
Pienellä
bensa-asemalla on vain yksi bensapumppu ja sitä käyttämässä
asemanhoitaja, joka täyttää tankin ja ottaa maksun.
Kesäaikaan asemalla silloin tällöin on asiakkaita
ihan ruuhkaksi asti. Bensapumpun viereen mahtuu vain yksi auto
kerrallaan. Muiden tankkausta haluavien on odotettava kauempana,
kunnes tankattavana ollut auto on poistunut. Auto voi poistua
vasta, kun se on tankattu ja maksu suoritettu. Laadi toimintakoodi
tankkaamaan tuleville autoille (prosesseille auto[i = 1 to N]) ja
asemanhoitajalle (prosessille hoitaja), kun tankkaavien autojen ja
asemanhoitajan toiminnan synkronointiin käytetään
semaforia.
Eräs ratkaisu:
Auton odotettava:
- pumpulle
ajamista
- tankkauksen
valmistumista
Asemanhoitajan on
odotettava:
=> kutakin
odottamista varten tarvitaan oma semafori.
Aluksi sallittua on vain
yhden auton ajaminen pumpulle, joten vain sillä semaforilla on
alkuarvo 1, muiden alkuarvo on 0.
sem pumppu_vapaa =1, # mutex-tyyppinen; valvoo, että vain yksi auto on kerrallaan tankkaamassa
auto_pumpulla = 0, # tankkaustoiminnan synkronointia varten: tankkaamisen voi aloittaa
tankattu_on = 0, # tankkaustoiminnan synkronointia varten: tankkaus on valmis
maksu = 0; # asemanhoitaja odottaa maksua (jonka jälkeen voi häipyä muihin
# hommiin siihen asti kunnes seuraava auto tulee tankattavaksi)
process auto[i=1 to N] { # autoja N kappaletta
while true {
ajele ympäriinsä, kunnes tarvitsee tankata
P(pumppu_vapaa); # tässä jäädään odottamaan, jos pumppu on varattu
aja bensapumpulle tankkaamaan;
V(auto_pumpulla); # herätetään asemanhoitaja toimimaan
P(tankattu_on); # odotellaan, että tankkaus valmistuu
maksetaan;
V(maksu); # maksettu on
aja pois tankkausalueelta;
V(pumppu_vapaa); # päästä seuraava auto tankkaamaan, joko jo
#odottava tai joskus tuleva
}
process asemanhoitaja {
while true {
P(auto_pumpulla); # odottele tankkaamaan tulevaa autoa
tankkaa auto;
V(tankattu_on); # ilmoita tankkauksen valmistumisesta
P(maksu); # jää odottamaan maksua
}
Arvostelusta:
Koska pyydettiin käyttämään
semaforia, niin muut ratkaisut (monitori, sanomanvälitys, yms)
toivat 0 pistettä!
- semaforien määrittelyt
ja alkuarvot sekä semaforin käyttö
- alkuarvon puuttuminen
-1 p
- väärä
alkuarvo voi johtaa toiminnalliseen virheeseen => pisteitä
putoaa enemmän
- muita kuin P- ja
V-operaatioita -2 p
- toiminnan oikeellisuus
= P- ja V-operaatioiden oikeat kohdat ja järjestys
- toimintojen
synkronointi (-2 - -3 p)
- usea auto pääsee
samaan aikaan tankkausalueelle
- asemanhoitaja lorottta
bensaa, vaikka autoa ei ole paikalla
- päästää
pois, vaikka ei ole maksanutkaan
- lähtee pois,
vaikka ei vielä ole tankannut
- lukkiutuminen (-2 p)
- väärän
alkuarvon takia
- koska odottamaan
menevä ei vapauta mutexia
- P- ja V-operaatiot
väärässä järjestyksessä =>
lukkiutuminen
- päivitystä ei
suojata mutexilla -1 - -2 p
- määrittelemättömiä
muuttujia, selittämättömiä operaatioita -1 - -2
p
- tehokkuus = turhan
monimutkaiset ratkaisut
- turhat jonot ja
semaforit -1- -3p (yleensä nämä eivät edes
toimineet!)
Tehtävä oli
kuitenkin melko hyvin osattu. Siitä sai täydet pisteet
peräti kahdeksan opiskelijaa.
Tuottajien ja kuluttajien
synkronointi monitoria käyttäen (15 p)
Tuottaja- ja kuluttajaprosessien
välissä on rajallisen kokoinen puskuri (N alkiota), johon
tuottajat tuottavat tietoa alkio kerrallaan ja josta kuluttajat
sitä vastaavasti noutavat.
- Missä tilanteissa tässä
tarvitaan prosessien poissulkemista ja synkronointia? Esitä
sanallisesti,
miten monitoriratkaisusi selviää
näistä tilanteista. (3 p)
Vastaus:
- poissulkemista tarvitaan puskurin
käyttöön ( lähinnä osoittimien tutkimiseen
ja päivittämiseen). Monitori huolehtii itse
poissulkemisesta eli vain yksi kerrallaan pääsee
monitoriin.
- Synkronointia tarvitaan tuottajan
ja kuluttajan toimintojen tahdistamiseen: kuluttaja ei lue tyhjää
puskuria, tuottaja ei vie mitää täyteen puskuriin.
Tämä on hoidettava sopivilla signal- ja wait-
toiminnoilla.
Arvostelusta:
- poissulkeminen 1.5 p;
-
synkronointi 1.5 p
b) Laadi tuottaja- ja
kuluttajaprosessien toimintaa koordinoiva monitori. (8 p)
monitor puskuri {
typeT pusk[N]; # N on puskurin koko
int alku =0; # puskurin alkuun
int loppu = 0; # puskurin loppuun eli ensimmäiseen tyhjään slotiin
int lkm =0; # alkioiden (= tuotosten) lukumäärä puskurissa
cond mahtuu; # lkm < N
cond voi_ottaa; # lkm > 0
procedure vie (int data) {
while (count = = N) wait(mahtuu);
pusk[loppu] = data;
loppu = (loppu + 1) % N;
lkm ++;
signal(voi_ottaa);
}
int procedure hae ( ) {
int apu;
while (count = =0) wait(voi_ottaa);
apu = pusk[alku];
alku= (alku + 1) % N;
lkm --
signal(mahtuu);
return apu;
}
Ratkaisu löytyy myös
kurssikirjasta sivulta 214.
Arvostelusta:
-
~ 4 p monitorin perustoiminnasta
- monitorin ja cond-muuttujien
määrittely sekä proseduurien määrittelyt
- wait- ja signal -operaatiot
-
~ 4 p monitorin käytöstä
tässä tilanteessa (= tuottaja-kuluttaja + rajallinen
puskuri)
- if whilen tilalla -1 p
- pelkkä laskurimuuttuja, ei
puskurin osoittimia -2 p
- osoittimien päivitys
virheelistä -1p
- wait ja signal väärissä
kohdissa -1 - -2 p
- turha mutex monitoriin -1 p
- wait -lukitus alussa -1 p
c) Laadi tuottaja- ja
kuluttajaprosessien koodit, joista selkeästi käy ilmi,
kuinka prosessit vievät
tietoa puskuriin ja kuinka ne
noutavat tietoa puskurista.(4 p)
Eräs ratkaisu:
process tuottaja[i=1 to N] {
int data;
while true {
data = tuotettu_uusi_tieto( );
call pusk.vie(tieto);
}
}
process kuluttaja[i=1 to M] {
int data;
while true {
data = call pusk.hae(tieto);
kuluta(data);
}
}
Arvostelusta:
- call puuttuu -0.5 p
- monitorin nimi puuttuu -1p
- ei useita prosesseja -0.5 p
Kommunikointi sanomanvälitystä
käyttäen. (15 p)
Sääennustus on
toteutettu rinnakkaisena laskentana. Ennustettavan alueen ilmatila on
jaettu
kuutioihin ja kunkin kuution
ennusteesta huolehtii yksi solmukone. Laskenta etenee
vaiheittain:
- Alkuarvoista lähtien kukin
solmu laskee kuutiolleen ensimmäisen ennusteen (esimerkiksi
sään tunnin kuluttua).
- Kun ennuste on valmistunut, niin
solmu ilmoittaa ennustetun tilan naapureilleen.
- Saatuaan kaikilta naapureilta
näiden ennusteet solmu aloittaa seuraavan vaiheen ja laskee
seuraavan ennusteen (esim. säätilan kuutiossa seuraavan
tunnin kuluttua).
Näin jatketaan kunnes ennusteet
on saatu halutulle aikavälille (esim. kolmen vuorokauden
ennuste).
Laskentaohjelmat kommunikoivat
käyttäen sanomanvälitystä ja globaaleja kanavia.
Kirjoita yhden solmun
laskenta-algoritmin normaalivaiheen toimintaa ohjaavan ohjelman
oleelliset osat (sovelluksen
käynnistys- ja lopetusvaiheesta ei tarvitse välittää).
Esittele kanavat ja
täsmennä send/receive
-rutiinien synkronointisemantiikka (blocking vai non-blocking).
Ratkaisu:
globaalit määrittelyt
typedef ennuste .... ; #
sääennustetietue
chan mailbox[N,N] (sääennuste
arvo)
# kanavalla mailbox[i,j] kulkevat
sanomat prosessilta i prosessilta j
process P[i=0 to N-1] {
int maxlkm # vaiheiden
lukumäärä
ennuste arvo[N];
/* alustukset
....
*/
for [phase = 1 to maxlkm] {
/* laske tämä vaihe
input: aikaisemmat arvot
suoritetaan laskenta
tuloksena uudet paikalliset
arvot
*/
for [kaikille j: P[j] on P[i]:n
naapuri]
send mailbox[i, j] (value[i]);
for [kaikille j: P[j] on P[i]:n
naapuri]
receive mailbox[j,i](value[j]);
}
}
= = = = = = = = = = = = = = = = = = =
= = = = = == = = = = = = = = = = = = = = = = = = = = = = =
Millaiset
kanavat?
- Jokaisella prosessilla oma kanava kaikkiin naapureihin
jopa itseensä
- Jokaisella
prosessilla on oma kanava ('postilaatikko'), johon naapureiden
lähettämät sanomat tulevat
chan
postilaatikko[N] (int tunnus, int kierros, ennustetyyppi ennuste);
nyt
on pidettävä kirjaa, että on todella saanut oikean
määrän sanomia ja juuri kaikilta
- lkm
laskuri, joka laskee oikean kierroksen sanomien
lukumäärää
-
naapurilista-taulukko, johon merkitään saadut sanomat
-
talletettava myös sekaan eksyneet seuraavan kierroksen sanomat
Voi käydä niin, että jokin hyvin nopea naapuri,
joka
saatuaan uudet arvot kaikilta naapureiltaan on jo ehtinyt
laskea niiden
avulla uuden ennusteen ja lähettää sen
eteenpäin. Tämä seuraavan kierroksen
(i+1) arvo voi tulla jollekin naapurille (P) ennen joitakin
edellisen kierroksen (i )
arvoja. Koska K on lähettänyt J:lle ensimmäiseksi
ja P:lle paljon myöhemmin.
,..., {J, i+1, value[i+1]}, { K,i, value [i]}, ...
-
lähetä kaikille naapureille
for {all j: P(j) on P(i):n naapuri}
send
postilaatikko[j]( i, laskuri, arvo[i]);
-
vastaanota kaikilta naapureilta
while (ei ole vielä saatu
kaikilta naapureilta)
receive
postilaatikko[i] j, laskuri, arvo[j]);
-
Yhden ainoan yhteisen postilaatikon käyttö kaikkien
viestintään on todella hankalaa:
-
receive poistaa aina sanoman postilaatikosta => voi saada
ihan väärän, toiselle prosessille tarkoitetun
sanoman, joka on lähetettävä uudestaan kanavalle,
jotta sen oikea vastaanottaja joskus saisi sen
-
jokaisen prosessin pitäisi kait lukea (receive) joka kerta
kaikki postilaatikon sanomat ja tallettaa (send) takaisin kaikki ne,
jotka tarkoitettu joillekin muille
-
sen lisäksi tietenkin tehtävä kaikki sama kuin
edellisessa eli käytävä penkomasssa postilaatikkoa,
kunnes kaikki yhden kierroksen tiedot kaikilta naapureilta on saatu.
Arvostelusta:
-
sanomanvälitykseen
liittyvän kommunikoinnin perusasiat:
- kanavien
määrittelyt 2p
- kanavaan
lähettäminen 2 p
- kanavasta
lukeminen 2p
-
muu
tarpeellinen toiminta valitussa kanavaratkaisussa 5 p
-
blocking ja
non-blocking 4 p
-
- tässä lähettäminen = non-blocking, koska
muuten joutuu odottelemaan, että jokainen
vastaanottaja vuorollaan on saanut sanoman
oikea vastaus + perustelu 2p
-
- vastaanottaminen = blocking, koska saa edetä seuraavaan
vaiheeseen vasta, kun on saanut
sanoman jokaiselta naapuriltaan
oikea vastaus + perustelu 2p