Käyttöjärjestelmät (8 op), erilliskoe ja uusintakuulustelu 17.6.2016

Kirjoita jokaiseen vastauspaperiisi kurssin nimi, pvm, oma nimi, nimikirjoitus ja opiskelijanumero. Kuhunkin tehtävään riittää 1 sivun vastaus.
Tämä koe toimii tavallisena erilliskokeena tai kevään 2016 luentokurssin uusintakokeena.

Valitse 1 kpl seuraavista vaihtoehdoista ja mainitse valintasi koepaperissa. Oletusvalinta on (d).
(a) Kevään 2016 itseopiskelukurssin minikokeen 8 uusintakuulustelu: tehtävä 8.
      (Minikokeita 1-7 ei voi enää uusia)
(b) Kevään 2016 itseopiskelukurssin välikokeen 1 uusintakuulustelu: tehtävät 1-4.
      (Tässä uusitaan koko välikoe 1. Vastaa kaikkiin tehtäviin 1-4.)
(c) Kevään 2016 itseopiskelukurssin välikokeen 2 uusintakuulustelu: tehtävät 5-8.
      (Tässä uusitaan koko välikoe 2. Vastaa kaikkiin tehtäviin 5-8.)
(d) Tämä on tavallinen erilliskoe ja kattaa koko kurssin: tehtävät 2-7.

1. [6 p] Välimuisti
   1. [1 p] Kuinka välimuisti tukee alueellista (spatial) paikallisuutta ohjelman muistiviitteissä?
   2. [1 p] Kuinka välimuisti tukee ajallista (temporal) paikallisuutta ohjelman muistiviitteissä?
   3. [1 p] Miksi välimuistin toteutus moniytimisissä järjestelmissä on vaikeampaa kuin yhden ytimen järjestelmissä?
   4. [1 p] Kuinka viitattu tieto löytyy välimuistista? Käytä esimerkkinä lukuviitettä neljän tavun mittaiseen tietoon tavuosoitteessa 0x12345678 välimuistissa, jossa lohkon (rivin) pituus on 16 tavua.
   5. [2 p] Välimuistin saantiaika on 500 ns, välimuistilohkon keskusmuistin saantiaika 2 μs ja välimuistin osumasuhde 95%. Kuinka kauan muistiviite keskimäärin kestää? Kirjaa oletuksesi ja selitä laskelmasi.


2. [6 p] Prosessit, säikeet, kilpailutilanteet (race conditions)
   1. [2 p] Sovellus S on toteutettu 6-säikeisenä ja se suorittaa 4-ytimisessä laitteistossa. Säie s1 lukee dataa verkosta, säikeet s2-s5 prosessoivat sitä, ja säie s6 tallentaa prosessoidun yhteenvetodatan tiedostojärjestelmään. Olisiko järkevää toteuttaa S ytimen vai käyttäjätason säikeiden avulla? Selitä.
   2. [1 p] Yhteisen muuttujan Sum alkuarvo on nolla (0). Neljä säiettä A, B, C ja D kukin suorittavat joskus (konekielitason) koodinpätkän
      
                 100:     …
                 101:    LOAD R1, Sum          ;  R1  ← mem(Sum)
                 102:    ADD  R1, =1              ;  R1++
                 103:    STORE R1, Sum        ;  mem(Sum)  ←  Ri
                 104:    …
      
      Tarkoitus on, että kukin säie kasvattaa muuttujan Sum arvoa ja että sen loppuarvo on 4. Ohjelma ei nyt kuitenkaan toimi oikein kaikissa skenaarioissa. Anna skenaario, jossa muuttujan Sum loppuarvo on 3.
   3. [1 p] Kuinka ratkaiset edellisen kohdan (b) kilpailutilanteen aiheuttaman ongelman semaforien avulla?
   4. [2 p] Edellisen kohdan (b) ongelman semaforiratkaisussa odottava säie on odotustilassa, jolloin odotuksen kustannus on ainakin 2 säikeen vaihtoa. Miten em. ongelma voitaisiin moniytimisessä laitteistossa ratkaista niin, että odotukseen ei sisälly säikeiden vaihtoa?
      
      
