Rinnakkaisohjelmistot s 2004

Kurssikokeen 10.12.2004 arvostelusta

--------------------------------------------------------------------------------
Rinnakkaisohjelmistot, kurssikoe 10.12.2004, tehtävä 1               /Riikka Kaven
----------------------------------------------------------------------------------

1. Vastaa seuraaviin kysymyksiin. [12 p]

Mitä tarkoittaa, että tietty toimenpidesarja on suoritettava "atomisena"? Käytä esimerkkinä toimenpidesarjaa < x = x+1; y = y+1; >. (4 p)
Mitä tarkoitetaan lukkiutumisella (deadlock), elolukkiutumisella (livelock) ja nälkiintymisellä (starvation)? (3 p)
Miten etäproseduuri eroaa tavallisesta proseduurista? Mitä etäproseduuria kutsuttaessa tapahtuu kutsuvalle prosessille ja kutsutulle proseduurille? (3 p)
Mikä on kriittinen alue (critical section)? (2 p)

--------------------------------------------------------------------------------
Rinnakkaisohjelmistot, kurssikoe 10.12.2004, tehtävä 2               /Sini Ruohomaa
----------------------------------------------------------------------------------

2.Sekoilua semaforeilla? [14 p]

Oheinen ratkaisu tuottaja-kuluttaja-ongelmaan ei toimi oikein. Mitä virheitä ratkaisussa on ja mitä toimintaongelmia nämä virheet aiheuttavat? Onko mahdollista lisätä tuottajien ja kuluttajien rinnakkaisuutta? Jos on, niin miten? Korjaa koodi oikein toimivaksi tai kirjoita aivan oma ratkaisusi. Muista liittää kommentteja omaan koodiisi, vaikka annetussa koodissa ei niitä olekaan!

    char  buffer[n];
      int start = 0,  end = 0;
      sem empties = n, fulls =1, turn = 0;
   
      process Producer[i=1 to M] {
          char data;
            ....
          while (true) {
                .....
              produce data;
              P(empties);
              P(turn);
              buffer[end] = data; 
              end = (end + 1) % n;     
              V(fulls);
              V(turn);
          }
      }

      process Consumer[i=1 to N] {
          char result;
             .....
          while (true) {
              .....
             P(turn);
             P(fulls);    
             result= buffer[start]; 
             start= (start + 1) % n;
             V(turn);
             V(empties);
             use result;
         }
     }

------------------------------------------------------------------------------
Rinnakkaisohjelmistot, kurssikoe 10.12.2004, tehtävä 3                  /Avrll
------------------------------------------------------------------------------

3. Spagettia monitorissa [13 p]
Pitkän pohdinnan jälkeen aterioivat filosofit (N kappaletta) olivat viimein oivaltaneet, että yhdelläkin haarukalla on mahdollista syödä spagettia ja jonkun aikaa harjoiteltuaan olivat oppineet käteviksi yhdellä haarukalla syöjiksi. Nyt kaikki pääsivät vaikka yhtä aikaa syömään eikä kenenkään tarvinnut odotella nälkäisenä. Tästä tosin syntyi uusi ongelma, sillä pöydällä oleva spagettikulho oli melkein aina typötyhjä. Tähänkin keksittiin ratkaisu: otettiin apupoika ruokapalkalla (spagettia!) huolehtimaan ruuanvalmistuksesta. Filosofit pääsivät taas normaalirutiiniinsa: syömään spagettia ja syömisen jälkeen ajattelemaan.
Poika valmistaa spagettia, täyttää filosofien ruokakulhon kukkuroilleen (M annosta) ja vie sen pöydälle. Sitten poika syö keittiössä kattilan pohjalta ja nukahtaa odottelemaan kulhon tyhjenemistä. Kukin filosofi ottaa syödessäään aina yhden annoksen. Kun kulho aikanaan tyhjenee, filosofit herättävät pojan valmistamaan lisää spagettia.
Toteuta filosofit ja apupoika prosesseina, joiden toiminta synkronoidaan monitoria käyttäen. Kirjoita monitorin koodi sekä koodit filosofiprosesseille sekä apupoikaprosessille.

Eräs ratkaisu:

--------------------------------------------------------------------------------------
process filosofi[i=1 to N] 
{
   while (true) {
      ajattele, kunnes tulet nälkäiseksi;
      nappaa haarukka ja lautanen;
      call Spagettia.ota_lautasellinen();
      syö lautasellinen spagettia;
   }
}
 
