2. Semaforilla tahdistettu ruokinta [15p]
Lintuemo ruokkii pesässä olevia poikasiaan. Se täyttää ensin pesän keskellä olevan kuopan pienillä madoilla ja kutsuu sitten poikaset syömään. Itse se menee lepäämään. Kuoppaan mahtuu H annosta. Poikaset syövät vuorotellen, kukin ottaa kerralla yhden annoksen ja kuopan tyhjentänyt poikanen herättää emon hakemaan lisää ruokaa.
Kirjoita koodit emoprosessille ja poikasprosesseille, kun toimintojen koordinointiin käytetään semaforeja.

Eräs ratkaisu: Käytetään mutex-tyyppistä semaforia säätelemään sitä, että vain yksi poikanen kerrallaan on syömässä matoja. Ensimmäinen pääsee vasta, kun emo on täyttänyt kuopan madoilla. Jo syönyt poikanen päästää seuraavan mutex-semaforissa odottavan tai sinne tulevan poikasen syömään. Jos kuoppa tyhjenee, poikanen herättää emon eikä avaa mutexia seuraavalle poikaselle.

sem mutex = 0;                                  
sem herätys =0;
int annoksia = 0;  

process emo {
   while (true)  {
        kerää matoja;
        annoksia = H;  # täytä kuoppa madoilla                              
        V(mutex);  
        P(herätys);  # jää odottamaan herätystä
     }
 }

  
