581332 Rinnakkaisohjelmointi, välikoe 8.5.2012               in EnglishOther side in English

Kirjoita jokaiseen vastauspaperiisi kurssin nimi, pvm, oma nimi, nimikirjoitus ja opiskelijanumero.
  1. [5 p] Puomisynkronointi semaforeilla. Ohjelmassa on N säiettä ja laskenta koostuu useasta erillisestä vaiheesta. Jokaisen säikeen pitää suoritettaa nykyinen laskennan vaihe (vaihe i) loppuun, ennen kuin mikään niistä voi jatkaa suoritusta seuraavasta vaiheesta (vaihe i+1). Sama synkronointiongelma toistuu nyt uuden vaiheen (vaihe i+1) kanssa.

    Anna tämän synkronointiongelman pseudokooditason ratkaisu semaforeja käyttämällä. Muista alustukset seuraavaa varten. Selitä, miksi ratkaisusi on oikein.

  2. [5 p] Mehiläisparvi, karhut ja IRR monitori. Mehiläisparvi (N mehiläistä) ruokkii loukkuun joutuneita karhuja (B kpl) keräämällä niille hunajaa. Karhujen elämä loukossa on vain syömistä ja odottelua. Mehiläiset keräävät hunajaa ja laittavat hunaja-annoksensa purkkiin. Usea mehiläinen voi täyttää purkkia samanaikaisesti, mutta purnukka ei saa ylitäyttyä. Kun purnukka on täynnä (H annosta), viimeisen annoksen laittanut mehiläinen herättää kauiten nukkuneen karhun syömään ennenkuin poistuu paikalta. Hunajaa tuovat mehiläiset jäävät tällöin odottamaan purnukan tyhjenemistä. Kun karhu on tyhjentänyt purkin, se päästää mehiläiset taas täyttämään purkkia ja käy itse nukkumaan.

    Ohjelmoi purnukan täytön ja tyhjentämisen synkronoinnin ratkaisu monitorin avulla. Monitori sisältää siis vain synkronointiongelman ratkaisun - hunajan kerääminen, purkin täyttäminen ja tyhjentäminen tapahtuvat monitorin ulkopuolella. Esitä mehiläisprosessien (N kpl), karhuprosessien (B kpl) ja monitorin pseudokoodi.

  3. [5 p] Tarkastellaan alla olevaa Ricart-Agrawalan algoritmia 10.2.
    1. [3 p] Mikä on algoritmin tarkoitus? Milloin prosessi tietää, että on sen vuoro päästä kriittiseen vaiheeseen? Mikä on Main ja Receive prosessien merkitys. Mitkä tietorakenteet ovat yhteiskäyttöisiä ja mille kaikille prosesseille ne ovat yhteiskäyttöisiä?
    2. [1 p] Oletetaan, että prosesseja on hyvin monta ja että pääosa niistä ei juuri koskaan käytä kriittistä vaihetta. Ne ovat ns. hiljaisia (quiescent) solmuja. Minkä ongelman tällaiset hiljaiset solmut aiheuttavat ja kuinka ongelma on ratkaistu algoritmissa?
    3. [1 p] Receive:n rivillä p3 on "<<" operaattori. Mitä se tekee ja miksi sitä tarvitaan? Voisiko sen korvata tavallisella "<" operaattorilla? Miksi?

k