Vastausohjeita:

• Lue tehtävä kunnolla - ymmärrä tehtävä oikein. Mitä oikeastaan kysytään?
• Mitä algoritmin halutaan tekevän? Jos tehtävän voi mielestäsi ymmärtää monin tavoin, selitä oma tulkintasi.
• Vastaa selkeästi annettuun tehtävään ja perustele sanottavasi.
• Käytä kurssikirjan syntaksimerkintöjä. Käytä kuvaavia muuttujien tunnuksia.
• Kommentoi aina synkronointiin ja poisulkemiseen liittyvät kohdat.
• Piirrä kuvia ja kaavioita, vaikka niitä ei erikseen pyydetä.

1. Semaforit ja niiden käyttö [16 p]
   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ä.
   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; 
      }
    }
    
    

2. Sirkuksen apupoika monitorina [20] 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)

3. Sanomanvälitystä ja laskentapalvelua [15 p] 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)
   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)