Other side in English

581332 Rinnakkaisohjelmointi, 4 op, erilliskoe 15.1.2008

1. [15 p] Kriittinen alue (vaihe). Oletetaan, että monisäikeisen ohhelman yhteisessä muistissa olevien muuttujien X, Y ja Z käyttöä halutaan suojata kriittisen vaiheen avulla. Muuttujiin viitataan ohjelmassa viidessä kohtaa (kohdat A, B, C, D ja E): 

    A: X <- 7      B: some1 <- X    C: Y <- 87    D: some4 <- X    E: some5 <- Y
       Y <- 4         some2 <- Y                                      Y <- 0
       Z <- X+Y       some3 <- Z

   Kohdassa A muuttujien Y ja Z vanhat arvot eivät saa näkyä muille sen jälkeen kun X on saanut uuden arvon ja Z'n uuden arvon tulee olla X'n ja Y'n uusien arvojen summa. Kohdassa B muuttujien some1, some2 ja some3 arvoiksi tulee tulla X'n, Y'n ja Z'n arvot käskysarjan suorituksen alkuhetkellä. Kohdassa E muuttujan Y arvo tulee nollata välittömästi sen lukemisen jälkeen.
   1. Mitkä näistä (pseudo)koodinpätkistä (A, B, C, D ja E) tulee suojata kriittisenä alueena?  Erityisesti, tarvitaanko kohtaa C suojata, koska siinä muutetaan ainoastaan yhden muuttujan arvo? Entä kohta D, jossa vain luetaan yhden muuttujan arvo? Entä kohta E, jossa luetaan yhden muuttujan vanha arvo ja nollataan se sitten?
   2. Näytä (pseudokooditasolla), kuinka kriittiset vaiheet suojataan keskeytykset estämällä. Millaisessa laskentaympäristössä tämä olisi järkevä ratkaisu? Miksi?
   3. Näytä (pseudokooditasolla), kuinka kriittiset vaiheet suojataan busy-wait -loopissa (esim test-and-set -käskyn avulla). Millaisessa laskentaympäristössä tämä olisi järkevä ratkaisu? Miksi?
   4. Näytä (pseudokooditasolla), kuinka kriittiset vaiheet suojataan semaforin avulla. Millaisessa laskentaympäristössä tämä olisi järkevä ratkaisu? Miksi?
   5. Oletetaan nyt, että ohjelma on toteutettu hajautetussa ympäristössä ja että muuttujat X, Y ja Z sijaitsevat yhteiskäyttöisellä tiedostopalvelimella. Muuttujien arvoja kirjoitetaan ja luetaan viestien avulla. Miten kriittinen alue tulee nyt suojata käytännössä?
       
2. [15 p] Monitorit
1. Mikä on monitori? Mihin ongelmaan se on ratkaisu? 
2. Mitä etua monitoreilla on semaforeihin verrattuna? Anna esimerkki.
   Mitä etua semaforeilla on monitoreihin verrattuna? Anna esimerkki.
3. Mitä monitorin signalointisemantiikka tarkoittaa?
   Mikä on IRR (Immeadiate Resumption Requirement, "Signal and Urgent Wait", E<S<W) signalointisemantiikka?
   Miten IRR eroaa käytännössä esimerkiksi Javan signalointisematiikasta (E=W<S)?
4. Mikä ongelma liittyy monitorin signalointisemantiikkaan, jos IRR ei päde? Anna konkreettinen (pseudokoodi) esimerkki, jossa signalointisemantiikka ilman IRR'ää johtaa virheelliseen tulokseen, mutta jossa IRR signalointisemantiikka toimisi.
   
   
3. [15 p] Lukkiutuminen (deadlock)
   1. Mitä lukkiutuminen tarkoittaa ja milloin järjestelmä voi lukkiutua?
   2. Kuinka Dijkstran lukkiutumisen havaitsemis -algoritmi (DDA, Deadlock Detection Algorithm) toimii pääpiirteissään? Sehän käyttää taulukoita A (allokaatio matriisi) ja Q (pyyntömatriisi) sekä vektoreita R (kaikki resurssit), V (vapaat resurssit) ja W (työvektori).
   3. Oletetaan, että DDA löytää järjestelmästäsi 3 lukkiutunutta prosessia (säiettä). Mitä nyt tehdään?
   4. Kuinka lukkiutumiset voidaan (staattisesti) estää ennakolta siten, että resurssien varaamishetkellä lukkiutumismahdollisuutta ei tarvitse ottaa enää huomioon?
   5. Kuinka lukkiutumiset voidaan (dynaamisesti) estää ennakolta siten, että lukkiutumisen mahdollisuus tutkitaan vasta resurssien varaushetkillä?
       
4. [15 p]  Mehiläisparvi semaforissa. Mehiläisparvi (N mehiläistä) ruokkii loukkuun joutunutta karhua keräämällä sille hunajaa. Karhun elämä loukossa on vain syömistä ja odottelua. Mehiläiset kuljettavat hunajaa purnukkaan annos kerrallaan. Kun purnukka on täynnä (H annosta), viimeisen annoksen laittanut mehiläinen herättää karhun syömään ennenkuin poistuu paikalta. Hunajaa tuovat mehiläiset jäävät tällöin odottamaan purnukan tyhjenemistä. Kun karhu on tyhjentänyt purkin, se päästää mehiläiset taas täyttämään purkkia ja käy itse nukkumaan.
   
   Mehiläiset voivat täyttää hunajapurkkia samanaikaisesti, mutta purkkiin ei saa tulla enempää kuin H annosta hunajaa.
   
   Ohjelmoi purnukan täyttö ja tyhjentäminen semaforin avulla. Esitä mehiläisprosessien (N kpl) ja karhuprosessin koodi. Selvitä vielä sanallisesti, missä tilanteissa tarvitaan poissulkemista ja/tai synkronointia sekä kuinka ne toteutuvat ratkaisussasi.