581332 Rinnakkaisohjelmointi (4 op / 2 ov) /Liisa Marttinen

HUOM! Andrewsin kirjaan perustuva, syksyllä 2005 luennoitu kurssi

Erilliskoe 2.2.2007

Kirjoita jokaiseen vastauspaperiin nimesi ja nimikirjoituksesi, henkilötunnuksesi tai opintonumerosi sekä kokeen nimi ja päivämäärä.

LUKKIUTUMINEN JA PANKKIIRIN ALGORITMI [15 p]

Mitä tarkoitetaan lukkiutumisella (deadlock), elolukkiutumisella (livelock) ja nälkiintymisellä (starvation)? (6 p)
Mikä on ns. pankkiirin algoritmin perusidea? (3 p)
Laske 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 6 yksikköä ja resurssia C 4 yksikköä. Tietyllä hetkellä varaustilanne on seuraavanlainen:
```
         prosessi   varattu      maxtarve
                     A B C        A B C
          p1         1 2 2        3 5 3
          p2         2 1 0        2 2 1
          p3         0 2 1        3 4 2
```
Prosessi p1 pyytää saada lisää yhden A-resurssin. Voidaanko se myöntää? Perustele vastauksesi esittämällä pankkiirin algoritmin suoritusvaiheet. Mitä tapahtuu, jos prosessille ei voida myöntää sen tarvitsemia resursseja? ( 6 p)

KARHU, HUNAJAPURNUKKA JA MEHILÄISET SEMAFORISSA [15 p]

Millä tavoin semafori on parempi mekanismi kuin lukkomuuttuja? Mitä huonoja puolia semaforilla on taas monitoriin verrattuna? (5 p)

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, ja mehiläiset jäävät odottamaan purnukan tyhjenemistä. Kun karhu on tyhjentänyt purnukan, se päästää mehiläiset töihin ja käy itse nukkumaan.
Kirjoita koodit karhuprosesille ja mehiläisprosesseille, kun niiden toimintojen koordinointi hoidetaan semaforeja käyttäen. (10 p)

         
 sem mutex = 1, # mutual exlusion
       pot_full = 0; #  is the pot full of honey
   int   portions =0;  # portions in the pot

   process bee[i=1 to N] {    
     while (true) {
        collect_honey();
        P(mutex);
        portions ++;
        if (portions = = H)  V(pot_full);  # let the bear eat
          else  V(mutex);                  # let the next bee in to fill
       }
   }

  process bear {
     while (true) {
        P(pot_full);  # 'sleep' = wait until the pot is full
        portions =0;  # eat all the honey
        V(mutex);     # let the bees start filling the pot again;
      }
   }

Arvostelusta:

KAIVURI JA KUORMA-AUTOT MONITORIKUOPASSA[15 p]
Pienellä hiekkakuopalla on töissä yksi kaivuri ja useita kuorma-autoja. Kaivuri on hiekkakuopan pohjalla ja mättää hiekkaa autoihin.Yksi kuorma-auto kerrallaan ajaa kuopan pohjalle, odottaa kunnes kuorma on täynnä ja sitten poistuu kuopalta. Kaivuri taas odottaa kunnes hiekkakuopan pohjalla on kuorma-auto ja täyttää auton lavan hiekalla. Anna monitoria käyttävä ratkaisu kaivurin ja kuorma-autojen toiminnan synkronointiin. Esitä myös monitoria käyttävien kaivuri- ja kuorma-autoprosessien koodit.

         
      monitor  Sandpit { 
      cond   start_loading;    # kaivuri saa alkaa täyttää
      cond   loaded;           # kuorma-auto saa poistua
      cond   proceed;          #  kuorma-auto saa ajaa kuopalle
      boolean occupied =false; # sandpit is occupied

      procedure Lorry_loading(){
        while (occupied) wait (proceed);  # jos kuopassa jo toinen auto, mene odottamaan
        occupied = true;
        aja kuopan pohjalle;
        signal (start_loading);
        wait (loaded);
        aja pois kuopalta;
        occupied = false;
        if (!empty(proceed)) signal_all(proceed);   # herätetään kaikki odottavat autot kilpailemaan
                                                       # pääsystä  hiekkakuopalle!
      }

      procedure Fill_lorry() {   # tämä prosessi on koko ajan monitorissa: joko odottamassa
         while (true) {        # kuormattavaa tai kuormaamassa!
          if (!occupied) wait(start_loading); # jos lastattavaa autoa ei ole, mene odottelemaan
          fill the lorry;
          signal (loaded);
        }
      }
    }

    process Digger()}
        call Sandpit.Fill_lorry();
    }

    process Lorry[i=1 to n](){
       while (true) {
          ajele hiekkakuopalle;
          call Sandpit  (Lorry_loading);
          vie hiekka jonnekin;
       } 
    }

