58123-3 Tietokoneen toiminta Koe 17.12.1999 Esimerkkiratkaisuja ja arvosteluperusteita ========================================== 1. (Liisa Marttinen) a) (3 p) Muuta luku 109.625 binäärimuotoon. => 1 1101101.101 kokonaisoosa luvusta oikein => 1p desimaaliosa luvusta oikein => 1p pelkkä oikea bittimäärä ei riitä (sen saa laskimesta), vaan on myös perusteltava saatu tulos eli miten tulos on saatu. Jos tätä ei ole tehty => -1/2 p kummastakin osasta. Liitä saatuun binäärilukuun vasemmanpuoleisimmaksi bitiksi parillinen pariteettibitti. oikea vastaus (=1) ja perustelu (parillinen määrä bittejä bariteettibitti mukaanlukien) => 1/2 p Mitä hyötyä tästä bitistä voi olla? Bitin avulla voidaan huomata, jos luvussa on yksi bitti (tai yleensä pariton määrä bittejä) muuttunut. => 1/2 p Perustele vastauksesi. Jos ei perustellut => vähennettiin 1/2 - 1 p b) Mikä on välimuisti (cache)? (3p) yleensä nopeaa (lähes yhtä nopeaa kuin rekisterit) assosiatiivistä muistia (koko muisti tutkitaan yhdellä kertaa), jossa on viimeksi muistista tuodut käskyt ja data. Miksi sitä käytetään? Nopeuttamaan suoritusta, usein tarvittava data tai käsky löytyy jo välimuistista (ohjelman paikallisuus) eikä varsinaista hyvin hidasta muististanoutua tarvitse lainkaan tehdä. Missä sitä käytetään? Erityisesti prosessorissa nopeuttamaan muistiviittausten käsittelyä. Samanlaisia mutta erinimisiä välimuisteja on käytössä muuallakin esim. levyn ja keskusmuistin välissä tai haettaessa tietoa verkosta. 1p /vastaus kysymykseen (Tästä tehtävästä lähes kaikki saivat täydet pisteet) c) Mikä on semafori ja mihin sitä käytetään? Semafori on laskuri, jolla on alkuarvo ja odottajien jono. => 1p Prosessien välisen kommunikoinnin ja yhteistoiminnan helpottamiseen: resurssien varaamiseen ja vapauttamiseen (poissulkemiseen) ja samalla prosessin etenemisen pysäyttämiseen ja taas jatkamiseen (prosessien tahdistamiseen).=> 1p Miten toimivat semaforioperaatiot Up() ja Down()? Up() jos odottajia, herätä ensimmäinen odottaja muuten kasvata laskuria yhdellä; jatka etenemistä; => 1p Down() jos vähennettävää, vähennetään laskuria yhdellä ja jatketaan etenemistä muuten nukutetaan prosessi semaforin jonoon odottamaan => 1 p Operaatiot ovat jakamattomia (= niiden suorituksen aikana keskeytykset ovat kiellettyjä). ------------------------------------------------------------------------- 2. (Sami Andberg) Taulukkoon on talletettu ei-negatiivisiä lukuja esim. opiskelijoiden kokeesta saamat pistemäärät. Lukujen määrää ei tiedetä, mutta taulukkoon talletettu negatiivinen luku ilmoittaa varsinaisten lukujen loppuneen. Tee aliohjelma karvo, joka laskee taulukkoon talletettujen lukujen keskiarvon. Parametrien välitykseen käytetään pinoa. Aliohjelmalle annetaan pinossa parametrina taulukon osoite ja aliohjelma palauttaa pinossa laskemansa keskiarvon. (7 p) Tee myös pääohjelma, joka kutsuu aliohjelmaa karvo taulukkoon Pisteet talletettujen koepisteiden keskiarvon laskemiseen ja tulostaa saamansa keskiarvon. Voit olettaa, että pistemäärät on jo talletettu halutulla tavalla taulukkoon Pisteet. (3 p) 2. Taulukkoon on talletettu ei-negatiivisia lukuja esim. opiskelijoiden kokeesta saamat pistemäärät. Lukujen määrää ei tiedetä, mutta taulukkoon talletettu negatiivinen luku ilmoittaa varsinaisten lukujen loppuneen. Tee aliohjelma karvo, joka laskee taulukkoon talletettujen lukujen keskiarvon. Parametrien välitykseen käytetään pinoa. Aliohjelmalle annetaan pinossa parametrina taulukon osoite ja aliohjelma palauttaa pinossa laskemansa keskiarvon. (7p) Tee myös pääohjelma, joka kutsuu aliohjelmaa karvo taulukkoon Pisteet talletettujen koepisteiden keskiarvon laskemiseen ja tulostaa saamansa keskiarvon. Voit olettaa että pistemäärät on jo talletettu halutulla tavalla taulukkoon Pisteet. (3p) Aliohjelma: ka EQU -3 taulu EQU -2 Karvo LOAD R5, =0 ; lukujen summa nollaksi LOAD R4, =0 ; lukujen lukumäärä-laskuri nollaksi LOAD R1, taulu(FP) ; taulukon 1. alkion osoite R1:een Looppi LOAD R2, @R1 ; haetaan R2:een R1:n osoittaman muistipaikan arvo JNEG R2, Loppu ; jos negatiivinen, lopetellaan ADD R5, R2 ; lisätään summaan ADD R4, =1 ; kasvatetaan lukumäärää yhdellä ADD R1, =1 ; siirretään R1 osoittamaan seuraavaan alkioon JUMP Looppi Loppu JZER R5, Poistu ; oliko laskettavia DIV R5, R4 ; lasketaan keskiarvo STORE R5, ka(FP) ; talletetaan tulos pinoon paluuarvoksi Poistu EXIT SP, =1 ; poistutaan aliohjelmasta ja poistetaan pinosta yksi käytetty parametri Pääohjelma: ... Oletetaan tehtävänannon mukaisesti taulukossa Pisteet jo olevan oikeantyyppistä dataa. PUSH SP, =0 ; paluuarvolle tyhjä tila PUSH SP, =Pisteet ; Pisteet-taulukon osoite CALL SP, Karvo ; kutsutaan aliohjelmaa Karvo POP SP, R1 ; otetaan tulos pinosta R1:een OUT R1, =CRT ; tulostetaan se näytölle SVC SP, =HALT ; lopetetaan ohjelman suoritus Arvostelu: Kuten tehtävänannossa on mainittu, aliohjelmasta sai maksimissaan 7 pistettä ja pääohjelmasta 3. Pisteitä menetti vähintään yhden mm. seuraavista virheistä: nollalla jaon huomioon ottamatta jättäminen parametrien välitys muutoin kun pinon avulla parametrien välityksen virheet keskiarvon virheellinen lasku tai sen laskun unohtaminen syntaksivirheet, kuten vääränlaiset muistiosoitukset (esim. LOAD R1, R2(R3) ei ole TTK-91:ssä sallittua!) aliohjelmarakenteen puuttuminen tai virheellinen käsittely ratkaisu muuhun kuin kysyttyyn tehtävään. -------------------------------------------------------------------------------- 3.(Janne Kraft) Käytetään esimerkkinä tietokoneesta kurssilla esitettyä TTK-91 -tietokonetta, jonka prosessorissa on rekisterit LIMIT, BASE, MAR, MBR, TR, IR, PC, SR, R0-R5, SP ja FP. a) Kuvaa prosessorin rekistereiden tasolla, miten tehdään käskynouto. (4 p) - Mistä haetaan (PC) (1) - PC->MAR (2) - Osoitteenmuunnos (3) - Väylän varaus+lataus+vapautus (4) - Käsky->MBR (5) - MBR->IR (6) - ++PC; (7) Pisteytys: 1 ja 2 +1p 3 +1p 4 ja 5 ja 6 +1p 7 +1p Jos vastauksessa ei ole rekistereitä käytetty -3p. Muut yo. taulukosta. b) Esitä prosessorin rekisterien tasolla, miten suoritetaan käskyt: LOAD R2, =100 COMP R2, @R2(R2) JNLES pois .... pois ... (5 p) Kolme käskyä, joille pisteytykset 1+3+1. Load käskyssä alun käyttö tai TR->R2 +1p. Comp käsky: Indeksointi alussa +1p Vertailu alussa +1p Tieto tilarekisteriin +1p JNLES käsky:Tilarekisterin tutkinta +1p Ps.(Liisa Marttinen) Käsky COMP R2, @R2(R2) ei ole TTK91:n konekielen syntaksin mukainen, sillä yhdessä käskyssä käytettävissä on korkeintaan kaksi rekisteriä. Tämä ei kuitenkaan vaikuta käskyn konekieliseen suoritukseen yleensä. c) Jos muistipaikkoihin välillä 100-300 on talletettu ko. muistipaikan osoite eli muistipaikassa 100 on luku 100 ja muistipaikassa 300 on luku 300, niin hypätäänkö ohjelmassa osoitteeseen pois vai ei? (1 p) Ei hypätä +1p --------------------------------------------------------------------------- 4. (Raine Kauppinen) Mihin keskeytyksiä käytetään? Mitkä tilanteet aiheuttavat keskeytyksen? Miten keskeytys havaitaan ja mitä sitten tapahtuu? Missä tilanteissa on mahdollista tai järkevää keskeytyksen jälkeen jatkaa vielä samaa käyttäjän ohjelmaa? (10 p) Alla on luettolomaisesti esitetty asiat, joita vastauksessa piti käsitellä. Mihin keskeytyksiä käytetään? (yht. 1 piste) - prosessori saadaan keskeytyksen avulla suorittamaan käyttöjärjestelmän koodia (,joka käsittelee ko. keskeytyksen) Mitkä tilanteet aiheuttavat keskeytyksen? (yht. 3 pistettä) - keskeytyksiä aiheuttavat - laiteohjaimet (esim. levysiirto valmis, kello jne.) (1p) - poikkeukset (esim. nollalla jako, laiton muistiviittaus jne.) (1p) - palvelypyynnöt (esim. SVC SP, =TIME, SVC SP, =HALT jne.) (1p) Miten keskeytys havaitaan ja mitä sitten tapahtuu? (yht. 4 pistettä) - keskeytys havaitaan tilarekisteristä (SR), jonka tila tarkistetaan jokaisen käskyn suorituksen jälkeen (1p) - kun keskeytys on havaittu - talletetaan rekisterien arvoja pinoon (ainakin SR, PC ja FP) (1p) - prosessori siirretään etuoikeutettuun tilaan (1p) - selvitetään keskeytyksen syy SR:n lipukkeista tai oheislaitteitta pollaamalla; keskeytyksen syyn perusteella löydetään oikean keskeytyskäsittelijän osoite keskeytys- vektoritaulusta; hypätään saatuun osoitteeseen, jolloin keskeytys saadaan käsiteltyä (1p) Milloin on mahdollista tai järkevää keskeytyksen jälkeen jatkaa vielä saman käyttäjän ohjelmaa? (yht. 2 pistettä) - saman prosessin jatkaminen on mahdollista, kun keskeytys ei aiheuta prosessin päättämistä (eli kun keskeytys ei ole poikkeuksesta johtuva tai prosessin päättävä palvelupyyntö) ja mielekästä, kun prosessilla on vielä prosessoriaikaa jäljellä (kyseessä ei ollut aikaviipalekeskeytys), eikä keskeytys aiheuta prossin siirtymistä WAIT-tilaan pitkäksi aikaa (kyseessä ei ollut esim. lukupyyntö levyltä); käytännössä siis samaa prosessia voidaan keskeytyksen jälkeen jatkaa osassa laiteohjainkeskeytyksiä (esim. kun levyohjain ilmoittaa, että levysiirto on valmistunut) ja osassa palvelypyyntökeskeytyksiä (esim. pyydettäessä syötettä näppäimistöltä) Pistejakauma: 0 p: 5 kpl ***** 1 p: 4 kpl **** 2 p: 2 kpl ** 3 p: 8 kpl ******** 4 p: 15 kpl *************** 5 p: 17 kpl ***************** 6 p: 10 kpl ********** 7 p: 20 kpl ******************** 8 p: 11 kpl *********** 9 p: 12 kpl ************ 10 p: 4 kpl **** Keskiarvo 5,7 pistettä. ---------------------------------------------------------------------------- 5. (Satu Sihvo) Koneessa on käytössä virtuaalimuisti (virtual memory) ja sivun koko on 1000 tavua. a) Kun ohjelmassa on suoritettavana käsky LOAD R1, 2001, niin kuinka saadaan selville, mistä muistipaikasta data noudetaan? (4 p) Selvitetään ohjelman sivu ja siirtymä sivun sisällä: 2001 DIV 1000 = 2 = sivu, 2001 MOD 1000 = 1 = siirtymä (1p). Katsotaan sivutaulusta, missä sivutilassa ohjelman sivu 2 sijaitsee; jos ei ole muistissa, niin noudetaan se (2p). Lasketaan fyysinen osoite: sivutilan numero * 1000 + siirtymä (1p). b) Mitä hyötyä on osoitemuunnospuskurista TLB (Translation Lookaside Buffer) virtuaalimuistin yhteydessä? Vai onko siitä ylipäänsä mitään hyötyä? Mitä TLB:hen on talletettu? (4 p) TLB:ssä on sivutaulun alkioita (joissa on ohjelman sivu, sivutilan numero jossa sivu on, sekä läsnäolobitti) ja jokaisella alkiolla validibitti, joka kertoo, kuuluuko sivutaulun alkio suoritettavana olevalle prosessille (2p). TLB nopeuttaa osoitteenmuunnosta, koska jokaisen muunnoksen yhteydessä ei tarvitse hakea sivutaulun alkiota muistista (2p). (TLB ei siis poista tarvetta osoitteenmuunnoksen tekemiseen, kuten monet väittivät.) c) Onko mahdollista, että ohjelman viittaamaa osoitetta ei löydy keskusmuistista? Miten ohjelmalle tällöin käy? (2 p) On mahdollista, että ohjelman kaikki sivut eivät ole muistissa; tämä näkyy sivutaulun alkion läsnäolobitistä (1p). Tällöin aiheutuu sivunpuutoskeskytys, ja käyttöjärjestelmä noutaa sivun muistiin ja päivittää sivutaulua (1p).