3. [6 p] Monitorit, lukkiutuminen
1. [2 p] Kuinka monitorin ehtomuuttujien rakenne ja operaatiot eroavat semaforin rakenteesta ja operaatioista?
2. [1 p] Kuinka edellisen tehtävän kilpailutilanneongelma (teht. 2 kohta b) ratkaistaan monitorin avulla?
3. [1 p] Anna esimerkki lukkiutumasta.
4. [1 p] Oletetaan, että säikeet käyttävät viittä eri resurssia (yksi säie kerrallaan voi käyttää yhtä resurssia). Kuinka voidaan taata, että lukkiutumaa ei kertakaikkiaan voi tapahtua, mutta säikeet voivat silti suorittaa (pääosin) rinnakkain?
5. [1 p] Oletetaan, että säikeet käyttävät viittä eri resurssia (yksi säie kerrallaan voi käyttää yhtä resurssia). Lukkiutumisen estäminen (kohta d) ei ole käytännöllistä toteuttaa ja lukkiutuminen tapahtuu aina aika ajoin, mutta hyvin harvoin. Kuinka mahdollisen lukkiutumisen aiheuttamasta ongelmasta nyt selvitään?
   
   
4. [6 p] Virtuaalimuisti
   1. [2 p] Kuinka 2 tasoisen sivuttavan virtuaalimuistin osoitteenmuunnos tapahtuu? Ota TLB huomioon vastauksessasi. Käytä esimerkkinä virtuaaliosoitetta 0x12345678 (tavuosoite), kun sivun koko on 4KB.
   2. [1 p] Mikä on sivunpuutos (page fault) ja mikä on sen aiheuttama kustannus (suoritusajassa)? Selitä?
   3. [1 p] Minkä ongelman virtuaalimuistin poistoalgoritmi (replacement) ratkaisee?
   4. [2 p] Kuinka poistoalgoritmi Clock-algoritmi toimii?
      
      
5. [6 p] Suorittimen vuoronanto
1. [2 p] Miten aikaviipalevuoronannon (round robin, time slice) aikaviipaleen koko (quantum size) olisi hyvä asettaa? Milloin aikaviipale on liian pieni ja milloin se on liian suuri?
2. [2 p] Minkälaiseen järjestelmään Fair-Share vuoronantomenetelmä on tarkoitettu, minkä ongelman se ratkaisee ja kuinka se pääpiirteissään toimii?
3. [2 p] Milloin reaaliaikajärjestelmässä voidaan käyttää prioriteettipohjaista vuoronantomenetelmää (tavanomaisen aikaraja-vuoronannon asemesta)? Minkälaisista töistä on tällöin kyse ja miten prioriteetit määräytyvät?


6. [6 p] Levyn hallinta ja tiedostojen hallinta
1. [3 p] Linuxin hissialgoritmissa (Linus Elevator) on kaksi modifikaatiota verrattuna perinteiseen hissialgoritmiin: Linux Deadline Scheduler ja Linux Anticipatory I/O Scheduler. Mitkä ongelmat ne ratkaisevat ja kuinka ne sen tekevät?
2. [2 p] Anna esimerkki tilanteesta, jossa nimenomaan indeksoitu peräkkäistiedostojärjestelmä (indeksoitu sarjallinen, indexed sequential) olisi hyvä ratkaisu?
   Miksi peräkkäistiedostojärjestelmä (sequential) ei olisi esimerkissäsi hyvä ratkaisu?
   Miksi indeksoitu (indexed) tiedostojärjestelmä ei olisi esimerkissäsi hyvä ratkaisu?
3. [1 p] Kuinka indeksoidun peräkkäistiedostojärjestelmän indeksiä käytetään?
   
   
7. [6 p] Sulautetut järjestelmät ja hajautetut järjestelmät
1. [2 p] Sulautetussa käyttöjärjestelmässä eCos keskeytysten käsittely poikkeaa tavanomaisesta. Miksi näin on tehty ja kuinka keskeytykset käsitellään eCos'issa?
2. [2 p] Miten etäproseduurin kutsu (RPC, remote procedure call) eroaa tavanomaisesta proseduurin kutsusta?
   Mitä ongelmia RPC:n käyttöön liittyy? Miten RPC toteutetaan?
3. [2 p] Minkä hajautettuihin järjestelmiin liityvän ongelman SOA-malli (Service Oriented Architecture) ratkaisee? Mitkä ovat SOA-mallin perusrakenteet ja -toiminnot?
   
   
8. [6 p] Tietoturva, uhat ja tekniikat
1. [2 p] Tietokoneviruksilla on järjestelmässä oloaikanaan neljä eri vaihetta. Mitkä ne ovat ja kuinka virus käyttäytyy niiden aikana?
2. [2 p] Mainitse kolme (3) eri tekniikkaa, joilla viruksista saadaan vaikeasti havaittavia.
3. [2 p] Kuinka Generic Decryption menetelmä havaitsee useimmat virukset?