8104000 Käyttöjärjestelmät, Tentti 9.2.2004 tehtävistä ====================================================== Seuraavassa muutamia kommentteja tehtävien virheellisistä vastauksista, erityisesti kummastusta herättäneistä. Nämä eivät yritäkään olla vastauksia tehtävään. * Selitä termit ** Etuoikeutettu käsky Tämä ei liity vuorontamiseen: ei ole käsky, joka suoritetaan korkeammalla prioriteetilla kuin muut. Oleellista on prosessorin tila. ** Eräajo Interaktiivisen työn vastakohta, karkeasti. Voidaan suorittaa moniajonakin. ** Keskeytys Ohjelmallinen tai ulkoinen (oheislatteet!). ** Keskeytysvektori Ei ole se paikka, mihin tieto kesken suorituksen olevista keskeytyksistä pannaan. ** Lukkiutuminen Tilanne, jossa joukko prosesseja _kukin_ odottaa jonkin toisen, saman joukon prosessin hallussa olevaa resurssia. Tämä ei voi purkautua "itsekseen", sellaisen prosessin luopuessa resursseista, joka ei odota resurssia toiselta joukon prosessilta. Pelkkä odottaminen (ilman tuota keskinäistä riippuvuutta), jos se jatkuu periaatteessa ikuisuuksiin, on enemmänkin nälkiintymistä. ** Irrottava vuoronnus eli skedulointi Joku oli lukenut tämän niin, että määre "irrottava" kuuluisi vain sanaan "vuoronnus", ei "skedulointi", toisin kuin oli tarkoitus. * Kuvaa, nimeä edut, haitat ** SSTF (Shortest Seek Time First) Jos sanoo, että saavuttaa pienen keskimääräisen vasteajan, mutta voi aiheuttaa, että joitain pyyntöjä ei palvella lainkaan, koska "lähelle" osuvat "kiilaavat", tämä on looginen ristiriita. ** SCAN (hissialgoritmi) Joku oli erehtynyt sotkemaan tämän ja seuraavan keskenään. Tämä on kuin perushissi, palvelee pyyntöjä sekä matkalla ylös että alas. Reilu, mutta huonompi vaste juuri ohitetulla kulun alkupään uralla kuin seuraavalla. ** C-SCAN "Circular SCAN": palvellaan vain toiseen suuntaan pyyhkäisyn aikana ja sitten aloitetaan alusta (modulo-aritmetiikan tapaan). Takaisin esimerkiksi kalibrointitoiminnolla, palvelematta. Reilu, takaa paremman "worst case" -vasteen kuin SCAN, mutta paluu on hukka-aikaa. * Sivuttava virtuaalimuisti Joku kirjoitti, että pitäisi kysyä asioita käyttöjärjestelmistä eikä matematiikasta. Vastaväitteeni: näiden tehtävien matematiikka on lasten leikkiä, jos ymmärtää sivuttavan virtuaalimuistin toiminnan. Tällaiset tehtävät paljastavat hyvin juuri tämän ymmärryksen määrän tai puutteen. Juuri tämän ymmärryksen paljastamiseksi vaadin, että vastaukset perustellaan. Lisäksi, jos _teknillisen_ yliopiston vähintään toisen vuosikurssin opiskelija _tuntee aiheen_ hyvin, muttei osaa käyttää matematiikkaa tässä määrin kvantifioidakseen asioita, jonkun olisi pitänyt jo ajat sitten ohjata toiselle alalle: luvassa on ongelmia... (;-) ** FIFO/LRU Jos käyttää kolmea sivutilaa (kehystä), kun tehtävä sanoo neljä, kärsii turhan päiten. FIFO (3 kehyksellä): 0172327103 ---------- 0172333100 017222311 01777233 !!!!! !! Huomatkaa sivuvirheiden = läsnäolokeskeytysten aiheuttamat viistorivit vasemmalta ylhäältä oikealle alas JA ettei sisältö muutu, kun keskeytystä ei tule (FIFO!). Tässä esitystavassa vaakarivi EI esitä tietyn kehyksen sisältöä. (Sekin on mahdollista, mutta näyttää toisenlaiselta.) LRU (3 kehystä): 0172327103 ---------- 0172327103 017232710 01773271 !!!!! !! Huomatkaa taas viistorivit ja "pinokäytös", jos keskeytystä ei tule (LRU!). Käytetty notaatio ei ole tärkeää, joskin tämä on helppo lukea ja selkeä (ja kirjassa). Tärkeintä on käyttää oikeaa algoritmia: ei sitä tarvitsekaan osata mekaanisesti, kunhan on tarkka, järjestelmällinen ja käyttää järkeään. Joku (liian mekaanisesti näitä opetellut?) oli jopa onnistunut vaihtamaan algoritmit keskenään. ** Sivutauluelementtien määrä Sivutauluelementtejä on ainakin yksi kutakin sivua varten, sivutilaa käännetyssä sivutaulussa. Montako sivua/sivutilaa, siis? 1K = 1024 = 2^{10}, kun taas 1k = 1000. ** Välimuisti, hit ratio Välimuistihaussa menee se sama aika löytyi tavara tai ei. Tehtävässä hyvin pikkutarkasti selitettiin, miten haku jatkui sen jälkeen, kun tavaraa ei löytynyt. (Montako välimuistihakua, siis?) Varsin moni luuli, että 1 ms on 1 000 ns, kun oikea on 1 ms = 1 000 000 ns. Tämä saattoi olla tentin hankalin tehtävä. ** Rekisteritaulukon lataus Jos osoiteavaruus on on 32-bittinen ja sivut ovat 8 Ktavuisia, on sivuja 2^{32-13} = 2^{19}, koska 8K = 2^13. Kuinka joku vielä tässä opiskelun vaiheessa väittää, että sivuja olisi 2^{18}? Miksi joku jakaa sivumäärän vielä luvulla 2^3 = 8? En tunne koneita, joiden muistin osoite olisi 1 bitti (jolloin kahdeksalla jakaminen olisi jotenkin tulkittavissa, vaikkakaan ei järkevää): valtaosa nykykoneista on tavu-osoittavia. Joukossa on vielä sellaisiakin, jotka välttämättä haluavat ottaa tehtävän laskelmaan mukaan sivualkion pituuden (32 bittiä), vaikka se ei ole kuin vain "paikallisväriä". Vanhan tentinlaatija-vihtahousun kikka kolmonen on antaa enemmän tietoa kuin tarvitaan, että nähdään, kuka tietää, mikä on oleellista, mikä ei... (;-) Taas: 1K = 1024 = 2^{10} ja 1 ms = 1 000 000 ns. Luku 2^{19}/10^{6} ei ole lähelläkään 13%... Tämän tarkan arvon laskeminen päässä/paperilla kestää ehkä minuutin, jos sitäkään. Jos taskulaskinriippuvuutesi estää sinua tästä suorituksesta tai vastaavasta, kannattaa hankkiutua vieroitukseen... (;-) Jos ette osaa kakkosen potensseja ulkoa, opetelkaa laskemaan ne: se käy nopeasti, kun kahdella kertominen on varsin helppoa ja nopeaa. ** Virtuaalimuistin sivujen määrä Osoite: <----- 32 ------> +---+---+---+---+ | a | b | c | d | +---+---+---+---+ Osoitettavia muistialkioita on siis 2^32, joita kussakin sivussa on...? (Kaksi tapaa ilmaista!) * Luontoäiti Tämä käyttää yksinkertaisimmillaan laskevia semaforeja, koska vedyt ja hapet ovat kaikki "samannäköisiä". Tehtävä vaatii atomeja odottamaan: varsin moni oli vain laskenut, montako H/O-atomia tuli yrittämään, mutta päästi ne saman tein karkuun, jotkut jopa tekemättä vettä. Laskurit pitää myös vähentää, vieläpä niin, että niiden lukemaan voi luottaa silloin, kun sitä tarvitaan. Muistaako joku käsitteen "mutual inclusion": semaphore s1(0), s1(0); process p1 { V(s1); P(s2); } process p2 { V(s2); P(s1); } Tämä on vähän samantapainen kuin Ada:n "rendezvous" semaforein toteutettuna... Se virhe, jonka arvelen Luontoäidillä olevan ratkaisussaan on varsin pirullinen: happiatomi, joka odottelee kahta vetyatomia, ei saa odottaa näitä _peräkkäin_ saman semaforin takana, koska tällöin (jos happia ja vetyjä on paljon) kummassakin odotuksessa voi olla kiinni happiatomeja, jotka muuten voisivat reagoida. Joku turha toisto (busy-waiting) oli joukkoon eksynyt, joku makeWater:in peukaloijakin; joku oli unohtanut antaa alkuarvot, joku taas (turhaan) antoi semaforin jonon alkuarvon NULL/NIL. Jos käytätte näissä minun synkronointitehtävissäni sivun verran tietorakenteiden määrittelyyn, olette varsin todennäköisesti tekemässä sitä hankalammalla tavalla kuin kannattaisi.