581332 Rinnakkaisohjelmointi, 4 op, erilliskoe 3.6.2008

1. [9 p] Kriittinen alue (vaihe). Oletetaan, että monisäikeisen ohjelman yhteisessä muistissa olevien muuttujien X, Y ja Z käyttöä halutaan suojata kriittisen vaiheen avulla. Muuttujiin viitataan ohjelmassa viidessä kohtaa (koodinpätkät A, B, C, D ja E), joita kutakin voi olla samanaikaisesti suorittamassa usea ohjelman säie: 

   A: X <- 55   B: some1 <- X    C: X <- 5      D: Y <- 0    E: some4 <- X   
      Y <- 88      some2 <- Y       Z <- X+Y       
      Z <- X+Y     some3 <- Z

   Kohdissa A ja C muuttujien Y ja Z vanhat arvot eivät saa näkyä muille sen jälkeen kun X on saanut uuden arvon ja Z'n uuden arvon tulee olla X'n ja Y'n sen hetkisten arvojen summa. Kohdassa B muuttujien some1, some2 ja some3 uusien arvojen tulee olla X'n, Y'n ja Z'n arvot koodinpätkän suorituksen alkuhetkellä. 
   1. [3 p] Oletetaan, että kyseessä on yhden suorittimen laitteisto. Mitkä näistä (pseudo)koodinpätkistä (A, B, C, D ja E) tulee suojata kriittisenä alueena?  Miten tilanne muuttuu, jos suorittimia on useita ja säikeet voivat olla suorituksessa samanaikaisesti eri suorittimilla?
   2. [2 p] Anna yhden suorittimen laitteiston konkreettinen skenaario, jossa em. koodinpätkien kriittisten alueiden suojauksen puuttuminen aiheuttaa virhetilanteen. Selitä, mikä virhe syntyy ja erityisesti miksi virhe syntyy.
   3. [2 p] Oletetaan, että suorittimia on yksi kappale ja käyttöjärjestelmä vuorottelee säikeiden suoritusta aikaviipaleskeluduloinnin avulla. Näytä (pseudokooditasolla), kuinka edellämainitut kriittiset vaiheet suojataan järkevästi tässä ympäristössä. Perustele ratkaisun järkevyys.
   4. [2 p] Oletetaan, että suorittimia on useita ja että usea säie voi olla suorituksessa samanaikaisesti eri suorittimilla. Näytä (pseudokooditasolla), kuinka edellämainitut kriittiset vaiheet suojataan järkevästi tässä ympäristössä. Perustele ratkaisun järkevyys.
       
2. [9 p] Rinnakkaislaskennan koordinonti. Tietty rinnakkaislaskentaa hyödyntävä sovellus yhteistä muistia käyttävässä moniprosessorijärjestelmässä on toteutettu siten, että koordinoiva säie P antaa suuren määrän (T) tehtäviä laskettavaksi pienelle määrälle laskentasäikeitä Li (i=1,....,N). Huomaa siis, että T>>N (eli T on paljon suurempi kuin N). Kukin laskentatehtävä on määritelty pienen tietueen avulla ja tietueet on talletetaan muistiin. Koordinaattori P (i) antaa laskentasäikeille Li uusia tehtäviä laskettavaksi aika ajoin, (ii) odottaa, että ne on kaikki tehty ja (iii) siirtyy sitten laskennan seuraavaan vaiheeseen. Kukin laskentasäie Li (i) odottaa kunnes sille on saatavilla laskentatehtävä, (ii) suorittaa annetun tehtävän, (iii) tallettaa tuloksen muistiin, (iv) ilmoittaa tehtävän suorituksesta koordinoijalle, ja (v) siirtyy odottamaan seuraavaa laskentatehtävää. Voit olettaa, että virhetilanteita ei tapahdu ja että kaikki koordinaattorin kerralla antamat tehtävien määrittelyt (T kpl) mahtuvat muistissa olevaan puskuriin yhtä aikaa.
1. [6 p] Toteuta laskentatehtävien jakaminen laskentaprosesseille semaforien avulla tuottaja-kuluttaja -mallin mukaisesti. Esitä koordinoivan prosessin (P) ja laskentasäikeiden (Li) toiminta pseudokooditasolla. Muista esitellä kaikki semaforit alkuarvoineen.
2. [3 p] Koordinoivan säikeen tulee odottaa kaikkien laskentatehtävien loppuun saattamista, kunnes se siirtyy seuraavaan suoritusvaiheeseen. Esitä tämän odotuksen toteutus semaforien käyttöön perustuvalla puomisynkronoinnilla. Esitä koordinoivan prosessin (P) ja laskentasäikeiden (Li) toiminta pseudokooditasolla. Muista esitellä kaikki semaforit alkuarvoineen.
   
   Jos haluat, voit esittää molempien kohtien (a ja b) ratkaisut samalla kertaa.
   

 
3. [9 p]  Monitori. Oletetaan, että meillä on käytettävissä Signal and urgent wait (E<S<W) signalointisemantiikalla toteutettu monitori. Toteuta edellisen tehtävän ongelma (Rinnakkaislaskennan koordinointi) tällaista monitoria (M) käyttäen. Ainoastaan ongelmanratkaisun koordinointi tapahtuu monitorin sisällä.
   1. [6 p] Toteuta laskentatehtävien jakaminen laskentaprosesseille tuottaja-kuluttaja -mallin mukaisesti monitoria käyttäen. Esitä monitorin (M), koordinoivan prosessin (P) ja laskentasäikeiden (Li) toiminta pseudokooditasolla. Muista esitellä kaikki monitorin ehto- ja muut muuttujat alkuarvoineen.
   2. [3 p] Koordinoivan säikeen tulee odottaa kaikkien laskentatehtävien loppuun saattamista, kunnes se siirtyy seuraavaan suoritusvaiheeseen. Esitä tämän odotuksen toteutus monitorissa puomisynkronoinnilla. Esitä monitorin (M), koordinoivan prosessin (P) ja laskentasäikeiden (Li) toiminta pseudokooditasolla. Muista esitellä kaikki monitorin ehto- ja muut muuttujat alkuarvoineen.
      
      Jos haluat, voit esittää molempien kohtien (a ja b) ratkaisut samalla kertaa.

 
4. [9 p] Lukkiutuminen (deadlock)
   1. [3 p] Kerro täsmällisesti, mitkä neljä ehtoa tarvitsee täyttyä lukkiintumisessa.
   2. [2 p] Esittele aterioivien filosofien ongelma ja sille lukkiutuva ratkaisu. Selitä, miksi em. kaikki neljä ehtoa täyttyvät tässä tilanteessa.
   3. [4 p] Anna pääpiirteet neljään lukkiutumattomaan ratkaisuun aterioivien filosofien ongelmaan, yksi kutakin em. ehtoa kohden. Kukin lukkiutumaton ratkaisu perustuu siis siihen, että yksi em. ehdoista voidaan osoittaa olevan aina epätosi. Kerro kustakin ratkaisusta täsmällisesti, miksi se ei voi lukkiutua.