Other side in English

581332 Rinnakkaisohjelmointi, 4 op, erilliskoe 27.3.2007

1. [9 p] Monitorit
   1. Mikä on monitori? Mihin ongelmaan se on ratkaisu? Mitä etua monitoreilla on semaforeihin verrattuna? Mitä haittaa?
   2. Mitä monitorin signalointisemantiikka tarkoittaa? Mikä on IRR (Immeadiate Resumption Requirement, "Signal and Urgent Wait", E<S<W) signalointisemantiikka?
   3. Mikä ongelma liittyy monitorin signalointisemantiikkaan, jos IRR ei päde? Anna konkreettinen esimerkki, jossa signalointisemantiikka ilman IRR'ää johtaa virheelliseen tulokseen, mutta jossa IRR signalointisemantiikka toimisi.
       
2. [9 p] Lukkiutuminen (deadlock)
   1. Anna Aterioivien filosofien ongelmaan semaforeihin perustuva ratkaisu, jossa on lukkiutumisongelma. Anna lukkiutuva skenario.
   2. Kuinka Dijkstran lukkiutumisen havaitsemis -algoritmi (DDA, Deadlock Detection Algorithm) toimii pääpiirteissään? Sehän käyttää taulukoita A (allokaatio matriisi) ja Q (pyyntömatriisi) sekä vektoreita R (kaikki resurssit), V (vapaat resurssit) ja W (työvektori).
   3. Näytä, kuinka DDA'n avulla lukkiutuminen havaitaan a-kohdan esimerkissäsi.
       
3. [9 p] Linda.
   1. Mikä on Linda ja mihin sitä käytetään?
   2. Miten allaoleva Algoritmi 9.6 toimii? Minkälaiseen laskentaympäristöön se on tarkoitettu? Miten algoritmi päättyy?
   3. Muokkaa algoritmia 9.6 siten, että useankaan worker-prosessin kuoleminen missä vaiheessa tahansa ei vaaranna lopputuloksen oikeellisuutta.
      
4. [9 p] Yksikaistainen silta. Saareen johtaa kapea silta, jossa autot voivat ajaa vain yhteen suuntaan kerrallaan. Siltaa käyttävät autoprosessit kutsuvat proseduuria enter_bridge(suunta) pyrkiessään saareen vievälle sillalle ja proseduuria exit_bridge(suunta) poistuessaan sillalta. Parametri suunta tarkoittaa auton etenemissuuntaa (saareen, saaresta). Autoprosessien koodi on:

    process car[1 to N] {
            ...
            enter_bridge(suunta);
            aja_sillalla();
            exit_bridge(suunta);
            }

Esitä proseduurien enter_bridge() ja exit_bridge() koodi. Ratkaisun tulee perustua semaforien käyttöön, ja sen tulee sallia sillan tehokas käyttö, ts. sillalla voi olla useita samaan suuntaan eteneviä autoja kerrallaan. Vuoroaan odottavat autot pääsevät etenemään vasta kun kaikki toiseen suuntaan matkalla olevat autot ovat ylittäneet sillan. Ratkaisu ei siis ole reilu, koska odotusajat saattavat muodostua pitkiksi. Sillan päässä odottamassa olevat autoprosessit on päästettävä jatkamaan FCFS-järjestyksessä.