581332-8 Rinnakkaisohjelmistot
Erilliskuulustelu 26.9.2006
Kirjoita jokaiseen
vastauspaperiisi nimikirjoituksesi ja nimen selvennys sekä
kokeen nimi että päivämäärä.
Lue tehtävä kunnolla - ymmärrä tehtävä oikein. Mitä oikeastaan kysytään?
Mitä algoritmin halutaan tekevän? Jos tehtävän voi mielestäsi ymmärtää monin tavoin, selitä oma tulkintasi.
Vastaa selkeästi annettuun tehtävään ja perustele sanottavasi.
Käytä kurssikirjan syntaksimerkintöjä . Käytä kuvaavia muuttujien tunnuksia.
Kommentoi aina synkronointiin ja poisulkemiseen liittyvät kohdat.
Piirrä kuvia ja kaavioita, vaikka niitä ei erikseen pyydetä.
Miksi tuottajan ja kuluttajan väliin kannattaa laittaa puskuri? Miten puskurin koko vaikuttaa järjestelmän suorituskykyyn? (2 p)
Miten monitorin signal-operaatiolle määritellyt toimintatavat "Signal and Wait" ja "Signal and Continue" eroavat toisistaan? Miksi tällaisia täsmennyksiä on tarpeen määritellä? (4p)
Mitä tarkoitetaan lukkiutumisella (deadlock), elolukkiutumisella (livelock) ja nälkiintymisellä (starvation)? (3 p)
Mihin ns. pankkiirin algoritmia käytetään? Mikä on pankkiirin algoritmin perusidea? Mitä
tapahtuu asiakkaalle, jos pankkiiri ei suostu asiakkaan pyyntöön? Mitä tapahtuu, jos resurssimanageri antaa resurssiyksikön, vaikka pankkiirin algoritmin mukaan ei pitäisi?
YHTEISÖN KEITTIÖ [15 p]
Yhteisön keittiössä on iso pata, josta nälkäiset käyvät noutamassa itselleen ruoka-annoksen. Jos pata on tyhjä, niin ruokailija herättää kokin ja odottaa, kunnes kokki on saanut padan täytettyä (pataan mahtuu M annosta).
Asiakkaiden ja kokin käyttäytymistä kuvaavat prosessit:
process customer[1:n] { while (true) { get serving from the pot; eat; } } process cook { while (true) { sleep; put M servings in the pot; } }
Kirjoita asiakkaiden ja kokin toimenpiteiden koodien keskeiset osat käyttäen semaforeja ja P/V-operaatioita.
Monitoroitu silta [15p]
Kahden kylän A ja B
välissä olevan joen yli kulkee niin kapea silta, että
autot voivat ajaa sitä pitkin vain yhteen suuntaan kerrallaan.
Kun sillalla kulkee autoja A:sta B:hen, niin B:stä A:han
haluavien täytyy odottaa. Silta ei myöskään ole
kovin vankka, joten sillalla saa olla korkeintaan 10 autoa yhdellä
kertaa. Kirjoita koodi sillan käyttöä valvovalle
monitorille Silta. Laadi myös koodit autoprosesseille. Käytä
'Signal and Continue' -semantiikkaa. Pyri tekemään
ratkaisustasi mahdollisimman reilu. Samalta suunnalta tulevien
autojen tulee päästä sillalle saapumisjärjestyksessä
eikä kumpikaan suunta saisi vallata siltaa vain yhden suunnan
liikenteelle.
Oikein toimivasta ratkaisusta saa maksimissaan 10
p, reiluuden huomioonottaminen tuo lisää 1-5 p.
Parturit ja
asiakkaat käyttäen sanomanvälitystä (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 toimivat. (5 p)
Kirjoita ratkaisu, jossa parturi- ja asiakasprosessit viestivät sanomanvälitystä käyttäen. (10 p)
Vastaa lyhyesti seuraaviin kysymyksiin [15p]
Mitä tarkoittaa, että tietty toimenpidesarja on suoritettava "atomisena"? Käytä esimerkkinä toimenpidesarjaa < x = x+1; y = y+1; >. (3 p)
Mitä tarkoittaa lukkiutuminen (deadlock)? Miten se eroaa nälkiintymisestä (starvation)? Lukkiutuminen on mahdollista vain tiettyjen ehtojen ollessa voimassa. Mitkä nämä ehdot ovat? Selitä, mitä kukin ehto tarkoittaa resurssien jakelussa. (6 p)
Miten etä proseduuri eroaa tavallisesta proseduurista? Mitä etäproseduuria kutsuttaessa tapahtuu kutsuvalle prosessille ja kutsutulle proseduurille? (3 p)
Miten monitorin signal-operaatiolle määritellyt toimintatavat "Signal and Wait" ja "Signal and Continue" eroavat toisistaan? Miksi tällaisia täsmennyksiä on tarpeen määritellä ? (3 p)
Semaforilla
tahdistettu karuselli [15 p]
Huvipuistossa on N
asiakasprosessia ja yksi karuselliprosessi. Asiakkaat ajelevat kerta
toisensa jälkeen karusellissa, johon mahtuu kerrallaan C
asiakasta (C on pienempi kuin N). Karuselli käynnistyy
kuitenkin vasta, kun se on täynnä . Kunkin ajokerran
jälkeen kaikki kyydissä olleet poistuvat karusellista
muihin puuhiin (kenties palatakseen karuselliin myöhemmin) ja
karuselli täyttyy taas seuraavista huvittelijoista.
Kirjoita asiakasprosessien ja karuselliprosessin koodien keskeiset osat, kun prosessien koordinointiin käytetään semaforeja. Karusellissa istuminen on asiakkaan koodissa pelkkää odotusta.
Monitoroitu
purnukka [15 p]
Mehiläisparvi ruokkii loukkuun
joutunutta karhua keräämällä sille hunajaa.
Karhun elämä loukussa 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 purkin, se päästää
mehiläiset taas töihin ja käy itse nukkumaan.
Ohjelmoi purnukan käyttöä synkronoivat osat monitoriin sekä esitä niiden lisäksi mehiläisprosessien (N kpl) ja karhuprosessin koodi.
Sanomanvä
litystä ja yhteinen pankkitili [15 p]
Pankkitili on
usean henkilön käytössä, joista jokainen voi
tallettaa tilille tai nostaa tililtä rahaa. Tili ei saa koskaan
mennä negatiiviseksi. Koodaa palvelin, joka huolehtii tilin
käytöstä. Asiakkaat voivat pyytää joko
jonkun rahasumman talletusta tai rahasumman nostoa. Jos tilillä
ei ole tarpeeksi rahaa, niin pyyntöä viivytetään.
Asiakkaat ja palvelin käyttävät sanomanvälitystä
kommunikointiin.
Muistin virkistämiseksi =>