Stýrikerfi I
09.12.41


Lokapróf 13. desember 1993


Leyfileg hjálpargögn: Kennslubækur og fyrirlestranótur


1. [10%] Tölva hefur harðan disk með 32 plötum (skrifað á allar hliðar), 32 geirum á spori og 512 bætum í hverjum geira.
a) Hvað er mikið gagnamagn á hverjum sívalning (cylinder)?
b) Ef hámarks flutningshraði disksins er um 640 KB á sekúndu hver er þá snúningshraðinn (miðið við að aðeins sé hægt að lesa af einni hlið einnar plötu í einu)?
c) Ef diskurinn getur samtals geymt 220 MB hvað hefur hann þá mörg spor?
d) Ef það tekur 5 msek. að færa hausinn milli samliggjandi spora hvernig væri þá best að raða geirunum á sporin (stagger) til að lágmarka snúningstöf þegar verið er að lesa geira í röð.



2. [10%] Ákveðnir útreikningar krefjast hlutfallslegrar nákvæmni (þ.e. hlutfallslegur munur milli hliðstæðra fleytitalna) upp á 2 og einnig þarf að vera hægt að tákna tölur allt að 10. Hver er smæsta fleytitala af IEEE gerð sem getur táknað slíkar tölur? Þið eigið sem sagt að hanna nýja gerð IEEE fleytitalna með eins fáum bitum í brothluta og veldishluta og mögulegt er, sem uppfylla ofangreindar kröfur.



3. [10%] Þegar gögn eru villukóduð með Endurbættu aðferð Hammings er best að hafa gagnapakkana sem minnsta, því þá eru meiri líkur á því að aðeins verði tvær eða færri villur í þeim. Á móti kemur að því minni sem pakkarnir eru, þeim mun fleiri verða varbitarnir í hlutfalli við gagnabita.
Segjum að við hefðum þjöppunaraðferð, sem þjappaði gögnunum niður í helming þess sem þau voru. Ef við beitum nú Endurbættu Hamming aðferðinni á þjöppuðu gögnin, hvað mættum við hafa gagnapakkana litla til að gögnin sem kæmu út úr villukóduninni væru jafnstór og upprunalegu gögnin fyrir þjöppunina?
En ef þjöppunin þjappaði aðeins niður í 2/3 af upphaflegri stærð?



4. [10%] Útskýrið nákvæmlega hvað gerist í 8086-forritsbútinum að neðan.
                 xor   bx, bx
         aftur:  add   bl, al
                 adc   bh, 0
                 inc   byte ptr [cs:smb + 1]
         smb:    cmp   al, 0
                 ja    aftur



5. [25%] Hér að neðan er fall sem reiknar út heiltöluveldi í sem fæstum margföldunum.
        fall veldi(heiltala b, heiltala e)
            ef e = 0 þá
                skila 1
            ef e = 1 þá
                skila b
            ef (e mod 2) = 0 þá
                skila veldi(b, (e div 2))
            annars
                skila (veldi(b, (e div 2)))*b
            endir
        endir
Skrifið veldi sem endurkvæmt fall sem hægt er að kalla á úr Borland C++. Setjið það upp þannig að það sé á forminu: 
        unsigned int veldi( unsigned short b, unsigned short e);
Fallið þarf líka að passa að ekki verði yfirflæði (overflow), en þá á að skila 0 og hætta.



6. [10%] Tölvur eru annað hvort "big-endian" eða "little-endian" eftir því í hvaða röð innan orðs bætin eru. Little-endian tölvur, eins og 8086, geyma lægra bætið fremst, en big-endian tölvur, eins og 68000, geyma hærra bætið fremst. Nú eru að koma á markað tölvur sem eru "bi-endian", því hægt er að skipta um "endianess" á þeim. Einn biti í stöðugistinu segir til um það hvaða röð á að nota. Lýsið nákvæmlega hvernig þessar tölvur geta farið að því að breyta um "endianess" og sýnið dæmi, bæði um tveggja bæta orð og fjögurra bæta orð.



7. [10%] Þýðið eftirfarandi forritsbút yfir í HP PA-RISC smalamál. Gerið ráð fyrir að breyturnar séu í gistum.
            if (a == b)
                c++
            else
                d += 4;
Til að fá alla 10 punktana fyrir dæmið má smalamálsforritið aðeins vera þrjár skipanir. Þið fáið 5 punkta ef notaðar eru fjórar skipanir og síðan færri punkta ef fleiri skipanir eru notaðar.



8. [15%] Við skulum líta á nýja aðferð við að ákvarða hvaða síðu á að henda út í sýndarminni. Aðferðin gæti kallast Víxlun, og felst í því að síðunum er haldið í röð og í hvert sinn sem vísað er í síðu x þá færist hún fram um eitt sæti í röðinni (þ.e., henni er víxlað við síðuna sem er á undan í röðinni). Þegar henda þarf út síðu er valin sú síða sem er aftast í röðinni. Nýja síðan kemur síðan inn aftast í röðina (næst aftast ef vísað er í hana í leiðinni).
a) Útskýrið nákvæmlega uppsetningu á þessari aðferð.
b) Berið aðferðina saman við LRU, FIFO og NRU. Ræðið kosti og galla. Hefur Víxlunaraðferðin einhverja augljósa galla?
c) Sýnið hvernig hægt væri að setja upp nálgun á Víxlunaraðferðinni á 486 gjörvanum með því að nota eingöngu það minni sem til staðar er í síðutöflum (og töfluskránni).