581332 Rinnakkaisohjelmointi, koe 25.1.2013              Other side in English

Kokeen perusteella kurssista saa 6 op, jos 2 op 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
1. [3 p] Anna kooditason esimerkki kriittisestä vaiheesta, jossa on vain yksi koodisegmentti. Anna esimerkkiisi liittyvä skenaario, jossa laskennan lopputulos on virheellinen, jos kriittistä vaihetta ei ole suojattu. Selitä, miksi tämän saman skenaarion laskennan tulos on oikein, kun kriittinen vaihe on suojattu.
2. [3 p] Anna kooditason esimerkki kriittisestä vaiheesta, jossa on kaksi erillistä koodisegmenttiä. Anna esimerkkiisi liittyvä kahteen koodisegmenttiin liittyvä skenaario, jossa laskennan lopputulos on virheellinen, jos kriittistä vaihetta ei ole suojattu. Selitä, miksi tämän saman skenaarion laskennan tulos on oikein, kun kriittinen vaihe on suojattu.
3. [1 p] Milloin kriittinen vaihe olisi hyvä suojata busy wait -silmukalla? Miksi?
4. [1 p] Milloin kriittinen vaihe olisi hyvä suojata semaforilla? Miksi?
5. [1 p] Milloin kriittinen vaihe olisi hyvä suojata Ricart-Agrawalan kolikko-pohjaisella algoritmilla? Miksi?


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 kohdan (a) esimerkissäsi.
3. [3 p] Anna edellämainittuihin (kohta b) neljään ehtoon perustuen kolme eri tapaa estää lukkiutuminen ennakolta Aterioivien filosofien ongelmassa. Selitä, miten ja miksi kukin tapa toimii lukkiutumisen estämisessä tässä tapauksessa.
    
3. [9 p] Monitori.
1. [2 p] Mikä on monitori? Mihin ongelmaan monitori on ratkaisu? Miten monitorien käyttö rinnastuu semaforien käyttöön?
2. [2 p] Miten monitori ratkaisee kriittisen vaiheen ongelman? Missä kohtaa monitorin koodia kriittinen vaihe alkaa ja milloin se loppuu?
3. [3 p] Miten monitorin ehtomuuttujat ja niiden operaatiot eroavat semaforeista ja niiden operaatioista?
4. [2 p] Mitä tarkoittaa käsite "monitorin signalointisemantiikka"? Miten se täytyy ottaa huomioon monitorin toteutuksessa?


4. [9 p] Tuottaja-kuluttaja -ongelma semaforeilla. Tuottajia ja kuluttajia on kumpiakin useita. Puskurin koko on N.
1. [3 p] Kuvaile ongelma. Erityisesti kerro, mitä synkronointi- ja kommunikointiongelmia tähän liittyy.
2. [6 p] Anna ongelman ratkaisu semaforien avulla. Esitä tuottajien ja kuluttajien pseudokoodi. Määrittele selkeästi kaikki käyttämäsi semaforit alkuarvoineen. Selitä, miksi ratkaisusi on oikein.