Tietojenkäsittelytieteen laitos

Rinnakkaisohjelmointi, LH 5

1. Tehtävä 6.6 oppikirjasta.
    
2. [2 htp] Yksisuuntainen silta semaforeilla. Kahden kylän A ja B välissä olevan joen yli kulkee niin kapea silta, että autot voivat ajaa sitä pitkin vain yhteen suuntaan (itään tai länteen) kerrallaan. Kun sillalla kulkee autoja A:sta B:hen, niin B:stä A:han haluavien täytyy odottaa. Jotta varmistetaan, että autot menevät sillalle vain kulloinkin sallitusta suunnasta, siltaa käyttävät autoprosessit kutsuvat proseduuria aja_sillalle(suunta) pyrkiessään sillalle ja sillalta poistuessaan proseduuria poistu_sillalta(suunta).

     Process auto[i = 1 to N] {
       .....
       aja_sillalle(suunta);     -- aja_sillalle_itään() tai aja_sillalle_länteen()
       ylitä silta
       poistu_sillalta(suunta);  -- poistu_sillalta_itään() tai poistu_sillalta_länteen()
       ......
       }
   

   Tee semaforeja ja P- ja V-operaatioita (wait ja signal) käyttävät koodit proseduureille aja_sillalle(suunta) ja poistu_sillalta(suunta). Ratkaisun ei tarvitse olla reilu, vaan autojen odotusajat saavat olla pitkiä. Kuitenkin samalta suunnalta tulevien autojen tulee päästä sillalle saapumisjärjestyksessä. Jos haluat, voi kokeilla algoritmejasi BACIssa, sijoittamalla ne silta-simulaattorin ratkaisurunkoon. (Tarkkaile simulointiaikana yhteisten muuttujien west_bound ja east_bound arvoja ja katso, että animoidulla "sillalla" on sopivasti autoja. Virittele parametreja sopivasti tarvittaessa. Jos sinulla on liikaa aikaa, voit virittää animointia fiksummaksi - ks. jBACI Concurrency Simulator User Guide)
   Toimiihan algoritmisi oikein ainakin seuraavissa eritystapauksissa:
   1. Ensimmäinen auto tulee yksin suuntaan A tai B.
   2. Sillalla 5 autoa suuntaan A ja paikalle tulee uusi auto suuntaan A tai B.
   3. Sillalla on 4 autoa suuntaan A, uusi auto tulee suuntaan B ja sitten heti perään toinen uusi auto tulee suuntaan A.
   4. Sillalla on autoja, jotka poistuvat jättäen sillan tyhjäksi. Toiseen suuntaa oli odottamassa autoja.
   5. Sillalla on autoja, jotka poistuvat jättäen sillan tyhjäksi. Uusi auto tulee suuntaan A tai suuntaan B.
   6. Muokkaa vastaustasi tilanteeseen, jossa sillan painorajoituksen vuoksi sille mahtuu kerrallaan vain 3 autoa.
       
3. Tee laskuharjoitusten 4 tehtävä 1 (PlusMinus BACI ohjelma) uudelleen siten, että prosessien synkronointiin käytetään monitoria.
   1. Tee ohjelmasta versio, jossa kriittisen vaiheen suojaus ei toimi. Miten tämä ilmenee?
   2. Tee ohjelmasta versio, jossa kriittisen vaiheen suojaus toimii oikein. Miten tiedät, että ohjelmasi toimii oikein? Perustele.
   3. Miten ohjelmasi muuttuisi, jos laskentaprosesseja olisikin 4 tai 10 kappaletta?
      Huom: sinun ei tarvitse muokata BACI-toteutusta 4 tai 10 laskentaprosessille, vaikka toki saat sen halutessasi tehdä.
   4. Olisiko hyödyllistä käyttää 10 laskentaprosessia? Miksi?
      Mikä olisi suurin hyödyllinen laskentaprosessien määrä? Miksi?
       
4. Tarkastellaan kirjan algoritmia 7.3 (s. 152). Huomaa typo algoritmissa.
   1. Mitä merkittäviä eroja algoritmilla 7.3 on luennolla esitetystä usean tuottaja/kuluttajan semaforipohjaisesta ratkaisusta (luento 6, kalvo 16; Andrews, Fig 4.5)? Kumpi on parempi/huonompi ja miksi?
   2. Mikä tarkoittaa käsite monitorin signalointisemantiikka?
   3. Algoritmi 7.3 perustuu IRR signalointisemantiikan. Anna skenaario, jossa algoritmi toimii väärin, jos signalointisemantiikkana olisi E=S=W.
   4. Kuinka algoritmia 7.3 tulee muuttaa, jos monitorin signalointisemantiikkana on E=S=W?