Other side in English

Rinnakkaisohjelmointi, kurssikuulustelu 14.12.2007

1. [10 p] Kriittinen vaihe
   1. Mitä tarkoittaa käsite kriittinen vaihe (critical section)? Anna mahdollisimman kattava määrittely.
   2. Milloin ja minkälaisessa ympäristössä olisi järkevää suojata kriittinen vaihe keskeytykset estämällä, eikä käyttäen test-and-set -käskyä tai semaforia? Miksi?
   3. Milloin ja minkälaisessa ympäristössä olisi järkevää suojata kriittinen vaihe test-and-set -käskyllä, eikä käyttäen keskeytysten estoa tai semaforia? Miksi?
   4. Milloin ja minkälaisessa ympäristössä ei olisi järkevää suojata kriittinen vaihe test-and-set -käskyllä? Miksi?
   5. Oletetaan, että laitteistossasi ei olekaan test-and-set -käskyä, vaan ainoastaan fetch-and-add -käsky, jonka atominen toiminta on seuraavanlainen

      fetch-and-add (common, local, x) is
        local <- common
        common <- common+x

      Toteuta kriittisen vaiheen suojaaminen fetch-and-add -käskyn avulla. Anna algoritmit kilpaileville prosesseille p ja q. Esitä selkeästi, mikä muuttujat ovat yhteisiä ja mitkä paikallisia kullekin prosessille.

2. [10 p] Tahdistusta sanomilla. Laskenta on jaettu rinnakkaisuuden saavuttamiseksi N:lle eri prosessille, kukin omassa solmussaan. Prosessien välinen kommunikointi perustuu kanavien kautta tapahtuvaan sanomanvälitykseen. Laskentaan ohjelmoidaan vikasietoisuutta varten joukko tahdistuspisteitä - jos jotain mene pieleen, laskentaa voidaan aina jatkaa viimeksi talletetusta tahdistuspisteestä. Aina kun prosessin suoritus saapuu tahdistuspisteeseen, se tallettaa sen hetkisen tilatietonsa levylle. Suoritus saa jatkua laskennan seuraavaan vaiheeseen vasta, kun kaikki prosessit ovat saaneet tämän tarkistuspisteen tilan talletuksen valmiiksi.
   
   Tehtävässä ei tarvitse huomioida kuinka laskentaa jatketaan jostakin talletetuspisteestä mahdolliseen virheen ilmaantuessa. Tehtävässä keskitytään ainoastaan prosessien synkronointiin tahdistuspisteiden tallettamiseksi.
   
   Määrittele kommunikoinnissa tarvittavat kanavat ja kirjoita tahdistukseen tarvittavat koodin osat.

 
3. [10 p]  Mehiläisparvi semaforissa. 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.
   
   Mehiläiset voivat täyttää hunajapurkkia samanaikaisesti, mutta purkkiin ei saa tulla enempää kuin H annosta hunajaa.
   
   Ohjelmoi purnukan täyttö ja tyhjentäminen semaforien avulla. Esitä mehiläisprosessien (N kpl) ja karhuprosessin koodi. Selvitä vielä sanallisesti, missä tilanteissa tarvitaan poissulkemista ja/tai synkronointia sekä kuinka ne toteutuvat ratkaisussasi.
    
4. [10 p] Pikkukysymyksiä (max puolen sivun vastaus per kohta)
   1. Miksi rinnakkaisohjelman toimivuutta on vaikea analysoida? Kun virhe ilmenee, niin normaali virheen paikallistamistapa on suorittaa koodia uudelleen lähelle virheen ilmaantumiskohtaa ja tutkia ohjelmiston kehitysympäristössä kaikki tietorakenteet virheellisen koodin paikallistamiseksi. Mikä tässä on vaikeata?
   2. Miten rinnakkaisohjelma voidaan osoittaa määrittelyjensä mukaan oikein toimivaksi?
      Miten koodin virheellisyys voidaan pätevästi todistaa?
   3. Mitä tarkoittaa käsite viestikapulan välitys (baton passing) samanaikaisuuden hallinnassa? Miksi ja milloin sitä tarvitaan? Miten se toteutetaan?
   4. Miten rinnakkaisohjelman ratkaisu suojatuilla olioilla (protected objects) eroaa monitori-ratkaisusta? Anna hyvä esimerkki.
   5. Minkä rinnakkaisohjelmoinnin ongelman tapahtumamuisti (tapahtumaperustainen muisti, transaction memory) ratkaisee ja kuinka tapahtumamuisti pääpiirteissään toimii?