Opiskeltava alue: Andrews: 4 Semaphores, Stallings 6.1-6.6: Concurrency - Deadlock and Starvation. Andrewsin kirjan sivut 203-215 kapplaeesta 5. Monitors.

Harjoituksissa käytetään semaforeja poissulkemisessa ja synkronoinnissa, sekä pohditaan lukkiutumisongelmia. Harjoituksissa tulee esiin "Baton passing" -tekniikan käyttö ja siitä saadut hyödyt.
Monitoriin liittyvissä harjoituksissa tutustutaan monitorin käyttöön prosessien synkronoinnissa.

1 - TUNNELI, YKSISUUNTAINEN LIIKENNE JA "SEMAFORIVALOT"

Vuoren läpi on kaivettu etelä-pohjoissuunnassa tunneli, jossa autot voivat ajaa vain yhteen suuntaan kerrallaan. Tunnelia käyttävät autoprosessit kutsuvat proseduureja enter_tunnel(suunta) ja exit_tunnel(suunta) pyrkiessään tunneliin ja poistuessaan tunnelista. Suunta tarkoittaa auton etenemissuuntaa (etelään tai pohjoiseen). Autoprosessien koodi on:

   process car[1 to N] {
	...
	enter_tunnel(suunta);
	aja_tunnelissaa();
	exit_tunnel(suunta);
   }

Esitä proseduurien enter_tunnel() ja exit_tunnel() koodi. Ratkaisun täytyy sallia tunnelin tehokas käyttö, eli tunnelissa täytyy voida olla useita autoja kerrallaan. Sen ei tarvitse olla reilu, ts. odotusajat saavat muodostua pitkiksi. Perustele lyhyesti se, että ratkaisusi toimii.

[Vihje: tarvitset omat semaforit ja laskurit eri suuntiin ajaville autoille.]

2 - HUVIPUISTON KARUSELLI

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 asiakkaat poistuvat karusellista muihin puuhiin (kenties palatakseen karuselliin myöhemmin).

Kirjoita asiakkaiden ja karusellin koodien keskeiset osat. Karusellissa istuminen on asiakkaan koodissa pelkkää odotusta.

3 - ATERIOIVAT FILOSOFIT

1. Aterioivat filosofit on kirjallisuuden klassikko, mutta millaisia tietojenkäsittelyyn liittyviä tilanteita filosofien ongelma oikeastaan pyrkii havainnollistamaan? Mitä tällöin ovat filosofit, haarukat, spagetit ja mahdolliset sihteerit, jotka voisivat jaella haarukoita pyytäjille?
2. Lukkiutumisriskin syntymiselle on kolme staattista edellytystä. Miten kukin näistä täyttyy aterioivien filosofien ongelmassa?
   Voidaanko filosofien tapauksessa lukkiutuminen estää muuttamalla haarukoiden käyttösääntöjä siten, että jokin em. ehdoista ei täyty. Tarkastele kutakin sääntöä erikseen.
3. Filosofit toteavat, että vain kaksi heistä voi olla yhtäaikaa syömässä. He heittävät yhden haarukan menemään ja sopivat, että jokainen saa käyttää mitä tahansa kahta haarukkaa. Haarukoista huolehtimaan palkataan tarjoilija ja tiskaaja. Kun filosofille tulee nälkä, hän istahtaa omalle paikalleen pöytään ja pyytää tarjoilijalta haarukat. Filosofi odottaa, että saa tarjoilijalta kaksi haarukkaa. Kun filosofi on syönyt, hän palauttaa haarukat tiskaajalle. Ohessa filosofien koodi:

      process filosofi[i=1 to 5] 
      {
         while (true) {
           ajattele();
           V(pyydä_haarukat);
           P(saa_aloittaa);   
           syö();
           V(vapauta_haarukat);
         }
      }
   

   Kirjoita tarjoilija- ja tiskaajaprosessien koodit. [Huomaa: Tässä odotetaan kahta erillista tapahtumaa: haarukoiden pyytämistä ja palauttamista. Se hoituu parhaiten s.e. kumpaakin varten on oma prosessi!]

4 - PANKKIIRIN ALGORITMI

Laske ns. pankkiirin algoritmia käyttäen seuraava esimerkki. Järjestelmässä on kolmea resurssityyppiä A, B ja C. Resurssia A on 9 yksikköä, resurssia B 3 yksikköä ja resurssia C 6 yksikköä. Tietyllä hetkellä varaustilanne on seuraavanlainen:

prosessi     varattu   pyytänyt    maxtarve
              A B C     A B C       A B C
   p1         1 0 0     0 0 0       3 2 2
   p2         5 1 1     1 0 1       6 1 3
   p3         2 1 1     0 0 0       3 1 4
   p4         0 0 2     0 0 0       4 2 2

5 - MONITORIKYLPYJÄ

1. Kerro, miten monitori Bathroom toimii ja mihin sen muuttujia käytetään?
2. Toimiiko monitori kaikissa tilanteissa moitteettomasti? Jos ei toimi, niin mitä puutteita siinä on? Miten koodia pitäisi muuttaa, jotta monitori toimisi oikein?
3. Kirjoita koodit Girl- ja Boy-prosesseille, jotka käyttävät monitoria Bathroom kylpyhuoneen jakamiseen.

   monitor Bathroom {
   cond  bath_free;
   int girls = 0;
   int boys = 0;
   
   procedure Enter_Boy (){
         if (girls !=0) wait (Bath_free);
         boys ++;
       }
   
   procedure Enter_girl(){
        if (boys!=0) wait(Bath_free);
        girls++;
      }
   
   procedure Exit_boy(){
        boys --;
        if (boys==0)  signal_all(Bath_free);
      }
   procedure Exit_girl (){
        girls--;
        if (girls==0) signal_all(Bath_free);
      }
   }
   

6 - PURNUKAN KÄYTTÖ MONITORIIN

Mehiläisparvi ruokkii loukkuun joutunutta karhua keräämällä sille hunajaa. Karhun elämä loukossa 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 ennenkuin poistuu paikalta. Seuraavat paikalle saapuvat mehiläiset jäävät odottamaan purnukan tyhjenemistä. Kun karhu on tyhjentänyt purkin, se päästää mehiläiset töihin ja käy itse nukkumaan.

Ohjelmoi purnukan täyttö ja tyhjentäminen monitoriin Honey_pot ja esitä mehiläisprosessien (N kpl) ja karhuprosessin koodi. Selvitä vielä sanallisesti missä tilanteissa tarvitaan poissulkemista ja synkronointia ja kuinka ne toteutuvat ratkaisussasi.