Other side in English

581332 Rinnakkaisohjelmointi, 4 op, erilliskoe 23.9.2008

1. [9 p] Kriittinen alue (vaihe).  Meillä on neljä säiettä (A, B, C ja D), jotka suorittavat seuraavanlaisia koodeja. Me emme tiedä mitään suoritusnopeuksista - emme siis tiedä kuinka paljon aikaa kuluu eri semaforioperaatioiden välillä. Kaikkien semaforien (s1-s6) alkuarvo on 1. Semaforioperaatiothan ovat P (eli wait) ja V (eli signal).
   1. ... P(s1) ... P (s2) ... P(s3) ... V(s1) ... V(s3) ... V(s2) ...
   2. ... P(s2) ... P (s4) ... P(s5) ... V(s2) ... V(s4) ... V(s5) ...
   3. ... P(s5) ... P (s6) ... P(s1) ... V(s6) ... V(s1) ... V(s5) ...
   4. ... P(s5) ... P (s1) ... V(s1) ... P(s3) ... V(s5) ... V(s3) ...

   Kaikki neljä säiettä käynnistetään samalla kertaa ja ovat siis suorituksessa samanaikaisesti.

   1. Anna lukkiutuva skenaario ja siihen johtanut resurssien varauskaavio.
   2. Mikä ovat lukkiutumisen mahdollistavat neljä vaatimusta ja kuinka ne toteutuvat tässä?
   3. Lukkiutuuko systeemi joka suorituskerta vai ei? Jos kyllä, niin miksi? Jos ei, niin anna lukkiutumaton skenaario.
       
2. [9 p] Yksisuuntainen silta
   Kahden kylän A ja B välissä olevan joen yli kulkee niin kapea silta, että autot voivat ajaa sitä pitkin vain yhteen suuntaan kerrallaan. Kun sillalla kulkee autoja A:sta B:hen, niin B:stä A:han haluavien täytyy odottaa. Silta ei myöskään ole kovin vankka, joten sillalla saa olla korkeintaan 10 autoa yhdellä kertaa. 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);
       ylitä silta
       poistu_sillalta(suunta);
       ......
       }
   

   Tee semaforeja ja P- ja V-operaatioita 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ä.
    
3. [9 p] Spagettia monitorissa
   Pitkän pohdinnan jälkeen aterioivat filosofit (N kappaletta) olivat viimein oivaltaneet, että yhdelläkin haarukalla on mahdollista syödä spagettia ja jonkun aikaa harjoiteltuaan olivat oppineet käteviksi yhdellä haarukalla syöjiksi. Nyt kaikki pääsivät vaikka yhtä aikaa syömään eikä kenenkään tarvinnut odotella nälkäisenä. Tästä tosin syntyi uusi ongelma, sillä pöydällä oleva spagettikulho oli melkein aina typötyhjä. Tähänkin keksittiin ratkaisu: otettiin apupoika ruokapalkalla (spagettia!) huolehtimaan ruuanvalmistuksesta. Aina kun kulho on tyhjä, poika valmistaa lisää spagettia, täyttää filosofien ruokakulhon kukkuroilleen (M lautasellista) ja vie sen pöydälle. Sitten poika syö keittiössä kattilan pohjalta ja jää odottelemaan kulhon tyhjenemistä. Filosofit pääsevät taas normaalirutiiniinsa: syömään spagettia ja syömisen jälkeen ajattelemaan. Jokainen filosofi ottaa yhdellä syöntikerralla yhden lautasellisen. Jos kulho on tyhjä, filosofi herättää pojan valmistamaan lisää spagettia.
   
   Toteuta filosofit ja apupoika prosesseina, joiden toiminta synkronoidaan monitoria käyttäen. Kirjoita monitorin koodi sekä koodit filosofiprosesseille sekä apupoikaprosessille.
   
   
4. [9 p] Hajautettu poissulkemisongelma (mutex)
   Tarkastellaan liitteenä olevaa Ricart-Agrawalan algoritmia 10.2.
   1. Mikä on Main prosessin merkitys? Mikä on Receive prosessin merkitys? Mihin sitä tarvitaan? Voisiko sen yhdistää Main prosessiin? Mikä on deferred joukon merkitys?
   2. Oletetaan, että kolme prosessia (A, B ja C) yrittävät yhtä aikaa päästä kriittiseen vaiheeseen. Viimeksi kriittinen vaihe oli C:n hallussa ja sitä ennen B:n hallussa. Kuka pääsee seuraavaksi ja millä perusteella? Näytä, miten valinta tapahtuu. Näytä erityisesti kaikki valitsemiseen liittyvät viestit (lähettäjä, vastaanottaja, viestin tyyppi, viestin sisältö).
   3. Oletetaan nyt, että edellisessä kohdassa (b) mainittu prosessi on jo suorittanut kriittisen vaiheensa ja haluaa sinne uudelleen. Kuka (A, B vai C) nyt pääsee seuraavaksi kriittiseen vaiheeseen? Voiko se olla sama prosessi kuin edellisessä kohdassa?
   4. Voiko monelle prosessille tulla sama myNum-arvo? Jos voi, niin mikä estää useaa prosessia tällöin pääsemästä samaan aikaan kriittiseen vaiheeseen? Jos ei voi, niin miksi ei?