Tietokoneen toiminta, 12.5.2000 Arvosteluperusteet ---------------------------------------------------------------------- Tehtävä 1 (Arvostelija: Raine Kauppinen) ========= a) (luento 8, kalvot 1-15) - prosessi on järjestelmässä suorituksessa oleva ohjelma; sen esitysmuoto järjestelmässä on PCB, jossa prosessiin liittyvät tiedot, kuten koodi- ja data-alueiden osoitteet sijaitsevat - prosessin suoritusaikaiset tilat: - alkutila (initialized): prosessi on käynnistetty - ready-to-run: prosessi odottaa pääsyä suoritukseen - running: prosessi on suorituksessa - waiting: prosessi odottaa (ersim. levysiirron valmistumista) - lopputila (terminated): prosessin on suoritettu loppuun tai sen suoritus on päättynyt virhetilanteeseen - tilasiirtymät: - alkutila -> ready-to-run: prosessi on ladattu ja alustettu - ready-to-run -> running: vuorottaja on valitsee prosessin suoritukseen - running -> ready-to-run: tapahtuu keskeytys (esim.aikaviipale-), prosessi on kuitenkin edelleen valmiiina suoritettavaksi - running -> waiting: prosessi aiheuttaa keskeytyksen tai pyytää palvelua, esim. pyytää levysiirtoa, eikä voi jatkaa ennen kuin keskeytys on käsitelty tai palvelupyyntö suoritettu - waiting -> ready-to-run: prosessin aiheuttama keskeytys tai pyyntö on käsitelty, esim. levysiirto on valmis, joten prosessi on taas valmis suoritettavaksi Pisteytys: - prosessin määritelmä ja esitysmuoto järjestelmässä 1p - ready-to-run, running ja waiting -tilat 3p (-1p / puuttuva tila) - ready-to-run, running ja waiting -tilojen väliset siirtymät 3p (-1p / puuttuva siirtymä) - alku- ja lopputilat sekä niihin liittyvät siirtymät 1p b) (luento 5, kalvot 22-23) - suorittimen suoritusaikaiset tilat: - käyttäjätila (user), jossa käyttäjäprosesseja suoritetaan (kaikki konekäskyt eivät ole sallittuja ja muistiosoitukset ovat rajoitettuja) (1p) - etuoikeutettu tila (kernel), jossa suoritetaan käyttöjärjestelmän koodia (esim. keskeytyskäsittelijää) (1p) - siirtymät: - user -> kernel: keskeytykset, palvelupyynnöt (1p) - kernel -> user: paluu etuoikeutetulla konekäskyllä (esim. IRET), palautetaan keskeytetyn prosessin tilan keskeytystä edeltäneeseen tilaan (1p) Pistejakauma: 0p : 1 * 1p : 2 ** 2p : 3 *** 3p : 2 ** 4p : 4 **** 5p : 7 ******* 6p : 14 ************** 7p : 11 *********** 8p : 13 ************* 9p : 9 ******** 10p: 12 ************ 11p: 11 *********** 12p: 4 **** Keskiarvo 7,5 pistettä. ---------------------------------------------------------------------- Tehtävä 2 (Arvostelija: Raine Kauppinen) ========= a) (luento 1, kalvo 34) - rekisteri (nopeus juustokakkuesimerkissä 0,5s) - esim. load R1, R2 - välimuisti (1s) - esim. load R1, 200, kun muistipaikkaan 200 on viitattu myös aikaisemmin; tällöin mp:n sisältö löytyy välimuistista - keskusmuisti (10s) - esim. load R1, 200, kun mp 200:aa ei löydy välimuistista - levymuisti, esim. kiintolevy (12pv) - esim. kun prosessi pyytää levysiirtoa palvelupyynnöllä (SVC SP, =READ) Pisteytys: - luettelo 3p (-1p / puuttuva taso) - nopeudet 1p - esimerkit 2p (yhden pisteen sai kahdella esimerkillä, kahteen pisteeseen vaadittiin neljä esimerkkiä) b) (luento 9, kalvot 1-13) - virtuaalimuistiin liittyvät keskusmuisti ja levymuisti; virtuaalimuistin ideana on, että osa (virt.)osoiteavaruuden sisällöstä voi sijaita myös levyllä, josta se tarvittessa kopioidaan muistiin; tällöin muistista siirretään levylle vähän käytettyä tietoa; virtuaalimuistin toiminta vaatii osoitemuunnoksia loogisten ja fyysisten osoitteiden välillä - ne voidaan hoitaa esim. sivutaulujen avulla (3p) c) (luento 9, kalvot 13-18) - TLB kuuluu välimuistin tasolle (2p) - TLB:n tarkoitus on nopeuttaa virtuaalimuistin toimintaa nopeuttamalla joka muistinoudon yhteydessä tapahtuvaa osoitemuunnosta (usein/äsken käytettyjä osoitemuunnoksia säilytetään TLB:ssä, joten sen on toimittava nopeammin kuin kesku- ja levymuistin (eli sen toimintaperiaate on hyvin välimuistin kaltainen). TLB ei kuitenkaan ole yhtä nopea kuin rekisterit. (1p) Pistejakauma: 0p : 2 ** 1p : 1 * 2p : 1 * 3p : 3 *** 4p : 4 **** 5p : 6 ****** 6p : 11 *********** 7p : 12 ************ 8p : 15 *************** 9p : 10 ********** 10p: 11 *********** 11p: 8 ******** 12p: 9 ********* Keskiarvo 7,7 pistettä. ---------------------------------------------------------------------- Tehtävä 3 (Arvostelija: Lauri Alanko) ========= a) - Laitteisto ei tiedä, mikä kussakin muistipaikassa sijaitsevan sanan "merkitys" on, eri käskyt tulkitsevat sanoja eri tavoin. (2p) - Jos kokonaislukujen yhteenlaskukäskyä suoritettaessa operandina onkin sana, joka on "tarkoitettu" liukuluvuksi, prosessori ei tiedä siitä mitään, vaan käsittelee kyseistä sanaa ikään kuin se olisikin kokonaisluku (tyypillisesti varsin suuri ja näennäisen sattumanvarainen kokonaisluku). (1p) - Seurauksena yhteenlaskun tulos on melkeinpä mielivaltainen, ja siis hyödytön. (1p) b) - Java-ohjelmien ajaminen on mahdollista. (1p) - Kääntäjä (_ei_ JVM-tulkki) huolehtii tyyppiturvallisuudesta, sen tuottamassa konekielessä (tai tavukoodissa) tyyppejä ei enää tarvitse pystyä erottamaan. (1p) - Totuusarvot voidaan ilmaista jollain prosessorin tukemalla tietotyypillä, esim. kokonaisluvuilla niin, että "false":a vastaa 0, "true":a 1. (1p) - Operaatiot totuusarvoille voidaan vastaavasti ilmaista kokonaislukuoperaatioilla. Esim. looginen AND-operaatio voidaan ilmaista MUL-käskyllä tai AND-bittioperaatiolla tms. (1p) c) - Pariteettibittejä tarvitaan 4 (koska 8+4 < 2^4) (1p) - Pariteettibitit lasketaan niin, että kunkin pariteettibitin tarkistamien bittien summa on parillinen. Bittien sijainnit ja arvot: * Vähiten merkitsevästä laskien: 1 1 1 2 1 0 9 8 7 6 5 4 3 2 1 ----------------------- 0 1 1 1 1 0 1 0 1 1 0 1 ----------------------- D D D D P D D D P D P P P = pariteettibitti, D = databitti * Eniten merkitsevästä laskien: 1 1 1 1 2 3 4 5 6 7 8 9 0 1 2 ----------------------- 0 1 0 0 1 1 1 0 0 1 0 1 ----------------------- P P D P D D D P D D D D (1p) - Virhe paikannetaan katsomalla, mitkä pariteettibitit eivät täsmää (joissa siis tarkistettavien bittien summa on pariton). Näiden pariteettibittien indeksit lasketaan yhteen. (1p) - Kun yhden bitin virhe on paikannettu, se voidaan korjata välittömästi. (1p) Tyypillisiä virheitä: - Sekoitettu parillinen ja pariton pariteetti - Laskettu pariteetteihin vain databitit. Tällöin kolme pariteettibittiä riittäisi, mutta siirtovirhettä niissä ei huomattaisi. ---------------------------------------------------------------------------- Tehtävä 4 (Arvostelija: Lauri Alanko) ========= Tässä yksi ratkaisutapa: parN EQU -2 parArr EQU -3 retval EQU -4 ; rekisterit: R1: tämänhetkisen alkion osoite ; R2: viimeistä seuraavan alkion osoite ; R3: suurin arvo tähän mennessä ; R4: tämänhetkisen alkion arvo ; R5: suurimman alkion osoite MaxInd PUSHR SP LOAD R5, =-1 LOAD R2, parN(FP) JNPOS R2, return LOAD R1, parArr(FP) ADD R2, R1 LOAD R5, R1 LOAD R3, (R5) loop LOAD R4, (R1) COMP R4, R3 JNGRE skip LOAD R5, R1 LOAD R3, R4 skip ADD R1, =1 COMP R1, R2 JLES loop SUB R5, parArr(FP) return STORE R5, retval(FP) POPR SP EXIT SP, =2 Tyypillisiä virheitä: - Funktiorajapinnan toteutus: * Tehty pääohjelma, ei funktiota ollenkaan (-6p) * Rekistereitä ei otettu talteen (-2p) * Paluuarvoa ei talletettu pinoon (-1p) * Taulukko luettu suoraan pinon sisältä, ei viiteparametrinä (-1p) * Funktio ei toimi oikein kun kutsutaan uudestaan (-1p) - Etsintäalgoritmi: * Negatiivisia arvoja ei otettu huomioon (-1p) * Etsitty suurimman alkion arvo, eikä indeksiä (-2p) - TTK-91 -assembly: * Sekalaiset sekaannukset osoitusmuodoissa (-1p) * Yritetty indeksoida rekisteriä toisella rekisterillä (-1p) * Sekaannus SP/FP, POP/LOAD, PUSH/STORE (-1p) - Sallittuja puutteita (ei pisteiden menetystä): * Oletus, että taulukon koko >= 1 * Ohjelma ei "re-entrant" (eli käyttää globaaleja apumuuttujia) ---------------------------------------------------------------------- Tehtävä 5 (Arvostelija: Teemu Kerola) ========= Luento 4 kalvot 10-13, Häkkinen luvut 5.7-8, 5.11 a) Palauta pinosta FP:lle ja PC:lle vanhat arvot, vapauta 2 parametrin tila pinosta 1 puuttuu -> -1p (lisää miinuksia tullee kohdista b ja c) 1 mukana -> 1p b) POP SP, FP ; recover FP SUB SP, =1 ; remove PC from stack SUB SP, =2 ; recover param space JUMP @3(SP) ; jump to return address edes paluu oikein -> +1p edes tilan vapautus OK -> +1p tuhoaa rekistereitä -> -1p rekisteriin PC viitattu käskyssä -> -2p SUB käskyt voi yhdistää halutessaan tietojen väärään järjestys pinossa -> ei sakkoa c) STORE R1, -3(FP) ; save R1 on top of 1st par POP SP, FP ; recover FP POP SP, R1 ; return address ADD R1, jumpx ; compose return instruction STORE R1, ret ; store it for execution later on SUB SP, =1 ; recover 2. parameter space POP SP, R1 ; recover 1st par space, recover R1 ret NOP ; return instruction will be here jumpx JUMP =0 ; opcode for return instruction tuhoaa rekistereitä -> -1p Pistejakauma: 0p : 17 ***************** 1p : 11 *********** 2p : 7 ******* 3p : 6 ****** 4p : 14 ************** 5p : 11 *********** 6p : 8 ******** 7p : 4 **** 8p : 3 *** 9p : 1 * 10p: 3 *** 11p: 4 **** 12p: 4 **** Keskiarvo 4.1 pistettä. ----------------------------------------------------------------------