Jos esitetyissä malliratkaisuissa on virheitä tai omituisuuksia, niin ilmoitelkaa niistä Liisa Marttiselle.

1. Semaforit ja niiden käyttö [16 p] (Tarkastanut Risto Saarelma)
   1. Pitävätkö seuraavat väitteet paikkansa? Perustele vastauksesi. (10 p)
      1. Jos ohjelman kahdesta prosessista kumpikin suorittaaa ensin P-operaation samalle semaforille, niin prosessit aina ja välttämättä lukkiutuvat.
      2. Halkaistun binäärisemaforin (split binary semaphore) käyttö helpottaa keskinäisen poissulkemisen (mutual exclusion) toteuttamisen ohjelmointia.
      3. V-operaatio kasvattaa semaforin arvoa yhdellä vain, jos semaforin jono on tyhjä.
      4. Semaforissa jonottavien prosessien lukumäärää ei voida kysyä, mutta E-operaatiolla voidaan tutkia, onko semaforin jono tyhjä.
      5. Semaforin jono on aina FIFO-jono ja on käytettävä yksityisiä semaforeja (private semaphore), kun halutaan herättää prosessit jossain muussa järjestyksessä.

      a)-kohdan osatehtävistä sai kaksi pistettä, jos oli vastaus oli pääpiirteittäin oikein ja yhden pisteen, jos vastauksessa oli ymmärretty asiaa, mutta siinä oli joku selkeä virhe tai puute.

      Yleisesti:
      Perusteltu oikea vastaus: 2 pistettä,
      oikea vastaus ilman perusteluja: 1 piste, väärä vastaus mutta perusteluista näkee että oleelliset asiat ymmärretty: 1 piste,
      täysin puuta heinää: 0 pistettä

      1. Ei. Jos semaforin arvo on alussa nolla, molemmat prosessit lukkiutuvat, ja jos ohjelmassa on vain nämä kaksi prosessia eikä kolmatta, joka voisi tehdä semaforille V-operaation, ohjelma lukkiutuu. Jos semaforin alkuarvo on suurempi kuin 0, ainakin toinen prosessi saa semaforin vapautettua, ja jos se vapauttaa sen myöhemmin V-operaatiolla, myös toinen prosessi pääsee suoriutumaan.
      1 piste jos vastaus on ei, mutta ei mainittu että semaforin oltava alussa > 0 tai että semaforin varannut prosessi voi vapauttaa semaforin. Moni oli vastannut, että semaforin arvon pitää olla vähintään 2, vaikka 1 riittää, mutta tästäkin sai 2 pistettä.

      2. Kyllä. Halkaistu binäärisemafori on joukko semaforeja, joista vain yhdellä voi olla arvo 1 ja kaikilla muilla on oltava arvo 0. Sitä voidaan siis käyttää sulkemaan prosessijoukosta kaikki prosessit yhtä lukuunottamatta pois kriittiseltä alueelta.

      3. Tulkintakysymys. Semaforien toimintaa voidaan ajatella kahdella tavalla. Joko niin, että V-operaatio nostaa aina semaforin arvoa, ja jos semaforissa on jonottajia, ensimmäinen jonottaja poimii välittömästi arvon ja nollaa taas semaforin. Tässä tapauksessa vastaus olisi ei. Toinen tulkinta on, että V-operaatio kasvattaa semaforin arvoa jonon ollessa tyhjä ja vapauttaa jonon ensimmäisen prosessin, kun jonossa on semaforeja. Tässä tapauksessa vastaus olisi ei. Kurssikirja esittää luvussa 6.3 jälkimmäisen tulkinnan mukaisen kuvauksen V-operaation toiminnasta. Myös luennoilla on noudatettu lähinnä jälkimmäistä tulkintaa
      2 pistettä jos vastaus noudattaa johdonmukaisesti jompaa kumpaa tulkintaa, 1 piste jos vastaus ei ole aivan sekasotkua.

      4. Ei. Sen lisäksi ettei jonottajien lukumäärää voi kysyä, semaforeilla ei myöskään ole E-operaatiota.

      5. Ei välttämättä. Semaforin määritelmä (kurssikirja, luku 4.1) ei sisällä FIFO-jonoa. Kirja vain toteaa että semaforien toteutukset *yleensä* varmistavat sen, että odottavat prosessit herätetään siinä järjestyksessä, jossa ne suorittivat P-operaationsa semaforin suhteen. Herätysjärjestys siis riippuu semaforin toteutuksen yksityiskohdista, voidaan esimerkiksi toteuttaa sellainen semafori, jossa odottavista prosesseista vapautetaan ensin korkeimman prioriteetin prosessi.

      Lisäselvitystä kohtaan 5. (Liisa Marttinen)
      Itse semaforin semantiikka ei määrittele semaforin jonoa eli ei ole määrätty sitä, missä järjestyksesssä odottavat prosesit herätetään (satunnainen, FIFO, prioriteetti, joku muu) Semaforin jono ei siis välttämättä ole FIFO, vaan riippuu siitä, kuinka semafori on toteutettu.

      Yleensä kaikki toteutukset ovat FIFO-jonoja (käyttävät semaforin odottajille listaa ja lisäävät uuden odottajan aina listan loppuun ja poistavat listan alusta) ja kurssilla (luennoilla ja harjoituksissa) on yleensä oletettu jonon olevan FIFO-jono. Eli V(sem)-operaatiot vapauttavat P(sem)-operaatiossa jonottamaan joutuneet prosessit FIFO-järjestyksessä eli siinä järjestyksessä kuin ne ovat jonoon joutuneet. Monissa semaforitehtävissä herätysjärjestyksellä ei ole mitään väliä, mutta esim. harjoitusten Jurassic Park -tehtävässä herätysjärjestys aiheutti ongelmia.

      Lisäksi on otettava huomioon käyttöjärjestelmän vuorottaja ('skeduloija'), joka viime kädessä valitsee suoritukseen pääsevän prosessin. Semaforin jonosta herätetty prosessi pääsee vasta READY-tilaan eli suoritukseen kelpaavien prosessien joukkoon, joista vuorottaja omien toimintasääntöjensä mukaan valitsee suoritettavan prosessin.

      Olkoon semafori sitten toteutettu millä tavalla tahansa, niin mikä tahansa haluttu herätysjärjestys (jos se poikkeaa semaforin toteutuksen tarjoamasta) saadaan käyttämällä yksityisiä semaforeja. Käyttämällä eri luokkia ja kullekin luokalle omaa semaforia voidaan säännellä luokkien herätysjärjestystä, mutta sillä ei voida vaikuttaa luokan sisäiseen järjestykseen. Yksityisiä semaforeja käytettäessä jokaiselle prosessille on oma luokkansa.

      Kapulansiirto (Baton passing) -tekniikalla voidaan estää uusien tulijoiden etuileminen pakottamalla uuden tulijat menemään jonon kautta ja varaamalla pääsy tyhjälle kriittiselle alueelle semaforin jonossa jo odottavalle. Mutta tämä ei varsinaisesti vaikuta itse semaforin jonon herättämisjärjestykseen, vaan siihen missä järjestyksessä prosessit todella pääsevät kriittiselle alueelle. Näin pääsy esim. kriittiselle alueelle saadaan FIFO-järjestykseksi.

   2. Mitä ongelmia tai omituisuuksia seuraavassa ratkaisussa on? Perustele vastauksesi.(6 p)

   sem AutoKuopalla = 0,
       KuormaValmis = 1,
       KaivuriVapaa = 0;
   
   process Kaivuripappa ( ){
      V(KaivuriVapaa);
      P(AutoKuopalla);
    while(true) {
      täytä kuorma;
      V(KuormaValmis);  
      V(KaivuriVapaa);  
      P(AutoKuopalla);  
     }
   }
   
   process Kuormurikuski[i=1 to N](){
     while(true) {
       P(KaivuriVapaa); 
       aja monttuun;
       V(AutoKuopalla);
       P(KuormaValmis); 
       poistu montusta ;   
       vie hiekka sinne, minne kuuluukin; 
      }
    }
    
    

   b)-kohdasta sai täydet pisteet, jos on hahmottanut oikeat virheet ja maininnut jotain myös pikkukummallisuuksista. Jos pikkuongelmia ei huomannut, niin lisäpisteitä kuitenkin, jos varsinaiset virheet ovat kattavasti kuvailtuja. Tehtävässä ei pyydetty korjattua koodia, vaan virheiden kuvailua. Pelkästä koodista ilman kommentteja ei saa täysiä pisteitä, etenkään jos se ei toimi oikein. (Aika monessa pelkkää koodia tarjonneessa vastauksessa koodi oli myös jotenkin rikki).

   Tärkeitä:

   • KuormaValmis-semaforin arvo on alussa yksi, vaikka kaivuripappa ei ole vielä ehtinyt kauhoa ensimmäistäkään kuormaa. Tästä seuraa, että ensimmäinen kuormurikuski nappaa KuormaValmis-semaforin ja poistuu paikalta ennen kuin kaivuripappa on ehtinyt täyttää kuorman. Kaivuripappa kasaa hiekkaa kuopasta maahan, ja sama ongelma toistuu seuraavan kuormurin kanssa. (4p)
   • Kaivuri päästää KaivuriVapaa-semaforilla uuden kuormurikuskin monttuun ennen kuin on varmistanut, että edellinen on poistunut. Montussa tulee ahdasta jos sinne ajaa toinen kuormuri edellisen vasta tehdessä lähtöä. (2p)

   Pienempää virittelyä, jos varsinaisten virheiden huomaamisesta ei jo tullut täysiä pisteitä:

   • KaivuriVapaa-semaforin arvo voisi sensijaan olla alussakin yksi, kaivuripapan semaforipyörittely ennen while-luupin alkua on kummallista, vaikka tämä ei varsinainen virhe olekaan. (1p)

2. Sirkuksen apupoika monitorina [20] (Tarkastanut Liisa Marttinen)
   Sirkuksessa on 3 elefanttia ja 100 valkoista hiirtä. Eläimet siirtyvät areenalle kapeaa käytävää pitkin, jossa mahtuu kulkemaan kerrallaan vain yksi elefantti, mutta vaikka kaikki sata hiirtä. Koska elefantit pelkäävät hiiriä, ne eivät voi mennä käytävälle, jos siinä on yksikin hiiri kulkemassa. Ja mikään hiiri ei uskaltaudu käytävälle, jos siinä on elefantti kulkemassa, koska pelästynyt elefantti saattaisi tallata sen.
   1. Onko tämä ongelma erikoistapaus jostain kurssilla esitetyistä yleisistä ongelmista? Jos on niin mistä yleisestä ongelmasta? (2 p)
   2. Laadi monitori Apupoika, joka huolehtii siitä, että vain yksi elefantti saa mennä käytävälle kerrallaan, ja etteivät hiiret ja elefantit ole koskaan samaan aikaa käytävällä. (10 p)
   3. Kirjoita myös Hiiri- ja Elefantti-prosessien koodit.(3 p)
   4. Tee ratkaisustasi niin reilu, etteivät hiiret voi koskaan täysin estää elefantteja pääsemästä käytävälle tai vastaavasti elefantit hiiriä. (Näin voi olla jo b)-kohdassa.) (5 p)

   a)
   Kyseessä on lukijat ja kirjoittajat -ongelman muunnos. Tässä elefantit vastaavat kirjoittajia ja hiiret lukijoita. Lukijoiden ja kirjoittajien käyttämää tietokantaa vastaa tässä käytävä.

   Erona on se, että elefanttien ja hiirten kanssa merkitystä on vain poisulkemisella. Kirjoittajilla ja lukijoilla lisäksi jonkinlainen ajallinen riippuvuussuhde: kirjoittajat muuttavat sitä tekstiä, jota lukijat lukevat.

   Arvostelusta:

   2 p  lukijat ja kirjoitajat     (näin vastanneita 63 kpl eli 53 %)
   1 p  tytöt ja pojat suihkussa tai ajo tunnelissa (22 kpl eli 18,5%)
   0,5 p keskinäinen poissulkeminen      (9 kpl eli 7,6 %)
   0     muut  (25 kpl 21,5 %)
   

   b) Ratkaisu, jossa hiirilla ja elefanteilla on oma ehtomuuttujajononsa. Käytävältä poistuva pyrkii aina vapauttamaan odotusjonoista ne eläimet, jotka voisivat päästä käytävälle: poistuva elefantti 'signaloi' sekä yhdelle odottavalle elefantille että kaikille odottaville hiirille.

   monitor Helpboy (){
   
      procedure MouseEnter (){
          while(ecount >0) wait(MouseOk);      # start waiting: an elephant in the corridor
          mcount++;
      }
   
   
      procedure ElephantEnter(){
           while(ecount>0 OR  mcount>0)  wait (ElephantOk);
           ecount++;
       }
   
      procedure MouseExit(){
          mcount--;
           if (mcount==0)  signal(ElephantOk);  #the last mouse releases a  possibly waiting elephant
       }
   
      procedure ElephantExit(){
          ecount--;
          signal(ElephantOk);  # for  the possibly waiting elephant 
          signal_all(MouseOk);  # and mice
       }
    }
     
   

   Samantyyppinen ratkaisu, jossa erona on se, että nyt kaikki jonottajat laitetaan samaan jonoon odottamaan.

   monitor Helpboy {
     cond queue,    # jono sekä hiirille että elefanteille       
     int  mcount,     # laskuri käytävässä oleville hiirille
          ecount;     # ja elefanteille 
          
     procedure MouseEnter(){
         while(ecount!=0) wait(queue);
         mcount++; 
         }
         
    procedure MouseExit() {
         mcount--;
         if(mcount==0) signal(queue);  # viimeinen hiiri vapauttaa jonossa olevan elefantin
                                    # (nyt jonossa ei ole yhtään hiirtä, ainoastaan elefantteja)
         }
    procedure ElephantEnter() {
         while (mcount!=0 OR ecount!=0)  wait(queue);
         ecount++;
         }
   procedure ElephantExit() {
         ecount--;
         signal_all (queue);  # vapautetaan kaikki odottavat pyrkimään monitoriin
        }                 
   }
   

   Ratkaisut suosivat hiiriä: koska hiiriä on enemmän, niin todennäköisemmin hiiri saa monitorin ja tällöin kaikki halukaat hiiret pääsevät käytävälle.Elefantti pääsee käytävälle vain, jos juuri sen saadessa monitorin käytävä on tyhjä eli edellisestä käytävään päässeestä yrittäjästä on kulunut vähintään sen käytävän kulkemiseen käyttämä aika.

   Täydellinen kilpailutilanne: käytävän ollessa vapaaana ensin monitorin saanut pääsee käytävälle ja jos se on hiiri, niin kaikki halukkaat hiiret pääsevät käytävälle. Jos käytävän valtaa elefantti, niin monitoriin pääsevät hiiret joutuvat odotusjonoon, josta ne elefantin poistuttua pääsevät taas kilpailemaan monitorista.

   Arvostelusta: Virheet voidaan karkeasti jakaa seuraavasti:

   • monitoriin ja sen käyttöön liittyviin
     • monitorin proseduuri while (true)-tyyppinen eli pyörii ikuisesti kun sitä on kerran kutsuttu while (ehtoOk); aktiivinen odotus monitorin sisällä -3 p
       odottava prosessi pitää monitorin koko ajan hallussaan eikä mikään muu prosessi pääse monitoriin muuttamaan ehtoa => ikuinen silmukka
     • semaforien käyttö monitorin sisällä -2p
     • monitorin muuttujia käytetty monitorin ulkopuolella c)-kohdassa
     • käytävällä kulkeminen on monitorin sisällä => -3 p
       Jos hiiren kulkeminen on monitorin sisällä, niin kukin hiiri kulkee käytävällä yksinään eikä rinnakkaisuutta ole lainkaan! Elefanttien kanssa tällä ei ole niin suurta merkitysä, sillä ne muutenkin varaavat koko käytävän itselleen.
     • ehtomuuttujan määrittely puuttuu tai on väärässä paikassa -1 p
     • ehtomuuttujaa käytetään laskurina tai sille annetaan alkuarvo -2p
     • ei mitään wait- tai signal-komentoja monitorissa -2 p
     • prosesseja monitorissa -1 p
   • toiminnallisuuteen liittyviin virheisiin eli toiminta ei ole sellaista kuin pitäisi
     • Rikotaan poissulkemisvaatimusta: Hiiret menevät käytävälle, vaikka siellä on jo elefantti kulkemassa tai elefantti menee käytävälle, vaikka käytävä on jo varattu. -3 p tai -2 p
     • if vaikka pitäisi olla while => odottamasta vapautettu ei enää tarkasta tilannetta, vaan saatuaan monitorin haltuunsa menee suoraan käytävälle => voi rikkoa poissulkemisvaatimusta -2 -3 p
     • kaksi norsua pääsee käytävälle virheellisen ehdon takia (while(elefantteja>1)) (-1p)
   • Joudutaan lukkiutumistilaan (deadlock) tai hyvin rajoittuneeseen toimintaan
     • esim. monitorissa sekä elefanteille että hiirille heti aluksi ehdoton wait, jolloin kaikki vain jäävät monitoriin odottamaan -3
     • lukkiutuminen, jossa kaikki odottavat joko yhdessä tai kahdessa jonossa -2
     • syntyy ping-pong-lukkiutumistilanne, jossa hiiri antaa vuoron aina ehtomuuttujan jonossa odottavalle elefantille ja elefantti aina ehtomuuttujan jonossa odottavalle hiirelle. Kun kumpiakin on jonoissa odottamassa, siinä vaan pomputellaan vuoroa eli mennään aina jonoon ja tarjotaan vuoroa toiselle eikä kukaan pääse käytävälle. -2 p
     • hiiretkin menevät yksitellen -2p
     • estetään norsujen pääseminen käytävälle -2 p
     • hiiret (tai elefantit) kertyvät odotusjonoihin joko kaikki tai sitten vain yksi eläin kumpaakin lajia kulkee käytävässä vuorotellen -1 p
       koska käytävän ollessa käytössä odottamaan voi joutua monta eläintä, käytävästä poistuva vapauttaa vain yhden
     • jätetään turhaan odottamaan, vaikka käytävälle voisikin päästä -2 p
   • muita puutteellisuuksia tai huolimattomuusvirheitä
     • vain enter-koodit -5 p
     • joku koodeista puuttuu -3 p
     • lisäys, vaikka pitää vähentää -1p
     • AND ja OR sekoitettu -1p

   c)

   proces Mouse [i=1 to 100]{
     .....
    while (true) {
      .....   # do what ever you do except running in the corridor
      call Helpboy.MouseEnter();
      run in  the corridor  # now you can use the corridor!
      call Helpboy.MouseExit();
      ....   # perform or do what ever except running in the corridor
      }
      
   process Elephant[i=1 to 3] {
      .....
    while (true) {
      .....   # do what ever you do except running in the corridor
      call Helpboy.ElephantEnter();
      run in  the corridor  # now you can use the corridor!
      call Helpboy.ElephantExit();
      ....   # perform or do what ever except running in the corridor
      } 
         
   Arvostelusta:
    3 p  jos sekä prosessien määrittelyt että  monitorin kutsut oikein 
    -1p  jos call puuttui tai prosessien määrittelyssä virhe (esim  määritelty proseduureina tai vain yksi prosessi) tai  parametreja käytettäessä  
         parametrivirhe, väärä nimi 
        
   

   d)
   Ratkaisu 1.
   Ratkaisu, jossa odottavat hiiret vievät elefantit odotustilaan vain, jos on hiirten vuoro ja vastaavasti odottavat elefantit vievät hiiret odotustilaan, jos on elefanttien vuoro. Vuorottelu toteutetaan turn-muuttujan avulla.

   monitor Helpboy {
   cond MouseOk, ElephantOk;
   int ecount=0, mcount=0; # elephants, mice in corridor
   int edcoun=0, mdcount=0; # elephants, mice  waiting
   int turn =0; # whose turn it really
   
   procedure MouseEnter(){
     mdcount++;  # one more waiting mouse
     # odottamaan, jos elefantti käytävällä tai elefantteja odottamassa elefanttien vuorolla
     while (ecount>0 OR (edcount>0 AND turn ==0) wait(MouseOk);
     mdcount --; # ei enää odottamassa
     mcount ++;  # vaan jo käytävällä
    }
    
   procedure MouseExit();{
     mcount--;   # merkkaa poistuneeksi
     turn=0;     # vuoro elefanteille
     if (mcount == 0) signal(ElephantOk);  # vapauta odottava elefantti
     }
     
   procedure ElephantEnter(){
     edcount++;  
     while(mcount==0 OR ecount==0 OR (mdcount>0 AND turn==1)) wait(ElephantOk);
     edcount--;
     ecount++;
    }
    
   procedure ElephantExit(){
     ecount--;
     turn =1;   # vuoro hiirille
     signal_all(MouseOk); # vapauta kaikki odottavat hiiret
   } 
   

   Ratkaisu estää hiirien tai elefanttien jatkuvan virran käytävällä. Ratkaisu ei ole välttämättä reilu odottavalle eläimelle, mutta kyllä eläimen luokalle.

   Nyt jokainen käytävältä poistuva eläin siirtää vuoron toiselle lajille. Viimeinen poistuva hiiri vapauttaa odottavan elefantin ja poistuva elefantti päästää kaikki odottavat hiiret vapaiksi pyrkimääm taas uudestaan monitoriin. Koska laskurimuuttuja (mdcount tai edcount) yhä kertoo, että odottajia on, niin vuorossa olevaa lajia oleva eläin pääsee seuraavaksi käytävälle, väärää lajia olevat joutuvat odotustilaan.
   Koska vuoro vaihtuu vasta hiirjonon ensimmäisenä olleen hiiren poistuessa, niin kaikki ne hiiret pääsevät käytävälle, jotka saavat monitorin ennen tätä poistuvaa hiirtä. Tämän hiiren jälkeen tulevat joutuvat odotustilaan, jos yksikin elefantti on odottamassa.

   Ratkaisu 2
   Käytetään condition passing -tekniikkaa ja päästetään elefantit ja hiiret kulkemaan käytävälle järjestyksessä. Hiiriä saa olla käytävässä samanaikaisesti useita. Mutta hiirijono katkeaa, kun hiiri havaitsee odottavan elefantin. Ratkaisussa kumpikaan eläinlaji ei voi omia käytävää itselleen. Elefantit pääsevät käytävälle vain yksi kerrallaan ja aina elefantin kuljettua käytävän pääsevät sinä aikana odottamaan joutuneet hiiret käytävälle. Uusiakin hiiriä voi päästä, mutta uusien hiirien meno katkeaa heti, kun odottamassa on elefantti. Condition passing-tekniikalla varmistetaan, että odottamassa olleet todella pääsevät käytävälle.

   Elefantit ja hiiret vuorottelevat seuraavasti:

   • Hiiri ei mene käytävälle, jos käytävällä on elefantti tai elefantti on odottamassa käytävälle pääsyä
   • Kun hiiri vapautetaan wait-tilasta, se pääsee käytävälle heti saatuaan monitorin haltuunsa (if-ehto). Odotusehto (ecount >0) estää elefantteja pääsemästä käytävälle purkuvaiheen alussa, jolloin ensimmäinen hiiri on vasta jonottamassa monitoriin. Kun hiirijonon purkuvaihe on käynnissä (mgo >0), niin hiiret voivat mennä käytävälle niin kauan kun jonottamassa ei ole yhtään elefanttia. Jonottava elefantti pysäyttää 'uusien' hiirten virran käytävälle. Odottamasta tulleet pääsevät, koska eivät enää tarkasta ehtoa.
   • Käytävältä poistuva viimeinen hiiri päästää odottavan elefantin ja varaa sille käytävän (ecount =1) => vain tämä eläin pääsee käytävälle (if elefanteillakin).
   • Jos elefantti menee käytävälle odotustilasta, sen ei tarvitse enää merkata käytävää varatuksi. Jos elefantti pääsee käytävälle suoraan, niin sen täytyy merkata käytävän varatuksi.
   • Poistuva elefantti päästää
     • kaikki odottavat hiiret ja jättää niille käytävän varatuksi (ecount ==1)
     • Jos hiiriä ei ole niin yhden odottavan elefantin ja jättää sille käytävän varatuksi (ecount ==1).
     • Jos elefanttejakaan ei ole, niin merkkaa käytävän vapaaksi (ecount=0).

   monitor Helpboy (){
     int mcount=0, # hiiriä käytävällä
         mwait=0,  # hiiriä odottamassa
         mgo=0,    # jonossa olleiden hiirien lukumäärä; ilmoittaa myös milloin purkuvaihe on käynnissä
         ecount =0;   # elefantteja käytävällä: vain arvot 0 ja 1
     cond  MouseOk,     # hiiret odottavat tässä
           ElephantOk;  # elefantit odottavat tässä
   
     procedure MouseEnter (){
          if(ecount >0 and mgo ==0) or !empty(ElefantOk) ) { # an elephant in the corridor  or waiting to get in
                  mwait++;   # one more waiting mouse 
                  wait(MouseOk);   # start waiting;
                  # puretaan odottaneiden jono  
          # Now  still ecount >0 =>  those that were in waiting  can pass and also 'new' mice, elephants have to go waiting
          # condition passing-technique
                   mgo --;     # one allowed mouse less  
   		if (mgo ==0) ecount=0; 	#'huijaus' on loppu, mutta mcount estää elefantteja menemästä käytävälle
              }                            # hiiret pääsevät, jos elefantteja ei ole odottamassa 
          mcount ++;    #  one more mouse in the corridor
      }
   
   
      procedure ElephantEnter(){
           if (ecount>0 OR  mcount>0) wait(ElephantOk);  #  elefantti odottamaan	      
           else  ecount=1;  # asetetaan  vain jos päästään suoraan käytävälle
       }                  # odottamasta tulleelle ecount on jo valmiiksi 1!
   
      procedure MouseExit(){
          mcount--;
          if (mcount==0) AND !empty(ElephantOk)  {
                    signal(ElephantOk);  #the last mouse releases a  waiting elephant
   		 ecount=1;            # ja varaa sille valmiiksi käytävän => 
   		                      # vain tämä elefantti voi mennä käytävälle, muut elikot menevät odottamaan
         }
      
   
      procedure ElephantExit(){
      if(!empty(MouseOk)) {   # on odottavia hiiriä
          mgo=mwait;   #lukumäärä talteen => päästetään vain jonossa olleet
          mwait=0;     # laskuri nollille => uudet tulijat kasvattavat odottamaan mennessään
          signal_all(MouseOk);  # herätetään kaikki odottajat
          }  # mutta jätetään ehto päälle => odottamassa olleet pääsevät (koska hiirillä if) ja koska mgo >0, niin myös uusia voi päästä
            # jos ei ole elefantteja odottamassa
       else { 
         if (!empty(ElephantOk)  signal(ElephantOk)  # tässäkin ecount ==1 => yksi odottanut elefantti pääsee käytävälle 
        else  ecount=0;   # ei odottavia hiiriä eikä elefantteja  => tiedoksi kaikille, että käytävä tyhjä
        
         }
      }  
    }
    
   

   Ratkaisuyritys 1. Condition passing -tekniikkaa käyttävä vähän kimurantimpi ratkaisu. Elefanttien ehto (occupied = true) pakottaa elefantit odottamaan, kun hiiret pääsevät vapaiksi odotustilasta. Kun poistuva hiiri huomaa odottavan elefantin, se katkaisee hiirten virran (eleph=true) ja viimeksi käytävältä poistuva hiiri vapauttaa odottavan elefantin tai jos jono on tyhjä vapauttaa käytävän (occupied = false). Vastaavast1 poistuva elefantti päästää odottavat hiiret käytävälle tai jos hiiriä ei ole niin odottavan elefantin tai jos ei lainkaan odottavia, niin vapauttaa käytävän.

   monitor Helpboy {
   cond MouseOk, ElephantOk;
   int  mcount=0, #  number of mice in  the corridor
   bool occupied = false, # corridor occupied or reserved (mice or elephants) for mice
        eleph = false; # or for elephants 
   
   procedure MouseEnter(){
     if (eleph) wait(MouseOk); # 
     eleph=false;  #tässä käytävä on jo valmiiksi varattu hiirille
     occupied=true;
     mcount ++;  # jo käytävällä
    }
    
   procedure MouseExit();{
     mcount--;   # merkkaa poistuneeksi
     if(!empty(ElephantOk) eleph=true;  # siirrä vuoro elefanteille ja pysäytä hiirten virta käytävälle
     if (mcount == 0) {  # viimeinen hiiri käytävällä?
        if(!empty(ElephapntOk) signal(ElephantOk)  # vapauta odottava elefantti
        else occupied=false; 
      } 
     }
     
   procedure ElephantEnter(){  
     if (occupied) wait(ElephantOk);
     occupied = true # varaa käytävä
     eleph= true;   # käytävällä elefantti 
    
    }
    
   procedure ElephantExit(){
     occupied=false;  # käytävä vapaa
     if (!empty(MouseOk)  {
         signal_all(MouseOk); # vapauta kaikki odottavat hiiret
         occupied=true;     # merkkaa käytävä varatuksi ja estä näin elefanttien pääsy käytävälle
         }
     else  if(!empty(ElephantOk) signal(ElephantOk)  # tai vapauta odottava elefantti 
           else eleph=false;   #  tai päästä hiiret
     }
   } 
   
   
   Muuten hyvä ratkaisu, mutta ongelman aiheuttaa odottavien hiirten jonon katkeaminen itsestään:
   
     Poistuva elefantti vapauttaa 3 hiirtä h1, h2 ja h3 wait-tilasta. Hiiret h1 ja h2 kipittävät nopeasti käytävälle ja siitä pois.
     h2 on viimeinen hiiri, joka vapauttaa odottavan elefantin.  Elefantti meneekin heti käytävälle. Sitten tulee se hidastellut hiiri ja 
     menee sekin käytävälle (if!). Eihän näin pitänyt käydä! Täytyy lisäksi varmistaa, että kaikki odottaneet hiiret ovat todella päässeet 
     käytävälle ja sieltä vielä poistuneet ennenkuin elefantti päästetään irti.
   

   Ratkaisuyritys2 ,
   joka pyrkii suosimaan elefantteja, mutta voi tietyssä erityistilanteessa aiheuttaa hiirten jumittumisen odotusjonoon.

   monitor Helpboy {
     cond MouseOk,    # jonotuspaikka hiirille
          ElephantOk; # ja elefanteille
          
     int  mcount,     # laskuri käytävässä oleville hiirille
          ecount;     # ja elefanteille 
          
     procedure MouseEnter(){
         while(ecount!=0) wait(MouseOk);
         mcount++; 
         signal_all(MouseOk);  # vapautetaan kaikki odottavat hiiret
         }
    procedure MouseExit() {
         mcount--;
         if(mcount ==0) signal(ElephantOk);  # viimeinen hiiri vapauttaa odottavan elefantin
         }
    procedure ElephantEnter() {
         while (mcount!=0 OR ecount!=0)  wait(ElephantOk);
         ecount++;
         }
   procedure ElephantExit() {
         ecount--;
         if (!empty(ElephantOk)) signal(ElephantOk)   # jos on, niin vapautetaan odottava elefantti
         else signal_all (MouseOk);                 # muuten kaikki hiiret
        }                 
   }
    

   Ratkaisussa pyritään hieman suosimaan elefantteja, koska poistuva elefantti vapauttaa odottavan elefantin ja päästää hiiret odotustilasta vain, jos elefantteja ei ole odottamassa. Näin elefanteilla on hitusen suurempi mahdollisuus saada monitori ja käytävä haltuunsa.

   Ratkaisu voi johtaa tilanteeseen, jossa kaikki hiiret ovat odottamassa ja elefantit valloittavat käytävän omaan käyttöönsä niin pitkäksi aikaa kuin haluavat. Näin käy, jos elefanttien kulkiessa käytävässä kaikki hiiret ovat joutuneet wait-tilaan eli odottavat MouseOk-jonossa ja aina elefantin poistuessa käytävästä ElefantOk-jonossa on joku odottamassa.

   Useissa muissakin yrityksessä suosia elefantteja päädyttiin vastaaviin ongelmiin: joko hiiret kokonaan jumittuivat wait-jonoon tai vain yksi hiiri oli kerrallaan vapaana pyrkimään monitoriin.

   Arvostelusta
   5 p toimiva ja perusteltu ratkaisu 4 p hyvä idea ja lähes toimiva ratkaisu 3 p hyvä yritys, mutta ratkaisu ei toimi (lukkiutuminen tai muu ongelma tai sitten ei oikeastaan paranna reiluutta) 2 p hyvä ehdotus, mutta ei ehditty toteuttaa tai hyvin huonosti toimiva toteutus 1 p jotain yritystä lisätä reiluutta, jonkinlainen ehdotus tai reiluuteen liittyvä sopiva kommentti

3. Sanomanvälitystä ja laskentapalvelua [15 p] ( Tarkastanut Mika Karlstedt )
   Työlästä laskentaa (esim. matriisien kertomista) suoritetaan rinnakkain ja suoritusta valvoo erityinen koordinointiprosessi Master, joka ensin jakaa laskentaa suorittaville Worker- prosesseille (N kpl) niiden tarvitsemat syötteet. Kun Worker-prosessi on saanut oman laskentansa päätökseen, se lähettää tuloksensa Master-prosessille. Saatuaan tulokset kaikilta Worker-prosesseilta Master kokoaa tulokset yhteen.
   Koordinaattoriprosessi Master itse toimii palvelimena, joka vastaanottaa muilta prosesseilta laskentapyyntöjä. Pyynnöt se käsittelee aina yhden kerrallaan. Laskentapyynnön saatuaan Master lähettää tarpeelliset syöttötiedot Worker-prosesseille, jotka suorittavat laskennan ja palauttavat tuloksensa Masterille, joka puolestaan lähettää lopputuloksen laskentaa pyytäneelle prosessille.

   Kaikki prosessit käyttävät sanomanvälitystä keskinäiseen kommunikointiin.

   1. Piirrä kuva prosessien välisestä sanomanvälityksestä ja tarvittavista kanavista (5 p)
      Pisteitä kuvasta on saanut seuraavasti:

           5p jos kanavat eroteltu selkeästi, useita worker prosesseja ja
              useita asiakas prosesseja
           4p jos kuten yllä mutta vain 1 asiakas
           3p jos kuten yllä mutta ei asiakasta ollenkaan
           2p jos jotakin pientä oikein
           1p jos vain hiukan yritystä
      

   2. Esitä Master-prosessin ja Worker-prosessien koodit keskittyen vain toimintojen tahdistuksen kannalta oleelliseen. Muista myös määritellä prosessien käyttämät kanavat. (10 p)

      Ratkaisu b)-kohtaan:

      chan clients[m](data); // replies to clients
         chan request(ID, data);
         chan worker[n](data);
         chan reply(data);      // replies from workers
      
         process master {
           while (true) {
             receive request(id, task);
             data[i= 1 to n] = divide(task);
             for (i = 1 to n)
               send worker[i](data[i]);
             for (i = 1 to n)
               receive reply(data[i]);
             result = combine(data[i = 1 to n]);
             send clients[id](result);
           }  // end of while
         }
      
         process worker[i = 1 to n] {
           while (true) {
             receive worker[i](data);
             result = do_some_calculation(data);
             send reply(result);
           }
         }
         
      

      Pisteitä koodista on saanut seuraavasti:

           4p kanavien oikeasta määrittelystä
           3p jos pieni virhe
           2p jos useita virheitä
           1p jos vain mainittu kanavien nimet, ei muuttujia määrittelyissä
      
           4p oikeasta masterin koodista
           3p jos pieniä virheitä
           2p jos enemmän virheitä tai busy-wait tyyppinen ratkaisu
           1p jos hiukan yritystä
      
           2p oikeasta tai melkein oikeasta workerin koodista
           1p jos riittävästi yritystä