581332 Rinnakkaisohjelmointi, koe 19.8.2011         in EnglishOther side in English

Kirjoita jokaiseen vastauspaperiisi kurssin nimi, pvm, oma nimi, nimikirjoitus ja opiskelijanumero.
  1. [9 p] Kriittisen vaiheen ongelma monisäikeisessä ohjelmassa moniytimisessä järjestelmässä. Yhteiskäyttöisten muuttujien f1, ..., f8 arvojen tulee olla aina konsistensseja (yhteensopivia): niitä päivitettäessä kaikkien kenttien arvot tulee päivittää konsistentisti ja koskaan ei pidä pystyä lukemaan epäkonsistensseja muuttujien arvoja.
    1. [3 p] Oletetaan, että on vain yksi koodinpätkä, joka päivittää muuttujien f1, ..., f8 arvoja. Tarvitaanko sen suojaamiseen kriittistä vaihetta vai ei? Perustele.
      Ohjelmassa on myös muita kyseisiä muuttujia lukevia koodinpätkiä, mutta niitä ei koskaan suoriteta samanaikaisesti päivitysten kanssa. Niitä ei siis tarvitse ottaa huomioon tehtävän tässä osassa (a).
    2. Oletetaan nyt, että koodinpätkä u1 päivittää muuttujien f1, ..., f8 arvoja ja koodinpätkät r1 ja r2 lukevat niiden arvoja. Minkälaisia kriittisiä vaiheita tarvitaan nyt koodinpätkien u1, r1 ja r2 suojaamiseen? Perustele.
    3. Oletetaan kohdan (b) lisäksi, että koodinpätkä r3 ainoastaan lukee muuttujan f7 arvon. Minkälaisia kriittisiä vaiheita tarvitaan nyt koodinpätkien u1, r1, r2 ja r3 suojaamiseen? Perustele.
    4. Oletetaan kohdan (c) lisäksi, että koodinpätkä u2 ainoastaan päivittää muuttujan f7 arvon. Minkälaisia kriittisiä vaiheita tarvitaan nyt koodinpätkien u1, u2, r1, r2 ja r3 suojaamiseen? Perustele.

  2. [9 p] Kriittisen vaiheen ongelman ratkaisut. Anna kuhunkin seuraavista kriittisen vaiheen (KV) ongelman ratkaisumenetelmistä kaksi vastausta: (i) milloin ja missä ympäristössä KV:n voi ratkaista tällä menetelmällä? (ii) milloin ja missä ympäristössä ja minkä vuoksi KV:tä ei voi ratkaista tällä menetelmällä?
    1. keskeytysten esto
    2. lukko-muuttuja ja busy wait -odotus
    3. semafori
    4. monitori
    5. Ricart-Agrawalan kolikko-pohjainen algoritmi
       
  3. [9 p] Aterioivat filosofit ja semaforit
    1. [2 p] Kuvaile aterioivien filosofien ongelma. Selitä erityisesti, minkälaisia synkronointi- ja/tai kommunikointiongelmia siihen liittyy.
    2. [2 p] Mikä on "semafori" ("semaphore")? (Käyttötarkoitus, rakenne, operaatiot, toteutus, ...)
    3. [3 p] Anna aterioivien filosofien ongelman lukkiutumaton ratkaisu semaforien avulla. Selitä erityisesti, miten mainitsemasi synkronointi- ja/tai kommunikointiongelmat on siinä ratkaistu.
    4. [2 p] Todista (tai perustele tyhjentävästi), että ratkaisusi on lukkiutumaton.

  4. [9 p] Tuottaja-kuluttaja -ongelma ja monitori. Tuottajia ja kuluttajia on kumpiakin vain yksi. Kuluttaja on huomattavasti nopeampi kuin tuottaja, joten käytännössä puskurin koko (N) on äärettömän suuri.
    1. [3 p] Kuvaile ongelma. Erityisesti kerro, mitä synkronointi- ja kommunikointiongelmia tähän liittyy. Mikä vaikutus on sillä, että puskurin voidaan teoreettisesti katsoa olevan ääretttömän suuri, vaikka käytännössä se tietenkin on toteutettu äärellisen kokoisena?
    2. [6 p] Anna ongelman ratkaisu IRR (E<S<W) signalointisemantiikkaa käyttävän monitorin avulla. Monitori sisältää siis vain synkronointiongelman ratkaisun ja puskurin täyttö/tyhjennys tapahtuu monitorin ulkopuolella. Esitä tuottajien, kuluttajien ja monitorin pseudokoodi. Selitä, miksi ratkaisusi on oikein.