581332 Rinnakkaisohjelmointi, koe 27.9.2011         in EnglishOther side in English

Kirjoita jokaiseen vastauspaperiisi kurssin nimi, pvm, oma nimi, nimikirjoitus ja opiskelijanumero.
  1. [9 p] Kriittisen vaiheen ongelma (critical section problem)
    1. Anna kooditason esimerkki tilanteesta, jossa kriittisen vaiheen muodostaa kaksi erillistä koodisegmenttiä. Perustele.
    2. Oletetaan, että (i) kriittinen vaihe kestää noin 10-30 konekäskyä, (ii) kriittisen vaiheen suoritukseen käytetään alle 0.001% ohjelman kokonaissuoritusajasta, (iii) säikeitä suoritetaan rinnakkain 8-ytimisessä laitteistossa ja (iv) säikeillä on käytössään yhteinen muisti. Millä tavoin suojaisit kriittisen vaiheen tässä tilanteessa? Perustele, miksi valitsit tämän ratkaisumenetelmän.
    3. Oletetaan nyt, että edellisen kohdan (b) vaatimusta (iv) muokataan siten, että säikeillä ei olisi käytössään yhteistä muistialuetta vaikka ne suorittavatkin samassa laitteistossa. Millä tavoin nyt suojaisit kyseisen kriittisen vaiheen? Perustele ratkaisusi.

  2. [9 p] Lukkiutuminen.
    1. Mikä on lukkiutumisongelma? Mitkä neljä ehtoa täytyy olla voimassa, jotta lukkiutuminen voisi tapahtua?
    2. [3 p] Selitä pääpiirteissään Dijkstran algoritmi lukkiutumisen havaitsemiseksi. Mitä tehdään, jos lukkiutuman olemassaolo havaitaan? Mitä tehdään, jos algoritmi ei löydä lukkiutuneita prosesseja?
    3. Miten lukkiutuma voidaan estää ennakolta? Anna ainakin 2 erilaista tapaa.
    4. Selitä pääpiirteissään Pankkiirin algoritmi (Banker's algorithm) toimintaperiaatteet ja mihin ongelmaan se on ratkaisu.
       
  3. [9 p] Puomisynkronointi semaforeilla. Ohjelmassa on N säiettä ja laskenta koostuu useasta erillisestä vaiheesta. Jokaisen säikeen pitää suoritettaa 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.

    Anna tämän synkronointiongelman pseudokooditason ratkaisu semaforeja käyttämällä. Muista alustukset seuraavaa varten. Selitä, miksi ratkaisusi on oikein.

    4.  
  4. [9 p] Monitori.
    1. [1 p] Mikä on monitori? Mihin ongelmaan monitori on ratkaisu? Miten monitorien käyttö rinnastuu semaforien käyttöön?
    2. Miten monitori ratkaisee kriittisen vaiheen ongelman? Missä kohtaa monitorin koodia kriittinen vaihe alkaa ja milloin se loppuu?
    3. Miten monitorin ehtomuuttujat eroavat semaforeista? Huomioi ainakin käyttötarkoitus, sisäinen rakenne ja operaatiot?
    4. Mitä tarkoittaa käsite monitorin signalointisemantiikka? Miten monitorin signalointisemantiikka vaikuttaa monitorin metodien toteutukseen? Miten monitorin signalointisemantiikka tulee ottaa huomioon monitoria kutsuvissa ohjelmissa?
    5. (jatkoa kohtaan kohtaan d) Anna konkreettinen pseudokooditason esimerkki tilanteesta, jossa sama koodi toimii oikein yhdellä signalointisemantiikalla, mutta ei toisella. Selitä, miksi se ei toimi.