581332 Rinnakkaisohjelmointi, koe 17.6.2011         Other side in English

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] Lukkiutuminen. Sovellus App (4 säiettä, säikeet P, R, S ja T) käyttää kolmea resurssia (A, B ja C), joiden käyttö voi johtaa lukkiutumiseen. Resursseja on kutakin 1 kpl eikä niiden lukumäärää voi lisätä.
1. [3 p] Selitä, mikä on lukkiutumisongelma. Anna lukkiutumiseen johtava skenaario sovelluksessa App. Esitä skenaario sopivalla pseudokooditasolla.
2. [3 p] Mitkä neljä ehtoa täytyy olla voimassa, jotta lukkiutuminen voisi tapahtua? Näytä, että ne pätevät kohdan (a) lukkiutumisskenaariossa.
3. [3 p] Anna jokin (yksi) konkreettinen menetelmä, jolla lukkiutuminen voidaan suoritusaikana estää ennakolta. Selitä erityisesti, kuinka menetelmäsi toimii alkuperäisessä kohdan (a) lukkiutumisskenaariossa ja miten se estää lukkiutumisen tässä tapauksessa.
    
3. [9 p] Semafori
1. [4 p] Mikä on "semafori" ("semaphore")? (Käyttötarkoitus, rakenne, operaatiot, toteutus, ...)
2. Selitä käsite "binäärisemafori" ("binary semaphore").
3. Selitä käsite "yksityinen semafori" ("private semaphore").
4. Selitä käsite "blokkautuva semafori" ("blocking semaphore").
5. Selitä käsite "jaettu semafori" ("split semaphore").
6. Selitä käsite "viestikapulan käyttö" ("baton passing") semaforien yhteydessä.


4. [9 p] Tuottaja-kuluttaja -ongelma. Tuottajia ja kuluttajia on kumpiakin useita. Puskuri on äärellisen kokoinen. Kuvaile ongelma ja 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.