Jos huomaat näissä esitetyissä ratkaisuissa omituisuuksia, niin ilmoittele asiasta Liisa Marttiselle. Ratkaisuihin on yritetty ympätä mahdollisimman paljon opetusta ja hyödyllistä tietoa erityisesti niille, jotka valmistautuvat kokeisiin. 581332 Rinnakkaisohjelmistot (2 ov) Erilliskuulustelu 11.6.2004 1.Vastaa lyhyesti seuraaviin kysymyksiin. (15 p) a) Mitä tarkoittaa 'kriittinen vaihe' (critical section)? (2 p) ohjelmakoodi (joukko lauseita), joka on suoritettava ilman muiden prosessien häirintää eli keskinäisesti poissuljettuna. Esim. yhteisten muuttujien päivitys. Arvostelusta: 0-2 p b) Mitä tarkoittaa, että tietty toimenpidesarja on suoritettava 'atomisena' (atomically)? Käytä esimerkkinä toimenpidesarjaa < x = x+1; y = y+1;>. (3 p) Toimenpidesarja suoritetaan muiden prosessien kannalta yhtenä kokonaisuutena niin, että muut prosessit näkevät vain toimenpidensarjan lopputuloksen eikä mitään väluvaiheita. Esimerkissä muut prosessit näkevät ennen toimenpidesarjaa < x = x+1; y = y+1;> x:n ja y:n arvot ja toimenpidesarjan jälkeen sekä x:n että y:n arvot yhdellä suurempina. Eivätkä siis sellaista tilannetta, jossa x on yhtä suurempi, mutta y vielä ennallaan. Arvostelusta: selkeä määrittely: yksi kokonaisuus, jonka välivaiheet eivät näy muille 2 p esimerkin käsittely 1-2 p tietokantatyyppinen vastaus (peruutukset yms) 2 p c) Mitä tarkoittaa "puomisynkronointi" (barrier synchronization)? Miten se eroaa tavallisesta "P/V-synkronoinnista"? (4 p) Synkronoivat prosessit jäävät 'puomille' odottamaan. Jatkamaan päästään vasta, kun kaikki prosessit ovat saavuttaaneet puomin. Tavallisessa P/V-synkronoinnissa perusongelma on luonteeltaan epäsymmetrinen: prosessi B varmistaa ennen suorituksensa jatkamista, että prosessi A on ohittanut tietyn pisteen (mutta prosessin B eteneminen ei vaikuta millään tavalla prosessin A etenemiseen). Puomisynkronoinnissa on oleellista, että kaikki prosessit saavuttavat tarkoitetun "tahdistuspisteen" ennen kuin yksikään saa jatkaa. Arvostelusta: selvitys puomisynkronoinnista 2 p ero P/V-synkronointiin 2 p d) Mihin ns. pankkiirin algoritmia käytetään? Pankkiirin algoritmia käytettään lukkiutumisen ennalta estämiseen. Arvostelusta: 1 p Mikä on pankkiirin algoritmin perusidea? Resurssit niitä pyytäneille annetaan vain, jos pyyntöön suostuminen ei johda lukkiutumiseen pahimmassa mahdollisessa tilanteessa eli vaikka kaikki prosessit tarvitsisivat ilmoittamansa maksimimäärät resursseja, niin silti kaikki prosessit pystyvät saattamaan suorituksensa loppuun. Arvostelusta: 2 p Mitä tapahtuu asiakkaalle, jos pankkiiri ei suostu asiakkaan pyyntöön? Asiakas jää odottamaan ja aikanaan saa tarvitsemansa resurssit. Arvostelusta: 1 p Mitä tapahtuu, jos resurssimanageri antaa resurssiyksikön, vaikka pankkiirin algoritmin mukaan ei pitäisi? (6 p) Voi tulla lukkiutuminen, mutta ei mitenkään välttämättä. Algoritmi varautuuu pahimpaan tilanteeseen (= kaikki prosessit pyytävät yhtäaikaa ilmoittamansa maksimimäärän), mutta näin ei välttämättä tapahdu; joskus jopa hyvin harvinainen tilanne. Arvostelu: 1 p => seuraa lukkiutuminen 2 p => voi seurata lukkiutuminen, mutta ei välttämättä 2. Monitori toimivaksi (20 p) a) Alla oleva monitorin koodi ei joka tilanteessa toimi oikein. Selvitä, mitä ongelmia ohjelmassa on. (8 p) monitor Vastaanotto { cond sisään; cond ulos; cond tutki; boolean varattu = false; procedure Tulevastaanotolle ( ) { # potilaan koodi if (varattu) wait(sisään); # odota sisäänkutsua varattu = true; # merkitse varatuksi mene tutkimushuoneeseen signal(tutki); # ilmoita lääkärille ole tutkittavana wait(ulos); # jää odottamaan poistumismerkkiä poistu tutkimushuoneesta } procedure Tutkipotilas ( ) { # lääkärin koodi signal(sisään); # kutsu potilas sisään wait(tutki); # odotetaan potilasta tutki potilas signal(ulos); # anna poistumissignaali varattu =false; # vapauta tutkimushuone } } process Potilas( )[i = 1 to n] { while (true) { tee mitä ikinä teet tuntuu sairaalta call Vastaanotto.Tulevastaanotolle ( ); } } process Lääkäri( ) { while (true) call Vastaanotto.Tutkipotilas( ); } Tutki esimerkiksi, mitä tapahtuu, kun potilaat ja lääkäri pääsevät monitoriin eri järjestyksessä: i) potilas1, lääkäri, potilas2; - lääkäri ei ole välttämättä vielä paikalla kun potilas1 ilmoittautuu (signal(tutki)) ja lääkäri jää odottamaan tutkittavaa potilasta (wait(tutki)) ja potilas1 odottelee tutkimuksen valmistumista (wait(ulos)). Potilas2 saapuu ja jää odottamaan sisäänkutsua (wait(sisään)) (samoin myöhemmin mahdollisesti saapuvat muut potilaat). => lukkiutuminen. ii) potilas1, potilas2, lääkäri; - potilas1 menee tutkimushuoneeseen, potilas2 jää odottamaan lääkärin kutsua, lääkäri saapuu ja kutsuu odottavan potilas2:n sisään, joka puolestaan herättää lääkärin tekemään tutkimusta. Nyt tutkimushuoneessa on kaksi potilasta. => poissulkeminen ei toimi iii) lääkäri, potilas1, potilas2; - lääkäri tulee ja jää odottamaan potilasta, potilas1 tulee tutkimushuoneeseen ja ilmoittautuu lääkärille, potilas2 tulee ja jää odottamaan kutsua sisään. Lääkäri tutkii potilaan1 ja ilmoittaa tutkimuksen loppumisesta sekä vapauttaa tutkimushuoneen. Nyt joku juuri tullut potilas3 voi päästä sisään, vaikka potilas 1 ei olisi vielä ehtinyt poistua. Nyt jos lääkäri ehtii vielä pyytää potilas2:n sisään ennenkuin potilas1 todella poistuu, niin tutkimushuoneessa voi olla kolmekin potilasta ja potilas3 pääsee etuilemaan(lääkäri, potilas1, potilas2, potilas3, lääkäri, potilas2, potilas1,..) - Jos potilas2 saapuu vasta, kun lääkäri on jo tutkinut potilaan1 ja poistunut monitorista, niin tällöin seuraa kohdan i) kaltainen lukkiutumistilanne (= potilas2, lääkäri, ..) b) Miten koodi tulisi kirjoittaa, jotta ongelmia ei olisi? Voit korjata tehtävän koodia tai kirjoittaa ihan oman oikein toimivan Vastaanotto-monitorin ja sitä käyttävät prosessit lääkärille ja potilaille. (8 p) Ratkaistaan tehtävä vähitellen tarkentaen: mitä odotettava => mitä jonoja tarvitaan potilas: pääsyä tutkimushuoneeseen ja pääsyä tutkimushuoneesta pois => jonot cond sisään, ulos; lääkäri: potilasta paikalle => cond tutki; Jos signal (jono) annetaan ennenkuin on kukaan jonottamassa jono:ssa, niin lupa menee hukkaan, ja helposti voi syntyä lukkiutumistilanne, jossa kumpikin odottaa etenemislupaa toiselta. Tilanteissa, joissa näin voi käydä tarvitaan (boolean) muuttuja, johon talletetaan tieto siitä, että lupa on jo annettu eikä tarvitse turhaan mennä jonoon odottamaan. Potilas voi tulla ensin ja signalloida tutkimusluvan (signal tutki), vaikka lääkäri ei olekaan vielä paikalla => lääkäri jää odottamaan jo paikalle tullutta potilasta (wait (tutki)) => boolean onpotilas = false; Lääkäri voi olla ensin paikalla ja kutsua tyhjästä jonosta potilaaan sisään (signal(sisään)) ja sitten jäädä odottamaan tutkimuslupaa (wait(tutki)). Annetussa monitoriratkaisussa tämä ei ollut ongelma, sillä tutkimushuoneen ollessa vapaa seuraava potilas voi suoraan marssia sisään. Signaali signal(sisään) menee 'harakoille', mutta siitä ei ole mitään haittaa. Jos toimintajärjestys on kiinnitetty: wait(jono), signal(jono), ei ole mitään ongelmia. Esim. Ratkaisussa potilas menee ensin odottamaan ulospääsyä (wait(ulos) ja lääkäri antaa luvan aina myöhemmin. Jos ratkaisua muutetaan siten, että potilas poistuisi monitorista tutkimuksen ajaksi (kävisi esim. antamassa verinäytteen), niin toimintajärjestys (=monitoriin pääsy) ei olisikaan enää kiinnitetty, vaan lääkäri voisi antaa poistumisluvan ennenkuin potilas sitä odottaa. Potilaan toiminta: jos tutkimushuone varattu, niin jää odottamaan sisäänpääsyä (wait(sisään)) mene tutkimushuoneeseen ja lukitse se (varattu = true); jos lääkäri jo odottamassa, niin ilmoita lääkärille olevasi valmis tutkimuksiin (signal(tutki)), muuten jätä merkki paikallaolostasi (onpotilas = true); odota poispääsyilmoitusta (wait(ulos)); poistu tutkimushuoneesta ja vapauta se (varattu = false) Lääkärin toiminta: jos huoneessa ei ole odottavaa potilasta, niin { jos jonottavia potilaita, päästä sisään (signal(sisään)); wait(tutki); # odota joko jonottanutta tai suoraan tulevaa potilasta } tutki potilas ilmoita tutkimuksen päättymistä (signal(ulos)) Huom! Tämä ratkaisu sallii etuilun eli uusi potilas voi päästä suoraan tutkimushuoneeseen, vaikka aikaisemmin tulleita potilaita olisikin jo jonossa. Jonosta vapautettu potilas ja uudet potilaat kilpailevat monitoriin pääsystä. Jotta jonosta vapautettu pääsee sisälle vain jos tutkimushuone on vapaa, on 'if'-lauseen tilalla käytettävä 'while'-silmukkaa. monitor Vastaanotto { cond sisään; cond ulos; cond tutki; boolean varattu = false, onpotilas = false; procedure Tulevastaanotolle ( ) { # potilaan koodi while(varattu) wait(sisään); # odota sisäänkutsua (while välttämätön) varattu = true; # merkitse varatuksi mene tutkimushuoneeseen if (!empty(tutki)) signal(tutki) # ilmoita paikalla olevalle lääkärille else onpotilas=true; # merkki myöhemmin tulevalle lääkärille ole tutkittavana wait(ulos); # jää odottamaan poistumismerkkiä poistu tutkimushuoneesta varattu = false; # vapauta tutkimushuone, kun potilas on todella poistunut } procedure Tutkipotilas ( ) { # lääkärin koodi if (!onpotilas) { if (!empty(sisään)) signal(sisään); # kutsu potilas sisään wait(tutki); # odotetaan potilasta jonottanutta tai suoraan tulevaa } tutki potilas signal(ulos); # anna poistumissignaali } } c) Täydennä ohjelmaasi siten, että ns. condition passing -menetelmällä varmistat potilaiden pääsyn tutkimukseen saapumisjärjestyksessä. (Tämä voi sisältyä jo b)-kohdan vastaukseen.) (4p) Jos nyt halutaan varmistaa, että potilaat käsitellään saapumisjärjestyksessä, niin käytetään 'condition passing '-menetelmää: Kun jonossa on potilaita, pidetään tutkimushuone varattuna, jotta uudet potilaat eivät ryntäisi sisään ja päästetään jonottavat suoraan tutkimushuoneeseen Eli poistuva potilas vapauttaa tutkimushuoneen vain, jos ei ole kukaan jonottamassa. Muuten hän päästää seuraavan jonottavan potilaan sisään. Lääkäri ei enää kutsu potilaita sisään. Ensimmäinen potilas tulee suoraan tutkimushuoneeseen ja poistuva potilas kutsuu paikalle seuraavan odottavan tai avaa tutkimushuoneen uudelle tulijalle. Jos halutaan lääkärin huolehtivan potilaiden kutsumisesta, niin poistuvan potilaan tulee ilmoittaa lääkärille, milloin saa kutsua (cond uusipotilas, wait(uusipotilas), signal (uusipotilas)) Huom! Nyt käytettävä sisäänpääsyehdon testaamisessa if-lausetta, jotta jonottava pääsee sisään, vaikka tutkimushuone näyttää varatulta. monitor Vastaanotto { cond sisään; cond ulos; cond tutki; boolean varattu = false, onpotilas = false; procedure Tulevastaanotolle ( ) { # potilaan koodi if (varattu) wait(sisään) # odota sisäänkutsua (if välttämätön) else varattu = true; # merkitsee varatuksi vain jos tulee suoraan tyhjään # tutkimushuoneeseen; jonosta tulleille jo valmiiksi varattuna mene tutkimushuoneeseen if (!empty(tutki) signal(tutki) # ilmoita paikalla olevalle lääkärille else onpotilas=true; # jätä merkki myöhemmin tulevalle lääkärille ole tutkittavana wait(ulos); # jää odottamaan poistumismerkkiä poistu tutkimushuoneesta if (empty(sisään)) varattu = false # jos ei ole jonottajia, niin vapauta tutkimushuone else signal (sisään); # päästä seuraava jonottaja sisään, muille huone suljettu } procedure Tutkipotilas ( ) { # lääkärin koodi if (!onpotilas) wait(tutki); # odotetaan potilasta jonottanutta tai suoraan tulevaa } tutki potilas signal(ulos); # anna poistumissignaali } } process Potilas( )[i = 1 to n] { while (true) { tee mitä ikinä teet tuntuu sairaalta call Vastaanotto.Tulevastaanotolle ( ); } } process Lääkäri( ) { while (true) call Vastaanotto.Tutkipotilas( ); } ====================================================================== Ratkaisu, jossa pakotetaan toiminta tiettyyn järjestykseen: potilas menee aina jonoon ja ilmoittaa tulostaan mahdollisesti jo odottavalle lääkärille lääkäri kutsuu potilaat sisään jonosta saapumisjärjestyksessä ja jos ei ole jonottajia, niin lääkäri odottaa ilmoitusta jonosta. monitor Vastaanotto { cond sisään; cond ulos; cond tutki; cond jono; procedure Tulevastaanotolle ( ) { # potilaan koodi if (!empty(jono) signal(jono); # ilmoita tulostasi, jos lääkäri on odottelemassa ('tauolla') wait (sisään); # mene jonoon odottamaan lääkäriä mene tutkimushuoneeseen; signal(tutki); # ilmoita paikalla olevalle lääkärille ole tutkittavana; wait(ulos); # jää odottamaan poistumismerkkiä poistu tutkimushuoneesta ; } procedure Tutkipotilas ( ) { # lääkärin koodi if (empty(sisään)) wait (jono); signal(sisään); # kutsu potilas sisään wait(tutki); # odotetaan seuraavan jonossa olleen potilaan tulevan tutkimushuoneeseen tutki potilas signal(ulos); # anna poistumissignaali } Voidaan toteuttaa myös käyttäen jonomuuttujaa. ================================================================= Ratkaisuissa tutkimushuoneeseen meno ja sieltä poistuminen sekä itse tutkimus ovat monitorin sisällä, vaikka monitorin sisällä tulee olla aivan välttämättömän ajan. Tässä tehtävässä siitä ei tosin ole paljoakaan haittaa, koska varsinainen homma etenee vain sen yhden lääkärin tahdissa ja potilaan on ensin tultava paikalle, hänet on tutkittava ja potilaan on poistuttava ennenkuin seuraava potilas voi tulla. Kuitenkin monitorin varattuna pitäminen voi aiheuttaa jonoa monitoriin ja vapautuneen lääkärin on o dotettava monitoriin jonottavien potilaiden jonoon menoa ennenkuin se puolestaan pääsee monitoriin ja voi ruveta täyttämään tutkimaan seuraavaa potilasta. Tähän auttaa potilaan ja lääkärin monitori-proseduurien jakaminen pienemmiksi osiksi. Arvostelusta: hyvin pahat mokat: busy wait monitorissa -3 pahat mokat: lukkiutuminen tai poissulkemisen pettäminen kokonaan -2 pienemmät mokat = -1 p poissulkemisen pettäminen vain poikkeustilanteessa lääkäri vapauttaa tutkimushuoneen, vaikka edellinen potilas ei ole vielä poistunut ikuinen silmukka while(true) while -loopin tilalla epämääräinen odotustila ilman sopivaa cond-muuttujaa muuttujia ei päivitetä oikein . hyvin pienet kömmähdykset -1/2 Vinkkejä monitorin käyttöön: jos uudet tulijat ja monitorin jonossa odottavat kilpailevat monitoriin pääsystä, niin pääsyehdossa pitää olla while: while (varattu) wait (sisään); if (varattu) wait(sisään) => koska !varattu, niin uusi tulija ei jää odottamaan sisään-jonoon, vaan merkkaa varatuksi (varattu = true) ja menee suoraan odotushuoneeseen. Signal(sisään) herättää sisään-jonosta yhden odottavan, joka samoin merkkaa varatuksi ja marssii eteenpäin. Ja näin tutkimushuoneeseen pääsee kaksi potilasta (tai mitä tahansa prosessia). While-silmukka pakottaa myös jonosta vapautetun prosessin tutkimaan uudelleen muuttujan varattu tilaa, jolloin se huomaa, että tila onkin jo varattu ja sen on mentävä takaisin odottamaan sisään-jonoon. Condition passing -tekniikkaa käytettäessä pääsyehdossa pitää olla if: if (varattu) wait (sisään); Nyt ehdon tulee pysäyttää vain uudet tulijat. Ja jonossa olleet pääsevät sisään vuorotellen tulojärjestyksessä, koska eivät enää tarkista ehtoa. Condition passing -tekniikan idea on siinä, että niin kauan kun jonossa on odottajia, niin poistunut ilmoittaa seuraavalle jonottajalle eli päästää sen sisään, ja estää uusien pääsyn pitämällä estoehdon voimassa (varattu = true). Monitorissa voi helposti syntyä lukkiutumistilanteita: pelkkä signal ei riitä ilmoittamaan, että jokin tapahtuma on tapahtunut, koska se menee täysin hukkaan, jos kukaan ei ole sitä odottamassa (kuin huuto, joka kyllä herättää odottavan, mutta ei tavoita myöhemmin tullutta). Jotta prosessit eivät turhaan jäisi odottamaan jo tapahtunutta (esim. potilas jo paikalla ennen lääkäriä o dottelemassa että lääkäri alkaa tutkia ja myöhemmin tullut lääkäri ei tätä tiedä, vaan odottelee potilasta tulevaksi tai päinvastoin myöhemmin tullut potilas ei kuullut lääkärin kutsua ja taas kumpikin odottaa), niin tapahtuneesta pitää jättää 'merkki' eli asettaa jonkin muuttujan arvo (lääkäri jättää oven auki tai potilaskortti on lääkärin pöydällä kertomassa, ettei enää tarvitse odotella ilmoitusta.) Jos monitorin sisällä on while-silmukka, jossa prosessi testaa ehtoa, joka ei ole voimassa ja jonka joku muu prosessi asettaa, niin se toinen prosessi ei millään pääse muuttamaan ehtoa, jos testaava prosessi pitää koko ajan monitorin hallussaan: while (ei_lääkäriä) signal(potilas_odottaa); Etuilu voidaan estää pakottamalla kaikki palvelua haluavat ensin jonoon ja sieltä jonotusjärjestyksessä saamaan palvelua. Tässäkin on varottava lukkiutumista, jos kohtaavien prosessien tulojärjestys voi vaihdella. Potilas lääkäri ....... ...... wait(sisään); signal (sisään) ...... ....... signal(tutki) wait(tutki) ........... ....... Toivottu järjestys on: wait(sisään), signal(sisään), wait(tutki), signal(tutki). Mutta järjestys voi olla: signal(sisään), wait(tutki), wait(sisään), => lukkiutuminen 3. Yksisuuntainen silta (15 p) Kahden kylän A ja B välissä olevan joen yli kulkee niin kapea silta, että autot voivat ajaa sitä pitkin vain yhteen suuntaan kerrallaan. Kun sillalla kulkee autoja A:sta B:hen, niin B:stä A:han haluavien täytyy odottaa. Silta ei myöskään ole kovin vankka, joten sillalla saa olla korkeintaan 10 autoa yhdellä kertaa. Jotta varmistetaan, että autot menevät sillalle vain kulloinkin sallitusta suunnasta, siltaa käyttävät autoprosessit kutsuvat proseduuria ajasillalle(suunta) pyrkiessään sillalle ja sillalta poistuessaan proseduuria poistusillalta(suunta). Process auto[i = 1 to N] { ..... ajasillalle(suunta); ylitä silta poistusillalta(suunta); ...... } Tee semaforeja ja P - ja V-operaatioita käyttävät koodit proseduureille ajasillalle(suunta) ja poistusillalta(suunta). Ratkaisun ei tarvitse olla reilu, vaan autojen odotusajat saavat olla pitkiä. Kuitenkin samalta suunnalta tulevien autojen tulee päästä sillalle saapumisjärjestyksessä. Samanlainen ongelma oli käsitelty kurssin harjoituksisissa, tosin kyseessä oli tunneli eikä silta . Ja lisäksi koetehtävässä rajoitettiin myös sillalla olevien autojen lukumäärää. Muistin virkistämiseksi ensin harjoitustehtävän ratkaisu: ------------------------------------------------------------------------- Rinnakkaisohjelmistot, K2004 Harjoitus 4 tehtävä 2 / Averell ------------------------------------------------------------------------- ------------------ Pohjoinen Etelä ------------------ sem mutexA = 1, # poissulkeminen: laskuri lkmA mutexB = 1, # poissulkeminen: laskuri lkmB saa_ajaa = 1; # auto saa ajaa sillalle int lkmA = 0, # sillalla A:han etenevien lkm lkmB = 0; # sillalla B:hen etenevien lkm procedure ajasillalle(someType suunta) { switch (suunta) { case Aahan: { P(mutexA) # muut etelään ajavat odottavat tässä lkmA++; if (lkmA==1) # eka auto tsekkaa onko tunneli vapaa P(saa_ajaa); # jos ei odota tässä semaforissa V(mutexE); } case Beehen: { # vastaavasti P(mutexB); lkmB++; if (lkmB==1) P(saa_ajaa); P(mahtuu) V(mutexB); } } P(mahtuu); } procedure poistusillalta(someType suunta) { V(mahtuu); if (suunta==Aahan) { P(mutexA); lkmA--; if (lkmA==0) # viimeinen poistuja V(saa_ajaa); # vapauta toisen pään odottajan V(mutexA); } else { P(mutexB); lkmB--; if (lkmB==0) V(saa_ajaa); V(mutexB); } } Huomaa samankaltaisuus readers/writers - ongelman kanssa: vuoro vaihtuu luokalta toiselle. Ratkaisun voisi perustaa Andrewsin kuvan 4.13 algoritmiin. Tämä ratkaisu on yksinkertaisempi, koska 1) luokat ovat samanlaisia ja 2) eivät koske toistensa laskureihin: auto voi rauhassa jäädä odottamaan kriittisen alueen sisään. Toinen luokka voi samaanaikaan toimia vapaasti ja sieltä tulee aikanaan tarvittava V-operaatio. ======================================================================= Kyseessä on siis yksinkertaisempi versio lukijat ja kirjoittajat -ongelmasta (vastaa kurssin tytöt ja pojat suihkussa -tehtävää). Yhteinen resurssi (silta) ja kaksi luokkaa käyttäjiä (kylään A ajavat ja kylään B ajavat). Eri luokkien prosessit eivät saa samaan aikaan käyttää yhteistä resurssia, mutta saman luokan prosessit kyllä. Lisärajoituksena on, että korkeintaan 10 saman luokan prosessia voi samanaikaisesti käyttää resurssia (sillan kantavuus 10 autoa kerralla). Tässä ensin esitetty luokan A edustajan toimintaa kuvaavaprosessi: ----------------------------------------------------------------------------------- Process luokkaA[i=1 to M] { while (true) { # sillalle tultaessa # varmistetaan, ettei sillalla ole toiseen suuntaan ajajia P(mutex) # yhteisten muuttujien päivitystä ja tutkimista varten if (lkmB > 0) { # jos on toiseen suuntaan ajavia odottajiaA ++; # lisätään uusi odottaja tähän suuntaan V(mutex); # päästetään muut päivittämään yhteisiä muuttujia P(Aahan); # jäädään odottamaan tähän suuntaan ajavien vuoroa } lkmA ++; # paton passing: vapautetaan seuraava samaan suuntaan odottava ja vasta, jos ei ole yhtään # samaan suuntaan odottajaa, niin avataan mutex-semafori. if (odottajiaA >0) { odottajiaA --; V(Aahan) } else V(mutex) P(kestää); # jos sillalla jo 10 autoa, niin jää odottamaan aja sillalle; # sillalta poistuttaessa V(kestää); # sillalle mahtuu taas yksi lisää P(mutex); lkmA -- ; if (lkmA = = 0 and odottajiaB >0) { # on viimeinen tähän suuntaaa menijä ja # toiseen suuntaan on odottajia odottajiaB -- ; # päästetään toisen suunnan odottaja V(Behen); # etenemään sillalle }else V(mutex); # muuten päästetään seuraava tulija Toisen luokan prosessi luokkaB ihan vastaavasti: vain aina A:n tilalle B ja B:n tilalle A. Koska haluttiin proseduurit ajasillalle(suunta) ja poistusillalta (suunta) prosessien toiminnot on vain ryhmiteltävä eri tavalla => yleinen ratkaisu: procedure ajasillalle(suunta){ if (suunta = = A){ P(mutex) # yhteisten muuttujien päivitystä ja tutkimista varten if (lkmB > 0) { # jos on toiseen suuntaan ajavia odottajiaA ++; # lisätään uusi odottaja tähän suuntaan V(mutex); # päästetään muut päivittämään yhteisiä muuttujia P(Aahan); # jäädään odottamaan tähän suuntaan ajavien vuoroa } lkmA ++; if (odottajiaA >0) { odottajiaA --; V(Aahan) } else V(mutex) P(kestää); # jos sillalla jo 10 autoa, niin jää odottamaan } else { # nyt suunta on B P(mutex) # yhteisten muuttujien päivitystä ja tutkimista varten if (lkmA > 0) { # jos on toiseen suuntaan ajavia odottajiaB ++; # lisätään uusi odottaja tähän suuntaan V(mutex); # päästetään muut päivittämään yhteisiä muuttujia P(Behen); # jäädään odottamaan tähän suuntaan ajavien vuoroa } lkmB ++; if (odottajiaB >0) { odottajiaB --; V(Behen) } else V(mutex) P(kestää); # jos sillalla jo 10 autoa, niin jää odottamaan } } procedure poistusillalta (suunta) { if (suunta = = A) { V(kestää); # sillalle mahtuu taas yksi lisää P(mutex); lkmA -- ; if (lkmA = = 0 and odottajiaB > 0) { odottajiaB -- ; # päästetään toisen suunnan odottaja V(Behen); # etenemään sillalle } else V(mutex); # muuten päästetään seuraava tulija } else { # nyt suunta on B V(kestää); # sillalle mahtuu taas yksi lisää P(mutex); lkmB -- ; if (lkmB = = 0 and odottajiaA > 0) { odottajiaA -- ; # päästetään toisen suunnan odottaja V(Aahan); # etenemään sillalle } else V(mutex); # muuten päästetään seuraava tulija } } Tätä yleistä ratkaisua voi vielä yksinkertaistaa: Riittää, että vain ensimmäinen suuntaan A ja suuntaan B ajava auto tarkistaa, voiko sillalle mennä vai onko se jo varattu toiseen suuntaan menijöille. Jos silta on varattu, ensimmäinen auto jää odottamaan sillan vapautumista. P(mutexsuunta) ; 1. auto pääsee tästä heti läpi, mutta muut odottavat vuoroaan lkmsuunta ++; if (lkmsuunta = = 1) P(etene); # 1 auto varaa ajosuunnan V(mutexsuunta); Jos ensimmäinen auto joutuu odottamaan, se pitää sen suunnan mutex-muuttujan varattuna, joten muutkin samaan suuntaan haluavat autot joutuvat odottamaan. Kun ensimmäinen auto pääsee etenemään, se vapauttaa suunnan mutexin ja muut samaan suuntaan haluavat autot pääsevät etenemään saapumisjärjestyksessä sillalle. Semafori huolehtii järjestyksen säilymisestä ja päästää etenemään siinä järjestyksessä, kun prosessit ovat suorittaneet P(mutex)-operaation. Myös poistuvat pääsevät vuorollaan suorittamaan omia päivityksiään. Viimeinen sillalta poistuva, kumpaan tahansa suuntaan ajava auto taas vapauttaa sillan seuraavaksi sillalle tulevalle, tulee tämä sitten kummasta suunnasta tahansa. P(mutexsuunta); lkmsuunta --; if (lkmsuunta = = 0) V(etene); V(mutexsuunta) Koska sillalla saa olla korkeintaaan 10 autoa kerrallaan, tarvitaan 'laskuri'mutex, joka päästää sillalle korkeintaan 10 autoa (sem mahtuu = 10;) Tässä yksinkertaistettu ratkaisu: -------------------------------------- sem mutexA = 1, mutexB = 1, silta = 1; sem mahtuu = 10; int lkmA = 0, lkmB = 0; procedure ajasillalle(suunta) { if (suunta = = 'aahan') { P(mutexA); lkmA ++; if (lkmA = = 1) P(silta); # ensimmäinen jää tarvittaessa odottamaan eikä päästä muitakaan # samaan suuntaan haluavia etenemään pitämällä mutexA:n kiinni V(mutexA); # vasta kun suunta on vapaa, pääsee seuraava auto etenemään } else { # suunta siis 'beehen' ja ihan samalla tavalla, vain A:n tilalla B! P(mutexB); lkmB ++; if (lkmB = = 1) P(silta); # ensimmäinen jää tarvittaessa odottamaan eikä päästä muitakaan # samaan suuntaan haluavia etenemään pitämällä mutexA:n kiinni V(mutexB); # vasta kun suunta on vapaa, pääsee seuraava auto etenemään } P(mahtuu); # tästä sillalle pääsee korkeintaan kymmenen ja muut jäävät odottamaan vuoroaan } procedure poistusillalta (suunta) { V(mahtuu); # taas mahtuu yksi lisää if (suunta = = 'aahan') { P(mutexA); lkmA --; if (lkmA = = 0) V(silta); # viimeinen suuntaan A menevä vapauttaa sillan V(mutexA); # ja jokainen poistuva A-suunnan mutexin } else { # suunta siis 'beehen' ja ihan samalla tavalla, vain A:n tilalla B! P(mutexB); lkmB --; if (lkmB = = 0) V(silta); V(mutexB); } Arvostelusta: pyydettiin laatimaan proseduurit; ei prosesseja semaforit ja niiden käyttö määrittely ja alkuarvon asetus: sem semafori = 1; 2 p P- ja V-operaatiot ja niiden merkitys: 2 p semaforin käyttö poissulkemisesssa: 3 p semaforin arvoa ei voi kysyä -2 p semafori pitää käyttäjät jonossa 1 p semafori sallii usean käyttäjän samanaikaisen käytön: sem mahtuu = 10; ratkaisun oikea toiminnallisuus poissulkeminen toimii sillalle pääsee eri suuntiin kulkevia autoja samanaikaisesti lukkiutumista -2 vain yksi auto kerrallaan pääsee sillalle -2 jonoon joutunut ei jää odottamaan vuoroaan vaan ajaa silllalle -2 jonottajat jäävät uusien jalkoihin -2 kaikki autot jumittuvat alussa odottelemaan (väärät alkuarvot) -2 autot pääsevät joskus sillalle toiminnan logiikka viimeistely ja tehokkuus ja toteutus kaksi proseduuria, joissa toiminnot kahden suunnan mukaan toinen suunta jätetty käsittelemättä huolimattomuusvirheet: käytetyt semaforit oikein määritelty P- ja V-operaatiot oikeassa järjestyksessä laskurien oikea päivittäminen ja määrittelyt käytetään monitorin cond-muuttujia sekä signal- ja wait-operaatioita -2 kaikki määrittelyt ja alkuarvot puuttuvat -2 -3 4. Pankkitilin yhteiskäyttö (10 p) Pankkitili on usean henkilön käytössä, joista jokainen voi tallettaa tilille tai nostaa tililtä rahaa. Tili ei saa koskaan mennä negatiiviseksi. Koodaa palvelin, joka huolehtii tilin käytöstä. Asiakkaat voivat pyytää joko jonkun rahasumman talletusta tai rahasumman nostoa. Jos tilillä ei ole tarpeeksi rahaa, niin pyyntöä viivytetään. Asiakkaat ja palvelin käyttävät sanomanvälitystä kommunikointiin. Yksi kanava, jolla kaikki lähettävät otto- tai panopyyntönsä. Jokaisella asiakkaalla oma kanava, johon palvelin lähettää vastauksen. Jos saldoa ei ole riittävästi, otto-pyyntö pannaan jonoon odottamaan. Kun saldo kasvaa, niin tutkitaan, voidaanko jonossa oleviin pyyntöihin suostua FIFO-järjestyksessä. Jos pyyntö ei mahdu jonoon tästä ilmoitetaan asiakkaalle, joka lähettää myöhemmin uuden pyynnön. chan request (int asiakastunnus, int summa, int tyyppi); chan reply[n] (types of results); process Serveri { int asiakastunnus; # numero, jonka mukaisesti osataan lähettää asiakkaalle vastaus int summa; # asiakkaan pyytämä tai tallettama summa int tyyppi; # tapahtuman tyyppi: otto = 1, pano = 0 int saldo = 0; # tilin saldo int n, eka=0, vika = n-1, # jonopuskurin koko, ensimmäinen jonottaja, seuraava vapaa lkm = 0; # jonottavien lukumäärä type jono[n, 2]; jono, jossa odottavat otot : maara ja tunnus process Palvelin { while (true) { receive request (int asiakastunnus, int summa, int tyyppi); if (tyyppi = = 0) { # pano saldo = saldo + summa; # kasvata saldoa send reply[asiakastunnus] ('OK'); # lähetä asiakkaalle vastaus # tarkista voidaanko jonossa oleva pyyntö käsitellä while (saldo > jonossa [eka].summa) {# vanhin odottava pyyntö saldo = saldo - jonossa [eka].maara; send reply[jonossa [eka].tunnus] ('OK'); # lähetä asiakkaalle vastaus eka = (eka + 1)/n; # päivitä jono lkm --; } else { # otto if (saldo > summa AND lkm = = 0) { # saldoa riittävästi eikä kukaan ole saldo = saldo -summa; # vähennetään send reply[asiakastunnus] ('OK'); # lähetä asiakkaalle 'OK'-vastaus } else { # vie pyyntö jonoon odottamaan if (lkm < n) vika = (vika + 1) / n; { jono[vika].tunnus = asiakastunnus; jono[vika].summa = summa; lkm ++; } # asiakkaan pyyntö on jonossa ja oletetaan, että se pystytään melko nopeasti # täyttämään ja silloin vasta ilmoitetaan; tässä voisi kyllä antaa väliaikaisen # ilmoituksen tilanteesta else # pyyntö ei mahdu edes jonoon send reply[asiakastunnus] ('ongelmia'); # asiakkaan tulee lähettää pyyntö uudelleen } # end of otto } end of while }end of Palvelin Arvostelusta: kommunikointi sanomia lähettämällä 6 p kanavien määrittely send receive kanavien käyttö ja järkevä toiminta 4 p tässä riitti, että toiminta oli tehtävässä vaadittua, ei edellytetty esim. jonon päivitystä tms. Vinkki: Vaikka sanomanvälitys käsitellään vasta kurssin loppupuolella, se kannattaa opetella. Sanomavälitys on kohtalaisen helppo asia ja sitä yleensä kysytäään kokeessa.