581332 Rinnakkaisohjelmointi, 4 op, erilliskoe 2.2.2007   
(Kurssikuvaus 1.8.2006, Ben-Ari'n kirjaan perustuen)

Kirjoita jokaiseen vastauspaperiisi seuraavat tiedot: nimi ja nimikirjoitus, henkilötunnus tai opiskelijanumero, kurssin nimi ja sivunumero.
  1. [9 p] Monitori
    1. [3 p] Mikä on monitori? Vertaile monitorien ja semaforien käyttöä rinnakkaisohjelmien toteuttamisessa. Edut vs. haitat?
    2. [6 p] Monitoroitu purnukka. Mehiläisparvi ruokkii loukkuun joutunutta karhua keräämällä sille hunajaa. Karhun elämä loukussa on vain purnukasta 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.

      Anna monitoriin perustuva ratkaisu purnukan käyttön synkronointiin. Esitä monitorin lisäksi mehiläisprosessien (N kpl) ja karhuprosessin pseudokoodit. Voit käyttää ratkaisussasi monitorin ehtomuuttujia (CV) ja niihin kohdistuvia operaatioita WaitC(cond) ja SignalC(cond). Voit valita, mitä signalointisemantiikkaa (signalling semantics, precedence) monitorisi käyttää.

     
  2. [9 p] Lukkiutuminen (deadlock)
    1. [3 p] Anna Aterioivien filosofien ongelmaan semaforeihin perustuva ratkaisu, jossa on lukkiutumisongelma. Anna lukkiutuva skenario.
    2. [6 p] Lukkiutuminen voi tapahtua ainoastaan tiettyjen neljän ehdon vallitessa. Mainitse nämä ehdot. Selitä myös kunkin ehdon kohdalla, kuinka a-kohdan ratkaisua tulisi muuttaa, jotta lukkiutuminen estetään juuri kyseinen ehto rikkomalla.

     
  3. [9 p] Dekkerin algoritmi (Alg. 3.10 kääntöpuolella) kriittisen vaiheen suojaamiseksi kahden prosessin tapauksessa ympäristöön, jossa ei ole laitteisto- tai käyttöjärjestelmätukea samanaikaisuuden hallintaan. Osoita, että
    1. algoritmi ratkaisee poissulkemisongelman (mutual exclusion problem)
    2. algoritmi ei lukkiudu
    3. kumpikaan prosessi ei nälkiinny
       
  4. [9 p] Anna semaforeihin perustuva ratkaisu tuottaja-kuluttaja -ongelmaan (producer-consumer problem). Tuottaja-prosessit kirjoittavat yhteiskäytössä olevan puskurin seuraavaan vapaaseen lohkoon ja odottavat, jos tilaa ei ole. Kuluttaja-prosessit lukevat seuraavana vuorossa olevan lohkon puskurista ja odottavat, jos puskuri on tyhjä. Puskurin koko on N lohkoa. Tuottajat ja kuluttajat ovat ikuisessa loopissa tehden aina välillä jotain muuta työtä ja lopulta kirjoittamista tai lukemista puskurista. Lukijoita ja kirjoittajia on molempia useita.

    Erittele ratkaisussasi yhteisessä muistissa olevan puskurin, semaforien ja muiden tietorakenteiden alustus sekä tuottajien ja kuluttajien pseudo-koodit. Pidä erityisesti huoli, että kukin kirjoittaja kirjoittaa omaa vapaaseen lohkoonsa, ja että yhteen lohkoon kirjoitettu tieto menee vain yhdelle lukijalle.