581332 Rinnakkaisohjelmointi, koe 16.8.2013

Kokeen perusteella kurssista saa 6 op, jos 2 op projekti on tehty, ja 4 op muutoin.
Jos olet tehnyt 2 op projektin luentokurssin yhteydessä, mainitse asiasta ja kerro minä vuonna projektisi on tehty.
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 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ä. Muuttujat somei ovat lokaaleja kullekin säikeelle. 
     A: X <- 7     B: some1 <- X   C: Y <- 87      E: some5 <- Y   G: some7 <- 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 C, E ja G esiintyvät ohjelmakoodissa. Tarvitseeko joitakin niistä suojata kriittisenä alueena? Perustele.
    3. 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. [9 p] Lukkiutuminen.
    1. [3 p] Mikä on lukkiutumisongelma? Anna Aterioivien filosofien ongelmaan pohjautuva konkreettinen esimerkki lukkiutumisesta.
    2. [3 p] Oletetaan, että hyvin monisäikeinen ohjelma on suunniteltu niin, että lukkiutuminen on mahdollista laskennan lopputuloksen silti kärsimättä. Oletetaan, että lukkiutumistilanne on nyt havaittu 100 laskentasäikeen järjestelmässä ja kolme laskentasäiettä A, B ja C (noista 100 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. [3 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 (kun lukkiutumisen sallimisen sijasta ratkaisu perustuu sen estämiseen ennakolta).
       
  3. [9 p] Monitori
    1. Miten kriittisen vaiheen ongelman ratkaisu tehdään monitorissa? Miten ratkaisu eroaa semaforiratkaisusta?
    2. Miten synkronointiongelman ratkaisu tehdään monitorissa? Miten ratkaisu eroaa semaforiratkaisusta?
    3. Mitä tarkoittaa käsite "monitorin signalointisemantiikka"? Miten se vaikuttaa (i) monitorin toteutukseen ja (ii) monitoria kutsuvan rutiinin toteutukseen?

  4. [9 p] Mehiläisparvi, karhut ja semaforit. 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, 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ää 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ä karhu ei nälkiinny.
    1. [3 p] Mitä kaikkia synkronointiongelmia tähän liittyy? Kuka odottaa ketä ja milloin?
    2. [6 p] Ohjelmoi purnukan täytön ja tyhjentämisen synkronoinnin ratkaisu semaforien avulla. Esitä mehiläisprosessien (N kpl) ja karhuprosessin pseudokoodi. Muista esitellä ja alustaa semaforit ja muut ratkaisusi tietorakenteet.