581322 Rinnakkaisohjelmistot (2 ov)

Erilliskuulustelu 5.10.2004

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)
Vastaus:
Suoritus joskus päättyy ja joskus ei pääty. Päättyminen riippuu prosessien ajoituksesta.

Merkintä co // oc suoritetaan rinnakkain, eikä eri haarojen ajoitusta ole mitenkään määritelty..
Missä tahansa tilanteessa, jossa x:n ja y:n ero eli |x-y| = 1, voi sattua niin, että kumpikin prosessi tahollaan toteaa eroa olevan ja x kasvattaa ja y vähentää itseään yhdellä ja tuloksena on taas sama ero, mutta nyt niin että x > y . Prosessi ei pääty, vaan kumpikin jatkaa toimintaansa x kasvattaa itseään ja y vähentää itseään ja ero vain kasvaa. Esimerkisi tilanteessa x=2 ja y=3 x ja y kumpikin toteavat , että x!=y ja toimivat niin kuin niiden pitää: x:= 3 ja y :=2. Taas on eroa ja x:=4 ja y:=1 ja näin ero vain kasvaa loputtomiin.
Tilanteessa x= 2 ja y = 4, samanlainen ajoitus taas johtaisi tilanteeseen: x:=3 ja y:=3, jonka jälkeen kumpikin tyytyväisenä lopettaa.

Arvostelusta:

5 pistettä on saanut sekä esittämällä esimerkin, jossa suoritus joskus päättyy ja joskus ei, että perustelemalla asian riittävän tarkkaan sanallisesti
3-4 p jos asia on esitetty hieman puutteellisesti
“joskus päättyy, joskus ei, koska arvot eivät välttämättä kohtaa” => 2p, koska vain vihjaillaan syystä.
“saattaa käydä niin, ettei yhtäsuurta arvoa saavuteta” => 1 p, koska ei mitään perusteluja

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
Vastaus:
Välttämättömät ja riittävät ehdot:

