581332 Rinnakkaisohjelmointi, koe 31.5.2012                       

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 busy-wait odotuksella, mutta ei keskeytyksiä estämällä eikä semaforeilla. Perustele eri vaihtoehdot.
3. Anna esimerkki tilanteesta, jossa kriittisen vaiheen ongelma olisi hyvä ratkaista Ricart-Agrawala -algoritmilla semaforien asemesta. Perustele. Miksi semaforit eivät kelpaa?


2. [9 p] Lukkiutuminen.
1. Mikä on lukkiutumisongelma? Anna joku konkreettinen (pseudokoodi) esimerkki lukkiutumisesta.
2. Mitkä neljä ehtoa täytyy olla voimassa, jotta lukkiutuminen voisi tapahtua? Näytä, että ne pätevät esimerkissäsi.
3. Selitä Pankkiirin algoritmin (Banker's Algorithm) pääperiaatteet lukkiutumisen estämiseksi ennakolta. Kuinka se toimisi kohdan (a) esimerkissäsi?
   


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?
2. [2 p] Miten monitorin ehtomuuttujat ja niiden operaatiot eroavat semaforeista ja niiden operaatioista?
3. [2 p] Mitä tarkoittaa käsite "monitorin signalointisemantiikka"? Miten IRR-signalointisemantiikka vaikuttaa monitorin toteutukseen?
4. [3 p] Anna tehtävän 3 Tuottaja-kuluttaja -ongelman kohdan (b) ratkaisu monitorilla. Esitä tuottajan, kuluttajan ja monitorin pseudokoodi. Määrittele selkeästi kaikki käyttämäsi monitorin ehtomuuttujat alkuarvoineen. Selitä, miksi ratkaisusi on oikein.
   Huolehdi ratkaisussasi erityisesti siitä, että ainoastaan synkronointiongelman ratkaisu tapahtuu monitorissa ja että varsinainen työ (alkioiden "tuottaminen", puskuriin laittaminen ja sieltä poistaminen, alkioiden "kuluttaminen") tapahtuu monitorin ulkopuolella.