582405 Käyttöjärjestelmät II (2 ov) / Kokeessa kysyttyjä

1. KÄYTTÖJÄRJESTELMÄN YDIN

   Käyttöjärjestelmän toteutus voi perustua monoliittiseen ytimeen (monolithic kernel) tai mikroytimeen (microkernel). Selitä kuinka toteutukset eroavat toisistaan ja esitä kummankin tavan hyviä ja huonoja puolia.

2. MIKROYDIN

   Selvitä mikroytimeen (microkernel) perustuvan käyttöjärjestelmän rakennetta ja toimintaa. Mitä KJ:n osia on sijoitettava mikroytimeen? Miksi? Selvitä mitä hyviä / huonoja puolia tästä toteutustavasta seuraa.

3. MONIPROSESSORIJÄRJESTELMÄ

   a) Miten host-slave tyyppinen moniprosessorijärjestelmä poikkeaa SMP-järjestelmästä? Mitä vaikutusta eroilla on KJ:n ohjelmointiin? Hyvät / huonot puolet?

   b) Kuinka välimuistin yhtenäisyys (coherency) hoituu moniprosessorijärjestelmässä?

4. SÄIKEET

   Monissa nykyaikaisissa käyttöjärjestelmissä on sekä prosesseja että säikeitä. Miten säie eroaa perinteisestä prosessista? Anna perusteluja säikeiden hyödyllisyydestä.

   Säikeet voidaan toteuttaa kirjastorutiineilla (ns. käyttäjätason säikeet, user level threads) tai säikeet voi olla toteutettu jo käyttöjärjestelmän ytimessä (kernel level threads). Selitä kummankin tavan hyödyt ja vähemmän hyvät piirteet.

5. SÄIKEISTÄ

   Suoritettavana on kolme prosessia, jotka koostuvat alla mainituista säikeistä

      Prosessi Prosessin säikeet
         P1    T11, T12, T13
         P2    T21, T22
         P3    T31
   

   Järjestelmä käyttää keskeytyvää (preemptive) round-robin vuorottamista, ja T11 on suorituksessa, kun aikaviipale täyttyy. Mitkä säikeet voisivat olla suorituksessa seuraavan aikaviipaleen aikana a) jos säietoteutus on tehty käyttäjätason säikeillä? b) jos säietoteutus on tehty ytimessä?

   Oletetaan seuraavaksi, että T11 joutuu Blocked-tilaan ennen kuin aikaviipale täyttyy. Mitkä säikeet voisivat olla suorituksessa seuraavana c) jos säietoteutus on tehty käyttäjätason säikeillä? d) jos säietoteutus on tehty ytimessä?

6. VIRTUAALIMUISTI

   a) Selitä MMU:n rakenneosat, perustele kunkin osan tarve sekä selitä MMU:n toiminta sivutukseen perustuvassa virtuaalimuistitoteutuksessa.

   b) Kuinka globaali Clock-algoritmi toimii valitessaan virtuaalimuistista korvattavaa sivua. Miten se eroaa lokaalista Clock-algoritmista?

7. KORVAUSPOLITIIKKA

   a) Miten globaalit ja lokaalit korvausalgoritmit (replacement policy) eroavat toisistaan?

   b) Millä perusteella FIFO-algoritmi valitsee muistista poistettavan (korvattavan) sivun? Mikä huono piirre siinä on?

   c) Millä perusteella LRU-algoritmi valitsee muistista korvattavan sivun? Mikä ongelma liittyy tämän algoritmin toteuttamiseen? Miten ongelmaa on ratkottu käytännön toteutuksissa?

8. MUISTINHALLINNASTA

   a) Selitä clock-algoritmin toiminta. Mihin sivutilaan uusi sivu tuotaisiin allaolevan taulukon perusteella, jos käytössä on clock-algoritmi ja prosessille on varattu kiinteästi 4 sivutilaa (perustele). Ajat tarkoittavat aikaa prosessin käynnistämisestä (clock ticks).

   Sivu#	Sivutila#	Latausaika	Viittausaika	R-bitti	M-bitti
   2	0	60	121	0	1
   1	1	130	120	0	0
   0	2	26	122	1	0
   3	3	20	133	1	1

   b) Suoritus jatkuu ja tuloksena on viitejono (page reference string)

     4, 0, 0, 0, 2, 4, 2, 1, 0, 3, 2
   

   Kuinka monta sivunpuutosta syntyy, kun käyttöjoukon (working set) ikkunakooksi asetetaan 4 kiinteän sivutilamäärän sijasta? Osoita minkä sivujen kohdalla nämä sivupuutokset esiintyvät.

