Yliopiston etusivulle Suomeksi På svenska In English
Helsingin yliopisto Tietojenkäsittelytieteen laitos
 

Tietojenkäsittelytieteen laitos

Suomeksi In English Laskuharjoitus

Huom: Kaikkien pitäisi kohtapuoleen olla jossakin opintopiirissä projektin tekemiseksi. Mailatkaa luennoijalle (teemu.kerola (at) cs.helsinki.fi) opintopiirinne jäsenten nimet (1-3 opiskelijaa). Jos haluatte, että luennoija ryhmittää teidät johonkin opintopiiriin, niin lähettäkää mailia asiasta 9.2.2011 mennessä.

Rinnakkaisohjelmointi, LH 2

  1. Tarkastellaan Dekkerin algoritmia (Alg. 3.10, s. 60). Algoritmin lopussa muuttujille turn ja wantp (tai wantq) annetaan uudet arvot. Voisiko ne antaa päinvastaisessa järjestyksessä (lause p10 ennen lausetta p9)? Todista johtopäätöksesi.
     
  2. Tehtävät 3.11 ja 3.12 oppikirjasta
     
  3. Tehtävä 4.1 oppikirjasta
     
  4. Tehtävät 5.1 ja 5.3 oppikirjasta.
    (Huom: Sanoin luennolla vähän huonosti, että algoritmi 5.1 toimii myös jos yhteenlasku ei ole atominen. Olisi pitänyt sanoa, että tämä ongelma on ratkaistavissa. Katsokaa kalvoa 26, jossa ratkaisu on esitetty algoritmin muutoksella.)
     
  5. [2 htp] Ohjelma PlusMinus. Meillä on yhteisessä muistissa 6 muuttujaa: X1, X2, X3, X4, Ctrl ja Sum. Kaikkien alkuarvo on nolla. Meillä on kaksi laskentaprosessia, jotka 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 (50, 50, 50, 50, 100 ja 200).

    Toteuta tämä BACI'lla, käyttäen synkronointiin ainoastaan (muita) yhteisiä muuttujia. Mahdolliset odotukset voi toteuttaa busy-wait -tyyppisinä looppeina: while (...) {};.
    Lopulta BACI'n prosessien hallinta antaa vuoron myös muille prosesseille, eli odotus ei ole ikuista.
    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?