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

1. LUKKIUTUMINEN JA PANKKIIRIN ALGORITMI [15 p]
   1. Mitä tarkoitetaan lukkiutumisella (deadlock), elolukkiutumisella (livelock) ja nälkiintymisellä (starvation)? (6 p)
   2. Mikä on ns. pankkiirin algoritmin perusidea? (3 p)
   3. 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)

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

   1. Millä tavoin semafori on parempi mekanismi kuin lukkomuuttuja? Mitä huonoja puolia semaforilla on taas monitoriin verrattuna? (5 p)
   2. 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)

3. 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.

4. PARTURIT JA ASIAKKAAT SANOMIA VAIHDELLEN [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 viestivät. (5 p)
   2. Kirjoita parturi- ja asiakasprosessien koodit, kun prosessien toiminta synkronoidaan sanomanvälitystä käyttäen. (10 p)