process apupoika
{
   while (true) {
      call Spagettia.valmista_kulhollinen();
      syö jämät kattilan pohjalta;
   }  
}  
 
monitor Spagettia {
   int lautasellisia = 0;
   cont kulho_tyhjä;   # ehtomuuttuja, jossa apupoika odottaa,
		       # että kulho tyhjenee
   cond kulho_täynnä;  # ehtomuuttuja, jossa filosofit odottavat, 
		       # että kulho täyttyy

  procedure ota_lautasellinen() {
     # jos kulho tyhjä, jää odottamaan
     while (lautasellisia == 0) wait(kulho_täynnä);
     lautasellisia--; 
 
     # jos otit viimeisen annoksen, herätä apupoika
     if (lautasellisia == 0) signal(kulho_tyhjä);
  }

  procedure valmista_kulhollinen() {
     if (lautasellisia > 0) wait(kulho_tyhjä); 
     valmista spagetti, täytä kulho ja vie pöytään;
     lautasellisia = M;
     signal_all(kulho_täynnä);  # herätä KAIKKI odottavat
  }
}

Arvosteluperusteita:

4:n miinuspisteen mokia:

käytetty semaforeja monitorissa poissulkemiseen
ei esitetty prosesseja vaan kaikki toiminta proseduureissa (rinnakkaisuus?)
ratkaisun perusideana oletettu selvästi, että signal() "jonottaisi" (samaan tyyliin kuin V(sem) kasvattaa semaforin arvoa)

2:n miinuspisteen mokia:

whilen paikalla if tai if:n paikalla väärässä kohdassa while (if:n paikalla saa joskus olla while)
if puuttuu: signal() hukkuu (ei, se ei "jonota")
herätetty vain yksi odottava filosofi
monitorin muuttujat esitelty monitorin ulkopuolella tai monitorin muuttujat esittelemättä
monitorin muuttujaa käytetty sen ulkopuolella prosessin koodissa
prosessit monitorin sisällä, mutta käyttävät proseduureja (kenties loppusulku puuttuu?)

1:n miinuspisteen pikkumokia:

alkuarvo unohtunut tai väärin

ehtomuuttujalle yritetty asettaa alkuarvo

Pikkupisteille pääsi aina, jos oli selvästi oikeansuuntainen ja ymmärrettävä idea, vaikka seassa olikin paljon ym. virheitä. Tavallisin virhe oli while-lauseen tai if-lauseen puuttuminen wait()-operaation yhteydessä.

Huomaa, että syöminen tulee sijoittaa monitorin ulkopuolella (rinnakkaisuus!). Tuosta ei pistemenetyksiä, sillä monet eivät olleet kirjanneet syömistä lainkaan näkyviin. Mutta, jos ratkaisun rakenne oli sellainen, että syöminen väkisinkin jäi monitorin puolelle, siitä menetti 1p.

Ratkaisun ei tarvinnut olla reilu, ts. aiemmin paikalle tulleilla ei oletusarvoisesti "etuajo-oikeutta".

o-o-o-o-o

Allaoleva ratkaisu huolehtii myös siitä, että uusi paikalle tuleva filosofi ei pääse etuilemaan. Perustuu Condition passing -tekniikkaan.