process poikanen[i=1 to N] {
     while (true) {                                                 
         P(mutex)
             annoksia --;
             if (annoksia == 0)  V(herätys)  # jos ruoka loppui, herätetään emo 
	                                     #ja jätetään  mutex-muuttuja kiinni
                 else V(mutex);   # muuten päästetään seuraava poikanen syömään
            syö matoannos;
       }
       
==========================================

sem
full=0, empty=1; # split binary semaphore
sem e = 1; # mutex
int ruokaa =0;   # annosten määrä
  

process emo {
     while(true) {
              P(empty);
              P(e);
              ruokaa= H;  # täytä kuoppa
            V(e);
            V(full);
    }
} 

process (poikanen) [i=1 to N] {
    while (true) {
      P(full);
      P(e);
      ruoka --;
      if (ruoka == 0)  V(empty)
          else V(full);
      V(e);
     syö annos;
    }
}
    
=====================================

sem mutex = 0;                                  
sem herätys =0;
sem ruokaa = H;  # aloitustilanteessa  kuoppa on täynnä matoja
int annoksia = 0;
  
process emo {
   while (true)  {
        kerää matoja;
        annoksia = H;  # täytä kuoppa madoilla                                                    
        for i = 1 to H  {V(ruokaa) };   # lataa semaforin arvoksi H
        V(mutex);
        P(herätys); # jää odottamaan herätystä
     }
 }

process poikanen[i=1 to N] {
     while (true) { 
          P(ruokaa);                                             
          P(mutex)
             annoksia --;
             if (annoksia == 0)  V(herätys)  # herätetään emo ja jätetään  mutex-muuttuja kiinni
                 else V(mutex);   # muuten päästetään seuraava poikanaen syömään
         syö matoannoksesi;
       }
} 

• syntyy lukkiutumistilanne -3-5 p
  • jäädään odottamaan (herätystä tai ruuan tuloa) mutexin sisällä (mutex kiinni) => lukkiutuminen
  • semaforin alkuarvo = 0 ja sekä emo että poikaset aloittavat P(semafori) komennolla. => lukkiutuminen
  • P- tai V-operaatio väärässä kohtaa
  • Turha semafori, joka jumittaa poikasten toiminnan, koska V(semafori) puuttuu => -3 p
• poissulkemisvirhe –3-5p
  • Poissulkeminen ei toimi: emo ja poikanen voivat käsitellä yhteistä muuttujaa samanaikaisesti tai kaikki voivat käsitellä
  • yleensä yhteisen muuttujan käyttö mutexin ulkopuolella -4 p
• ohjelma toimii fataalisti väärin eli poikaset syövät olematonta ruokaa ja annosten määrä menee negatiiviseksi. -5 p
  • ennenkuin varmistuttiin ruuan riittävyydestä, päästettiin toisen poikanen syömään
  • emo ei kasvata annosten määrää, vaikka täyttää kuopan madoilla
  • annosten määrää kysytään mutexin alkopuolella => usea poikanen voi tutkia samanaikaisesti lukumäärää ja esim. havaita, että annoksia on 1 kappale jäljellä. Sitten ne menevät kukin vähentämään lukumäärää yhdellä => annoksia negatiivinen määrä
  • vaikka kuppi on tyhjä, poikanen voi päästä syömään ennenkuin emo pääse täyttämään
  • yhteisten muuttujien arvoja yritetään laskea funktioiden paikallisilla muuttujilla
• semaforien käyttö -3
  • emo ja poikaset käyttävät samaa semaforia eri tavoin: emo lisää aina kun lisää kuoppaan yhden madon, poikaset vähentävät vain kun kuoppa on tyhjä -3
  • kysytään semaforin arvoa while-silmukassa -3p
  • semaforeja ei ole lainkaan määritelty
  • Semaforeille ei ole annettu alkuarvoja
  • Semaforin alkuarvot false /true (ei ole välttämättä niin, että false ==0 ja true ==1) => -1
  • käytetty wait ja signal-komentoja
• turhaa odottelua -2--3
  • poikaset pääsevät syömään vain järjestyksessä (turha rajoitus, nälkäiset joutuvat turhaan odottamaan, jos välissä on ei-nälkäisiä). -3
  • Erikseen jokin sleep-toiminto ja semaforiodotus: nyt poikanen ei voi suoraan herättää sleep-toiminnossa olevaa emoa, 'herätys' vasta, kun emo on itse jo herännyt (sleep-toiminto on suoritettu). Tämä voi aiheuttaa turhaa odottelua, sillä emo suorittaa aina sleep-toiminnon, vaikka poikaset olisivat kuinka nälissään. -3
  • Varsinainen syöminen mutex-semaforin sisällä => turhaa odotusta -2 (koska hyvin nopea nielaisu)
  • emo odottaa samassa semaforissa kuin poikaset => nälkäiset poikaset käyvät koko ajan kurkkimassa ruokatilannetta, eikä emo pääse heti täyttämään kuoppaa -2
• kömmähdyksiä ohjelmoinnissa
  • emo-prosessia kutsutaan aliohjelmana -3
  • vain yksi poikasprosessi -2
  • while (true) -silmukka puuttuu -2
  • piilotetaan funktiokutsuun oleellisia muuttujien päivityksiä eikä itse funktiota anneta
• ei toimi niinkuin tehtävän annossa pyydettiin
  • Tehtävässä sanottiin, että ”kuopan tyhjentänyt poikanen herättää emon”, toteutuksessa kuopan tyhjäksi havainnut herättää emon! -3
  • Tehtävässä sanottiin, että ”kuopan tyhjentänyt poikanen herättää emon hakemaan lisää ruokaa”. Toteutuksessa emo touhuaa koordinaattorina ja päästää poikaset vuorotellen järjestyksessä syömään eikä mene lainkaan nukkumaan eikä siis ole mitään herättämistä.
  • Tehtävässä sanottiin, että emo täyttää kuopan madoilla eli laittaa sinne H annosta ja sitten vasta päästää poikaset syömään. Toteutuksessa poikaset pääsevät syömään kunhan kuopassa on jotain syötävää!
• selkeä huolimattomuusvirhe -1
  • väärät sulut poikasprosessissa (i=1 to N), vaikka pitäisi olla hakassulut
  • process puuttuu
  • H:n tilalla joku muu määrä

Hyvin yksinkertainen ratkaisu , joka vain estää eri suunnilta tulevia autoja törmäämästä ja liian montaa autoa menemästä sillalle. Ratkaisussa ei ole lainkaan huomioitu reiluutta eikä myöskään toiminnan tehokkuutta.
Jos auto ei heti pääse sillalle, niin se menee odottamaan. Kaikki odottavat samassa ehtomuuttujassa ja jokainen sillalta poistuja päästää kaikki odottajat yrittämään uudestaan ja uudestaan, kunnes sillalle meno onnistaa (joko silta on tyhjä tai silta on kyllä käytössä, mutta ajosuunta on sama kuin itsellä eikä sillalla ole vielä 10 autoa). Onnistuminen on hyvin sattumanvaraista ja prosessit saattavat joutua kiertämään kehää (mene odottamaan -> herää -> mene monitorin jonoon -> testaa pääsetkö nyt -> mene takaisin odottamaan).

Tämäntyyppinen oikein toimiva ratkaisu => 10 p

  
monitor Silta {
int ajosuunta = 0; # ajosuunta sillalla   A=>B = 1 ja B=>A = 2
int slkm = 0;   # autojen lukumäärä sillalla; jos 0 niin silta on vapaa
cond odota_vuoroa; #  kaikki autot odottavat samassa  ehtomuuttujassa
  
procedure enter_silta (oma_suunta) {
   while (slkm>0 && ajosuunta != oma_suunta ||  slkm  = 10)  
     wait(odota_vuoroa);
   if (slkm =0) ajosuunta = oma_suunta;
   slkm ++;
 }
  
procedure exit_silta(oma_suunta) {
  slkm --;  # tässä vähän suositaan omaa suuntaa, kun ajosuuntaa ei muuteta           
  signal_all(odota_vuoroa);
}
======================================================== 

Idea:
Käytetään condition passing -tekniikkaa samaan suuntaan menevien autojen etuilun estämiseen

1. eli kaikki autot (paitsi 1. silloin kun silta on vapaa) pääsevät sillalle vasta monitoriodotuksen jälkeen (ehtomuuttuja omasuunta).
   • Sillalle menevä auto päästää aina seuraavan odotustilasta. Viimeinen toisen suunnan auto päästää sen ensimmäisen auton.
   • monitorissa odottavat myös ne autot, jotka eivät voineet ajaa suoraan sillalle, koska sillalla oli jo täysi kuorma autoja eli se sallittu 10 kappaletta. Näillä autoilla on etuoikeus eli tätä jonoa puretaan ensin

  

monitor Silta{
cond atob, btoa;  # odotetaan oman suunnan vuoroa
int slkm =0;
int ajosuunta = 0;   # 0, kun atob; 1, kun btoa

procedure enter_atob()  {     
   if (sklm > 0 && ajosuunta !=0|| !empty(atob) || slkm =10)  
   # kun silta varattu toiseen suuntaan menijöille tai 
   # omaan suuntaan menijöitä on jo odottamassa tai sillalla on jo 10 autoa  
   # mennään odottamaan, mutta vain kerran (if) 
   {
      wait(atob); #odotetaan vuoroa ajaa  sillalle 
         #kun tästä päästään, niin ajosuunta == oma_suunta ja slkm:ää on jo valmiiksi  kasvatettu
     }
    else { #  auto pääsee suoraan sillalle ilman odottamista
          if (slkm ==0) ajosuunta = oma_suunta; # ensimmäinen muuttaa suunnan varmuuden vuoksi aina
          slkm=1;
    }
     # pura mahdollista odottajien jonoa
    if (slkm <10 && !empty (atob)) {
       slkm++;
     # varataan  paikka jo valmiiksi     HUOM!  FIFO-järjestys ei aivan toimi **  
       signal(atob);
       }
    aja sillalle;
  }

  Vastaavasti procedure enter_btoa()  
  
  

Mutta vapautettu pääsee varmasti sillalle, kun se saa aikanaan monitorin haltuunsa. Koska vapautetulle autolle on jo valmiiksi varattu paikka, niin ohittajia voi olla vain rajallinen määrä. Vaikka kaikki sillalla olleet 10 autoa ehtisivät poistua, niin laskuri slkm menee nollille vasta, kun tämä auto on ylittänyt sillan.

Sillan käytön tehokkuuden kannalta tämä ratkaisu on hyvä, sillä siinä hyödynnetään sitä luppoaikaa, joka kuluu ennenkuin se vapautettu auto saa monitorin haltuunsa ja pääsee itse sillalle.

 
procedure exit_atob() {
   if (!empty (atob))  {#  oman suunnan odottajia  on =>  suositaan oman suunnan odottajia
      signal(atob);  # HUOM! ei vähennetä slkm-laskuria
   }
   else {
      if (slkm ==1 && !empty (btoa))  {# viimeinen tältä suunnalta ja toisen suunnan odottajia on
           ajosuunta = 1;
          signal(btoa);
         }
      else slkm --;
     }
}
  
 Vastaavasti procedure exit_btoa() 

====================================================

Millaisia virheitä:

• sillan ylittäminen monitorin sisällä
• poistuva auto vapauttaa vain yhden, vaikka sinä aikana wait-tilaan on voinut joutua usea auto (olet. 100 autoa A=>B, 10 pääsee, mutta 90 joutuu jonoon. Nämä 10 vapauttavat (signal) 10 autoa odottamasta, mutta jonoon jää 80. Jos nyt vuoro vielä vaihtuu ja nämä 10 joutuvat taas odotustilaan, niin odottamassa on taas 90 autoa) Eli syntyy epätasapaino, vähitellen lähes kaikki autot ovat jonossa ja lopulta vain 2 autoa kumpaankin suuntaan pääsee kerrallaan liikkumaan -2 p
• eri suuntiin meneviä autoja sillalla eli törmäystilanne -3 p
• autoprosessien koodi puuttuu -2 p
• ehtomuuttujien määrittely -2-3p
• pannaan kyllä odottamaan (wait), mutta ei koskaan vapauteta (signal)! - 2-3 p
• Alussa kiinnitetty suunta => väärä suunta joutuu turhaan odottamaan, vaikka silta olisi vapaa
• Näitä tule vielä lisää

• jonottajien määrän mukaan
• sillan ylittäneiden määrän mukaan
  jos sekä silta on tyhjä ja riittävä määrä tästä suunnasta on ylittänyt sillan => vuoro vaihtuu
  • vaihtuu vaikka toisella puolella ei ole edes odottajia
  • ei vaihdu, vaikka silta on tyhjä ja odottajia toisella puolella olisi, kun vasta 9 autoa tähän suuntaan mennyt. Odotellaan nyt sitä kymmenettä, joka ehkä joskus saapuu!

• 1 p yrityksestä eli liitetty joku tapa eri suuntien vuorojaja jopa pelkästä selityksestä, miksi satunnainen järjestys on reilu
• 1 p yrityksestä hoitaa saman suunnan autot järjestyksessä
• 2 piste lisää, jos jompi kumpi lähes onnistuu
• 5 pistettä, jos reiluus toimii sekä eri suuntien välillä että saman suunnan autojen kesken tai jos ei ihan toimi, niin puutetta sopivasti perusteltu esimerkiksi tehokkuudella.

1. Esitä kaaviokuvana, kuinka toiminnan toteuttavat prosessit, reen kuljettajaprosessi ja lapsiprosessit, kommunikoivat tahdistaakseen toimintansa oikein, kun prosessien kommunikointiin ja toimintojen tahdistamiseen käytetään sanomanvälitystä. (3p)

   
      lapset                                    ajelupyyntö-                      kuljettaja 
          lähettävät ajelupyynnön,              kanava
          jossa kertovat oman                   __________
          tunnuksensa ja jäävät      ---------> |          |  --->   lukee kanavasta 8 ajelupyyntöä
          kuuntelemaan omaa kanavaansa          |__________|          lähettää  tiedon  näille lapsille,
                                       <------------------------      kunkin omaan kanavaan
                                       <------------------------
                                               ......
                                       <-------------------------                                                          
   
         lapset nousevat rekeen ja                                    jää odottamaan lasten tuloa
         ilmoittavat  kuljettajalle  ---------------------------->     rekeen eli kuuntelee omaa 
         olevansa reessä                           ( 8 kpl )           kanavaansa
   
                                                                      kun saanut vastauksen 8 lapselta
                                                                      lähtee liikkeelle ja ajaa
                                                                      kierroksen jäälllä
                                                 (8 kpl)                  
                                    <----------------------------      ilmoittaa  reessä oleville lapsille, 
   				                                    että  kierros on päättynyt
   								    (omaan reki-kanavaan)
                                               (8 kpl)
        Lapset kertovat poistuneensa  ------------------------------->                                           
                                                                        odottaa, että kaikki ovat poistuneet
                                                                        Tämän jälkeen aloittaa uuden kierroksen.
   

   Huom! Lapset voivat ilmoittaa ajelupyynnön myös suoraan kuljettajalle sen omaan kanavaan, mutta palvelukanavan käyttö tekee c)-kohdan toteuttamien helpommaksi.
   2. Kirjoita koodit reen kuljettajaprosessille ja lapsiprosesseille. Määrittele myös tarvittavat kanavat.(7 p)

   
   chan ajelu (int i);  #  palvelukanava, josta ajelua pyydetään ja ilmoitetaan oma id eli i
   chan lapset[n](char ); # jokaisella lapsella on oma kanava, jossa odottelee tietoa kyytiin pääsystä
   chan ajuri (char);
   chan reki[8] (char);   # reessä istuessaan lapset kuuntelevat tätä kanavaa
   
   process kuljettaja(){
     int i;            
     while (true) {
        for i=1 until 8 {
           receive ajelu (lid);
           send lapset[lid];                
      }
   
       for i=1 step 1 until 8 {
            receive ajuri();    # tieto, että lapsi istuu reessä                 
      }                                
     aja kierros järven jäällä;
     for i = 1 step 1 until 8 { # pura kuorma               
       send reki();            
       receive ajuri ();               
     } 
    }
   }
         
   process lapsi[i=1 to n] {
       while (true) {
          send ajelu(i);    # oma tunnus ajelupyyntöön
          receive lapset[i](”Kyytiin”);  # odotellaan lupaa nousta kyytiin
          nouse rekeen;             
          send ajuri(”Kyydissä”); # ilmoitus kuljettajalle
          istu reessä;
          receive reki (”Poistu)”; # ilmoitus  kierroksen päättymisestä              
          nouse reestä;
          send ajuri (”Poistuin”); # ilmoita kuljettajalle poistuneesi
          tee jotain muuta; syö vaikka makkaraa;
        }
   }
   

   Huom!
   • Vain kanavaan ajelu lähetyn sanoman sisällöllä merkitystä. Siinä kerrotaan oman pyytäjän oman kanavan tunnus. Tätä tarvitaan, jotta kuljettaja osaa ilmoittaa oikeille lapsille. Muiden kanavien sisällöllä ei ole merkitystä, merkitystä on vain sanomien järjestyksellä.
   • Reki-kanavaa käytetään kertomaan reessä oleville lapsille ajelun päättymisestä. Ajuri voisi myös muistaaa kyytiin nousseiden lapsien tunnukset. Kerätä ne vaikka 8 alkion taulukkoon. Vert. ”Nyt reki tyhjäksi lapset!” ja ” Matti, Kalle, ....ja Maija nouskaapas pois reestä!”
   3. Oletetaan, että rekiä onkin kaksi ja ne kulkevat niin kapeaa uraa, etteivät voi ohittaa toisiaan eli rekien järjestys säilyy koko ajan. Molempiin rekiin mahtuu sama määrä lapsia ja ne lähtevät liikkeelle vasta, kun reki on täynnä. Mitä muutoksia prosessien kommunikointiin ja koodiin tarvitaan, jotta prosessien yhteistoiminta sujuisi? (5p)

      2 kuljettajaprosessia:

      chan ajuri[2](); 
      chan  lapset[n](kid);   # lapsen kanavaan ilmoitetaan kuljettajan tunnus kid
      chan  reki[2] ; # kaksi reki-kanavaa
      chan  vuoro(); # varmistaa, että järjestys säilyy
      

      Reet voivat lastata lapsia samanaikaisesti, mutta säilyttää ajojärjestyksen: reki 1 ja sitten reki2.
      Pieni ongelma syntyy, jos reki 2 tulee ensin täyteen lapsia, mutta reestä 1 puuttuu vielä ainakin yksi lapsi, jolloin reki 2 joutuu turhaan odottamaan, että rekeen 1 tulisivat ne puuttuvat lapset. Odotusaika on lyhyt, jos halukkaista lapsia on paljon.
      Tämä ongelma estetään, jos reet lastataan järjestyksessä reki1 ja reki 2, mutta tällöin lastauksessa ei voida toimia rinnakkain. Tällöin kommunikointi kuljettajien kesken käydään jo lasatusvaiheessa.
      Paras ratkaisu olisi, jos reet voitaisiin lastata rinnakkain ja ensin täyteen tullut reki lähtisi heti liikkeelle. Tietenkin lastausalueella pitäisi nyt olla tilaa niin paljon, että reet voisivat tarvittaessa ohittaa toisensa.

      process  kuljettaja [j=1 to 2](){
        int i;                         
        while (true) {
           for i=1 until 8  {   # reet voivat lastata samaan aikaan lapsia              
           receive ajelu (lid);              
           send lapset[lid](j);  # kerrotaan kumpi kuljettaja                
         }               
        for i=1 step 1 until 8 {
           receive ajuri[j]();   tieto, että lapsi istuu reessä
          }                 
        if(j=1)  { # varmistetaan lähtöjärjestys reki 1 ensin
            lähde liikkeelle;
            send vuoro(); # anna 2. reelle lupa lähteä
         }
        else {
            receive vuoro(); # 0dota lähtölupaa
            lähde liikkeelle;               
            }                       
        aja kierros järven jäällä;
        for i = 1 step 1 until 8 { # pura kuorma             
           send reki[j]();
           receive ajuri[j] ();
         }
        }
      }
      
      process lapsi[i=1 to n] {
           while (true) {
              send ajelu(i);    # oma tunnus ajelupyyntöön
              receive[i](kid);    #odotellaan lupaa nousta kyytiin
              nouse rekeen kid;
              send ajuri(kid);    #ilmoitus kuljettajalle
              istu reessä;
              receive reki [kid](); #ilmoitus  kierroksen päättymisestä
              nouse reestä;
              send ajuri[kid] ();  #ilmoita kuljettajalle poistuneesi
              tee jotain muuta; syö vaikka makkaraa;
          }
      }
      

      Toinen tapa toteuttaa b): (vert. Jonotetaan lupalappuja, joilla pääsee kyytiin. Lupalappuja on aina kerralla 8 tarjolla. Lupalapun saaneet nousevat rekeen.) Nyt ei tarvita tietää mitään identiteettejä.

       chan ajelulupa (),
             ajuri (),
             reki ();
      
       process kuljettaja (){                       
           while (true) {
               for i=1 step 1 until 8  send ajelulupa();      # 8 ajelulupaa        
               for i=1 step 1 until 8  receive  ajuri();    # odota, kunnes8 lasta istuu reessä               
               aja kierros järven jäällä;
               for i = 1 step 1 until 8  send reki(); # pyydä lapsia poistumaan
               for i = 1 step 1 until 8  receive ajuri(); # odota, että kaikki kyydissä olleet poistuneet
              }
           }
      
       process lapsi[i=1 to n] {
              while (true) {                      
              receive ajelulupa(”Kyytiin”); # odotellaan lupaa nousta kyytiin
              nouse rekeen;
              send ajuri(”Kyydissä”); # ilmoitus kuljettajalle
              istu reessä;
              receive reki (”Poistu)”;# ilmoitus  kierroksen päättymisestä
              nouse reestä;
              send ajuri (”Poistuin”); # ilmoita kuljettajalle poistuneesi
              tee jotain muuta; syö vaikka makkaraa;
             }
       }
       
       Arvostelusta: