Erilliskuulustelu 18.8.2006

1. Vastaa lyhyesti seuraaviin kysymyksiin [15p]
   1. Mitä tarkoittaa, että tietty toimenpidesarja on suoritettava "atomisena"? Käytä esimerkkinä toimenpidesarjaa < x = x+1; y = y+1; >. (3 p)
      Toimenpidesarja suoritetaan muiden prosessien kannalta yhtenä kokonaisuutena niin, että muut prosessit näkevät vain toimenpidensarjan lopputuloksen eikä mitään välivaiheita. Esimerkissä muut prosessit näkevät ennen toimenpidesarjaa < x = x+1; y = y+1;> x:n ja y:n arvot ja toimenpidesarjan jälkeen sekä x:n että y:n arvot yhdellä suurempina. Eivätkä siis näe sellaista tilannetta, jossa x on yhtä suurempi, mutta y vielä ennallaan.
      Arvostelusta:
      • selkeä määrittely: yksi kokonaisuus, jonka välivaiheet eivät näy muille 2 p
      • esimerkin käsittely 1-2 p
      • tietokantatyyppinen vastaus (peruutukset yms) 2 p

   2. Mitä tarkoittaa lukkiutuminen (deadlock)? Miten se eroaa nälkiintymisestä (starvation)? Lukkiutuminen on mahdollista vain tiettyjen ehtojen ollessa voimassa. Mitkä nämä ehdot ovat? Selitä, mitä kukin ehto tarkoittaa resurssien jakelussa. (6 p)
   3. Miten etä proseduuri eroaa tavallisesta proseduurista? Mitä etäproseduuria kutsuttaessa tapahtuu kutsuvalle prosessille ja kutsutulle proseduurille? (3 p)
   4. Miten monitorin signal-operaatiolle määritellyt toimintatavat "Signal and Wait" ja "Signal and Continue" eroavat toisistaan? Miksi tällaisia täsmennyksiä on tarpeen määritellä ? (3 p)

