Stýrikerfi I
09.12.41


Lokapróf 20. desember 1991


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


1. [15%] Tölva nokkur notar 16 bita fleytitölur með einn bita undir formerki, 6 bita fyrir veldi og 9 bita undir brothluta. Kódun fleytitalnanna er hin sama og notuð er fyrir IEEE fleytitölur. Hér að neðan eru tvær slíkar tölur sem einnig hafa verið villukódaðar með Hamming kóda sem getur leiðrétt eina villu. Til þess hefur verið bætt við 5 varbitum í sætum 1, 2, 4, 8, 16. Afkódið tölurnar, leggið þær saman og setjið niðurstöðuna á Hamming kóda.

1100 1001 0111 0111 0100 0
1100 1000 0000 1000 0000 0



2. [10%] Skrifið 8086 undirforrit sem snýr við streng ('ABC' verður að 'CBA'). Þegar kallað er á undirforritið inniheldur BX upphafsvistfang strengsins og AX hefur lengd hans. Forritið má ekki nota neitt aukaminni, nema á staflanum til að forða þeim gistum sem það notar. Reynið að skrifa forritið þannig að það verði sem hraðvirkast.



3. [30%] Skrifið 8086 undirforrit sem notar síu Eratosþenesar til að búa til töflu A, sem segir til um hvort tala sé frumtala (prímtala). Töfluna á að vera hægt að nota þannig að x er frumtala ef A[x] = 1, annars er A[x] = 0 og x er ekki frumtala.
Sían byrjar í 2, segir að hún sé frumtala og síar síðan út aðra hverja tölu í töflunni. Næsta frumtala er 3 og þá er síuð út þriðja hver tala í afgangnum af töflunni. Tala 5 er næst, og svo koll af kolli. Hér að neðan er nánari lýsing á aðferðinni: 
            A[0]=0                 ; 0 og 1 ekki frumtölur
            A[1]=0
            fyrir i=2 til MAX
                A[i]=1             ; Upphaflega allar tölur frumtölur
            endir
            fyrir i=2 til MAX/2    ; Sía út samsettar tölur
                ef A[i]=1 þá
                    fyrir k=i+i til MAX skref i
                        A[k]=0
                    endir
                endir
            endir
Í ykkar 8086 undirforriti kemur vistfang töflunnar í ES:DI og stærðin (MAX) í AX.



4. [10%] Hvers vegna eru TSR (Terminate and Stay Resident) forrit ekki notuð í fjölverka stýrikerfum eins og t.d. UNIX? Er eitthvað þar sem kemur í staðinn?



5. [10%] Eftirfarandi forrit keyrir á RISC gjörva sem hefur 5 þrepa pípun (þrepin eru Ná í Skipun, Greina, Ná í Gögn, Framkvæma, Skrifa Niðurstöðu), 2 biðhólf og gjörvinn gerir ekkert til að stjórna gagnaárekstrum. 
             100    nop
             101    jmp 100
             102    jmp 100
             103    jmp 104
             104    move R1, 0
Þið megið gera ráð fyrir því að skipanabendi (instruction pointer) sé breytt í Framkvæmdaþrepi pípunnar. Hvað gerir forritið? Útskýrið hvers vegna.



6. [10%] Ein aðferð sem notuð er af þýðendum til að láta forrit keyrast hraðar er kölluð "loop unrolling". Hún felst í því að breyta lykkjum með fastan ítrunarfjölda, t.d. 10, þannig að í stað lykkjunnar eru skipanirnar inní lykkjunni endurteknar 10 sinnum í forritinu. Þetta stækkar forritið, en eykur oftast hraðann. a) Hvers vegna? b) Hvers vegna hefur þessi aðferð lítil áhrif í HP PA tölvunum og getur jafnvel minnkað hraðann í Cray tölvum?



7. [15%] Tölva hefur 16 MB minni, 1 KB skyndiminni (cache), sem er mengistengið (set associative) þar sem hvert mengi hefur 2 línur og hver lína er 8 bæti.
a) Lýsið þessu skyndiminni nánar (fjölda lína, fjölda mengja, hvaða bitar í vistfangi gegna hvaða hlutverki, hvaða línur í minni fara í hvaða mengi í skyndiminni, ...)
b) Gjörvinn vill fá aðgang að eftirfarandi eins bætis minnishólfum í þessari röð:
56C2A0, 8BE829, 78AEA4, 56C2A7, 00C8A1
Í hvaða línusæti og mengi fara línurnar sem náð er í og hvaða línum er hent út ef þess þarf? Gefið ykkur þær forsendur sem þarf, í viðbót við það sem kemur fram í dæminu og segið frá þeim.