Tietojenkäsittelytieteen laitos

Laskuharjoitus

Rinnakkaisohjelmointi, LH 4

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. [2 htp] 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.
   1. Tee ohjelmasta versio, jossa kriittisen vaiheen suojaus ei toimi. Miten tämä ilmenee?
   2. Tee ohjelmasta versio, jossa kriittisen vaiheen suojaus toimii oikein. Miten tiedät, että ohjelmasi toimii oikein? Perustele.
   3. Miten ohjelmasi muuttuisi, jos laskentaprosesseja olisikin 4 tai 10 kappaletta?
      Huom: sinun ei tarvitse muokata BACI-toteutusta 4 tai 10 laskentaprosessille, vaikka toki saat sen halutessasi tehdä.
   4. Olisiko hyödyllistä käyttää 10 laskentaprosessia? Miksi?
      Mikä olisi suurin hyödyllinen laskentaprosessien määrä? Miksi?
       
2. Risteys.
   1. Näytä, että lukkiutumisen neljä ehtoa täyttyvät risteysesimerkissä (ks. Fig. 6.1 [Stall05], tai luento 5 kalvo 8).
   2. Anna jokaiselle ehdolle esimerkki, kuinka sen toteutuminen voitaisiin estää. Koeta tehdä esimerkit sellaisiksi, että niissä estetään vain yhden ehdon toteutuminen, mutta muut ehdot voivat silti toteutua.
       
3. Tarkastellaan lukkiutumisen välttämistä pankkiirin (Banker) algoritmin avulla (ks. Fig. 16.11 [Bacon93], tai luento 5 kalvot 44-45)
   1. Prosessi P2 pyytää vapaana olevaa resurssia R5. Voiko sen antaa ilman lukkiutumisvaaraa? Miksi?
   2. Prosessi P4 pyytää vapaana olevaa resurssia R5. Voiko sen antaa ilman lukkiutumisvaaraa? Miksi?
      
   
    
4. Meillä on seuraavat aliohjelmat, joiden toiminnat ovat sidoksissa toisiinsa:
   1. Aliohjelma PrintOut (Pr, Db, ...) tarvitsee suorituksensa aikana tulostimen Pr ja varaa tietokannan Db itselleen.
   2. Aliohjelma Update (Db, ...) varaa tietokannan Db itselleen.
   3. Aliohjelma Combine (Db1, Db2, Db3, ...) varaa tietokannat Db1, Db2 ja Db3 suorituksensa ajaksi.

Toteuta näiden aliohjelmien keskeinen synkronointi semaforien avulla, kun käytössä on tietokannat Payroll, Personnel, Customers ja Inventory.

1. Perustele, miten ratkaisusi toteuttaa em. funktionaalisuusvaatimukset.
2. Perustele, miksi poissulkemisongelmaa ei ilmene.
3. Perustele, miksi ratkaisusi ei johda lukkiutumiseen.
4. Perustele, miksi ratkaisusi ei johda nälkiintymiseen.
5. Miksi tehtävänasettelu on epärealistinen? Anna ainakin kaksi syytä.
    

---

Teemu Kerola 27.11.2009 12:43