581332-8 Rinnakkaisohjelmistot

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

• 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ä.

  Miksi tuottajan ja kuluttajan väliin kannattaa laittaa puskuri? Miten puskurin koko vaikuttaa järjestelmän suorituskykyyn? (2 p)

• 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)

  Mitä tarkoitetaan lukkiutumisella (deadlock), elolukkiutumisella (livelock) ja nälkiintymisellä (starvation)? (3 p)

  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?

1. 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] {
      while (true) {
         get serving from the pot; 
         eat; 
      }
   }

   process cook {
      while (true) {
         sleep; 
         put M servings in the pot; 
      }
   }

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

1. Monitoroitu silta [15p]
   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.

2. 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)

1. Vastaa lyhyesti seuraaviin kysymyksiin [15p]

   1. Mitä tarkoittaa, että tietty toimenpidesarja on suoritettava "atomisena"? Käytä esimerkkinä toimenpidesarjaa < x = x+1; y = y+1; >. (3 p)

2. Mitä tarkoittaa lukkiutuminen (deadlock)? Miten se eroaa nälkiintymisestä (starvation)? Lukkiutuminen on mahdollista vain tiettyjen ehtojen ollessa voimassa. Mitkä nämä ehdot ovat? Selitä, mitä kukin ehto tarkoittaa resurssien jakelussa. (6 p)

3. Miten etä proseduuri eroaa tavallisesta proseduurista? Mitä etäproseduuria kutsuttaessa tapahtuu kutsuvalle prosessille ja kutsutulle proseduurille? (3 p)

4. 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ä ? (3 p)

5. Semaforilla tahdistettu karuselli [15 p]
   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 kyydissä olleet poistuvat karusellista muihin puuhiin (kenties palatakseen karuselliin myöhemmin) ja karuselli täyttyy taas seuraavista huvittelijoista.

   Kirjoita asiakasprosessien ja karuselliprosessin koodien keskeiset osat, kun prosessien koordinointiin käytetään semaforeja. Karusellissa istuminen on asiakkaan koodissa pelkkää odotusta.

6. Monitoroitu purnukka [15 p]
   Mehiläisparvi ruokkii loukkuun joutunutta karhua keräämällä sille hunajaa. Karhun elämä loukussa 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, ja mehiläiset jäävät odottamaan purnukan tyhjenemistä. Kun karhu on tyhjentänyt purkin, se päästää mehiläiset taas töihin ja käy itse nukkumaan.

   Ohjelmoi purnukan käyttöä synkronoivat osat monitoriin sekä esitä niiden lisäksi mehiläisprosessien (N kpl) ja karhuprosessin koodi.

7. Sanomanvä litystä ja yhteinen pankkitili [15 p]
   Pankkitili on usean henkilön käytössä, joista jokainen voi tallettaa tilille tai nostaa tililtä rahaa. Tili ei saa koskaan mennä negatiiviseksi. Koodaa palvelin, joka huolehtii tilin käytöstä. Asiakkaat voivat pyytää joko jonkun rahasumman talletusta tai rahasumman nostoa. Jos tilillä ei ole tarpeeksi rahaa, niin pyyntöä viivytetään. Asiakkaat ja palvelin käyttävät sanomanvälitystä kommunikointiin.

Muistin virkistämiseksi =>