Rinnakkaisohjelmointi, LH 6

1. 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.
4. Anna esimerkki tilanteesta, jossa kriittisen vaiheen ongelma olisi hyvä ratkaista monitorilla, mutta ei semaforeilla. Perustele.
5. Selitä käsite viestikapulan välittäminen (baton passing) kriittisen vaiheen ongelman ratkaisuissa. Milloin ja miksi sitä tarvitaan? Miten se toteutetaan?
    
2. Luolasto. Luolaston sisäänkäynti on yhdessä päässä ja uloskäynti toisessa päässä. Luolaston vierailijat pääsevät sisään 10 henkilön ryhmissä. Uudet vierailijat odottavat kunnes vierailijoita on tasan 10 kpl, jonka jälkeen he pääsevät oman oppaansa johdolla sisään. He tutustuvat luolastoon itsenäisesti ja opas odottaa heitä luolaston loppupäässä matkamuistomyymälässä. Kun kaikki ovat valmiita poistumaan luolastosta, opas päästää heidät ulos ja menee sisäänkäynnille keräämään uuden ryhmän. Voit olettaa, että kaikki vierailijat lopulta haluavat pois luolastosta eikä kukaan eksy matkalla.
   
   Oletetaan, että oppaat ja vierailijat ovat prosesseja, joiden synkronointiin käytetään semaforeja. Kirjoita prosessien toimintaa kuvaavat tarpeelliset pseudokoodit oppaille ja vierailijoille. Tee tarvittavat oletukset käyttämistäsi semaforeista ja semaforioperaatioista.
    
3. Mehiläisparvi, karhut ja IRR monitori. Mehiläisparvi (N mehiläistä) ruokkii loukkuun joutuneita karhuja (B kpl) keräämällä niille hunajaa. Karhujen elämä loukossa on vain syömistä ja odottelua. Mehiläiset keräävät hunajaa ja laittavat hunaja-annoksensa purkkiin korkeintaan 100 mehiläistä kerrallaan. Kun purnukka on täynnä (H annosta), viimeisen annoksen laittanut mehiläinen herättää yhden 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 taas nukkumaan.Varmista, että mikään karhuista ei nälkiinny.
   
   Ohjelmoi purnukan täytön ja tyhjentämisen synkronoinnin ratkaisu IRR (E<S<W) signalointisemantiikkaa käyttävän monitorin avulla. Monitori sisältää siis vain synkronointiongelman ratkaisun - hunajan kerääminen, purkin täyttäminen ja tyhjentäminen tapahtuvat monitorin ulkopuolella. Esitä mehiläisprosessien (N kpl), karhuprosessien (B kpl) ja monitorin pseudokoodi.
    
4. Anna kurssipalaute.
   Kohta 11 (Mielipiteesi oppimateriaalista). Anna mielipiteesi BACI-ohjelmiston käytöstä tällä kurssilla. Tukiko BACI oppimistasi? Oliko siihen käytetty aika hyödyllinen? Oliko C-- -kielen käyttö vaikeata?
   Kohta 14 (Miten kurssia voisi kehittää?). Anna mielipiteesi ainakin (a) kurssin luentokäytännöstä ja (b) projektista. (a) Tunsitko keskustelutilaisuudet hyödylliseksi? Olisiko parempi vain luennoida koko aika? Mielipiteesi luentokeskustelujen aihepiireistä? (b) Miten projektista saisi "paremman"?
   
   Ota mukaan laskuharjoitustilaisuuteen em. kohtien vastauksesi keskustelua varten. 
    
5. [2 htp] Lue artikkeli Data Structures in the Multicore Age (Nir Shavit, Comm ACM vol. 54 no. 3 - March 2011, ACM pdf, local pdf) ja pohdi seuraavia kysymyksiä artikkelin perusteella.
   1. Mikä on varsinainen ongelma ensimmäisessä (Lock-based Stack) ratkaisussa?
   2. Miten se on ratkaistu toisessa (LockFreeStack) ratkaisussa?
   3. Mikä on kriittinen vaihe ensimmäisessä ja toisessa ratkaisussa?
   4. Mitä backoff-algoritmi oikeastaan tekee ensimmäisessä ja toisessa ratkaisussa? Milloin sitä käytetään?
   5. Miten kolmas ratkaisu (EliminationBackoffStack) oikeastaan toimii?
   6. Mitä backoff-algoritmi oikeastaan tekee kolmannessa ratkaisussa? Milloin sitä käytetään?