581332 Rinnakkaisohjelmointi, koe 15.6.2012                           Other side in English

Tämä erilliskoe toimii myös kevään 2012 luentokurssin korvaavana kuulusteluna yhden puuttuvan tai huonommin menneen välikokeen suhteen. Kokeen perusteella kurssista saa 6 op, jos projekti on tehty, ja 4 op muutoin.

1. [9 p] Kriittisen vaiheen ongelma
1. Anna kooditason esimerkki tilanteesta, jossa kriittisen vaiheen muodostaa kaksi erillistä koodisegmenttiä. Eroaako tilanne mitenkään oleellisesti siitä, että kriittisen vaiheen koodisegmenttejä olisi vain yksi kappale? 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. Mitkä neljä ehtoa täytyy olla voimassa, jotta lukkiutuminen voisi tapahtua?
2. Selitä Dijkstran lukkiutumisen havaitsemisalgoritmin (DDA) pääperiaatteet. Mihin sitä tarvitaan? Mitä tietoja ja mitä tietorakenteita siinä tarvitaan? Milloin algoritmi käynnistyy ja milloin se päättyy? Mitä algoritmin tuloksella tehdään?
3. Selitä Pankkiirin algoritmin (Banker's Algorithm) pääperiaatteet. Mihin sitä käytetään? Mitä tietoja ja mitä tietorakenteita siinä tarvitaan? Milloin algoritmi käynnistyy ja milloin se päättyy? Mitä algoritmin tuloksella tehdään?
   


3. [9 p] Tuottaja-kuluttaja -ongelma. Tuottajia ja kuluttajia on molempia yksi kappale. Puskurin koko on 1000.
1. Kuvaile ongelma. Erityisesti kerro, mitä synkronointi- ja kommunikointiongelmia tähän liittyy. Mitä hyötyä isommasta puskurista on?
2. Anna ongelman ratkaisu semaforien avulla. Esitä tuottajan ja kuluttajan pseudokoodi. Määrittele selkeästi kaikki käyttämäsi semaforit alkuarvoineen. Selitä, miksi ratkaisusi on oikein.
3. Oletetaan nyt, että järjestelmän kokonaislogiikka on sellainen, että puskurissa odottavien alkioiden lukumäärä ei ikinä voi olla 500 enempää. Kuinka tämä vaikuttaa ongelman ratkaisuun ja sen sisältämiin synkronointi- ja kommunikointiongelmiin. Anna ongelman ratkaisu semaforien avulla. Esitä tuottajan ja kuluttajan pseudokoodi. Määrittele selkeästi kaikki käyttämäsi semaforit alkuarvoineen. Selitä, miksi ratkaisusi on oikein.


4. [9 p] Monitori.
1. [2 p] Miten monitori ratkaisee kriittisen vaiheen ongelman? Mistä kriittinen alue alkaa ja mihin se loppuu?
2. [3 p] Miten monitori ratkaisee synkronointiongelman? Miten ratkaisu eroaa semaforien käytöstä?
3. [2 p] Missä eri kohdissa monitorissa suorittavat prosessit voivat joutua odottamaan suoritusvuoroaan?
4. [2 p] Mitä tarkoittaa käsite monitorin signalointisemantiikka? Anna koodiesimerkki tilanteesta, jossa koodi toimii IRR-semantiikalla, mutta ei signal-and-continue semantiikalla.