Käyttöjärjestelmät, erilliskoe 24.1.2014                      Other side in English

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

Tämä koe on tavallinen erilliskoe ja sen koealue on koko kurssi.

1. [9 p] Lukkiutuminen
1. [2 p] Mikä on lukkiutumisongelma? Anna konkreettinen esimerkki.
2. [2 p] Miten Dijkstran kehittämä lukkiutumisen havaitsemisalgoritmi (DDA) toimii pääpiirteissään? Mitä tietoja se tarvitsee? Milloin se ajetaan?
3. [2 p] Oletetaan, että lukkiutuminen on mahdollista järjestelmässäsi ja että olet varautunut siihen etukäteen. Oletetaan myös, että lukkiutumisen olemassaolo on havaittu DDA:lla. Miten nyt toimitaan? Anna ainakin 2 eri vaihtoehtoa.
4. [3 p] Miten lukkiutumisen estäminen ennakolta tapahtuu Pankkiirin algoritmin avulla? Mitä tietoja se tarvitsee? Kuinka algoritmi toimii pääpiirteissään? Kuinka se toimisi kohdan (a) esimerkissäsi?
   


2. [9 p] Tuottaja-kuluttaja -ongelma. Tuottajia ja kuluttajia on kumpiakin yksi kappale. Puskurin koko on 200 alkiota.
1. [2 p] Kuvaile ongelma. Erityisesti kerro, mitä synkronointi- ja kommunikointiongelmia tähän liittyy.
2. [3 p] Anna ongelman ratkaisu semaforien avulla. Esitä tuottajan ja kuluttajan pseudokoodi. Määrittele selkeästi kaikki käyttämäsi semaforit ja muut tietorakenteet alkuarvoineen. Selitä, miksi ratkaisusi on oikein.
3. [4 p] Anna ongelman ratkaisu monitorin avulla. Esitä tuottajan, kuluttajan ja monitorin pseudokoodi. Käytä monitoria ainoastaa synkronointiongelman ratkaisussa. Määrittele selkeästi kaikki käyttämäsi monitorin ehtomuuttujat ja muut tietorakenteet alkuarvoineen. Selitä, miksi ratkaisusi on oikein.


3. [9 p] Vuoronanto.
   1. [3 p] Minkä ongelman vuoronantomenetelmä ratkaisee?
      Miten käyttäjätason säikeet vaikuttavat siihen? Miten ytimen tason säikeet vaikuttavat siihen?
   2. [3 p] Mitä erityisominaisuuksia on moniprosessorijärjestelmien vuoronannossa?
      Mitä erityisominaisuuksia on realijärjestelmien vuoronannossa?
   3. [3 p] Kuinka Rate Monotonic Scheduling vuoronantomenetelmä pääpiirteissään toimii, minkälaiseen ympäristöön se on tarkoitettu ja mitä hyviä/huonoja puolia sillä on muihin samaan ympäristöön tarkoitettujen vuoronantomenetelmien kanssa.


4. [9 p] Muistinhallinta
1. [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?
2. [3 p] Minkä ongelman sivuttavan virtuaalimuistin poistoalgoritmi oikeastaan ratkaisee? Milloin se käynnistyy? Mitä tietoja se tarvitsee? Mitä laitteistotukea se tarvitsee?
3. [2 p] Miten sivuttavan virtuaalimuistin poistoalgoritmi Clock pääpiirteissään toimii? Mitä tietoja se tarvitsee? Mitä laitteistotukea se tarvitsee? Mikä tässä on hyvää/huonoa verrattuna LRU-algoritmiin?
4. [1 p] Anna esimerkki sivujen viitejonosta, jossa ensimmäinen poistettavaksi valittu sivu on erilainen Clock ja LRU algoritmeilla. Oleta, että prosessi on allokoitu 3 sivukehystä ja että viitejono koostuu sivunumeroista 0, 1, 2, 3. Perustele.