581332-8 Rinnakkaisohjelmistot

Erilliskuulustelu 26.9.2006

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

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. Vastaa lyhyesti seuraaviin kysymyksiin [15p]
   1. Miksi tuottajan ja kuluttajan väliin kannattaa laittaa puskuri? Miten puskurin koko vaikuttaa järjestelmän suorituskykyyn? (2 p)
   2. 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ä? (5 p)
   3. Mitä tarkoitetaan lukkiutumisella (deadlock), elolukkiutumisella (livelock) ja nälkiintymisellä (starvation)? (3 p)
   4. Mihin ns. pankkiirin algoritmia käytetään? Mikä on pankkiirin algoritmin perusidea? Mitä tapahtuu asiakkaalle, jos pankkiiri ei suostu asiakkaan pyyntöön? Mitä tapahtuu, jos resurssimanageri antaa resurssiyksikön, vaikka pankkiirin algoritmin mukaan ei pitäisi? (5 p)

2. Semaforilla varustettu yhteisön keittiö [15 p]
   Yhteisön keittiössä on iso pata, josta nälkäiset käyvät noutamassa itselleen ruoka-annoksen. Jos pata on tyhjä, niin ruokailija herättää kokin ja odottaa, kunnes kokki on saanut padan täytettyä (pataan mahtuu M annosta). Asiakkaiden ja kokin käyttäytymistä kuvaavat prosessit:

    process customer[1:n] {                      process cook {
           while (true) {                                while (true) {
             get serving from the pot;                      sleep; 
             eat;                                           put M servings in the pot;   
            }                                              }
           }                                              }
   

   Kirjoita asiakkaiden ja kokin toimenpiteiden koodien keskeiset osat käyttäen semaforeja ja P/V-operaatioita.

3. Monitoroitu silta [15 p]
   Kahden kylän A ja B välissä olevan joen yli kulkee niin kapea silta, että autot voivat ajaa sitä pitkin vain yhteen suuntaan kerrallaan. Kun sillalla kulkee autoja A:sta B:hen, niin B:stä A:han haluavien täytyy odottaa. Silta ei myöskään ole kovin vankka, joten sillalla saa olla korkeintaan 10 autoa yhdellä kertaa.
   Kirjoita koodi sillan käyttöä valvovalle monitorille Silta. Laadi myös koodit autoprosesseille. Käytä 'Signal and Continue' -semantiikkaa. Pyri tekemään ratkaisustasi mahdollisimman reilu. Samalta suunnalta tulevien autojen tulee päästä sillalle saapumisjärjestyksessä eikä kumpikaan suunta saisi vallata siltaa vain yhden suunnan liikenteelle. Oikein toimivasta ratkaisusta saa maksimissaan 10 p, reiluuden huomioonottaminen tuo lisää 1-5 p.

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)