Käyttöjärjestelmät, välikoe 1, 4.3.2015                      Other side in English

Kirjoita jokaiseen vastauspaperiisi kurssin nimi, pvm, oma nimi, nimikirjoitus ja opiskelijanumero.
Kuhunkin tehtävään riittää 1-2 sivun vastaus.
Anna kunkin tehtävän vastaus omalla konseptiarkillaan.

HUOM: Palauta jokainen tehtävä omalla konseptiarkillaan oikeaan pinoon!

1. [6 p] Kriittisen alueen ongelma. Ajatellaan monisäikeistä sovellusta moniytimisessä laitteistossa.
1. [1 p] Anna (pseudo)kooditason esimerkki kriittisestä alueesta (koodisegmentti A), jota säikeet P, Q ja R suorittavat kukin jossain vaiheessa. Selitä, miksi A on kriittinen alue (vaihe)?
2. [1 p] Anna kohdan (a) esimerkkiisi liittyvä skenaario, jossa laskennan lopputulos on oikein, vaikka kriittistä aluetta ei ole suojattu.
3. [1 p] Anna kohdan (a) esimerkkiisi liittyvä skenaario, jossa laskennan lopputulos on virheellinen, jos kriittistä aluetta ei ole suojattu.
4. [2 p] Millä menetelmällä tehtävän kriittinen alue on hyvä suojata? Näytä, miten kriittisen vaiheen suojaus (valitsemallasi menetelmällä) toteutetaan pseudokooditasolla koodisegmentille A.
5. [1 p] Kuinka kohdan (d) tilanne muuttuu, jos tähän samaan kriittiseen alueeseen kuuluu myös koodisegmentit B ja C?


2. [6 p] Lukkiutuminen. Prosessi P käyttää kriittisiä alueita CS1 ja CS2 (joskus yhtä aikaa). Prosessi Q käyttää kriittisiä alueita CS1, CS3 ja CS4 (joskus yhtä aikaa). Prosessi R käyttää kriittisiä alueita CS2 ja CS4 (joskus yhtä aikaa). Prosessi S käyttää kriittisiä alueita CS3 ja CS5 (joskus yhtä aikaa).
1. [2 p] Anna osaan tai kaikkiin em. prosesseihin liittyvä lukkiutumiseen johtava skenaario. Mitkä prosessit päätyvät lukkiutuneiksi?
2. [2 p] Eräs keino lukkiutumisen välttämiseksi olisi varata kaikki resurssit tietyssä järjestyksessä.
   Miksi tämä menettely estää lukkiutumiset?
3. [2 p] Kuinka resurssien varaaminen tietyssä järjestyksessä tarkasti ottaen toimii tässä tapauksessa?
   Missä järjestyksessä resurssit varataan?
   Kuinka kohdan (a) skenaarion lukkiutuminen vältetään nyt? Anna vastauksesi olennaiset osat pseudokoodina.
   


3. [6 p] Tuottaja-kuluttaja -ongelma ja semaforit. Tuottajia yksi kappale ja kuluttajia max 20 kappaletta. Puskurin koko on 10 alkiota. Puskuria käsitellään operaatioilla Put() ja Get(). Puskuriin voi kirjoittaa (Put) ja siitä lukea (Get) samanaikaisesti, mutta vain yksi Put (tai Get) operaatio voi olla suorituksessa kerrallaan.
1. [3 p] Kuvaile ongelma. Erityisesti kerro, mitä synkronointi- ja kommunikointiongelmia tähän liittyy. Kuka odottaa ketä ja milloin ja miksi ja miten? Milloin odotus päättyy?
2. [3 p] Anna ongelman ratkaisu semaforien avulla. Esitä tuottajan ja kuluttajan pseudokoodit. Ratkaisun tulee sallia yhden Put ja yhden Get operaation samanaikaisen suorituksen. Määrittele selkeästi kaikki käyttämäsi semaforit ja muut tietorakenteet alkuarvoineen. Selitä, miksi ratkaisusi on oikein.
   


4. [6 p] Muistinhallinta
1. [3 p] Oletetaan, että suorituksessa oleva konekäsky hakee virtuaaliosoitteesta 0x1234BCDE kokonaislukuarvon laiterekisteriin R2.
   Kuinka kauan tämän konekäskyn suorittaminen kestää parhaassa tapauksessa? Perustele.
   Kuinka kauan tämän konekäskyn suorittaminen kestää huonoimmassa tapauksessa? Perustele.
   (Määrittele viittaamiesi laitteistojen nopeus jollain karkealla järkevällä tasolla.)
2. [3 p] Selitä käsite "ruuhkautuminen" (thrashing). Mikä siinä on ongelma? Mistä se aiheutuu? Kuinka sen voi välttää? Miten Page Fault Frequency (PFF) algoritmi liittyy tähän?