2. Semaforilla tahdistettu karuselli [15 p]
   Huvipuistossa on N asiakasprosessia ja yksi karuselliprosessi. Asiakkaat ajelevat kerta toisensa jälkeen karusellissa, johon mahtuu kerrallaan C asiakasta (C on pienempi kuin N). Karuselli käynnistyy kuitenkin vasta, kun se on täynnä . Kunkin ajokerran jälkeen kaikki kyydissä olleet poistuvat karusellista muihin puuhiin (kenties palatakseen karuselliin myöhemmin) ja karuselli täyttyy taas seuraavista huvittelijoista.

   Kirjoita asiakasprosessien ja karuselliprosessin koodien keskeiset osat, kun prosessien koordinointiin käytetään semaforeja. Karusellissa istuminen on asiakkaan koodissa pelkkää odotusta.

   sem karuselli_täynnä = 0;	# auki, jos karuselli täynnä
   sem saa_nousta_kyytiin = 1;# auki, jos saa mennä kyytiin
   sem saa_poistua = 0;		# auki, jos saa poistua 
   int lkm = 0;			# karusellissa istuvien lkm
   
   process karuselli 
   { 
      while (true) {
         P(karuselli_täynnä);	# odota, että täysi
         pyöritä_karusellia();
         V(saa_poistua);		# päästä jengi pois
      }
   }
   
   process huvittelija[i=1 to n]
   {
      while (true) {
        
         huvittele_muuten_vaan();
   
         P(saa_nousta_kyytiin); # odota kyytiinnousulupaa
         lkm++;			    # baton passing
         if (lkm == C)		
             V(karuselli_täynnä) # viim: "herätä" karuselli
         else 
             V(saa_nousta_kyytiin); # vielä on tilaa
   
         istu_ja_nauti_karusellista();
   
         P(saa_poistua); # karuselli pysähtyi, saa poistua
   
         lkm--;
         if (lkm > 0)		    # baton passing
            V(saa_poistua);	    # seuraava pois
         else
   	 V(saa_nousta_kyytiin); # viim: uudelle lupa nousta 
     }
   

   Arvostelusta:
   • hyvin vakavista virheistä eli toimii selkeästi vastoin esitettyjä vaatimuksia tai sisältää semaforien karkeaa väärinkäyttöä yleensä -3 p. Jos laajempi, tahdistuksen kannalta tärkeä toimillisuus on jätetty kokonaan selvittämättä => jopa -5 p.
     • yhteisen muuttujan käyttö ilman mutexia
     • P- ja V-operaatioiden väärin käyttäminen
     • aktiivinen odotus
     • koko toiminnan jumittuminen
     • yhteisen muuttujan muuttumisen odottelu mutex suljettuna => lukkiutuminen
     • asiakas ei mene koskaan kyytiin
     • asiakas poistuu karusellin pyöriessä tai poistuu heti saavuttuaan
     • vain yksi asiakas poistuu karusellista
     • vain yksi pääsee kyytiin
     • karusellia ajaa tyhjänä
     • karuselli käynnistyy vaikka asiakkaat eivät vielä ole ehtineettulla tai edes poistua
     • asiakkaat sekoilevat pahasti poistumisen kanssa
     • kaikki eivät ehdi poistua, vaan jäävät uudelle kierrokselle
     • karusellin tyhjenemisestä ei huolehdita lainkaaan
   • melko vakavista virheistä -2 p
     • semaforien määrittelyiden paikka
     • asiakas ei aina osaa poistua karusellista
     • jossain vaiheesa kukaan ei enää pääse karuselliin
     • sekoitettu semaforien nimet
   • pienet lähinnä huolimattomuusvirheiksi tulkitut
     • muuttujalla ei ole alkuarvoa
     • väärä muuttujan nimi

   Jos virheitä on runsaasti, niin pisteitä on saanut siitä, mikä vastauksessa on ollut oikein.

3. Monitoroitu purnukka [15 p]
   Mehiläisparvi ruokkii loukkuun joutunutta karhua keräämällä sille hunajaa. Karhun elämä loukussa on vain syömistä ja odottelua. Mehiläiset kuljettavat hunajaa purnukkaan annos kerrallaan. Kun purnukka on täynnä (H annosta), viimeisen annoksen tuonut mehiläinen herättää karhun, ja mehiläiset jäävät odottamaan purnukan tyhjenemistä. Kun karhu on tyhjentänyt purkin, se päästää mehiläiset taas töihin ja käy itse nukkumaan.

   Ohjelmoi purnukan käyttöä synkronoivat osat monitoriin sekä esitä niiden lisäksi mehiläisprosessien (N kpl) ja karhuprosessin koodi.

   process bee[i=1 to N]
   {
      while (true) {
           collect_honey();
           call pot.into_pot();
      }
   }
   
   process bear()
   {
      while (true) {
        call pot.sleep();
        call pot.empty_pot();
      }
   }
   
   monitor pot {
      int portions=0;
      cond pot_full, pot_empty;
    
      procedure into_pot()
      {
         while (portions==H) wait(pot_empty);	# note while!
         portions=portions + 1;
         if (portions==H) signal(pot_full);
      }
   
      procedure sleep()
      {
         if (portions < H) wait(pot_full);	# note if, does while cause problems
      }                                         
   
      procedure empty_pot()
      {
         portions=0;
         signal_all(pot_empty) # wake all waiting bees to deposit honey
      }
   }
   

4. Sanomanvä litystä ja yhteinen pankkitili [15 p]
   Pankkitili on usean henkilön käytössä, joista jokainen voi tallettaa tilille tai nostaa tililtä rahaa. Tili ei saa koskaan mennä negatiiviseksi. Koodaa palvelin, joka huolehtii tilin käytöstä. Asiakkaat voivat pyytää joko jonkun rahasumman talletusta tai rahasumman nostoa. Jos tilillä ei ole tarpeeksi rahaa, niin pyyntöä viivytetään. Asiakkaat ja palvelin käyttävät sanomanvälitystä kommunikointiin.