------------------------------------------------------------------------- Käyttöjärjestelmät I, Kurssikoe 04.11.2002 Tehtävä 1 / Mika, Turjo, Avrll ------------------------------------------------------------------------- a) (Mika) Prosessorin välimuisti, paikallisuuden perusteella seuraavana suoritettava käsky on nyt suoritettavana olevan käskyn lähistöllä muistissa. Ohjelman suoritus siis pyörii lähekkäisten muistipaikkojen sisällä. Osoitteenmuunnospuskuri, edellisen kohdan perusteella seuraava käsky on edellisen lähistöllä, eli todennäköisesti joko samalla tai viereisellä sivulla. Levyvälimuisti, ohjelmat käsittelevät tiedostoja usein paikallisesti jolloin seuraavaksi tarvittavat tavut kuuluuvat samaan lohkoon viimeeksikäytettyjen kanssa. Virtuaalimuisti, yleensä ohjelmasta käytetään vain pientä osaa kerrallaan eli suoritus pyörii pienessä osassa sivuja, jolloin loppuja sivuja voidaan säilyttää levyllä ja näin vapautuvaa muistia käyttää muiden prosessien tarpeisiin. Yksi piste per kohta. Maininta 1/2p ja perustelu 1/2p. b) (Turjo) Kellolaite aiheuttaa keskeytyksen => KJ siirtää sisäistä kelloaan eteenpäin ja tarvittaessa kutsuu vuorottajaa, joka vaihtaa suorituksessa olevan prosessin toiseksi. Sovellusohjelma suorittaa laittoman toiminnon, esimerkiksi nollalla jako => KJ joko lopettaa prosessin suorituksen tai ilmoittaa virheestä prosessille jonkin menettelyn (UNIX:ssa signaalit) avulla. I/O-laite on saanut siirrännän valmiiksi, esimerkiksi levyasema on lukenutlevylohkon muistiin => KJ herättää siirräntää odottaneen prosessin eli siirtää sen Ready to Run -jonoon. Sovellusohjelma kutsuu käyttöjärjestelmäpalvelua => KJ suorittaa pyydetyn operaation, jonka jälkeen prosessin suoritus jatkuu. Jos palvelupyyntö siirtää prosessin Blocked-jonoon, KJ valitsee jonkun toisen prosessin suoritukseen. Pisteytys: 2 p tilanteiden kuvaamisesta 2 p tilanteiden käsittelyn kuvaamisesta ("Miten KJ käsittelee kunkin tilanteen") Arvioinnissa on kiinnitetty huomiota siihen, että esitetyt tilanteet ovat oleellisesti erilaisia. Esimerkiksi eri I/O-laitteilta tulevat keskeytykset on tulkittu yhdentyyppiseksi tilanteeksi. c) (Avrll) ks. kirja s 62 Yksi piste per kohta. Maininta 1/2p ja perustelu 1/2p. ------------------------------------------------------------------------- Käyttöjärjestelmät I, Kurssikoe 04.11.2002 Tehtävä 2 / Turjo ------------------------------------------------------------------------- ks. kirjan taulukko 3.5 (s. 129) Prosessikuvaaja (PCB) sisältää prosessin tunnistetiedot, prosessorin tilatietoja sekä prosessiin liittyviä hallintatietoja. Prosessin tunnistetietoja ovat PID-numero, äitiprosessin PID sekä tieto prosessin omistajasta. PID-numeron tarkoituksena on yksilöidä prosessi muiden joukosta. Esimerkiksi eräissä palvelupyynnöissä (kill, waitpid, ptrace) on yhtenä parametrina PID-numero, jonka avulla sovellusohjelma voi viitata muihin prosesseihin. Äitiprosessin PID-numeron avulla sovellusohjelmat näkevät hierarkian, missä järjestyksessä prosessit on luotu. KJ tarvitsee itsekin tietoa äitiprosessista, sillä prosessin päättyessä KJ välittää tästä ilmoituksen äitiprosessille. Omistajatiedot sisältävät käyttäjänumeron (uid) ja ryhmänumeron (gid). KJ tarvitsee näitä eräiden palvelupyyntöjen yhteydessä tehtäviin suojaustarkistuksiin. Esimerkiksi tiedostoa avattaessa KJ tarkistaa, onko prosessin omistajalla oikeus avata tiedosto pyydetyssä käyttötarkoituksessa (lukeminen tai kirjoittaminen). Toinen esimerkki voisi olla kill-palvelupyyntö, jonka avulla sovellusohjelma voi lopettaa toisen prosessin. Tällöin KJ tarkistaa, onko palvelupyynnön kutsujan käyttäjänumero sama kuin lopetettavan prosessin. Prosessorin tilatietojen avulla KJ toteuttaa moniajon. Tilatiedot sisältävät prosessorin yleiskäyttöiset rekisterit sekä seuraavat erityisrekisterit: PSW (tilarekisteri), PC (käskylaskuri) ja SP (pino-osoitin). Kun KJ:n vuorottaja vaihtaa toisen prosessin suoritukseen, se kopioi edellä mainittujen rekisterien arvot PCB:hen, jonka jälkeen seuraavaksi suoritukseen tulevan prosessin PCB:stä ladataan rekisterihin uudet arvot. Tällöin myös PTR (sivutaulun osoiterekisteri) saa uuden arvon. PTR mielletään usein hallintatietoihin kuuluvaksi, koska se liittyy prosessin muistinhallintaan. Prosessin hallintatietoihin kuuluu muistinhallinnan lisäksi skedulointitiedot, tiedostokuvaajataulu, työhakemiston nimi sekä muita hallintaa helpottavia tietorakenteita. Muistinhallintatiedot kuvaavat prosessin virtuaalimuistin eli prosessin muistialueet. KJ:n vuorottaja tarvitsee prosessin sivutaulun osoitteen, kun se ottaa prosessin CPU:lle suoritukseen. KJ:n muistinhallinta päivittää näitä tietoja esimerkiksi heittovaihdon yhteydessä, kun muistissa olevia sivuja siirretään levylle. KJ:n vuorottaja valitsee seuraavan suoritukseen otettavan prosessin skedulointitietojen perusteella. Skedulointitietoja ovat prosessin tila (ready, running, waiting), prioriteetti, tieto prosessin odottamasta tapahtumasta sekä aikalaskurit ja tilastot (prosessin yhteensä saama CPU-aika, odotuksessa kulunut aika, sivunpuutoskeskeytysten määrä jne). Vuorottaja päivittää itse osaa skedulointitiedoista. Vuorottaja vaihtaa tilaa ready- ja running-tilan välillä, päivittää osaa tilastoista ja mahdollisesti muuttaa prosessin prioriteettiakin. Prosessin tila saattaa muuttua myös palvelupyynnön yhteydessä, esimerkiksi tiedostoihin liittyvät järjestelmäpalvelut saattavat siirtää prosessin waiting-tilaan. Tiedostokuvaajataulun alkiot esittävät prosessin avaamia tiedostoja. Kukin alkio sisältää osoittimen tiedostokuvaajaan, josta käy ilmi erilaisia tiedostoon liittyviä tietoja, kuten tiedoston käyttöoikeudet (luku/kirjoitus), tiedosto-osoitin (luku/kirjoituspositio) sekä tieto prosessista, jolla tiedosto on auki. Tiedostokuvaajaan sisältyy usein myös tiedostokohtaista saantitietoa, esimerkiksi levytiedostojen yhteydessä tiedostokuvaaja saattaa sisältää luettelon tiedoston käyttämistä levylohkoista. Jos tiedosto esittää verkkoyhteyttä, saantitietona voi olla osoitin verkkoyhteyden kuvaajaan. KJ tarvitsee tiedostokuvaajataulua tiedostopalvelupyyntöjen (open, read, write, close) toteutukseen. PCB sisältää myös työhakemiston polkunimen, jonka avulla KJ kanonisoi palvelupyyntöjen parametreina saamansa suhteelliset polkunimet. Yllä mainittujen tietojen lisäksi prosessikuvaaja saattaa sisältää prosessien väliseen kommunikointiin liittyviä tietoja (semaforit ja signaalit), rajoituksia (CPU-ajan tai muistikoon suhteen), sekä tietoja prosessiin kuuluvista säikeistä. Prosessikuvaaja sisältää myös tietorakenteita, jotka eivät näy prosessille millään tavalla. Tällaisia rakenteita ovat esimerkiksi osoittimet suoritusjonossa seuraavaan tai edelliseen prosessiin (vuorottaja saattaa käyttää tätä) tai viite äitiprosessin kuvaajaan. Viitteiden avulla KJ pääsee muiden prosessien kuvaajiin käsiksi nopeammin kuin pelkällä PID-numerolla. Pisteytys: 6 p prosessikuvaajan sisältämistä kentistä 6 p siitä, että on kertonut missä yhteydessä tai milloin KJ käyttää prosessikuvaajan tietoja Vastausten yleisin puute oli, ettei kerrottu, mihin KJ tarvitsee prosessikuvaajan sisältämiä tietoja. ------------------------------------------------------------------------- Käyttöjärjestelmät I, Kurssikoe 04.11.2002 Tehtävä 3 / Mika ------------------------------------------------------------------------- 3 a) Prosessorissa on Base ja Limit rekisterit. Base on muistialueen alkuosoite ja Limit muistialueen loppuosoite (tai muistialueen koko). Ohjelma käyttää loogisia osoitteita eli osoitteita prosessin alusta lähtien jolloin osoitteen muodostus on yhteenlasku base + looginen osoite = fyysinen osoite Lopuksi täytyy tarkistaa, että osoite on sallittu. Jos Limit rekisterissä on loppuosoite, niin fyysinen osoite < loppuosoite. Jos Limit rekisterissä on koko, niin looginen osoite < Limit rekisterin arvo. Lisäksi loogisen osoitteen täytyy olla nollaa suurempi tosin sitä ei tarviste tarkistaa, jos osoite tulkitaan etumerkittömäksi luvuksi. Pisteytys: - 1 p Base ja Limit rekisterien maininnasta - 1 p loogisen osoitteen selityksestä - 1 p osoitteenmuodostuksesta, Base+looginen osoite - 1 p osoitteen tarkistuksesta, osoite < Limit b) Prosessorissa on rekisteri PTR, johon KJ tallentaa prosessin vaihdon yhteydessä uuden prosessin sivutaulun alkuosoitteen. Looginen osoite voidaan jakaa kahteen osaan, sivun numero ja siirtymä sivun sisällä. Koska kaikki sivut ovat samankokoisia ja sivun koko on aina jokin kahden potenssi, on osoitteen jako helppoa. Alkuosan bitit kertovat sivun numeron ja loppuosa siirtymän. Sivun koosta riippuu montako bittiä tarvitaan siirtymään ja loput jää sivun numeroa varten. Suorituskykysyistä prosessorissa on osoitteenmuodostus välimuistia (TLB). Se on kokoelma rekistereitä, joihin talletetaan sivunumero sekä sitä vastaava fyysisen muistilohkon alkuosoite, sekä voimassaolo bitti. Prosessinvaihdon yhteydessä TLB tyhjennetään, jotta prosessi ei pääsisi edellisen prosessin muistialueille. Käytännössä tyhjentäminen tarkoittaa voimassaolobitin (validi-bitti) asettamista pois asentoon. Kun prosessori yrittää muodostaa osoitetta aluksi käydään läpi TLB. Haku suoritetaan assosiatiivisesti, jolloin kaikkia rekistereitä verrataan samaan aikaan, joka nopeuttaa hakua. Mikäli tulos löytyi TLB:stä ja tuloksen voimassaolo bitti on päällä voidaan osoite muodostaa suoraan katenoimalla fyysisen kehyksen alkuosoitteen bitit ja siirtymä sivun sisällä. Jos vastausta ei löytynyt TLB:stä täytyy hakea sivutaulusta. Sivunumeron ja sivutaulun alkion koon perusteella voidaan laskea siirtymä sivutaulun sisällä (esim. alkuosoite 1000, alkion koko 40 tavua ja sivun numero 21 => osoite on 1000+21*40 = 1840). Kyseisestä alkiosta löytyy tarvittavat tiedot, aluksi tarkistetaan onko sivu keskusmuistissa sitä varten varatusta kentästä alkiossa. Jos ei ole aiheutetaan sivunpuutoskeskeytys ja KJ huolehtii sivun lataamisesta muistiin. Kun sivu on keskusmuistissa, saadaan alkiosta fyysisen kehyksen alkuosoite ja osoite muodostetaan samaan tapaan kuin TLB:ssä. Lisäksi TLB:n lisätään juuri suoritetun muunnoksen tiedot. Joissakin prosessoreissa käytetään monitasoisia sivutauluja, koska yksitasoinen sivutaulu olisi liian suuri, tällöin PTR sisältää osoitteen ylimmälle tasolle ja alemman tason sivutaulut haetaan ylemmän tason kautta. kts kirja s. 339-342. Pisteytys: - 1 p loogisen osoitteen osien nimeämisestä (sivu nro ja siirtymä) - 1 p sivutaulun alkuosoitteen rekisteristä (PTR) - 1 p TLB:stä ja assosiatiivisesta hausta (1/2p ilman assos. hakua) - 1 p sivutaulun alkion hausta - 1 p osoitteen laskusta (alkuosoite + siirtymä) - 1 p maininta sivunjen vakiokokoisuudesta ja sivun koon rajoituksesta (sivujen koko kakkosen potenssi), 1/2p jos toinen unohtui - 1 p sivunpuutoksesta ja Valid bitistä - 1 p monitasoisista sivutauluista ------------------------------------------------------------------------- Käyttöjärjestelmät I, Kurssikoe 04.11.2002 Tehtävä 4 / Avrll ------------------------------------------------------------------------- Tämä tehtävä osoittautui eräänlaiseksi killeriksi. Kun kokeessa oli 118 henkilöä, niin tässä tipahti nollille joka neljäs eli 29 opiskelijaa. Toisaalta täysiin tai lähes täysiin pisteisiin pääsi joka viides (21 hlöä). Jotkut osasivat siis hyvin, mutta iso osa oli ns. kuutamolla - valitettavasti sanoisi Mara. Tehtävän avainmenetelmät ja niiden hyvät/huonot puolet voit kurkistaa kirjasta s 545-551. a) - yhtenäinen alue - lohkojen linkitys linkki srvaan lohkon lopussa, tai linkeille oma alue - lohkonumeroiden luetteleminen ns. indeksilohkoissa indeksilohkojen linkitys useampitasoiset indeksirakanteet (vrt. UNIX) Pisteytys: - 1 menetelmä + selitykset (= 3p) - 2 menetelmää + selitykset (= 5p) - 3 menetelmää selitykset (= 6p) b) - bittikartta - vapaiden lohkojen luettelo - vapaiden lohkojen ketjutus - 1 menetelmä + selitykset (= 3p) - 2 menetelmää + selitykset (= 5p) - 3 menetelmää + selitykset (= 6p) -------------------------------------------------------------------------