581332 Rinnakkaisohjelmointi, koe 19.1.2010         Other side in English

1. [9 p] Kriittisen vaiheen ongelma
1. Anna esimerkki tilanteesta, jossa kriittisen vaiheen ongelma olisi hyvä ratkaista keskeytykset estämällä, mutta ei busy-wait -odotuksella (esim. test-and-set käskyn avulla) eikä semaforeilla. Perustele.
2. Anna esimerkki tilanteesta, jossa kriittisen vaiheen ongelma olisi hyvä ratkaista busy-wait -odotuksella, mutta ei keskeytyksiä estämällä eikä semaforeilla. Perustele.
3. Anna esimerkki tilanteesta, jossa kriittisen vaiheen ongelma olisi hyvä ratkaista semaforeilla, mutta ei busy-wait -odotuksella eikä keskeytyksiä estämällä. Perustele.
    
2. [9 p] Lukkiutuminen. Mikä on lukkiutumisongelma? Anna konkreettinen esimerkki lukkiutumisesta. Mitkä neljä ehtoa täytyy olla voimassa, jotta lukkiutuminen voisi tapahtua? Näytä, että ne pätevät esimerkissäsi. Selitä pääpiirteissään Dijkstran algoritmi lukkiutumisen havaitsemiseksi. Mitä tehdään, jos lukkiutuman olemassaolo havaitaan? Millä kahdella erilaisella tavalla lukkiutuma voidaan estää ennakolta?
    
3. [9 p] Ohjelmassa on N säiettä ja laskenta koostuu useasta erillisestä vaiheesta. Kunkin säikeen pitää saada suoritettua nykyinen laskennan vaihe (vaihe i) loppuun, ennen kuin mikään niistä voi jatkaa suoritusta seuraavasta vaiheesta (vaihe i+1). Sama synkronointiongelma toistuu nyt uuden vaiheen (vaihe i+1) kanssa.
   
   Anna tämän synkronointiongelman ratkaisu semaforeja käyttämällä. Selitä, miksi ratkaisusi on oikein.
    
4. [9 p] Mehiläisparvi ja karhu. Mehiläisparvi (N mehiläistä) ruokkii loukkuun joutunutta karhua keräämällä sille hunajaa. Karhun elämä loukossa on vain syömistä ja odottelua. Mehiläiset keräävät hunajaa ja laittavat hunaja-annoksensa purkkiin yksi kerrallaan. Kun purnukka on täynnä (H annosta), viimeisen annoksen laittanut mehiläinen herättää karhun syömään ennenkuin poistuu paikalta. Hunajaa tuovat mehiläiset jäävät tällöin odottamaan purnukan tyhjenemistä. Kun karhu on tyhjentänyt purkin, se päästää mehiläiset taas täyttämään purkkia ja käy itse nukkumaan. Ohessa on annettu monitorilla tehty karkea ratkaisu, jossa mehiläiset täyttävät purkkia yksi kerrallaan monitorin ulkopuolella.
   1. Muokkaa allaolevan esimerkin monitoria siten, että max 50 mehiläistä voi täyttää hunajaa samanaikaisesti.
   2. Miten ratkaisusi muuttuu, jos monitori toteuttaakin IRR-semantiikkaa?