581322 Rinnakkaisohjelmistot (2 ov)


Erilliskuulustelu 5.10.2004

1. Rinnakkainen suoritus (15 p)
  a)  Tarkastellaan seuraavaa ohjelmaa
       int  x= 0, y =4;
       co  while (x!=y)  x=x+1;
       //    while (x!=y)  y=y-1;
       oc
     Päättyykö ohjelman suoritus aina /joskus/ ei koskaan? Perustele vastauksesi. (5 p)
   b) Mitkä ovat lukkiutumistilanteen  (deadlock) syntymiselle välttämättömät ja riittävät ehdot ja
       miten kukin näistä ehdoista  täyttyy aterioivien filosofien ongelmassa?  Miten filosofien
       tapauksessa lukkiutuminen voitaisiin estää muuttamalla haarukoiden käyttösääntöjä? Tarkastele
       kutakin sääntöä erikseen. (10 p)

2.Tankkausta semaforipohjalta (15 p)
Pienellä  bensa-asemalla on vain yksi  bensapumppu ja sitä käyttämässä asemanhoitaja, joka täyttää
tankin  ja ottaa maksun. Kesäaikaan asemalla silloin tällöin on asiakkaita ihan ruuhkaksi asti.
Bensapumpun viereen mahtuu vain yksi auto kerrallaan. Muiden tankkausta haluavien on odotettava kauempana, 
kunnes tankattavana ollut auto on poistunut.  Auto voi poistua vasta, kun se on tankattu ja 
maksu suoritettu.  Laadi toimintakoodi tankkaamaan tuleville autoille  (prosesseille auto[i = 1 to N]) 
ja asemanhoitajalle (prosessille hoitaja), kun  tankkaavien autojen ja asemanhoitajan toiminnan
synkronointiin käytetään semaforia.

3.Tuottajien ja kuluttajien synkronointi monitoria käyttäen (15 p)
Tuottaja-  ja kuluttajaprosessien  välissä on rajallisen kokoinen puskuri (N alkiota), johon
 tuottajat tuottavat  tietoa alkio kerrallaan ja josta kuluttajat sitä vastaavasti noutavat. 
a) Missä tilanteissa tässä tarvitaan prosessien  poissulkemista ja synkronointia? Esitä sanallisesti,
   miten  monitoriratkaisusi selviää näistä tilanteista. (3 p)
b) Laadi  tuottaja- ja kuluttajaprosessien toimintaa koordinoiva monitori. (8 p)
c) Laadi tuottaja- ja kuluttajaprosessien koodit, joista selkeästi käy ilmi, kuinka prosessit  vievät
    tietoa puskuriin ja kuinka ne noutavat tietoa puskurista.(4 p)

4. Kommunikointi  sanomanvälitystä käyttäen.(15 p)
  Sääennustus  on toteutettu rinnakkaisena laskentana. Ennustettavan alueen ilmatila on jaettu
  kuutioihin ja kunkin  kuution ennusteesta huolehtii  yksi  solmukone.  Laskenta etenee
  vaiheittain:

 - Alkuarvoista lähtien kukin solmu laskee kuutiolleen ensimmäisen ennusteen (esimerkiksi sään tunnin kuluttua).
-  Kun ennuste on valmistunut, niin solmu ilmoittaa ennustetun tilan  naapureilleen. 
-  Saatuaan kaikilta naapureilta näiden ennusteet solmu aloittaa seuraavan vaiheen ja laskee
   seuraavan ennusteen (esim. säätilan kuutiossa seuraavan tunnin kuluttua).
   Näin jatketaan kunnes ennusteet on saatu halutulle aikavälille (esim. kolmen vuorokauden
   ennuste).
   Laskentaohjelmat kommunikoivat käyttäen sanomanvälitystä  ja globaaleja kanavia.

   Kirjoita yhden solmun laskenta-algoritmin  normaalivaiheen toimintaa ohjaavan ohjelman
   oleelliset osat (sovelluksen käynnistys- ja lopetusvaiheesta ei tarvitse  välittää). Esittele 
   kanavat ja  täsmennä send/receive -rutiinien synkronointisemantiikka (blocking vai non-blocking).



Muistin virkistämiseksi:

process foo  [i = 1 to n] {
    int sum = 0;
    int c [1:n] = ([n] 0);  # comment
    for [i = 1 to 10]  sum = sum + 1;
}

monitor M {
  declarations;
  procedure A ( formals) {
     body of A;
  }
  procedure B( formals) {
    body of B; 
  }
}


module S
    op op1 (int par1, type par2; result type out);
    op op2( );
body
     declarations;
     proc op1(par1, par2, out) {
         statements;
     }
    proc op2( ) {
         statements;
     }
    
    process Internal {
        statements;
   } 
end Server


module C
     op op1 (formals1), op2 (formals2);
body
    process P1 {
         declarations;
         while (true) {
             in   op1 (formals1) and B1 by e1 -> S1;
            [ ]   op2( formals2) and B2 by e2 -> S2;
             ni
           }
    }
end C