Tietojenkäsittelytieteen laitos

Laskuharjoitus

Rinnakkaisohjelmointi, S2007, LH 4

Nämä tehtävät käsitellään harjoituksissa viikolla 47, 19-23.11.2007.

Ohjelma PlusMinus. Yhteisessä muistissa on 6 muuttujaa: X1, X2, X3, X4, Ctrl ja Sum. Kaikkien alkuarvo on nolla. Viisi laskentaprosessia suorittavat 50 kertaa loopin, jonka kriittinen vaihe on:

• Jos muuttujan Ctrl arvo on pariton, vähennä kustakin Xi'stä luku 1. Muutoin lisää niihin luku 2.
• Lopuksi lisää 1 muuttujaan Ctrl ja laske muuttujien Xi summa muuttujaan Sum.

Kun laskentaprosessit ovat lopettaneet, tulostetaan kaikkien kuuden muuttujan arvot.

1. Tee BACI'lla ohjelmasta PlusMinus semaforeihin perustuva versio, jossa kriittisen vaiheen suojaus toimii oikein.
   Kun toteutat tämä BACI'lla, käytä synkronointiin BACIn semaforeja.
   Miten tiedät, että ohjelmasi toimii oikein? Perustele.
    
2. Näytä, että lukkiutumisen neljä ehtoa täyttyvät risteysesimerkissä (ks. Fig. 6.1 [Stall05], tai luento 5 kalvo 5).
    
3. Tarkastellaan lukkiutumisen välttämistä pankkiirin (Banker) algoritmin avulla (ks. Fig. 16.11 [Bacon93], tai luento 5 kalvot 33-34)
   1. Prosessi P2 pyytää vapaana olevaa resurssia R5. Voiko sen antaa ilman lukkiutumisvaaraa?
   2. Prosessi P4 pyytää vapaana olevaa resurssia R5. Voiko sen antaa ilman lukkiutumisvaaraa?
      
   
    
4. [2 htp] 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. 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. Ratkaisun ei tarvitse olla reilu, ts. odotusajat saavat
muodostua pitkiksi. Sillan päässä odottamassa olevat autoprosessit on päästettävä
jatkamaan FCFS-järjestyksessä.

 

---

Teemu Kerola 06.11.2007 13:12