Tässä ratkaisussa kuopalle ajot ja kuopalta poistumiset sekä kuorman täyttäminen ovat monitorin sisällä eli niiden aikana mikään muu prosessi ei pääse monitoriin. Kaikki tällöin tulevat kuorma-autot jäävät odottamaan monitorin jonoon. Mutta tässä tehtävässä tästä ei ole mitään haittaa, sillä on samantekevää, odottavatko kuorma-autot monitorin ulkopuolella tai sen sisällä, joka tapauksessa ne joutuvat odottamaan.
Itseasiassa juuri tällainen monitori kuvastaa tilannetta hiekkakuopalla. Kaivuri on koko ajan kuopassa joko työn touhussa tai odottelemassa. Yksi kuormuri pääsee ajamaan kuopalle, jossa odottelee kuorman lastauksen ajan ja ajaa sitten pois kuopasta. Muut lastaamaan tulleet kuormurit odottelevat vuoroaan kuopan reunalla.

Ratkaisu ei takaa järjestyksen säilymistä. Järjestys saadaan säilymään käyttämällä condition passing -tekniikkaa edellyttäen, että sekä monitorissa että monitoriin pyrittäessä jonot ovat FIFO-jonoja.

         
 procedure Lorry_loading(){
           if (occupied) wait (proceed);  # if there is a lorry already in the sandpit, start waiting
                else  occupied = true;
           aja kuopan pohjalle;
           signal (start_loading);
           wait (loaded);
           aja pois kuopalta;
           if (!empty(proceed)) signal(proceed);   # päästetään seuraava jo  monitorissa odottava 
                 else occupied =false ;         # tai  'uusi tulija'  hiekkakuopalle
        {

Arvostelusta:

PARTURIT JA ASIAKKAAT SANOMIA VAIHDELLEN [15 p]
Esitä "nukkuvan parturin ongelman" ratkaisu käyttäen sanomanvälitystä. Partureita oletetaan olevan useita.

Esitä ensin sanallisesti tai selkeänä kaaviokuvana, miten parturit ja asiakkaat viestivät. (5 p)

Kirjoita parturi- ja asiakasprosessien koodit, kun prosessien toiminta synkronoidaan sanomanvälitystä käyttäen. (10 p)

         
chan service(int clientid, ...); # tässä voisi myös ilmoittaa, mitä palvelua haluaa
chan client[n](int barberid);
chan barber[m](int barberid);

process client [i=1 to N] {
  int barnerid;
  while (true) {
     .........
     mene parturiin;
     send service(i);  # ilmoita oman kanavasi tunnus
     receive client[i](barberid);  # jää odottamaan tietoa parturilta
     siirry 'oman' parturisi tuoliin;
     send barber[barberid](i);   # ilmoita parturille olevasi valmis
     receive client[i](barberid)  #odota parturin ilmoitusta työn valmistumisesta
     nouse tuolista;
     send barber[barberid](i);   #ilmoita poistuneesi
    }
    
process barber[j=1 to M]{
  int clientid;
  while(työaika) {
    receive service(clientid); # odottele asiakkaita ja ota seuraavan tunnus kanavasta
    send client[clientid](j);  # ilmoita asiakkaalle oma tunnuksesi
    receive barber[j](clientid); # odottele, kunnes asiakas istuu tuoliin
    suorita tukan leikkkuu tms;
    send client[clientid](j);  # ilmoita toimenpiteen valmistumisesta
    receive barber[j](clientid) # odota, että asiakas on poistunut
   }

Ratkaisussa kullakin asiakkaalla ja parturilla on oma yksityinen kanavansa. Parturin täytyy tietää asiakkaan kanavatunnus ja asiakkaan parturin kanavatunnus. Muu viestien sisältö ei ole tärkeää. Jo pelkkä viestien saapuminen riittää tahdistamaan toiminnan.

Arvostelusta:

Muistin virkistämiseksi =>