581332 Rinnakkaisohjelmointi, koe 17.8.2012                           Other side in English

Kokeen perusteella kurssista saa 6 op, jos projekti on tehty, ja 4 op muutoin.
Jos olet tehnyt 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] 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 mahdollisesti samaan aikaan suorituksesa olevat 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ä mahdollisesti samaan aikaan suorituksesa oleva 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ä mahdollisesti samaan aikaan suorituksesa oleva 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ä. Kutakin resurssia voi käyttää vain yksi säie kerrallaan.
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)
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 molempia yksi kappale. 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ä (a) tuottajan, (b) kuluttajan ja (c) monitorin pseudokoodi. Selitä, miksi ratkaisusi on oikein.