Tietokoneen toiminta (avoin yliopisto) Kurssikuulustelu 7.9.2001 Tehtävä 1 (arvostelu: Heikki Lindholm) ====================================== Ref. Luento 8, kalvot 1-13 LH 4 a) (2 pistettä) Mikä on prosessin esitysmuoto järjestelmässä? - prosessin kuvaaja eli kontrollilohko (PCB = Process Control Block) (o sisältää kaiken tiedon yhdestä prosessista) b) (2 pistettä) Mitkä ovat prosessin suoritusaikaiset tilat (state)? - 3 tilaa (jonoa): o valmis suoritukseen (ready-to-run) o suorituksessa (running) o odottaa (waiting) c) (2 pistettä) Miten prosessin tila näkyy käyttöjärjestelmälle (operating system)? - prosessin kontrollilohkoon on viite käyttöjärjestelmän jonosta, joka vastaa prosessin tilaa ja/tai prosessin kontrollilohkoon on merkitty prosessin tila. d) (2 pistettä) Miten prosessin tila näkyy prosessille itselleen? - ei mitenkään e) (4 pistettä) Miten ja milloin prosessin tila muuttuu? Käsittele kukin mahdollinen tilasiirtymä erikseen. Kerro kustakin tilasiirtymästä esimerkkitapahtuma, joka voisi aiheuttaa kyseisen tilasiirtymän. - 4 mahdollista tilasiirtymää (b-kohdan tilojen pohjalta): o ready-to-run -> running o running -> ready-to-run o running -> waiting o waiting -> ready-to-run - ready-to-run -> running o prosessi saa prosessorin itselleen ja siirtyy siis suoritukseen o tapahtuu kun ajossa olleen prosessin suoritus on keskeytynyt (aikaviipalekeskeytys on sattunut tai prosessi on tehnyt I/O pyynnön). Käyttöjärjestelmä valitsee ready-to-run jonosta uuden prosessin suoritukseen. - running -> ready-to-run o prosessi menettää prosessorin ja poistetaan ajosta o tapahtuu aikaviipalekeskeytyksen (tai periaatteessa myös muun keskeytyksen) sattuessa - running -> waiting o prosessi siirtyy ajosta odottamaan jotakin o tapahtuu prosessin tehdessä I/O- tai odotuspyynnön (jolloin käyttöjärjestelmä saa kontrollin) - waiting -> ready-to-run o prosessin siirtyy odottamasta ajovalmiiden jonoon o tapahtuu, kun prosessin odottama asia on tapahtunut. Esimerkiksi, kun prosessin tekemän I/O-pyynnön suoritus on valmis. Käyttöjärjestelmä huomaa tapahtuman (I/O)keskeytyksen käsittelyn yhteydessä. ! tärkeää olisi tietää oikeat tilasiirtymät ja se mekanismi (keskeytys), jolla prosessi saadaan yleensä ajosta pois, ts. päästään suorittamaan käyttöjärjestelmän koodia Pistejakauma: 0p: 0 1p: 0 2p: 0 3p: 1 4p: 1 5p: x 6p: 1 7p: 0 8p: 4 9p: 1 10p: 2 11p: 2 12p: 6 ka.: 9 1/3 --------------------------------------------------------------------- Tehtävä 2 (Arvostelija: Raine Kauppinen) ========= Luento 5, kalvot 1-14 (käskyjen suoritussykli); Luento 5, kalvot 18-23 (keskeytykset) a) (2 pistettä) - käskyn suoritussykli: - nouto: käsky noudetaan muistista IR:ään - purku: selvitetään operaatiokoodi, operandit ja muistinoutojen määrä - operandin nouto: haetaan toinen operandi muistista tarvittaessa - suoritus ja talletus: käsky suoritetaan (ALU-operaatio) ja tulos talletetaan tarvittaessa muistiin b) (2 pistettä) - seuraavan suoritettavan käskyn osoite on talletettuna resisteriin PC - PC:tä kasvatetaan käskyn noudon yhteydessä; sen arvo voi myös muuttua käskyä suoritettaessa (hyppykäskyt) c) (3 pistettä) - keskeytys on tilanne, jonka käsittely vaatii poikkeuksen käskyjen normaaliin suoritusjärjestykseen - keskeytystyyppejä: - käskyn aiheuttamat virhetilanteet (esim. nollalla jako) - käskyn aiheuttamat muut poikkeustilanteet (esim. palvelupyynnöt) - CPU:n ulkopuolelta tulleet keskeytykset (esim. kellokeskeytys) d) (2 pistettä) - jokaiselle keskeytystyypille on oma käyttöjärjestelmän tuntema käsittelyrutiini (keskeytyskäsittelijä), joka suoritetaan keskeytyksen sattuessa - keskeytys havaitaan, kun käskyn suorituksen jälkeen tarkistetaan tilarekisteri SR; tarkistuksen jälkeen siirrytään tarvittessa suorittamaan keskeytyskäsittelijää e) (3 pistettä) - etuoikeutettu tila on suorittimen tila, jossa esimerkiksi keskeytyskäsittelijät suoritetaan - etuoikeutetussa tilassa - voi käyttää kaikkia konekäskyjä, myös etuoikeutettuja (esim. iret) - voi viitata kaikkialle muistiin, myös käyttöjärjestelmän ytimeen (voi käyttää myös suoria muistiosoitteita) Pistejakauma: 0p: 1 1p: 0 2p: 1 3p: 1 4p: 0 5p: 1 6p: 1 7p: 4 8p: 2 9p: 1 10p: 2 11p: 2 12p: 2 Keskiarvo 7,5 pistettä. ---------------------------------------------------------------------- Tehtävä 3 (arvostelu: Heikki Lindholm) ====================================== Ref. Luento 7, kalvot 9-20 LH 4, tehtävä 1 (Hamming-koodi) a) (4 pistettä) Mitä tarkoittaa käsite pariteettibitti? Anna esimerkki, jossa käytetään pariteettibittiä tiedon muuttumattomuuden valvonnassa. Anna myös esimerkki tiedon muuttumattomuuden valvontaan liittyvästä tilanteesta, jossa pariteettibitin käyttö ei ole riittävä (mutta Hamming-koodin käyttö olisi riittävä). Perustele molemmat esimerkkisi. - yksi ylimääräinen bitti per tietoalkio, joka kertoo sopimuksen (parillinen/pariton pariteetti) mukaan tietoalkion 1-bittien lukumäärän parillisuuden. o parillinen pariteetti tarkoittaa, että 1-bittejä on pariteettibitti mukaan lukien parillinen määrä; pariton pariteetti tarkoittaa paritonta määrää. o pariteettibitin arvosta voidaan päätellä tiedossa tapahtuneet yhden bitin muutokset (virheet). - käytetään kohteissa, joissa virheet ovat melko harvinaisia tai/ja tiedon uudelleenlähetys on mahdollista, esim. tietokoneeseen liitettävien ulkoisten laitteiden ja koneen välisen tietoliikenteen tarkistuksessa (sarja-/rinnakkaisportit). Käytetään mahdollisesti myös silloin kun tarkistuksen on oltava yksinkertainen eikä läpipäässeillä virheillä ole välttämättä kovin suurta väliä (videoneuvottelu) - pariteettibitin käyttö ei ole riittävä, kun o kahden bitin virheet ovat mahdollisia (todennäköisiä) o halutaan mahdollisuus virheenkorjaukseen (esim. uudelleenlähetys ei mahdollista) b) (4 pistettä) Mitä tarkoittaa käsite Hamming-koodi? Anna esimerkki, jossa käytetään Hamming-koodia tiedon muuttumattomuuden valvonnassa. Anna myös esimerkki tiedon muuttumattomuuden valvontaan liittyvästä tilanteesta, jossa Hamming-koodin käyttö ei ole riittävä (mutta CRC:n käyttö olisi riittävä). Perustele molemmat esimerkkisi. - Hamming-koodissa lisätään tarkistettavaan tietoon pariteettibittejä tiedon pituuden mukaan. Pariteettibitit lisätään kohtiin, joiden järjestysnumero on jokin kahden potenssi. Pariteettibittien arvo määräytyy laskemalla kaikkien niiden 1-bittien määrä, joiden järjestys- numeron binääriesitykseen kyseinen pariteettibitti sisältyy. Toisinpäin tämä voidaan ilmaista niin, että n:ttä bittiä tarkistavat ne pariteetti- bitit joiden summasta n muodostuu. Pariteettibittien arvoista voidaan huomata kahden tai useamman bitin virheet sekä korjata yhden bitin virheet. - Hamming-koodia käytetään kohteissa, joissa virheet ovat melko harvinaisia, ja joissa ei välttämättä ole mahdollisuutta tiedon uudelleenlähetykseen (esim. väylät) - Hamming-koodi ei riitä kohteissa, joissa tulee paljon virheitä kerralla. (esim. verkkoliikenne) c) (4 pistettä) Mitä tarkoittaa käsite CRC (Cyclic Redundancy Code)? Anna esimerkki, jossa käytetään CRC:tä tiedon muuttumattomuuden valvonnassa. Anna myös esimerkki tiedon muuttumattomuuden valvontaan liittyvästä tilanteesta, jossa CRC:n käyttö ei ole riittävä. Perustele molemmat esimerkkisi. - CRC tarkoittaa tarkistussummaa, joka lasketaan annetun tiedon pohjalta. Summa kertoo vain onko tieto muuttunut vai ei. - CRC:tä käytetään, kun virheitä tulee paljon kerralla ja uudelleenlähetys on mahdollista. Esim. verkkoliikenne. - CRC:tä ei voi käyttää, kun tarvitaan virheenkorjausta tai suurempaa varmuutta kuin CRC tarjoaa. CRC:tä ei myöskään voi käyttää tarkistamaan abstraktimpia tietokokonaisuuksia, jotka vaativat monimutkaisempaa tiedon rakenteen tarkastelua (luennot: tietokannan eheys). Pistejakauma: 0p: 0 1p: 0 2p: 2 3p: 0 4p: 0 5p: 0 6p: 2 7p: 3 8p: 3 9p: 1 10p: 1 11p: 2 12p: 4 ka.: 8 1/3 ---------------------------------------------------------------------- Tehtävä 4 (Arvostelija: Raine Kauppinen) ========= Luento 3 (konekielinen ohjelmointi); Luento 4 (aliohjelmien toteutus konekielen tasolla); Laskuharjoitus 2, tehtävät 2,3 ja 5 (konekielinen ohjelmointi); Laskuharjoitus 3, tehtävä 1 (aliohjelman toteutus); Laskuharjoitus 3, tehtävä 3 (suuret vakiot) a) (4 pistettä) - aliohjelmakutsu laskuharjoituksen 3, tehtävän 1 tapaan - huomattavaa: vakio 1234567 ei mahdu käskyn 2. operandiin, joten ko. parametri on välitettävä muistipaikasta (välitön operandi ei käy) - tyypillisiä virheitä: paluuarvolle ei varattu tilaa (-1p), parametrin välityksessä virheitä (esim. viimeinen parametri välittömänä operandina -1p), tulosta ei haeta pinosta (-1p) yms. b) (3 pistettä) - vastaava idea kuin a-kohdassa - huomattavaa: Help(5,6,7)- ja Help(1,2,3)-kutsujen tulokset pidettävä tallessa ja välitettävä (talletusongelmat pystyi välttämään rakentamalla kutsun suoraan, eli kutsumalla Help-funktiota kahteen kertaan varsinaisen kutsun aktivointitietueen rakentamisen yhteydessä) - tyypillinen ongelma Help(5,6,7)- ja Help(1,2,3)-kutsujen tulosten talletus ja/tai liian monimutkainen aktivointitietueen rakennusyritys (-1-3p vakavuuden mukaan) c) (5 pistettä) - aliohjelman toteutus laskuharjoituksen 3, tehtävän 1 tapaan - tyypillisiä virheitä: työrekistereitä ei talletettu ja palautettu (-1p), parametrien haussa pinosta virheitä (-1-2p), tuloksen talletuksessa pinoon virheitä (-1p), aliohjelmasta paluussa virheitä (-1p) yms. Pistejakauma: 0p: 2 1p: 1 2p: 1 3p: 1 4p: 1 5p: 1 6p: 1 7p: 1 8p: 1 9p: 2 10p: 3 11p: 0 12p: 3 Keskiarvo 6,7 pistettä. ---------------------------------------------------------------------- Kokonaispisteet: 30,45,30,29,17,34,43,46,35,44,38,47,25,27,35,6,14,28 ka.: 31.83