Other side in English

581332 Rinnakkaisohjelmointi (4 op), erilliskuulustelu 7.4.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] Lukkiutuminen. Järjestelmässä S on viisi resurssia: suuri muistialue A (2 kpl) tiedon prosessointiin, tietokanta B (1 kpl), tietokanta C (1 kpl), tulostimet D (2 kpl) ja näppäimistön käyttö E (1 kpl). Kutakin resurssia voi käyttää vain yksi prosessi kerrallaan.
   
   Järjestelmässä on neljä prosessia, P1-P4. P1:llä on hallussaan yksi kpl resursseja A, C ja D. P2:lla on hallussaan yksi kpl resursseja A ja B. P3:lla on hallussaan yksi kpl resurssia D. P4:lla ei ole hallussaan mitään resursseja.
   
   Juuri nyt edetäkseen P1 tarvitsee yhden kpl resursseja B ja E, P2 tarvitsee yhden kpl resursseja C ja E, P3 tarvitsee 1 kpl resurssia E ja P4 tarvitsee yhden kpl resursseja A, C ja E.
    
   1. Mitä lukkiutuminen tarkoittaa? Mitä tarkoittaa se, että järjestelmä ei ole lukkiutunut?
   2. Milloin järjestelmä voi lukkiutua?
   3. Onko järjestelmä S lukkiutumistilassa vai ei?
   4. Kuinka järjestelmän S lukkiutumisen olemassaolo tarkastettaisiin Dijkstran lukkiutumisen havaitsemis -algoritmin (DDA, Deadlock Detection Algorithm) avulla? Sehän käyttää taulukoita A (allokaatio matriisi) ja Q (pyyntömatriisi) sekä vektoreita R (kaikki resurssit), V (vapaat resurssit) ja W (työvektori).
   5. Miten lukkiutumisen synnyn voisi estää ennakolta (yleensä ja erityisesti tässä tapauksessa)
       
3. [9 p] Monitorit
1. Mikä on monitori? Mihin ongelmaan se on ratkaisu? 
2. Mitä etua monitoreilla on semaforeihin verrattuna? Anna esimerkki.
   Mitä etua semaforeilla on monitoreihin verrattuna? Anna esimerkki.
3. Mitä monitorin signalointisemantiikka tarkoittaa?
   Mikä on IRR (Immeadiate Resumption Requirement, "Signal and Urgent Wait", E<S<W) signalointisemantiikka?
   Miten IRR eroaa käytännössä esimerkiksi Javan signalointisematiikasta (E=W<S)?
4. Mikä ongelma liittyy monitorin signalointisemantiikkaan, jos IRR ei päde? Anna konkreettinen (pseudokoodi) esimerkki, jossa signalointisemantiikka ilman IRR'ää johtaa virheelliseen tulokseen, mutta jossa IRR signalointisemantiikka toimisi.
   
   
4. [9 p] 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 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 (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ä. Päästä autot sillalle saapumisjärjestyksessä.