monitor Spagettia {
   int lautasellisia = 0;
   boolean odottajia_jonossa = false;
   cont kulho_tyhjä;
   cond saa_ottaa;

   procedure ota_lautasellinen() {
      # jos kulho on tyhjä, tai joku odottaa kulhon täyttymistä, jää odottamaan
      if (lautasellisia == 0 OR odottajia_jonossa) wait (saa_ottaa); 
      spagettia --;

      if (lautasellisia == 0) signal(kulho_tyhjä); 
      elif (!empty(saa_ottaa)
	   signal(saa_ottaa);        # herätä SEURAAVA odottava	
      else odottajia_jonossa=false;  # uusi tulija pääsee ottamaan
   }

   procedure valmista_kulhollinen() {
      if (lautasellisia > 0)  wait(kulho_tyhjä); 
      valmista spagetti, täytä kulho ja vie pöytään;
      lautasellisia = M;

      # jos joku odottamassa jonossa, päästä etenemään

      if (!empty(saa_ottaa) {
         signal(saa_ottaa);          # herätä jonon ENSIMMÄINEN
         odottajia_jonossa = true;   # estä uutta tulijaa etuilemasta
      }
   }
}

------------------------------------------------------------------------------
Rinnakkaisohjelmistot, kurssikoe 10.12.2004, tehtävä 4        / Liisa Marttinen
--------------------------------------------------------------------------------

4. Sanomanvälitystä Korvatunturilla [12 p]
Lähes koko vuoden Pukin vetoporot vaeltavat Lapin tuntureilla ja syövät jäkälää muiden porojen kanssa. Jouluaaton lähestyessä vetoporot kokoontuvat Korvatunturille Pukin pajan läheisyyteen. Kun kaikki N vetoporoa ovat saapuneet paikalle, vetoporoista Petteri Punakuono ilmoittaa tästä Pukille. Pukki valjastaa porot lahjareen eteen ja niin lähdetään matkaan lahjoja jakamaan.
Kun Pukki on saanut jaettua lahjat kaikille maailman lapsille, porot kiidättävät Pukin taikareen takaisin Korvatunturille, jossa Pukki kiittää poroja ja vapauttaa ne vaeltamaan muiden porojen kanssa.
Toteuta Pukki ja porot prosesseina, jotka kommunikoivat sanomanvälitystä käyttäen. Piirrä kaaviokuva, josta selviää Pukin ja porojen välinen kommunikointi. Kirjoita Pukki-ja Petteri-prosessin ja muiden poroprosessien koodit.


-------------------------------------------------------------------------------------------
Eräs ratkaisu:

# käytettyjen kanavien määrittelyt
  chan   paikalla( char),              # poroilta Petterille tieto poron saapumisesta
             kaikkivalmiina( ),        # Petteriltä Pukille tieto 
             pukilta[N](char);         # pukki ilmoittaa (lähtiessä 'MENOKSI',  päättyessä 'KIITOS')

# prosessien määrittelyt

  process Pettteri  {        # tässä ratkaisussa yksi vetoporoista, Petteri, toimii koordinaattorina
        while (true) {
              kuljeskele siellä sun täällä Lapissa; 
              joulun lähestyessä saavu Korvatunturille; # jotenkin vetoporot aistivat tämän 
              for [i=1 to N-1 ] receive paikalla( );    # vastaanota saapumisilmoitus N-1:ltä porolta
              send kaikkivalmiina( );                   # ilmoita pukille porojen olevan valmiina
              receive pukilta[0](  );                   # odota pukin lähtökäskyä ('MENOKSI')

     # Lahjojen jakamisen toteutus voidaan tehdä eri tavoin: 
     
     # Tässä ratkaisussa poroilla on valmis rutiini, jonka ne toteuttavat
             vedä taikarekeä se tavallinen joululenkki; # joulukierroksen toteuttaminen

     # Voidaan myös käyttää pukilta-kanavia pukin tarkempien ohjauskomentojen antamiseen:
     # 'Nyt lennetään Villen luo!', 'Nyt suunta takaisin kotiin!' jne.

     # Tai kukin poroprosessi käynnistää suuren määrän rinnakkaisia porosäikeitä, jotka Internetin
     # välityksellä hyvin nopeasti leviävät eri puolille maapalloa suorittamaan jakelutehtäviä. Itse
     # prosessi vaipuu unihorteeseen, josta pukin KIITOS sen herättää. 
     # Myös Pukki ja lahjareki monistuvat jotenkin eri puolilla maapalloa sijaitseviin lähtöpisteisiin.
     # (Tässä ehkä tapahtuuu Kiina-ilmiö eli kiinalaisilla alihankkijoilla voi olla sormensa pelissä.) 
     # Lähtöpisteistä lahjojen jako aloitetaan siinä määrin kuin mahdollista  rinnakkaisesti.
     # Vain rinnakkaisuuden avulla pystytään näin valtaisasta jakelutehtävästä suoriutumaan 
     # riittävän nopeasti.
 
           receive pukilta[0]( ); # homma on hoidettu, pukki kiittää ('KIITOS')
       } 
  }
   
   process vetoporo[i= 1 to N-1] {
        while (true) {
            kuljeskele siellä sun täällä Lapissa
            joulun lähestyessä saavu Korvatunturille; 
            send paikalla( );                          # ilmoita Petterille olevasi valmis 
            receive pukiltaporoille[i]( );             # vastaanota Pukin lähtökäsky 
     # tässä porot lumoutuvat  ja muuttuvat lentäviksi poroiksi, jotka kuin unessa vetävät
     # taikarekeä  valonnopeutta suuremmalla vauhdilla 
            vedä taikarekeä tavallinen joululenkki;    # joulukierroksen toteuttaminen
            receive pukiltaporoille[i] (  );           # homma on hoidettu, otetaan vastaan kiitokset
        }
  }
             

   process Pukki {
         while (true) {
             tee sitä sun tätä  siellä sun täällä;
             valvo lahjojen valmistusta;
             lepää ennen joulun ponnistuksia;
             receive kaikkivalmiina( );   #  ota vastaanPetterin ilmoitus porojen  saapumisesta
             valjasta porot lahjareen eteen;
      # tässäkin riittäisi lähettää N  sanomaa yhteiseen kanavaan, mutta ratkaisussa jokaisella
      # porolla on oma kanavansa, johon Pukki voisi lähettää juuri tälle porolle tarkoitetun viestin
      # (MATKAAN 'i'.)
      #  Ratkaisussa kaikille lähetetään sama viesti, jonka sisällöllä ei ole  toiminnan kannalta väliä
             for [i = 0 to N-1] send pukiltaporoille[i]('MATKAAN');     # anna lähtökäsky 
             jaa lahjoja kunnes kierros lopussa ja kaikille kilteille on lahjat jaettu;
             for [i = 0 to N-1] send pukiltaporoille[i]('KIITOS');  # kiitä ja vapauta porot 
             nauti joulusta;
      }
   }
-------------------------------------------------------------------------------------------------------

Ratkaisussa sanomia käytetään tahdistamaan toimintaa. Niiden sisällöllä ei tässä ratkaisussa ole merkitystä. Porot voivat ilmoittaa tunnuksensa, mutta sillä ei ole mitään käyttöä. Tarvitaan vain N-1 ilmoitusta, jotta tiedetään, että kaikki vetoporot ovat koollla. Lisäksi poroprosessit on numeroitu 0:sta N-1:een, joten kullekin osataan lähettää sen omaan kanavaan.

Arvostelusta:
Tehtävä oli osattu melkoisen hyvin; lähes 1/3 sai tehtävästä täydet pisteet.

Petterin tulee ilmoittaa porojen saapumisesta ja Petteri voi myös toimia välittäjänä kaikessa Pukin ja muiden porojen välisessä viestinnässä.
Tärkeintä on prosessien välinen tahdistus ja viestintä sanomanvälitystä käyttäen. Lahjojen jakamista maailman lapsille tai muuta kommunikointiin liittymätöntä toimintaa, ei tarvitse tarkemmin selvittää.

Arvostelun painopiste oli kanavissa ja niiden käytössä sanomien välitykseen.

Ei sanomanvälitystä
- Jos perusti ratkaisun jollekin muulle tahdistus- tai kommunikointitavalle => 0 p
- yhteisten muuttujien (esim. porojen lukumäärä) käyttäminen poroprosessien kesken
  - jos käytetty poissulkemista => - 4 p
  - jos ei ole käytetty poissulkemista = > - 5 p
puuttuvat kanavien määrittelyt
- ei lainkaan kanavien määrittelyjä -3 p
- kaikkia käytettyjä kanavia ei ole määritelty -1p tai -2p
- kanavat määritelty prosesseille lokaalisina -2 p
kanavien käyttö
- sanomat eivät välity, koska viesti lähetetään eri nimiseen kanavaan kuin mistä sitä yritetään vastaanottaa=> -2 tai -3 p riippuen käytön vaikutuksista
- samaa kanavaa käytetään kahdensuuntaiseen kommunikointiin niin, että lähettäjä saattaa ehtiä lukea oman sanomansa eikä sen kuittausta kuten tarkoitus oli -2 p; jos oikein monessa kohtaa niin, että toiminta täysin sekaisin -3 – 4 pistettä
- receive ch (message):lla oletettu olevan jokin arvo (vaikka lähetetty sanoma kopioidaan muuttujan message arvoksi) -2 p
Toiminta
- Pukki (tai Petteri) lähettää poroille vain yhden yhteisen viestin -2 p
- Petteri (tai Pukki) vastaanottaa viestin vain yhdeltä porolta - 2 p
- Pukin koodi puuttuu tai Petterin koodi puuttuu – -3p
- Petteri esitetty kahtena prosessina sekä porona että Petterinä -1p
kömmähdyksiä ohjelmoinnissa yms.
- ikuinen silmukka -1 p
- määrittelyt siellä sun täällä -1 p
- huolimattomuusvirheet -1 p