resurssia saa kerrallaan käyttää vain yksi (mutual exclusion) ja resursseja ei ole riittävästi kaikille
jo varattuja resursseja ei luovuteta pois puuttuvia odotettaessa (wait and hold)
resursseja ei saa myöskään otta pois väkisin (no preemption
Näiden staattisten ehtojen lisäksi dynaaminen edellytys: syntyy odotussilmukka, jossa jokainen odottaja odottaa jotain muiden odottajien hallussa pitämiä rerursseja.
Filosofien tapauksessa:

kutakin haarukkaa saa käyttää vain yksi => yhteiskäyttöiset haarukat (lisää kertakäyttöhaarukoita)
ei luovuta jo kädessää olevaa haarukkaa odottaessaan toista => molemmat haarukat saatava haltuun samalla kertaa
naapurilta ei saa riistää haarukkaa => filosofeille prioriteetit (kuka saa riistää keneltä haarukan)
varataan haarukat aina samassa järjestyksessä (esim. vasen ensin) => joku filosofi toimii toisin kuin muut (eli varaa ensin oikean)
Arvostelusta:

4 ehtoa a' 1 p
4 ratkaisua filosofien ongelmassa a' 1 ½ p
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.
Eräs ratkaisu:
Auton odotettava:
- pumpulle ajamista
- tankkauksen valmistumista
Asemanhoitajan on odotettava:
- tankattavaa autoa
- maksua
=> kutakin odottamista varten tarvitaan oma semafori.
Aluksi sallittua on vain yhden auton ajaminen pumpulle, joten vain sillä semaforilla on alkuarvo 1, muiden alkuarvo on 0.
```
sem pumppu_vapaa =1,  # mutex-tyyppinen; valvoo, että vain yksi auto on kerrallaan tankkaamassa
    auto_pumpulla = 0,  # tankkaustoiminnan synkronointia varten: tankkaamisen voi aloittaa 
    tankattu_on = 0,   # tankkaustoiminnan synkronointia varten: tankkaus on valmis 
    maksu = 0;        # asemanhoitaja odottaa maksua (jonka jälkeen voi häipyä muihin
                       # hommiin siihen asti kunnes seuraava auto tulee tankattavaksi)

process auto[i=1 to N]  {     # autoja N kappaletta
   while true {
      ajele ympäriinsä, kunnes tarvitsee tankata
      P(pumppu_vapaa);  # tässä jäädään odottamaan, jos pumppu on varattu 
      aja bensapumpulle tankkaamaan;
      V(auto_pumpulla);  # herätetään  asemanhoitaja toimimaan
      P(tankattu_on); # odotellaan, että tankkaus valmistuu
      maksetaan; 
      V(maksu);  # maksettu on 
      aja pois tankkausalueelta;   
      V(pumppu_vapaa);  # päästä seuraava auto tankkaamaan, joko jo 
                        #odottava tai joskus tuleva 
    }

       
process asemanhoitaja {
    while true {
      P(auto_pumpulla); # odottele tankkaamaan tulevaa autoa
      tankkaa auto;
      V(tankattu_on);  # ilmoita tankkauksen valmistumisesta
      P(maksu);  #  jää odottamaan maksua
    }
    
```
Arvostelusta:
Koska pyydettiin käyttämään semaforia, niin muut ratkaisut (monitori, sanomanvälitys, yms) toivat 0 pistettä!
- semaforien määrittelyt ja alkuarvot sekä semaforin käyttö
  - alkuarvon puuttuminen -1 p
    - väärä alkuarvo voi johtaa toiminnalliseen virheeseen => pisteitä putoaa enemmän
  - muita kuin P- ja V-operaatioita -2 p
- toiminnan oikeellisuus = P- ja V-operaatioiden oikeat kohdat ja järjestys
  - toimintojen synkronointi (-2 - -3 p)
    - usea auto pääsee samaan aikaan tankkausalueelle
    - asemanhoitaja lorottta bensaa, vaikka autoa ei ole paikalla
    - päästää pois, vaikka ei ole maksanutkaan
    - lähtee pois, vaikka ei vielä ole tankannut
  - lukkiutuminen (-2 p)
    - väärän alkuarvon takia
    - koska odottamaan menevä ei vapauta mutexia
    - P- ja V-operaatiot väärässä järjestyksessä => lukkiutuminen
  - päivitystä ei suojata mutexilla -1 - -2 p
  - määrittelemättömiä muuttujia, selittämättömiä operaatioita -1 - -2 p
- tehokkuus = turhan monimutkaiset ratkaisut
  - turhat jonot ja semaforit -1- -3p (yleensä nämä eivät edes toimineet!)
Tehtävä oli kuitenkin melko hyvin osattu. Siitä sai täydet pisteet peräti kahdeksan opiskelijaa.
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.

Missä tilanteissa tässä tarvitaan prosessien poissulkemista ja synkronointia? Esitä sanallisesti, miten monitoriratkaisusi selviää näistä tilanteista. (3 p)

Vastaus:
- poissulkemista tarvitaan puskurin käyttöön ( lähinnä osoittimien tutkimiseen ja päivittämiseen). Monitori huolehtii itse poissulkemisesta eli vain yksi kerrallaan pääsee monitoriin.
- Synkronointia tarvitaan tuottajan ja kuluttajan toimintojen tahdistamiseen: kuluttaja ei lue tyhjää puskuria, tuottaja ei vie mitää täyteen puskuriin. Tämä on hoidettava sopivilla signal- ja wait- toiminnoilla.
Arvostelusta:
- poissulkeminen 1.5 p;
- synkronointi 1.5 p
b) Laadi tuottaja- ja kuluttajaprosessien toimintaa koordinoiva monitori. (8 p)
```
	
monitor puskuri {
   typeT pusk[N]; # N on puskurin koko 
   int  alku =0;  # puskurin alkuun
   int  loppu = 0; # puskurin loppuun eli ensimmäiseen tyhjään slotiin
   int  lkm =0;  # alkioiden (= tuotosten)  lukumäärä  puskurissa
       cond  mahtuu;  # lkm < N
       cond voi_ottaa;  # lkm > 0
      
     procedure vie (int  data) {
        while (count = = N) wait(mahtuu);
        pusk[loppu] = data; 
        loppu = (loppu + 1) % N;
        lkm ++;
        signal(voi_ottaa);
    }
 
 int procedure hae ( ) {
       int apu;
        while (count = =0) wait(voi_ottaa);
        apu = pusk[alku]; 
        alku= (alku  + 1) % N;
        lkm -- 
        signal(mahtuu);
        return apu;
    }  
  
```
Ratkaisu löytyy myös kurssikirjasta sivulta 214.
Arvostelusta:
- ~ 4 p monitorin perustoiminnasta
  - monitorin ja cond-muuttujien määrittely sekä proseduurien määrittelyt
  - wait- ja signal -operaatiot
- ~ 4 p monitorin käytöstä tässä tilanteessa (= tuottaja-kuluttaja + rajallinen puskuri)
  - if whilen tilalla -1 p
  - pelkkä laskurimuuttuja, ei puskurin osoittimia -2 p
  - osoittimien päivitys virheelistä -1p
  - wait ja signal väärissä kohdissa -1 - -2 p
  - turha mutex monitoriin -1 p
  - wait -lukitus alussa -1 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)
Eräs ratkaisu:
```
process tuottaja[i=1 to N] {
  int data;
  while true {
       data = tuotettu_uusi_tieto( );
       call  pusk.vie(tieto);
     }
}


process kuluttaja[i=1 to M] {
  int data;
  while true {
  data =  call  pusk.hae(tieto);
  kuluta(data);
    }
}  
```
Arvostelusta:
- call puuttuu -0.5 p
- monitorin nimi puuttuu -1p
- ei useita prosesseja -0.5 p
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).
Ratkaisu:
```
globaalit määrittelyt


typedef    ennuste   .... ;         #
sääennustetietue
chan mailbox[N,N] (sääennuste
arvo)
# kanavalla  mailbox[i,j] kulkevat
sanomat  prosessilta i prosessilta j


process P[i=0 to N-1]  {
   int maxlkm           #  vaiheiden
lukumäärä
   ennuste  arvo[N];
  /* alustukset
     ....
 */


  for [phase = 1 to maxlkm] {
  /*  laske tämä vaihe
       input: aikaisemmat arvot
       suoritetaan laskenta 

       tuloksena  uudet paikalliset
arvot
 */
 

 for [kaikille j: P[j]   on  P[i]:n
naapuri] 

     send mailbox[i, j] (value[i]); 

 for [kaikille j: P[j] on P[i]:n
naapuri]
     receive mailbox[j,i](value[j]);


   }
 }
```
= = = = = = = = = = = = = = = = = = = = = = = = == = = = = = = = = = = = = = = = = = = = = = = =
Millaiset kanavat?
- Jokaisella prosessilla oma kanava kaikkiin naapureihin jopa itseensä
  - chan kytkin[N,N] (ennustetyyppi ennuste);
    tässä ei tarvitse huolehtia siitä, että sanomat sekoontuisivat eikä erikseen varmistua siitä, että on saanut jokaiselta sanoman
  - lähetä kaikille naapureille oma arvo
    for {all j: P(j) on P(i):n naapuri} send kytkin[i,j](value [i]);
  - vastaanota kaikilta naapureilta niiden lähettämä arvo
    for {all j: P(j) on P(i):n naapuri} receive kytkin[j,i](value[j]);
- Jokaisella prosessilla on oma kanava ('postilaatikko'), johon naapureiden lähettämät sanomat tulevat
  chan postilaatikko[N] (int tunnus, int kierros, ennustetyyppi ennuste);
  nyt on pidettävä kirjaa, että on todella saanut oikean määrän sanomia ja juuri kaikilta
  - lkm laskuri, joka laskee oikean kierroksen sanomien lukumäärää
  - naapurilista-taulukko, johon merkitään saadut sanomat
  - talletettava myös sekaan eksyneet seuraavan kierroksen sanomat
  Voi käydä niin, että jokin hyvin nopea naapuri, joka saatuaan uudet arvot kaikilta naapureiltaan on jo ehtinyt laskea niiden avulla uuden ennusteen ja lähettää sen eteenpäin. Tämä seuraavan kierroksen (i+1) arvo voi tulla jollekin naapurille (P) ennen joitakin edellisen kierroksen (i ) arvoja. Koska K on lähettänyt J:lle ensimmäiseksi ja P:lle paljon myöhemmin.
  ,..., {J, i+1, value[i+1]}, { K,i, value [i]}, ...
  - lähetä kaikille naapureille
    for {all j: P(j) on P(i):n naapuri} send postilaatikko[j]( i, laskuri, arvo[i]);
  - vastaanota kaikilta naapureilta
    while (ei ole vielä saatu kaikilta naapureilta) receive postilaatikko[i] j, laskuri, arvo[j]);
- Yhden ainoan yhteisen postilaatikon käyttö kaikkien viestintään on todella hankalaa:
  - receive poistaa aina sanoman postilaatikosta => voi saada ihan väärän, toiselle prosessille tarkoitetun sanoman, joka on lähetettävä uudestaan kanavalle, jotta sen oikea vastaanottaja joskus saisi sen
  - jokaisen prosessin pitäisi kait lukea (receive) joka kerta kaikki postilaatikon sanomat ja tallettaa (send) takaisin kaikki ne, jotka tarkoitettu joillekin muille
  - sen lisäksi tietenkin tehtävä kaikki sama kuin edellisessa eli käytävä penkomasssa postilaatikkoa, kunnes kaikki yhden kierroksen tiedot kaikilta naapureilta on saatu.
  Arvostelusta:
  - sanomanvälitykseen liittyvän kommunikoinnin perusasiat:
    - kanavien määrittelyt 2p
    - kanavaan lähettäminen 2 p
    - kanavasta lukeminen 2p
  - muu tarpeellinen toiminta valitussa kanavaratkaisussa 5 p
  - blocking ja non-blocking 4 p
    - - tässä lähettäminen = non-blocking, koska muuten joutuu odottelemaan, että jokainen vastaanottaja vuorollaan on saanut sanoman
      oikea vastaus + perustelu 2p
    - - vastaanottaminen = blocking, koska saa edetä seuraavaan vaiheeseen vasta, kun on saanut sanoman jokaiselta naapuriltaan
      oikea vastaus + perustelu 2p