581332 Rinnakkaisohjelmointi
Erilliskuulustelun 28.3.2006 arvostelusta
HUOM! Jos esitetyissä ratkaisuissa on painovirheitä tai muita kömmähdyksiä tai mitä tahansa kummallisuuksia, niin ilmoitelkaa niistä Liisa Marttiselle.
1. Lukkiutumisesta ja vähän nälkiintymisestä [15p]
staattisia:
dynaaminen ehto:
2.
Semaforilla tahdistettu ruokinta [15p]
Lintuemo ruokkii
pesässä olevia poikasiaan. Se täyttää ensin
pesän keskellä olevan kuopan pienillä madoilla ja
kutsuu sitten poikaset syömään. Itse se menee
lepäämään. Kuoppaan mahtuu H annosta. Poikaset
syövät vuorotellen, kukin ottaa kerralla yhden annoksen ja
kuopan tyhjentänyt poikanen herättää emon
hakemaan lisää ruokaa.
Kirjoita koodit emoprosessille
ja poikasprosesseille, kun toimintojen koordinointiin käytetään
semaforeja.
Eräs ratkaisu: Käytetään mutex-tyyppistä semaforia säätelemään sitä, että vain yksi poikanen kerrallaan on syömässä matoja. Ensimmäinen pääsee vasta, kun emo on täyttänyt kuopan madoilla. Jo syönyt poikanen päästää seuraavan mutex-semaforissa odottavan tai sinne tulevan poikasen syömään. Jos kuoppa tyhjenee, poikanen herättää emon eikä avaa mutexia seuraavalle poikaselle.
sem mutex = 0; sem herätys =0; int annoksia = 0; process emo { while (true) { kerää matoja; annoksia = H; # täytä kuoppa madoilla V(mutex); P(herätys); # jää odottamaan herätystä } } process poikanen[i=1 to N] { while (true) { P(mutex) annoksia --; if (annoksia == 0) V(herätys) # jos ruoka loppui, herätetään emo #ja jätetään mutex-muuttuja kiinni else V(mutex); # muuten päästetään seuraava poikanen syömään syö matoannos; } ==========================================Ratkaisu, joka toimii, mutta siinä käytetään ihan turhaan 'kaksinkertaista lukitusta' eli e-semafori on turha. => muuten samanlainen ratkaisu kuin ed. tehtävässä
sem full=0, empty=1; # split binary semaphore sem e = 1; # mutex int ruokaa =0; # annosten määrä process emo { while(true) { P(empty); P(e); ruokaa= H; # täytä kuoppa V(e); V(full); } } process (poikanen) [i=1 to N] { while (true) { P(full); P(e); ruoka --; if (ruoka == 0) V(empty) else V(full); V(e); syö annos; } } =====================================Ratkaisu, jossa käytetään (turhaa) semaforia ruokaa
sem mutex = 0; sem herätys =0; sem ruokaa = H; # aloitustilanteessa kuoppa on täynnä matoja int annoksia = 0; process emo { while (true) { kerää matoja; annoksia = H; # täytä kuoppa madoilla for i = 1 to H {V(ruokaa) }; # lataa semaforin arvoksi H V(mutex); P(herätys); # jää odottamaan herätystä } } process poikanen[i=1 to N] { while (true) { P(ruokaa); P(mutex) annoksia --; if (annoksia == 0) V(herätys) # herätetään emo ja jätetään mutex-muuttuja kiinni else V(mutex); # muuten päästetään seuraava poikanaen syömään syö matoannoksesi; } }Tehtävä 2: virheitä:
Hyvin
yksinkertainen ratkaisu , joka vain estää eri suunnilta
tulevia autoja törmäämästä ja liian montaa
autoa menemästä sillalle. Ratkaisussa ei ole lainkaan huomioitu reiluutta eikä myöskään toiminnan tehokkuutta.
Jos
auto ei heti pääse sillalle, niin se menee odottamaan.
Kaikki odottavat samassa ehtomuuttujassa ja jokainen sillalta
poistuja päästää kaikki odottajat yrittämään
uudestaan ja uudestaan, kunnes sillalle meno onnistaa (joko silta on
tyhjä tai silta on kyllä käytössä, mutta
ajosuunta on sama kuin itsellä eikä sillalla ole vielä
10 autoa). Onnistuminen on hyvin sattumanvaraista ja prosessit
saattavat joutua kiertämään kehää (mene
odottamaan -> herää -> mene monitorin jonoon ->
testaa pääsetkö nyt -> mene takaisin odottamaan).
Tämäntyyppinen oikein toimiva ratkaisu => 10 p
monitor Silta { int ajosuunta = 0; # ajosuunta sillalla A=>B = 1 ja B=>A = 2 int slkm = 0; # autojen lukumäärä sillalla; jos 0 niin silta on vapaa cond odota_vuoroa; # kaikki autot odottavat samassa ehtomuuttujassa procedure enter_silta (oma_suunta) { while (slkm>0 && ajosuunta != oma_suunta || slkm = 10) wait(odota_vuoroa); if (slkm =0) ajosuunta = oma_suunta; slkm ++; } procedure exit_silta(oma_suunta) { slkm --; # tässä vähän suositaan omaa suuntaa, kun ajosuuntaa ei muuteta signal_all(odota_vuoroa); } ========================================================Ratkaisu, jossa aina samaan suuntaan pyrkivät autot pääsevät sillalle saapumisjärjestyksessä (FIFO). Mutta samaan suuntaan etenevät autot pitävät siltaa hallussaan niin kauan kuin autoja riittää eli ei tule niin pitkää väliä, että silta ehtisi tyhjentyä ja suunta voitaisiin muuttaa.
Idea:
Käytetään condition passing -tekniikkaa samaan
suuntaan menevien autojen etuilun estämiseen
monitor Silta{ cond atob, btoa; # odotetaan oman suunnan vuoroa int slkm =0; int ajosuunta = 0; # 0, kun atob; 1, kun btoa procedure enter_atob() { if (sklm > 0 && ajosuunta !=0|| !empty(atob) || slkm =10) # kun silta varattu toiseen suuntaan menijöille tai # omaan suuntaan menijöitä on jo odottamassa tai sillalla on jo 10 autoa # mennään odottamaan, mutta vain kerran (if) { wait(atob); #odotetaan vuoroa ajaa sillalle #kun tästä päästään, niin ajosuunta == oma_suunta ja slkm:ää on jo valmiiksi kasvatettu } else { # auto pääsee suoraan sillalle ilman odottamista if (slkm ==0) ajosuunta = oma_suunta; # ensimmäinen muuttaa suunnan varmuuden vuoksi aina slkm=1; } # pura mahdollista odottajien jonoa if (slkm <10 && !empty (atob)) { slkm++; # varataan paikka jo valmiiksi HUOM! FIFO-järjestys ei aivan toimi ** signal(atob); } aja sillalle; } Vastaavasti procedure enter_btoa()**)
Mutta vapautettu pääsee varmasti sillalle, kun se saa aikanaan monitorin haltuunsa. Koska vapautetulle autolle on jo valmiiksi varattu paikka, niin ohittajia voi olla vain rajallinen määrä. Vaikka kaikki sillalla olleet 10 autoa ehtisivät poistua, niin laskuri slkm menee nollille vasta, kun tämä auto on ylittänyt sillan.
Sillan käytön tehokkuuden kannalta tämä ratkaisu on hyvä, sillä siinä hyödynnetään sitä luppoaikaa, joka kuluu ennenkuin se vapautettu auto saa monitorin haltuunsa ja pääsee itse sillalle.
procedure exit_atob() { if (!empty (atob)) {# oman suunnan odottajia on => suositaan oman suunnan odottajia signal(atob); # HUOM! ei vähennetä slkm-laskuria } else { if (slkm ==1 && !empty (btoa)) {# viimeinen tältä suunnalta ja toisen suunnan odottajia on ajosuunta = 1; signal(btoa); } else slkm --; } } Vastaavasti procedure exit_btoa() ====================================================Entä kun halutaan olla reiluja molemmille suunnille? Tarvitaan vielä joku rajoitus: toisella puolella on paljon odottajia, omia on mennyt tietty määrä ja toisella puolella on odottajia.
Millaisia virheitä:
lapset ajelupyyntö- kuljettaja lähettävät ajelupyynnön, kanava jossa kertovat oman __________ tunnuksensa ja jäävät ---------> | | ---> lukee kanavasta 8 ajelupyyntöä kuuntelemaan omaa kanavaansa |__________| lähettää tiedon näille lapsille, <------------------------ kunkin omaan kanavaan <------------------------ ...... <------------------------- lapset nousevat rekeen ja jää odottamaan lasten tuloa ilmoittavat kuljettajalle ----------------------------> rekeen eli kuuntelee omaa olevansa reessä ( 8 kpl ) kanavaansa kun saanut vastauksen 8 lapselta lähtee liikkeelle ja ajaa kierroksen jäälllä (8 kpl) <---------------------------- ilmoittaa reessä oleville lapsille, että kierros on päättynyt (omaan reki-kanavaan) (8 kpl) Lapset kertovat poistuneensa -------------------------------> odottaa, että kaikki ovat poistuneet Tämän jälkeen aloittaa uuden kierroksen.Huom! Lapset voivat ilmoittaa ajelupyynnön myös suoraan kuljettajalle sen omaan kanavaan, mutta palvelukanavan käyttö tekee c)-kohdan toteuttamien helpommaksi.
chan ajelu (int i); # palvelukanava, josta ajelua pyydetään ja ilmoitetaan oma id eli i chan lapset[n](char ); # jokaisella lapsella on oma kanava, jossa odottelee tietoa kyytiin pääsystä chan ajuri (char); chan reki[8] (char); # reessä istuessaan lapset kuuntelevat tätä kanavaa process kuljettaja(){ int i; while (true) { for i=1 until 8 { receive ajelu (lid); send lapset[lid]; } for i=1 step 1 until 8 { receive ajuri(); # tieto, että lapsi istuu reessä } aja kierros järven jäällä; for i = 1 step 1 until 8 { # pura kuorma send reki(); receive ajuri (); } } } process lapsi[i=1 to n] { while (true) { send ajelu(i); # oma tunnus ajelupyyntöön receive lapset[i](”Kyytiin”); # odotellaan lupaa nousta kyytiin nouse rekeen; send ajuri(”Kyydissä”); # ilmoitus kuljettajalle istu reessä; receive reki (”Poistu)”; # ilmoitus kierroksen päättymisestä nouse reestä; send ajuri (”Poistuin”); # ilmoita kuljettajalle poistuneesi tee jotain muuta; syö vaikka makkaraa; } }Huom!
2 kuljettajaprosessia:
chan ajuri[2](); chan lapset[n](kid); # lapsen kanavaan ilmoitetaan kuljettajan tunnus kid chan reki[2] ; # kaksi reki-kanavaa chan vuoro(); # varmistaa, että järjestys säilyyReet voivat lastata lapsia samanaikaisesti, mutta säilyttää ajojärjestyksen: reki 1 ja sitten reki2.
process kuljettaja [j=1 to 2](){ int i; while (true) { for i=1 until 8 { # reet voivat lastata samaan aikaan lapsia receive ajelu (lid); send lapset[lid](j); # kerrotaan kumpi kuljettaja } for i=1 step 1 until 8 { receive ajuri[j](); tieto, että lapsi istuu reessä } if(j=1) { # varmistetaan lähtöjärjestys reki 1 ensin lähde liikkeelle; send vuoro(); # anna 2. reelle lupa lähteä } else { receive vuoro(); # 0dota lähtölupaa lähde liikkeelle; } aja kierros järven jäällä; for i = 1 step 1 until 8 { # pura kuorma send reki[j](); receive ajuri[j] (); } } } process lapsi[i=1 to n] { while (true) { send ajelu(i); # oma tunnus ajelupyyntöön receive[i](kid); #odotellaan lupaa nousta kyytiin nouse rekeen kid; send ajuri(kid); #ilmoitus kuljettajalle istu reessä; receive reki [kid](); #ilmoitus kierroksen päättymisestä nouse reestä; send ajuri[kid] (); #ilmoita kuljettajalle poistuneesi tee jotain muuta; syö vaikka makkaraa; } }Toinen tapa toteuttaa b): (vert. Jonotetaan lupalappuja, joilla pääsee kyytiin. Lupalappuja on aina kerralla 8 tarjolla. Lupalapun saaneet nousevat rekeen.) Nyt ei tarvita tietää mitään identiteettejä.
chan ajelulupa (), ajuri (), reki (); process kuljettaja (){ while (true) { for i=1 step 1 until 8 send ajelulupa(); # 8 ajelulupaa for i=1 step 1 until 8 receive ajuri(); # odota, kunnes8 lasta istuu reessä aja kierros järven jäällä; for i = 1 step 1 until 8 send reki(); # pyydä lapsia poistumaan for i = 1 step 1 until 8 receive ajuri(); # odota, että kaikki kyydissä olleet poistuneet } } process lapsi[i=1 to n] { while (true) { receive ajelulupa(”Kyytiin”); # odotellaan lupaa nousta kyytiin nouse rekeen; send ajuri(”Kyydissä”); # ilmoitus kuljettajalle istu reessä; receive reki (”Poistu)”;# ilmoitus kierroksen päättymisestä nouse reestä; send ajuri (”Poistuin”); # ilmoita kuljettajalle poistuneesi tee jotain muuta; syö vaikka makkaraa; } } Arvostelusta: