581332 Rinnakkaisohjelmointi, 4 op, erilliskoe 8.4.2008

1. [9 p] Kriittinen alue (vaihe). Oletetaan, että monisäikeisen ohjelman yhteisessä muistissa olevien muuttujien X, Y ja Z käyttöä halutaan suojata kriittisen vaiheen avulla. Muuttujiin viitataan ohjelmassa kuudessa kohtaa, koodinpätkissä A, B, C, D, E ja F: 

   A: X <- 78   B: some1 <- X  C: Y <- 87  D: Y <- Y+1  E: some4 <- X   F: some5 <- Y
      Y <- 49      some2 <- Y                                              Y <- 0
      Z <- X+Y     some3 <- Z

   Kohdassa A muuttujien Y ja Z vanhat arvot eivät saa näkyä muille sen jälkeen kun X on saanut uuden arvon ja Z'n uuden arvon tulee olla X'n ja Y'n uusien arvojen summa. Kohdassa B muuttujien some1, some2 ja some3 uusien arvojen tulee olla X'n, Y'n ja Z'n arvot koodinpätkän suorituksen alkuhetkellä. Kohdassa F muuttujan Y vanha arvo ei saa olla saatavilla sen jälkeen kun se on kopioitu muuttujaan some5.
   1. [3 p] Mitkä näistä (pseudo)koodinpätkistä (A, B, C, D ja E) tulee suojata kriittisenä alueena?  Erityisesti, tarvitaanko kohtia C tai D suojata, koska niissä muutetaan ainoastaan yhden muuttujan arvo? Entä kohta E, jossa vain luetaan yhden muuttujan arvo? Entä kohta F, jossa luetaan yhden muuttujan vanha arvo ja nollataan se sitten?
   2. [2 p] Anna skenaario, jossa kriittisen alueen (A, B, ...) suojauksen puuttuminen aiheuttaa virhetilanteen. Selitä, mikä virhe syntyy.
   3. [2 p] Näytä (pseudokooditasolla), kuinka kriittiset vaiheet (A, B, ...) suojataan busy-wait -loopissa (esim test-and-set -käskyn avulla). Millaisessa laskentaympäristössä tämä olisi järkevä ratkaisu? Miksi?
   4. [2 p] Näytä (pseudokooditasolla), kuinka kriittiset vaiheet (A, B, ...) suojataan monitorin avulla. Millaisessa laskentaympäristössä tämä olisi järkevä ratkaisu? Miksi?
       
2. [9 p] Puomisynkronointi (barrier synchronization) ja kommunikointi semaforien avulla. Kuvankäsittelyohjelmassa on usea laskentasäie, joista kukin muokkaa (K*K pikselin kokoisen) pienen alueen kokonaiskuvasta (N*M pikseliä). Pääohjelma pyytää käyttäjältä kuvankäsittelykomennon parametreineen ja antaa kuvankäsittelyn toteutuksen laskentasäikeille. Itse kuva on yhteisessä muistissa, laskentasäikeitä on P kappaletta ja suorittimia on S kappaletta. Pääohjelma saa jälleen kontrollin, kun kaikki laskentasäikeet ovat saaneet tehtävänsä suoritettua. Synkronisointi pääohjelman ja laskentasäikeiden välillä tapahtuu semaforeilla. Pääohjelma antaa laskentasäikeen tehtävänmäärittelyn kaikille säikeille yhteisen muistialueen kautta, jonne myös laskentasäikeiden tulokset talletetaan. Voit olettaa, että virhetilanteita ei tapahdu.
1. [6 p] Näytä kuinka pääohjelman ja laskentasäikeiden välinen kontrolli ja kommunikointi toteutetaan semaforien ja yhteisen muistin avulla? Esitä pääohjelma ja laskentasäikeet pseudokooditasolla. Muista esitellä kaikki semaforit alkuarvoineen.
2. [3 p] Oletetaan nyt, että muutamat laskentasäikeet voivat epäonnistua laskennassaan (esimerkiksi laskennan aikana tarvitaan tietoja joltain vähän epäluotettavalta palvelimelta). Kuinka tähän voisi varautua? Esitä vastaus sanallisena selityksenä (pseudokoodia ei tarvita)
   
   
3. [9 p] Lukkiutuminen (deadlock)
   1. Anna konkreettinen esimerkki lukkiumisesta. Kerro, mitkä neljä ehtoa tarvitsee täyttyä lukkiintumisessa ja kuinka ne täyttyvät esimerkissäsi.
   2. Kuinka Dijkstran lukkiutumisen havaitsemis -algoritmi (DDA, Deadlock Detection Algorithm) toimii pääpiirteissään? Minkä ongelman se täsmällisesti ratkaisee? Päättyykö algoritmi aina? Mitä algoritmin päättymisen jälkeen tehdään? Algoritmihan käyttää taulukoita A (allokaatio matriisi) ja Q (pyyntömatriisi) sekä vektoreita R (kaikki resurssit), V (vapaat resurssit) ja W (työvektori).
   3. Kuinka Dijkstran pankkiirin algoritmi (Banker's Algorithm) pääpiirteissään toimii? Minkä ongelman se täsmällisesti ratkaisee? Mitä tietoja se tarvitsee ja mistä nämä tiedot saadaan? Päättyykö algoritmi aina? Mitä algoritmin päättymisen jälkeen tehdään?
       
4. [9 p]  Mehiläisparvi ja monitori. 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 kuljettavat hunajaa purnukkaan annos 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.
   1. [6 p] Ohjelmoi pseudokooditasolla purnukan täyttö ja tyhjentäminen monitorin avulla. Esitä mehiläisprosessien (N kpl) ja karhuprosessin koodi. Selvitä vielä sanallisesti, missä tilanteissa tarvitaan poissulkemista ja/tai synkronointia sekä kuinka ne toteutuvat ratkaisussasi. Muista mainita monitorisi signalointisemantiikka ja kuinka se vaikuttaa ratkaisuusi. Ilmaise koodissa selkeästi purnukan täyttötapahtuma.
   2. [3 p] Meillä on lisävaatimus: Mehiläiset voivat täyttää hunajapurkkia samanaikaisesti (siinä on hyvin suuri suuaukko), mutta purkkiin ei saa tulla enempää kuin H annosta hunajaa. Perustele, miksi edellisen kohdan (a) ratkaisusi toimii jo tällä tavoin, tai anna uuden vaatimuksen mukainen ratkaisu.