9. POISTOALGORITMEJA

   Prosessille on varattu kiinteästi 4 sivutilaa, ja sen suorituksesta saadaan viitejono

      1, 0, 0, 2, 2, 1, 5, 4, 5, 0, 1, 2, 0, 3, 0, 1
   

   a) Kuinka monta sivunpuutosta syntyy, kun poistoalgoritmina on LRU? Osoita mitkä sivut ovat kullakin hetkellä muistissa ja sivut, jotka aiheuttavat sivupuutoksen.

   b) Selitä käyttöjoukkoalgoritmin (working set) idea. Kuinka monta sivupuutosta syntyy, kun sivutilojen hallintaan käytetään käyttöjoukkoalgoritmia ja ikkunankooksi on asetettu 4? Osoita mitkä sivut kuuluvat kullakin hetkellä käyttöjoukkoon ja sivut, jotka aiheuttavat sivupuutoksen.

10. MUISTINHALLINTA

    a) Muistinhallinta käyttää prosessin sivujen hallintaan lokaalia algoritmia, jossa kukin prosessi saa 3 sivutilaa. Prosessin viittaamat sivut muodostavat viitejonon (page reference string)

        6 5 2 6 1 0 7 0 1 0 1 5 2 1 4 0 4 6 0
    

    Kuinka monta sivunpuutosta syntyy, kun poistoalgoritmina on i) FIFO ii) OPT iii) LRU.

    b) Kuinka monta sivunpuutosta syntyy prosessille, kun muistinhallinta käyttää globaalia poistopolitiikkaa ja poisto perustuu käyttöjoukkoalgoritmiin, jonka ikkunankoko on 4.

    Osoita vastauksessasi selkeästi mitkä sivut ovat kullakin hetkellä muistissa ja mitkä sivut aiheuttavat sivunpuutoksen.

11. VUOROTTAMISESTA

    Selitä Round-Robin vuorottamisen, Multilevel Feedback vuorottamisen ja Fair-Share vuorottamisen toimintaideat.

12. VUOROTTAMISALGORITMEJA

    Selitä prioriteetteja käyttävän Round-Robin vuorottamisen, Multilevel Feedback vuorottamisen sekä reaaliaikajärjestelmissä käytettävän Rate Monotonic vuorottamisen toimintaideat.

13. MULTILEVEL FEEDBACK

    Prosessien vuorottaminen käyttää Multilevel Feedback-algoritmia, jossa on kolme jonoa RQ0, RQ1 ja RQ2. Selvitä allaolevien prosessien A - E suoritusjärjestys, valmistumisaika (finish time) ja läpimenoaika (turnaround time):

    Prosessi	Saapumisaika	Prosessointiaika
    A	0	3
    B	1	5
    C	3	2
    D	9	5
    E	12	5

    Mikä heikkous Multilevel Feedback -algoritmissa on?

14. VUOROTTAMINEN

    a) Miten tapahtumaohjattu (non-preemptive) ja keskeyttävä (preemptive) vuorottaminen eroavat toisistaan?

    b) Selitä Virtual Round-Robin vuorottamisalgoritmin toimintaidea. Mitä hyötyä tästä saadaan verrattuna normaaliin RR-vuorottamiseen?

    c) Mitkä kurssilla esiintulleista vuorottamisalgoritmeista sopivat eräajojärjestelmään, mitkä interaktiiviseen ympäristöön? Perustelut.

15. RMS-VUOROTTAMINEN

    Selitä RMS-vuorottamisen perusideat. Piirrä ajoituskaavio seuraaville kolmelle jaksolliselle työlle (jaksot toistuvat uudestaan ja uudestaan):

        työ P1: C1 = 30, T1 = 145 		C = execution time
        työ P2: C2 = 20, T2 = 100 		T = period
        työ P3: C3 = 68, T3 = 150  
    

    Pystytäänkö asetetut aikarajat saavuttamaan?

