581332 Rinnakkaisohjelmointi, koe 18.1.2011

Kirjoita jokaiseen vastauspaperiisi kurssin nimi, pvm, oma nimi, nimikirjoitus ja opiskelijanumero.
  1. [9 p] Kriittisen vaiheen ongelma
    1. Anna kooditason esimerkki tilanteesta, jossa kriittisen vaiheen muodostaa kaksi erillistä koodisegmenttiä. Perustele.
    2. Anna esimerkki tilanteesta, jossa kriittisen vaiheen ongelma olisi hyvä ratkaista semaforeilla, mutta ei busy-wait -odotuksella eikä keskeytyksiä estämällä. Perustele.
    3. Anna esimerkki tilanteesta, jossa kriittisen vaiheen ongelma olisi hyvä ratkaista monitorilla semaforien asemesta. Perustele.

  2. [9 p] Lukkiutuminen.
    1. [2 p] Mikä on lukkiutumisongelma? Anna Aterioivien filosofien ongelmaan pohjautuva konkreettinen esimerkki lukkiutumisesta.
    2. [4 p] Mitkä neljä ehtoa täytyy olla voimassa, jotta lukkiutuminen voisi tapahtua? Näytä, että ne pätevät esimerkissäsi.
    3. [3 p] Selitä Pankkiirin algoritmin (Banker's Algorithm) pääperiaatteet lukkiutumisen estämiseksi ennakolta. Kuinka se toimisi Aterioivien filosofien ongelmassa, kohdan (1) esimerkissäsi?
       
  3. [9 p] Monitori.
    1. [1 p] Mikä on monitori?
    2. [2 p] Miten monitori ratkaisee kriittisen vaiheen ongelman?
    3. [2 p] Miten monitori ratkaisee synkronointiongelman?
    4. [2 p] Missä eri kohdissa monitorissa suorittavat prosessit voivat joutua odottamaan suoritusvuoroaan?
    5. [2 p] Mitä tarkoittaa käsite monitorin signalointisemantiikka? Miten monitorin signalointisemantiikka vaikuttaa monitorin metodien toteutukseen? Miten monitorin signalointisemantiikka tulee ottaa huomioon monitoria kutsuvissa ohjelmissa?

  4. [9 p] Lukijat-kirjoittajat -ongelma. Kääntöpuolella on eräs ratkaisu ongelmaan.
    1. [2 p] Ratkaisussa käytetään jaettuja viestikapula semaforeja (baton passing split semaphores). Selitä mitä tämä tarkoittaa ja kuinka se ilmenee ratkaisussa.
    2. [2 p] Oletetaan, että kukaan ei ole käyttämässä kyseistä tietokantaa. Ensin tietokantaa haluaa käyttää 2 lukijaa (r1 ja r2), sitten yksi kirjoittaja (w3) ja lopulta kolmas lukija (r4). Ensimmäinen lukija (r1) on vielä lukemassa tietokantaa, kun kolmas lukija (r4) saapuu. Miten algoritmi toimii tässä tapauksessa? Selitä algoritmin toiminta siihen hetkeen saakka, kun nämä kaikki neljä prosessia ovat saaneet työnsä tehtyä. Kuka odottaa ja missä? Kuka vapauttaa kenet ja milloin? Kuka pääsee käyttämään tietokantaa ja milloin?
    3. [2 p] Nykyinen algoritmi suosii lukijoita. Selitä millä tavoin suosiminen tapahtuu ja miten tämä on toteutettu algoritmissa.
    4. [3 p] Muokkaa algoritmia siten, että se suosiikin kirjoittajia. Selitä millä tavoin suosiminen tapahtuu ja miten tämä on toteutettu algoritmissa. Miten algoritmi nyt toimii kohdan (b) tapauksessa?
      (Voit muokata algoritmia myös suoraan kääntöpuolen algoritmiin. Muista tällöin palauttaa koepaperi nimelläsi ja nimikirjoituksellasi varustettuna)

img