Other side in English

581332 Rinnakkaisohjelmointi, 4 op, erilliskuulustelu 20.1.2009

1. [9 p] Tarkastellaan allaolevaa Algoritmia 2.10. Oletetaan, että K:n arvo on 10.
    
                
    
   1. Voiko muuttujan n loppuarvo olla 10? Jos voi, niin anna siihen johtava skenaario. Jos ei voi, niin miksi ei.
   2. Voiko muuttujan n loppuarvo olla 11? Jos voi, niin anna siihen johtava skenaario. Jos ei voi, niin miksi ei.
   3. Voiko muuttujan n loppuarvo olla 0? Jos voi, niin anna siihen johtava skenaario. Jos ei voi, niin miksi ei.
   4. Voiko muuttujan n loppuarvo olla 1? Jos voi, niin anna siihen johtava skenaario. Jos ei voi, niin miksi ei.
   5. Mikä tässä on varsinainen ongelma ja miten se tulisi korjata, jotta muuttujan n loppuarvo olisi joka suorituskerralla 0?
   
    
2. [9 p] 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. [9 p] Mehiläisparvi, karhut ja IRR monitori. Mehiläisparvi (N mehiläistä) ruokkii loukkuun joutuneita karhuja (K 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 yksi 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.
   
   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 (K kpl) ja monitorin pseudokoodi. Selvitä vielä sanallisesti, missä tilanteissa tarvitaan poissulkemista ja/tai synkronointia sekä kuinka ne toteutuvat ratkaisussasi. Tee tarvittavat oletukset monitorin piirteistä ja kirjoita ne näkyville.
   
   
4. [9 p] Tarkastellaan liitteenä olevaa Ricart-Agrawalan algoritmia 10.2.
   1. Mikä on algoritmin tarkoitus? Mihin ongelmaan se on ratkaisu?
      Mikä on prosessien Main ja Receive merkitys? Mihin niitä tarvitaan?
      Voisiko ne yhdistää yhdeksi prosessiksi? Miten tai miksi ei?
      Mitkä tietorakenteet ovat yhteiskäyttöisiä ja mille kaikille prosesseille ne ovat yhteiskäyttöisiä?
   2. Mikä on deferred joukon merkitys ja miten se päivittyy? Miksi tarvitaan muuttujia requestCS?
      Voivatko eri prosessien myNum arvot olla samoja? Miksi ei tai miten ne käsitellään?
      
   3. Oletetaan, että kolme prosessia (p1, p2 ja p3) yrittävät nyt kaikki yhtä aikaa päästä kriittiseen vaiheeseen. Prosessien p1, p2 ja p3 myNum-arvot ovat 5, 10 ja 15. Lisäksi järjestelmässä on kaksi prosessia q1 ja q2, jotka eivät ole pyrkimässä kriittiseen vaiheeseen tällä hetkellä. Näytä, miten ja missä järjestyksessä prosessit p1, p2 ja p3 pääsevät kriittiseen vaiheeseen. Näytä erityisesti kaikki valitsemiseen liittyvät viestit (lähettäjä, vastaanottaja, viestin tyyppi, viestin sisältö) ja miten niihin reagoidaan?