581332 Rinnakkaisohjelmointi, 4 op, erilliskoe 17.8.2007

1. [9 p] Lukot, semaforit ja monitorit rinnakkaisohjelmoinnissa.
   1. Mikä on lukko (lock, busy-wait semaphore, await with busy-wait loop)? Mihin ongelmaan se on ratkaisu? Mitä etua lukoilla on semaforeihin ja monitoriin verrattuna? Anna esimerkki tilanteesta, jossa on luontevaa käyttää lukkoja, mutta ei semaforeja tai monitoria.
   2. Mikä on semafori? Mihin ongelmaan se on ratkaisu? Mitä etua semaforeilla on lukkoihin ja monitoriin verrattuna? Anna esimerkki tilanteesta, jossa on luontevaa käyttää semaforeja, mutta ei lukkoja tai monitoria.
   3. Mikä on monitori? Mihin ongelmaan se on ratkaisu? Mitä etua monitorilla on lukkoihin ja semaforeihin verrattuna? Anna esimerkki tilanteesta, jossa on luontevaa käyttää monitoria, mutta ei lukkoja tai semaforeja.
       
2. [9 p] Lukkiutuminen (deadlock)
   1. Anna Aterioivien filosofien ongelmaan semaforeihin perustuva ratkaisu, jossa on lukkiutumisongelma. Anna lukkiutuva skenario.
   2. Kuinka Dijkstran lukkiutumisen havaitsemis -algoritmi (DDA, Deadlock Detection Algorithm) toimii pääpiirteissään? Sehän käyttää taulukoita A (allokaatio matriisi) ja Q (pyyntömatriisi), sekä vektoreita R (kaikki resurssit), V (vapaat resurssit) ja W (työvektori).
   3. Anna Aterioivien filosofien ongelmaan semaforeihin perustuva ratkaisu, joka ei lukkiudu. Perustele, miksi lukkiutumista ei voi tapahtua.
       
3. [9 p] Tarkastellaan Algoritmia 6.21 [Ben-Ari 2006] kääntöpuolella.
   1. Oletetaan, että lukija R2 ja kirjoittaja W2 odottavat vuoroaan ja että kirjoittaja W1 on kirjoittamassa. Odottavat prosessit ovat saapuneet järjestyksessä W2, R2 (eli prosessi W2 saapui ensin). Kun kirjoittaja W1 poistuu, niin kumpi odottajista (R2 vai W2) pääsee sisään seuraavaksi? Perustele.
   2. Oletetaan, että 4 lukijaa (R2, R3, R4, R5) ja 2 kirjoittajaa (W2, W3) odottavat vuoroaan ja että kirjoittaja W1 on kirjoittamassa. Odottavat prosessit ovat saapuneet järjestyksessä W2, R2, R3, R4, W3, R5. Kun W1 poistuu, niin missä järjestyksessä vuorot annetaan odottaville 6 prosessille? Perustele. Oleta, että uusia lukijoita tai kirjoittajia ei saavu, kunnes kaikki R2, R3, R4, R5, W2, W3 ovat saaneet vuoronsa.
   3. Jatkoa edelliseen kohtaan (c). Oletetaan, että uusi lukija R6 saapuu juuri sen jälkeen kun kohdan (c) ensimmäinen odottanut prosessi (R2 tai W2) on saanut vuoronsa. Miten tämä vaikuttaa aiemmin odottaneiden prosessien R3, R4, R5, W2, W3 vuoronantoon? Perustele.
   4. Algoritmia voi muokata siten, että kirjoittajilla on prioriteetti lukijoihin nähden. Millaisessa ympäristössä tällainen priorisointi olisi tarpeellista tehdä? (Huom: sinun ei tarvitse toteuttaa tuota muokkausta)
      
      
4. [9 p] Mehiläisparvi monitorissa. Mehiläisparvi ruokkii loukkuun joutunutta karhua keräämällä sille hunajaa. Karhun elämä loukossa on vain syömistä ja odottelua. Mehiläiset kuljettavat hunajaa purnukkaan annos kerrallaan. Kun purnukka on täynnä (H annosta), viimeisen annoksen tuonut mehiläinen herättää karhun ennenkuin poistuu paikalta. Seuraavat paikalle saapuvat mehiläiset jäävät odottamaan purnukan tyhjenemistä. Kun karhu on tyhjentänyt purkin, se päästää mehiläiset töihin ja käy itse nukkumaan.
   
   Ohjelmoi purnukan täyttö ja tyhjentäminen monitorin avulla. Esitä mehiläisprosessien (N kpl) ja karhuprosessin koodi. Selvitä vielä sanallisesti, missä tilanteissa tarvitaan poissulkemista ja synkronointia sekä kuinka ne toteutuvat ratkaisussasi.