581332-8 Rinnakkaisohjelmointi

Erilliskuulustelu 3.2.2006
Kirjoita jokaiseen vastauspaperiisi nimikirjoituksesi ja nimen selvennys sekä kokeen nimi että päivämäärä.

1. Vähän sitä sun tätä [15 p]
   1. 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ä? (4p)
   2. Miten etäproseduuri eroaa tavallisesta proseduurista? Mitä etäproseduuria kutsuttaessa tapahtuu kutsuvalle prosessille ja kutsutulle proseduurille? (3 p)
   3. Laske ns. pankkiirin algoritmia käyttäen seuraava esimerkki. Järjestelmässä on kolmea resurssi-tyyppiä A, B ja C. Resurssia A on 4 yksikköä, resurssia B 4 yksikköä ja resurssia C 3 yksikköä. Tietyllä hetkellä varaustilanne on seuraavanlainen:

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

      Prosessi p1 pyytää saada lisää yhden A-resurssin ja yhden B-resurssin. Voidaanko se myöntää? Perustele vastauksesi esittämällä pankkiirin algoritmin suoritusvaiheet. Mitä tapahtuu, jos prosessille ei voida myöntää sen tarvitsemia resursseja? Mihin pankkiirin algoritmia oikein tarvitaan? ( 8 p)

2. Semaforilla tahdistettu rotkonylitys [15p]
   Paviaanit ylittävät rotkon heilauttamalla itsensä köyden avulla rotkon toiselle puolen. Yhdessä köydessä voi roikkua korkeintaan 5 paviaania. Tätä raskaampi kuorma katkaisee köyden ja syöksee paviaanit rotkoon. Ylityskohta on niin kapea, että rotkon voi samanaikaisesti ylittää vain yhteen suuntaa, muuten ylittäjät törmäävät ja taas putoavat rotkoon.
   Käytetään semaforeja koordinoimaan paviaanien rotkon ylitystä. Kirjoita koodi eri suuntiin rotkon ylitse haluaville paviaaneille (paviaaniprosesseille). Ratkaisun ei tarvitse olla reilu, ts. paviaanien virta yhteen suuntaan voi pakottaa toiseen suuntaan haluavat odottamaan pitkiäkin aikoja, mutta samalla rotkon reunalla odottavat päästetään jatkamaan saapumisjärjestyksessä.

3. Pata monitorissa [15 p]
   Yhteisön keittiössä on iso pata, josta yhteisön asukkaat käyvät noutamassa itselleen ruoka-annoksia. Jos pata on tyhjä, niin asukas herättää kokin ja odottaa, kunnes kokki on saanut padan täytettyä ruualla (pataan mahtuu M annosta).
   Asukkaiden ja kokin käyttäytymistä kuvaavat prosessit:

    process asukas[1:n] {
   	      while (true) {ota annos padasta; syö;  kuluta kalorit;}
   	   }
   	   process kokki{
   	      while (true) {laita M annosta pataan; nuku}
   	   }  	   
   

   Toteuta tarvittava synkronointi ja poissulkeminen monitoria käyttäen sekä esitä asukasprosessien (N kpl) ja kokkiprosessin koodit. Selvitä vielä sanallisesti, missä tilanteissa tarvitaan poissulkemista ja synkronointia ja kuinka ne toteutuvat ratkaisussasi.

4. Parturit ja asiakkaat käyttäen sanomanvälitystä (15 p)
   Esitä "nukkuvan parturin ongelman" ratkaisu käyttäen sanomanvälitystä. Partureita oletetaan olevan useita.
   1. Esitä ensin sanallisesti tai selkeänä kaaviokuvana, miten parturit ja asiakkaat toimivat. (5 p)
   2. Kirjoita ratkaisu, jossa parturi- ja asiakasprosessit viestivät sanomanvälitystä käyttäen. (10 p)