581332 Rinnakkaisohjelmistot (2 ov) Erilliskuulustelu 11.6.2004 1.Vastaa lyhyesti seuraaviin kysymyksiin. (15 p) a) Mitä tarkoittaa 'kriittinen vaihe' (critical section)? (2 p) b) Mitä tarkoittaa, että tietty toimenpidesarja on suoritettava 'atomisena' (atomically)? Käytä esimerkkinä toimenpidesarjaa < x = x+1; y = y+1;>. (3 p) c) Mitä tarkoittaa "puomisynkronointi" (barrier synchronization)? Miten se eroaa tavallisesta "P/V-synkronoinnista"? (4 p) d) Mihin ns. pankkiirin algoritmia käytetään? Mikä on pankkiirin algoritmin perusidea? Mitä tapahtuu asiakkaalle, jos pankkiiri ei suostu asiakkaan pyyntöön? Mitä tapahtuu, jos resurssimanageri antaa resurssiyksikön, vaikka pankkiirin algoritmin mukaan ei pitäisi? (6 p) 2. Monitori toimivaksi (20 p) a) Alla oleva monitorin koodi ei joka tilanteessa toimi oikein. Selvitä, mitä ongelmia ohjelmassa on. Tutki esimerkiksi, mitä tapahtuu, kun potilaat ja lääkäri pääsevät monitoriin eri järjestyksessä: i) potilas1, lääkäri, potilas2; ii) potilas1, potilas2, lääkäri; iii) lääkäri, potilas1, potilas2; (8 p) 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) 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.) (4 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 } } käännä 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( ); } 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ä. 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. 581332 Concurrent Systems (2 cu) Separate Examination 11.6.2004 Please write on each paper the date and the name of the course as well as your name and signature. 1. Give a short answer to each of the following questions: (15 p) a) What is a "critical section"? (2 p) b) What does it mean that a sequence of actions must be executed "atomically"? Use the sequence < x = x+1; y = y+1; > as an example. (3 p) c) What is "barrier synchronization"? How does it differ from the customary "P/V-synchronization"? (4 p) d) For what is the Banker's algorithm used? Explain the basic ideas of the algorithm. What happens to the requesting process, if the algorithm shows that the request can not be granted? What would happen, if the resource is granted, although according to the Banker's algorithm the request should be rejected? (6 p) 2. Correctly working mónitor (20 p) a) The monitor code given below is not always working correctly. Explain what all problems the code includes. For example check out what happens when the doctor and patients get the monitor in different order: i) patient1, doctor, patient2; ii) patient1, patient2, doctor; iii) doctor, patient1, patient2; (8 p) b) How should the code written so that there will not any problems? You can try to fix the given code or write a new code of your own for the monitor Reception and for the doctor and patient processes. (8 p) c) Use condition passing technique to make sure that the patients can go to the doctor in the order they have arrived. (4 p) (This can already be included in the b)-part answer.) monitor Reception { cond in; cond out; cond check; boolean reserved = false; procedure Cometoreception( ) { # code for a patient if (reserved) wait(in); # wait to get in reserved = true; # mark reception room reserved go to the reception room signal(check); # tell the doctor examination by the doctor wait(out); # wait until allowed to leave leave the reception room } procedure Examinepatient ( ) { # code for the doctor signal(in); # call a patient in wait(check); # wait for a patient to arrive o examine a patient signal(out); # allow a patient to leave reserved =false; # mark reception room empty } Please turn over } process Patient( )[i = 1 to n] { while (true) do what ever you do feel sick call Reception.Cometoreception( ); } } process Doctor( ) { while (true) call Reception.Examinepatient( ); } 3. One-lane bridge (15p) There runs a river between two villages A and B and the villages are connected by a narrow one-lane bridge, where cars are allowed to drive only in one direction in a time. When cars are passing the brigde from A to B, then the cars willing to cross the bridge from B to A have to wait. The bridge is noy very sturdy, so maximum amount of 10 cars are allowed on the bridge at a time. The car processes call procedure enter_bridge(direction) before using the bridge, and procedure exit_bridge(direction), when thy leave the bridge. Process cari = 1 to N] { ..... enter_bridge(direction); drive over the bridge exit_bridge(direction); ...... } Give the code for procedures enter_bridge(direction) and exit_bridge(direction). The solution must be based on semaphores and P and V operations. The solution needs not to be fair, which means that the waiting times on the other end may be very long. When the waiting ends, the cars must be allowed to proceed in FCFS order. 4. A savings account (10 p) A savings account is shared by several people. Each person may deposit or withdraw funds from the account. The balance of the account must never become negative.Write code for a server that takes care of the account. The clients may ask either for deposition or withdrawal of some amount of money. If there is not enough money on the account, the withdrawal has to wait until there are enouhg funds. The server and clients communicate using message passing.