Other side in English

581332 Rinnakkaisohjelmointi, 4 op, kurssikulustelu 12.12.2008

1. [11 p] Kriittisen vaiheen ongelma
1. Mikä on kriittisen vaiheen ongelma?
2. Milloin ongelma olisi hyvä ratkaista keskeytykset estämällä ja milloin taas ei?
3. Milloin ongelma olisi hyvä ratkaista lukko-muuttujalla ja busy-wait -odotuksella ja milloin taas ei?
4. Milloin ongelma olisi hyvä ratkaista semaforin avulla ja milloin taas ei?
5. Milloin ongelma olisi hyvä ratkaista monitorin avulla ja milloin taas ei?
6. Milloin ongelma olisi hyvä ratkaista Ricart-Agrawalan kolikko-pohjaisella algoritmilla ja milloin taas ei?
    
2. [11 p] Lukkiutuminen. Järjestelmässä S on viisi resurssia: suuri muistialue A (2 kpl) tiedon prosessointiin, tietokanta B (1 kpl), tietokanta C (1 kpl), tulostimet D (2 kpl) ja näppäimistön käyttö E (1 kpl). Kutakin resurssia voi käyttää vain yksi prosessi kerrallaan.
   
   Järjestelmässä on neljä prosessia, P1-P4. P1:llä on hallussaan yksi kpl resursseja A, C ja D. P2:lla on hallussaan yksi kpl resursseja A ja B. P3:lla on hallussaan yksi kpl resurssia D. P4:lla ei ole hallussaan mitään resursseja.
   
   Juuri nyt edetäkseen P1 tarvitsee yhden kpl resursseja B ja E, P2 tarvitsee yhden kpl resursseja C ja E, P3 tarvitsee 1 kpl resurssia E ja P4 tarvitsee yhden kpl resursseja A, C ja E.
    
   1. Mitä lukkiutuminen tarkoittaa? Mitä tarkoittaa se, että järjestelmä ei ole lukkiutunut?
   2. Milloin järjestelmä voi lukkiutua?
   3. Onko järjestelmä S lukkiutumistilassa vai ei?
   4. Kuinka järjestelmän S lukkiutumisen olemassaolo tarkastettaisiin Dijkstran lukkiutumisen havaitsemis -algoritmin (DDA, Deadlock Detection Algorithm) avulla? Sehän käyttää taulukoita A (allokaatio matriisi) ja Q (pyyntömatriisi) sekä vektoreita R (kaikki resurssit), V (vapaat resurssit) ja W (työvektori).
   5. Miten lukkiutumisen synnyn voisi estää ennakolta (yleensä ja erityisesti tässä tapauksessa)
       
3. [11 p] Mehiläisparvi ja karhu. Mehiläisparvi (N mehiläistä) ruokkii loukkuun joutunutta karhua keräämällä sille hunajaa. Karhun elämä loukossa on vain syömistä ja odottelua. Mehiläiset keräävät hunajaa ja laittavat hunaja-annoksensa purkkiin yksi kerrallaan. Kun purnukka on täynnä (H annosta), viimeisen annoksen laittanut mehiläinen herättää 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), karhuprosessin ja monitorin pseudokoodi. Selvitä vielä sanallisesti, missä tilanteissa tarvitaan poissulkemista ja/tai synkronointia sekä kuinka ne toteutuvat ratkaisussasi. Tee tarvittavat oletukset monitorin piirteistä ja kirjoita ne näkyville.
   
   
4. [11 p] Tarkastellaan liitteenä olevaa Ricart-Agrawalan algoritmia 10.3.
   1. Mikä on algoritmin tarkoitus? Mikä on prosessien Main ja Receive merkitys? Mihin niitä tarvitaan? Voisiko ne yhdistää yhdeksi prosessiksi? Miten tai miksi ei?
   2. Mikä on requested joukon merkitys ja miten se päivittyy? Mikä on granted joukon merkitys ja miten se päivittyy?
   3. Oletetaan, että kolme prosessia (p1, p2 ja p3) yrittävät nyt kaikki yhtä aikaa päästä kriittiseen vaiheeseen. Viimeksi kriittinen vaihe oli p1:llä ajankohtana 550, p2:llä ajankohtana 7700 ja p3:lla ajankohtana 33. Järjestelmässä ei ole muita prosesseja. Näytä, miten ja missä järjestyksessä prosessit p1, p2 ja p3 pääsevät kriittiseen vaiheeseen. Näytä erityisesti kaikki valitsemiseen liittyvät viestit (lähettäjä, vastaanottaja, viestin tyyppi, viestin sisältö) ja miten niihin reagoidaan?