581332 Rinnakkaisohjelmointi, koe 6.5.2011         Other side in English

1. [10 p] Kriittinen alue (vaihe). Oletetaan, että monisäikeisen ohjelman yhteisessä muistissa olevien muuttujien X, Y ja Z käyttöä halutaan suojata kriittisen vaiheen avulla. Muuttujiin voitaisiin viitata ohjelmassa seitsemässä kohtaa (kohdat A, B, C, D, E, F ja G), mutta eri ohjelman versioissa nuo kaikki kohdat eivät ole käytössä. 

    A: X <- 7     B: some1 <- X   C: Y <- 87      E: some5 <- Y   G: some5 <- Y
       Y <- 4        some2 <- Y                                      Y <- 0
       Z <- X+Y      some3 <- Z   D: some4 <- X   F: some6 <- 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 G muuttujan Y arvo tulee nollata välittömästi sen lukemisen jälkeen.
   1. Oletetaan, että ainoastaan koodinpätkät A, D, E ja F esiintyvät ohjelmakoodissa. Tarvitseeko joitakin niistä suojata kriittisenä alueena? Perustele.
   2. Oletetaan, että ainoastaan koodinpätkät B, C, D, E ja F esiintyvät ohjelmakoodissa. Tarvitseeko joitakin niistä suojata kriittisenä alueena? Perustele.
   3. Oletetaan, että ainoastaan koodinpätkät C, E ja G esiintyvät ohjelmakoodissa. Tarvitseeko joitakin niistä suojata kriittisenä alueena? Perustele.
   4. Oletetaan, että kaikki koodinpätkät A, B, C, D, E, F ja G esiintyvät ohjelmakoodissa. Tarvitseeko joitakin niistä suojata kriittisenä alueena? Perustele.


2. [10 p] Lukkiutuminen.
1. [2 p] Mikä on lukkiutumisongelma? Anna Aterioivien filosofien ongelmaan pohjautuva konkreettinen esimerkki lukkiutumisesta.
2. [4 p] Oletetaan, että lukkiutumistilanne on havaittu 40 laskentasäikeen järjestelmässä ja kolme laskentasäiettä A, B ja C (noista 40 säikeestä) ovat lukkiutuneet. Miten nyt toimitaan, kun koko laskentaa ei haluta keskeyttää ja olet varautunut tähän tilanteeseen? Tee tarvittavat oletukset ratkaisuusi ja selitä, miten kokonaislaskenta silti onnistuu.
3. [4 p] Anna kaksi erilaista menetelmää lukkiutumisen estämiseksi ennakolta. Selitä menetelmien pääperiaatteet ja erityisesti selitä miksi lukkiutumista ei voi nyt tapahtua. Selitä, kuinka menetelmiä käytettäisiin b-kohdan monisäikeisessä laskennassa.
    
3. [10 p] Mehiläisparvi, karhut ja IRR monitori. Mehiläisparvi (N mehiläistä) ruokkii loukkuun joutuneita karhuja (B kpl) keräämällä niille hunajaa. Karhujen elämä loukossa on vain syömistä ja odottelua. Mehiläiset keräävät hunajaa ja laittavat hunaja-annoksensa purkkiin, mutta purkkia voi täyttää korkeintaan 60 mehiläistä yhtä aikaa. Kun purnukka on täynnä (H annosta), viimeisen annoksen laittanut mehiläinen herättää yhden 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. Varmista, että mikään karhuista ei nälkiinny.
   
   Ohjelmoi purnukan täytön ja tyhjentämisen synkronoinnin ratkaisu IRR (E<S<W) signalointisemantiikkaa käyttävän monitorin avulla. Monitori sisältää siis vain synkronointiongelman ratkaisun - hunajan kerääminen, purkin täyttäminen ja tyhjentäminen tapahtuvat monitorin ulkopuolella. Esitä mehiläisprosessien (N kpl), karhuprosessien (B kpl) ja monitorin pseudokoodi.