581332 Rinnakkaisohjelmointi, koe 1.6.2010         in EnglishOther side in English
Kirjoita jokaiseen vastauspaperiisi kurssin nimi, pvm, oma nimi, nimikirjoitus ja opiskelijanumero.
  1. [9 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 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 ja miksi?  Miksi niitä muita ei tarvitse suojata?
    2. Anna virheelliseen lopputulokseen johtava suoritusskenaario, jos kriittisiä alueita ei ole suojattu. Selitä, miksi tulos on virheellinen ja mistä virhe aiheutui? Tapahtuuko sama virhe joka suorituskerta?
    3. Näytä (pseudokooditasolla), kuinka näiden säikeiden kriittiset vaiheet suojataan busy-wait -loopissa (esim. test-and-set -käskyn avulla). Millaisessa laskentaympäristössä tämä olisi järkevä ratkaisu? Miksi?
       
  2. [9 p] Ohjelmassa on N säiettä ja laskenta koostuu useasta erillisestä vaiheesta (phase). Kunkin säikeen pitää saada suoritettua nykyinen laskennan vaihe (vaihe i) loppuun, ennen kuin mikään niistä voi jatkaa suoritusta seuraavasta vaiheesta (vaihe i+1). Sama synkronointiongelma toistuu nyt uuden vaiheen (vaihe i+1) kanssa. Säikeen pseudokoodi on siis seuraavanlainen: 
    for i=1 to nPhases
  <compute Phase i>
  Boom.PhaseDone(myId)
    Anna tämän synkronointiongelman ratkaisu monitorin avulla, toteuttamalla monitori Boom. Monitorissa Boom on metodi PhaseDone, jota säikeet kutsuvat kunkin vaiheen lopussa. Selitä, miksi ratkaisusi on oikein.
     
  3. [9 p] Kysymyksiä
    1. Mitä tarkoittaa käsite yksityinen semafori? Milloin käyttäisit sitä?
    2. Mikä ero on semaforin wait() ja monitorin waitC() operaatioilla?
    3. Miten pankkiirin algoritmi (Bankers algorithm) eroaa Dijkstran DDA-algoritmista? Mitä niillä on yhteistä?
       
  4. [9 p] Mehiläisparvi ja karhu. 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 keräävät hunajaa ja laittavat hunaja-annoksensa purkkiin yksi 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.

    Ohessa on annettu semaforeilla tehty karkea ratkaisu.
    1. Muokkaa allaolevan esimerkin ratkaisua siten, että max 50 mehiläistä voi täyttää hunajaa samanaikaisesti.
    2. Muokkaa allaolevan esimerkin ratkaisua siten, että karhuja on nyt 2 kappaletta ja ne pitää herättää vuorotellen syömään.
                                              Semaphore Pot