- [9 p] Kriittinen alue (vaihe). Oletetaan,
että monisäikeisen ohhelman yhteisessä
muistissa olevien muuttujien X, Y ja Z
käyttöä halutaan suojata kriittisen vaiheen
avulla. Muuttujiin viitataan ohjelmassa viidessä
kohtaa (kohdat A, B, C, D ja E):
A: X <- 7 B: some1 <- X C: Y <- 87 D: some4 <- X E: some5 <- Y
Y <- 4 some2 <- Y Y <- 0
Z <- X+Y some3 <- Z
Kohdassa A muuttujien Y ja Z vanhat arvot eivät saa
näkyä muille sen jälkeen kun X on saanut
uuden arvon ja Z'n uuden arvon tulee olla X'n ja Y'n uusien arvojen
summa. Kohdassa B muuttujien some1, some2 ja some3 arvoiksi tulee tulla
X'n, Y'n ja Z'n arvot käskysarjan suorituksen
alkuhetkellä. Kohdassa E muuttujan Y arvo tulee nollata välittömästi sen lukemisen jälkeen.
- Mitkä näistä
(pseudo)koodinpätkistä (A, B, C, D ja E) tulee
suojata
kriittisenä alueena ja miksi?
- Näytä (pseudokooditasolla), kuinka
näiden säikeiden kriittiset vaiheet suojataan keskeytykset
estämällä. Millaisessa
laskentaympäristössä tämä
olisi järkevä ratkaisu? Miksi?
- Näytä (pseudokooditasolla), kuinka
näiden säikeiden kriittiset vaiheet
suojataan busy-wait -loopissa (esim test-and-set -käskyn avulla). Millaisessa
laskentaympäristössä tämä
olisi järkevä ratkaisu? Miksi?
- [9 p] Lukkiutuminen. Meillä on neljä säiettä (A, B, C ja D), jotka suorittavat allaolevia koodeja.
Me emme tiedä mitään suoritusnopeuksista - emme siis tiedä kuinka paljon aikaa kuluu eri semaforioperaatioiden välillä. Kaikkien semaforien (s1-s6) alkuarvo on 1. Semaforioperaatiothan ovat P (eli wait) ja V (eli signal).
- ... P(s1) ... P (s2) ... P(s3) ... V(s3) ... V(s2) ... V(s1) ...
- ... P(s2) ... P (s4) ... P(s5) ... V(s5) ... V(s4) ... V(s2) ...
- ... P(s5) ... V(s5) ... P (s1) ... V(s1) ... P(s3) ... V(s3) ...
- ... P(s6) ... P (s5) ... P(s1) ... V(s1) ... V(s5) ... V(s6) ...
Kaikki neljä säiettä käynnistetään samalla kertaa ja ovat siis suorituksessa samanaikaisesti.
- Resurssien varauskaavio (resource reservation graph) näyttää samalla kertaa kullekin prosessille sen sillä hetkellä varaamat ja haluamat resurssit. Kuvaa lukkiintumisongelma varattavien resurssien ja varauskaavion avulla. Mitkä ovat nämä varattavat resurssit tässä tapauksessa? Missä järjestyksessä kukin säie varaa ja vapauttaa niitä? Piirrä resussien varauskaavio skenaariolle, jossa kaikki säikeet pääsevät yhtä aikaa ensimmäiseen semaforioperaatioonsa (P(s1), P(s2), P(s5) tai P(6)).
- Anna lukkiutuva skenaario ja lukkiutumishetken resurssien varauskaavio.
- Mikä ovat lukkiutumisen mahdollistavat neljä vaatimusta ja kuinka ne toteutuvat tässä?
- [9 p] Yksisuuntainen silta
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
5 autoa yhdellä kertaa. Jotta varmistetaan, että autot menevät sillalle vain kulloinkin sallitusta
suunnasta, siltaa käyttävät autoprosessit kutsuvat proseduuria aja_sillalle(suunta) pyrkiessään
sillalle ja sillalta poistuessaan proseduuria poistu_sillalta(suunta):
Process auto(suunta) {
.....
aja_sillalle(suunta);
ylitä silta
poistu_sillalta(suunta);
......
}
Tee semaforeja ja P- ja V-operaatioita käyttävät koodit proseduureille aja_sillalle(suunta) ja
poistu_sillalta(suunta). Ratkaisun ei tarvitse olla reilu, vaan autojen odotusajat saavat olla pitkiä.
Jos autoja suuntaan A:sta B:hen tulee jatkuvalla virralla, niin suuntaa B:stä A:han odottavat autot voivat joutua odottamaan tosi pitkään. Kuitenkin samalta suunnalta tulevien autojen tulee päästä sillalle saapumisjärjestyksessä.
- [9 p] Mehiläisparvi, karhu ja IRR monitori. 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 annos 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 taas nukkumaan.
Ohjelmoi purnukan täytön ja tyhjentämisen synkronoinnin ratkaisu IRR (E<S<W) signalointisemantiikkaa käyttävän 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. Kerro myös, mikä osa ratkaisuasi perustuu nimenomaan IRR signalointisemantiikkaan. Tee tarvittavat oletukset muista monitorin piirteistä ja kirjoita ne näkyville.
Other side in English