581332 Rinnakkaisohjelmointi, välikoe 29.2.2012                      Other side in English

1. [5 p] Monisäikeinen ohjelma moniytimisessä järjestelmässä. Muuttujat x, y ja z ovat yhteisessä muistissa. Koodinpätkä Code1 toteuttaa (korkean tason kielen) lausekkeen "x=x+y" ja Code2 lausekkeen "x=x-z".
1. [1.5 p] Anna virheelliseen lopputulokseen johtava skenaario, jossa kolme säiettä suorittaa yhtäaikaa koodinpätkää Code1 sisältävää koodia. Muuttujien alkuarvot ovat x=100 ja y=10, jolloin oikea lopputulos olisi x=130.
2. [1.5 p] Anna virheelliseen lopputulokseen johtava skenaario, jossa kaksi säiettä suorittaa yhtäaikaa siten, että yksi suorittaa koodinpätkää Code1 sisältävää koodia ja toinen koodinpätkää Code2 sisältävää koodia. Muuttujien alkuarvot ovat x=100, y=10 ja z=1, jolloin oikea lopputulos olisi x=109.
3. [2 p] Kuinka koodinpätkät Code1 ja Code2 tulee suojata, jotta lopputulos on kaikissa mahdollisissa skenaariossa oikein. Anna yksityiskohtainen toimiva ratkaisu. Perustele ratkaisusi oikeellisuus.


2. [5 p] Lukkiutuminen. Meillä on kolme säiettä (A, B ja C) ja neljä resurssityyppiä (r, s, t ja u). Kutakin resurssia voi käyttää kerrallaan vain yksi säie. Resursseja r, s ja t on yksi kappale ja resurssia u kaksi kappaletta. Säie A käyttää (jossain järjestyksessä) resursseja r ja s, säie B käyttää resursseja s, t ja u, ja säie C käyttää resursseja r, t ja u. Säikeet eivät voi "varastaa" resursseja muilta säikeiltä ja ne varaavat resurssit yksi kerrallaan.
1. [1.5 p] Anna lukkiutumiseen johtava resurssien varaamisskenaario. Perustele, miksi lukkiutumistilanne vallitsee skenaariosi lopputilanteessa.
2. [2 p] Miten Dijkstran algoritmi pääpiirteittäin toimii ja kuinka se havaitsee lukkiutumisen kohdassa (a) antamassasi skenaariossa?
3. [1.5 p] Pankkiirin algoritmia ei tässä tapauksessa voi käyttää, mutta lukkiutumisen voi silti estää ennakolta, kun siihen osataan varautua. Millä periaatteella lukkiutuminen voidaan tässä tapauksessa ennakolta estää ja mitä muutoksia säikeiden ohjelmakoodiin tulisi tämän periaatteen mukaisesti tehdä? Selitä pseudokooditasolla, kuinka lukkiutumisen estävä muutos toteutetaan resurssien varaamisessa kohdassa (a) antamassasi skenaariossa.
   


3. [5 p] Torikauppias. Torikauppias tuo aika ajoin uuden pussillisen omenoita (25-30 omenaa) myyntikoriin, johon mahtuu 200 omenaa. Torikauppias ei kaada uutta pussillista koriin, ellei koko pussillinen mahdu sinne. Asiakkaat (N kpl) tulevat silloin tällöin paikalle ja ostavat korista 1-5 omenaa kerrallaan. Asiakkaat odottavat, jos tarvittavaa määrää omenia ei ole saatavilla. Asiakkaat palvellaan saapumisjärjestyksessä.
   
   Selitä edellä esitetty synkronointiongelma ja ratkaise se semaforien avulla. Anna ratkaisussasi (a) kauppiaan ja (b) asiakkaan pseudokoodit. Muista määritellä käyttämäsi semaforit ja kertoa niiden alkuarvot.
   
   Huom: Voit käyttää pseudokoodissasi funktiota Random(i,j), joka palauttaa satunnaisen arvon suljetulla välillä [i,j].