16. LEVYPYYNTÖJÄ

    Miten levypyyntöjen uudelleenjärjestelyllä voidaan nopeuttaa levytoimintoja? Missä KJ:n osassa uudelleenjärjestely tehdään?

    Missä järjestyksessä SSTF-algoritmi palvelee levypyynnöt? Entä SCAN-algoritmi? Minkä SSTF-algoritmin ongelman SCAN-algoritmi välttää?

    Miten N-step-SCAN ja FSCAN poikkeavat tavallisesta SCAN-algoritmista? Mitä ko. muutoksilla on yritetty hakea?

17. LEVYPYYNTÖJEN JÄRJESTELY

    Levyllä on 1024 uraa ja hakuvarsi on uralla 100. Käsiteltäväksi tulee pyynnöt urille 27, 129, 110, 186, 147, 41, 10, 64 ja 120. Monenko uran yli hakuvarsi joutuu siirtymään, kun pyyntöjen järjestelyssä käytetään a) SSTF-algoritmia ja b) SCAN-algoritmia. Kumpi algoritmi on parempi? Perustele!

    Miten N-step-SCAN ja FSCAN poikkeavat tavallisesta SCAN-algoritmista? Mitä ko. muutoksilla on yritetty hakea?

18. LEVYNOUTOJA

    Levyn sylinterit on numeroitu 0:sta 255:een. Levyn hakuvarsi on sylinterillä 106. Yhden uran ylitykseen kuluu aikaa 0.1 ms. Jonossa on hakupyynnöt urilta

            37, 200, 47, 172, 190, 227, 133, 200, 108, 6, 96 ja 52.
    

    Paljonko kuluu aikaa hakuvarren siirtoihin, kun pyyntöjen käsittelyalgoritmi on a) FIFO b) SSTF c) SCAN d) C-SCAN

19. TIEDOSTON KÄYTTÖÄ

    Sovelluksessa on lauseet

            fd = open("puppu.txt", O_RDONLY);
            if (fd < 0) exit(0);
                    n_read = read(fd, buf, 80);
            if (n_read > 0)
                    ...;
    

    Aluksi tiedosto puppu.txt avataan tiedosto lukemista varten. Jos se ei onnistu, sovelluksen suoritus päättyy heti exit-lauseeseen. Jos avaaminen onnistuu, sovellus lukee tiedostosta korkeintaan 80 merkkiä muuttujaan buf. Rutiini read() palauttaa arvonaan montako merkkiä saatiin luettua.

    Selitä miten KJ löytää mainitun tiedoston, päättää onnistuuko tiedoston avaaminen ja kuinka kaivatut tavut saadaan siirrettyä levyltä sovelluksen muuttujaan buf. Tee itse tarvittavat lisäoletukset.

20. TIEDOSTOJÄRJESTELMÄSTÄ

    Tiedostojen käyttö ja tiedostojärjestelmän toteutus voidaan jakaa toiminnallisesti neljään tasoon: sovellus, laiteriippumaton taso, laiteriippuva taso ja laitteisto. Kuvaa tiedostojärjestelmän toimintaa selvittämällä näiden tasojen tehtäviä ja toimintaa a) tiedostoa avattaessa ja b) tiedostosta luettaessa.

    Kiinnitä erityisesti huomiota siihen mitä tilanteitataso käsittelee, milloin tason toimintoja tarvitaan ja mitä tietoja missäkin tilanteessa tarvitaan päätöksentekoon. Pyri toiminnallisuuden mukaan loogisesti eteneväään eistyskeen. Voit halutessasi käyttää UNIXia tai Windowsia esimerkkinä.

21. PÄÄSYLISTAT vs. VALTAKIRJAT

    Vertaa toisiinsa pääsylistaa (access control list) ja valtakirjaa (capability list).

22. SUOLASTA JA HEVOSIA

    Mitä tarkoitetaan salasanan suolauksella (salting) ja mitä hyötyä siitä on on?

23. TIETOTURVASTA

    a) Troijan hevonen ja takaovi (back door)

    b) Polymorfinen virus

    c) Digital Immune System

Opiskelu on Asenne - ei olotila.

Sivu luotu 12.11.2002, Auvo Häkkinen